import collections


def sort_query_keys(part):
  """sort keys in place.

  We do this to every mqlread with a cursor because
  graphd relies on GQL query string order to
  maintain the state of the cursor.

  This calls itself recursively sorting keys
  in any ply of the query that is a dict

  Args:
    part: any ply of your dict

  Returns:
    an OrderedDict where all keys have been sorted
    in every ply of the query.
  """

  if isinstance(part, list):
    new_d = []
    for item in part:
      new_d.append(sort_query_keys(item))
    return new_d
  elif isinstance(part, dict):
    new_d = collections.OrderedDict()

    for k in sorted(part.keys()):
      new_d[k] = sort_query_keys(part[k])
    return new_d
  else:
    return part