Non-recursive sampling of the entire tree. Adjacency List

In general, what I don't like about the Adjacency List is recursion, especially when you need to select a tree, without any restrictions, for example:

• All comments tree;
• Site Map;
• Navigation menu;
• etc.;

The proposed solutions for forming an array of wood using pointers, of course, make it possible to get rid of unnecessary queries to the database, but alas, they do not rule out recursion, albeit in an array, but still. And we have…

Task

Make one request to the database and in a single pass to collect a single-level list in the desired order.

Decision

How to solve such a problem at the database level, I have no ideas at the moment, but at the application level it is easy. The main difficulty is that for a certain node we may not get its parent and children. Therefore, we will use temporary lists and glue them as needed. Algorithm suggest on Perl.
')
Perl code (1)

 #! / usr / bin / perl
 use warnings;  use strict;

 # Data sampling is done as ORDER BY pid DESC, [ORDER] ASC
 # I’ll not use the database for this now, but I’ll take the selected list
 my @select = (
 # ID PID ORDER OTHER DATA ...
     {id => 14, pid => 1, ord => 1, data => 'other data'},
     {id => 15, pid => 4, ord => 1, data => 'other data'},
     {id => 24, pid => 4, ord => 2, data => 'other data'},
     {id => 23, pid => 7, ord => 1, data => 'other data'},
     {id => 27, pid => 7, ord => 2, data => 'other data'},
     {id => 25, pid => 7, ord => 3, data => 'other data'},
     {id => 17, pid => 7, ord => 4, data => 'other data'},
     {id => 28, pid => 11, ord => 1, data => 'other data'},
     {id => 21, pid => 11, ord => 2, data => 'other data'},
     {id => 5, pid => 12, ord => 1, data => 'other data'},
     {id => 11, pid => 12, ord => 2, data => 'other data'},
     {id => 13, pid => 12, ord => 3, data => 'other data'},
     {id => 10, pid => 12, ord => 4, data => 'other data'},
     {id => 22, pid => 12, ord => 5, data => 'other data'},
     {id => 2, pid => 13, ord => 1, data => 'other data'},
     {id => 6, pid => 15, ord => 1, data => 'other data'},
     {id => 20, pid => 15, ord => 2, data => 'other data'},
     {id => 9, pid => 15, ord => 3, data => 'other data'},
     {id => 7, pid => 16, ord => 1, data => 'other data'},
     {id => 1, pid => 20, ord => 1, data => 'other data'},
     {id => 26, pid => 20, ord => 2, data => 'other data'},
     {id => 8, pid => 25, ord => 1, data => 'other data'},
 # The most important thing is that the root nodes are right at the end
     {id => 12, pid => 0, ord => 1, data => 'other data'},
     {id => 4, pid => 0, ord => 2, data => 'other data'},
     {id => 3, pid => 0, ord => 3, data => 'other data'},
     {id => 18, pid => 0, ord => 4, data => 'other data'},
     {id => 16, pid => 0, ord => 5, data => 'other data'},
     {id => 19, pid => 0, ord => 6, data => 'other data'},
               );

 my% indexes = ();  # In this hash we will store the coordinates of the nodes (list key, and order in the list)
 my% lists = ();  # Lists of nodes initially by PID
 my $ tpid = undef;  # Current list PID

 foreach my $ row (@select) {
     # It is not known what is the pid of the root nodes, maybe undef, or maybe 0
     $ row -> {pid} || = 'root';
     # If the current ID of the parent node is not defined, then we substitute it.
     $ tpid || = $ row -> {pid};
     # Set the node level initially 1
     $ row -> {level} = 1;
     # Insert our node in the PID list
     push @ {$ lists {$ row -> {pid}}}, $ row;
     # We put down the coordinate for the node
     $ indexes {$ row -> {id}} = [$ row -> {pid}, $ # {$ lists {$ row -> {pid}}}];
     # If there is already a generated list for the current node ID
     if ($ lists {$ row -> {id}}) {
         # For this list we put down the new coordinates, that he will join the current list,
         # order in the new list, and increase the level by 1
         map {
                 $ indexes {$ _-> {id}} -> [0] = $ row -> {pid};
                 $ indexes {$ _-> {id}} -> [1] + = scalar @ {$ lists {$ row -> {pid}}};
                 $ _-> {level} ++
             } @ {$ lists {$ row -> {id}}};
         # Join subordinate list to current
         push @ {$ lists {$ row -> {pid}}}, @ {$ lists {$ row -> {id}}};
         # Remove it as unnecessary
         delete $ lists {$ row -> {id}};
     }
     # If our current PID does not match the node PID, then the list with the current PID is formed to the end
     if ($ tpid ne $ row -> {pid}) {
         # Do we have a parent node up to this point, if not, then he will pick up this list
         # when it comes to turn
         if ($ indexes {$ tpid}) {
             # Increase the order of nodes in the parent list from the parent node to the end by the number
             # nodes of the list being implemented
             map {
                     $ indexes {$ _} -> [1] + = scalar @ {$ lists {$ tpid}}
                 } @ {$ lists {$ indexes {$ tpid} -> [0]}} [$ indexes {$ tpid} -> [1] + 1 .. $ # {$ lists {$ indexes {$ tpid} -> [ 0]}}];
             # put down the new coordinates for the nodes of the list being introduced,
             # and level relative to parent node
             map {
                     $ indexes {$ _-> {id}} -> [0] = $ indexes {$ tpid} -> [0];
                     $ indexes {$ _-> {id}} -> [1] + = $ indexes {$ tpid} -> [1] + 1;
                     $ _-> {level} + = $ lists {$ indexes {$ tpid} -> [0]} -> [$ indexes {$ tpid} -> [1]] -> {level};
                 } @ {$ lists {$ tpid}};
             # Introduce the list relative to the coordinates of the parent node
             splice @ {$ lists {$ indexes {$ tpid} -> [0]}}, $ indexes {$ tpid} -> [1] + 1, 0, @ {$ $ {$ tpid}};
             # Delete the list as useless
             delete $ lists {$ tpid};
         }
         # We put a new PID
         $ tpid = $ row -> {pid};
     }
 }

 # Actually we will have a ready list under the key that we specified for the root nodes.
 my @result = @ {$ lists {root}};

 # We'll see for verification
 foreach my $ row (@result) {
     print $ row -> {id}, "\ t", $ row -> {pid}, "\ t", $ row -> {ord}, ​​"\ t", $ row -> {level}, "\ t ", $ row -> {data}," \ n "
 }

 one;
    

Explanations

The initial sorting is required only for the PID (in the reverse order) only because the list of root nodes is generally not necessary to paste in. Otherwise, I would have to add the last list after the completion of the cycle. I also implemented the node level calculation in the algorithm, since the Adjacency List algorithm does not have this field by definition. what is not tied.
original