def get_hierarchy(self, loc_types):
        """
        Return loc types in order from parents to children
        """
        lt_dict = {lt['pk']: lt for lt in loc_types}

        # Make sure there are no cycles
        for loc_type in loc_types:
            visited = set()

            def step(lt):
                assert lt['name'] not in visited, \
                    "There's a loc type cycle, we need to prohibit that"
                visited.add(lt['name'])
                if lt['parent_type']:
                    step(lt_dict[lt['parent_type']])
            step(loc_type)

        hierarchy = {}

        def insert_loc_type(loc_type):
            """
            Get parent location's hierarchy, insert loc_type into it,
            and return hierarchy below loc_type
            """
            name = loc_type['name']
            parent = lt_dict.get(loc_type['parent_type'], None)
            if not parent:
                lt_hierarchy = hierarchy
            else:
                lt_hierarchy = insert_loc_type(parent)
            if name not in lt_hierarchy:
                lt_hierarchy[name] = (loc_type, {})
            return lt_hierarchy[name][1]

        for loc_type in loc_types:
            insert_loc_type(loc_type)

        ordered_loc_types = []

        def step_through_graph(hierarchy):
            for name, (loc_type, children) in hierarchy.items():
                ordered_loc_types.append(loc_type)
                step_through_graph(children)

        step_through_graph(hierarchy)
        return ordered_loc_types
dataset/ETHPy150Open dimagi/commcare-hq/corehq/apps/locations/views.py/LocationTypesView.get_hierarchy/original