When retrieving a group of objects from a database, sometimes we need to recreate some hierarchy inside a multidimensional array or object for further processing. However, since the language wasn’t developed with such usage scenarios in mind, the way to achieve this is anything but intuitive. Many developers just adjust their DB structure in order to make such sorting easier, but it’s always good to have a choice. I recently came across this problem myself, and think the solution I came up with is not only interesting, but could be useful to other developers out there. If you find this useful, or would like to propose a different solution, I’d love to read your comments below.
Let’s say, as an example, that you have a DB table with columns id and parent, where id is an auto-generated primary key, and parent refers to id by a foreign key. The idea is every entry has either a parent in the same table, or a NULL parent and hence is at the top level of the hierarchy. We do not know how deep the hierarchy goes, and must be able to recursively populate a multidimensional array or object in order to recreate it.
The (Generic) Solution
First of all, we assume we are retrieving all entries into a plain array. We ORDER BY parent ASC, with NULLS first so we process the top level entries first. We will need to create 2 arrays, one for storing the entries hierarchically, and the other to keep track of the path of each entry inside the hierarchy. We will be dealing with arrays exclusively in this example, but using objects instead is pretty straightforward.
As you can see, the main idea is to save the path of each entry we insert in order to know how to get to it, and then traverse the path of the parent by reassigning references to the children container of each post in the path. This way we can always reach the parent of a post inside our hierarchy, no matter how complicated, provided that all parents are inserted before their children into it.
Speak Yii to me
Actually, I came up with this algorithm while working with Active Records on Yii Framework, so might as well share the code that inspired this post. I have a Section Model, with id, parent, and order columns. id and parent are as in the above example, but the order column provides the order in which the children in a post should be sorted. I added a public property named “children” to the Model in order to be able to store a record’s children in it, but that’s all. Since it’s the same principle as above, it’s mostly uncommented:
Hope you find some of this as useful as I did, and if you find this solution pretty obvious or even intuitive, congratulations: you’re a better web developer than I am.