Algorithm for converting hierarchical flat data (w/ ParentID) into sorted flat list w/ indentation l
- by eagle
I have the following structure:
MyClass {
guid ID
guid ParentID
string Name
}
I'd like to create an array which contains the elements in the order they should be displayed in a hierarchy (e.g. according to their "left" values), as well as a hash which maps the guid to the indentation level.
For example:
ID Name ParentID
------------------------
1 Cats 2
2 Animal NULL
3 Tiger 1
4 Book NULL
5 Airplane NULL
This would essentially produce the following objects:
// Array is an array of all the elements sorted by the way you would see them in a fully expanded tree
Array[0] = "Airplane"
Array[1] = "Animal"
Array[2] = "Cats"
Array[3] = "Tiger"
Array[4] = "Book"
// IndentationLevel is a hash of GUIDs to IndentationLevels.
IndentationLevel["1"] = 1
IndentationLevel["2"] = 0
IndentationLevel["3"] = 2
IndentationLevel["4"] = 0
IndentationLevel["5"] = 0
For clarity, this is what the hierarchy looks like:
Airplane
Animal
Cats
Tiger
Book
I'd like to iterate through the items the least amount of times possible. I also don't want to create a hierarchical data structure. I'd prefer to use arrays, hashes, stacks, or queues.
The two objectives are:
Store a hash of the ID to the indentation level.
Sort the list that holds all the objects according to their left values.
When I get the list of elements, they are in no particular order. Siblings should be ordered by their Name property.
Update: This may seem like I haven't tried coming up with a solution myself and simply want others to do the work for me. However, I have tried coming up with three different solutions, and I've gotten stuck on each. One reason might be that I've tried to avoid recursion (maybe wrongly so). I'm not posting the partial solutions I have so far since they are incorrect and may badly influence the solutions of others.
