Non-recursive fetch of the entire Adjacency List tree

    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:
    • The entire comment tree;
    • Map of site;
    • Navigation menu;
    • etc.;
    The proposed solutions for forming a tree array using pointers, of course, allow you to get rid of unnecessary queries to the database, but alas, they do not exclude recursion, albeit through an array, but still. And we have…

    Task

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

    Decision

    I still have no idea how to solve such a problem at the database level, but at the application level it’s easy. The main difficulty is that for a certain node we may not yet get its parent and children. Therefore, we will use temporary lists and we will stick them together as needed. I suggest the algorithm in Perl.

    Perl code (1)
    #! / usr / bin / perl
    use warnings; use strict;
    # Data is sampled as ORDER BY pid DESC, [ORDER] ASC
    # Now I won’t use the database for this, 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 root nodes are at the very 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, (the key of the list, and the 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 pid the root nodes may undef, or maybe 0
        $ row -> {pid} || = 'root';
        # If the current ID of the parent node is not defined, then substitute it
        $ tpid || = $ row -> {pid};
        # Set the node level initially 1
        $ row -> {level} = 1;
        # Insert our node into the PID list
        push @ {$ lists {$ row -> {pid}}}, $ row;
        # 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, put down the new coordinates, that it 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}}};
            # Attach a subordinate list to the current
            push @ {$ lists {$ row -> {pid}}}, @ {$ lists {$ row -> {id}}};
            # Delete it as unnecessary
            delete $ lists {$ row -> {id}};
        }
        # If our current PID does not match the PID of the node, then the list with the current PID is formed to the end
        if ($ tpid ne $ row -> {pid}) {
            # Have we had a parent node up to this point, if not, then he will pick up this list
            # when it comes to him
            if ($ indexes {$ tpid}) {
                # Increase the order of nodes in the parent list from the parent node to the end by the number
                # injected list nodes
                map {
                        $ indexes {$ _} -> [1] + = scalar @ {$ lists {$ tpid}}
                    } @ {$ lists {$ indexes {$ tpid} -> [0]}} [$ indexes {$ tpid} -> [1] + 1 .. $ # {$ lists {$ indexes {$ tpid} -> [ 0]}}];
                # put down new coordinates for nodes of the implemented list,
                # and level relative to the 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}};
                # Implement a list relative to the coordinates of the parent node
                splice @ {$ lists {$ indexes {$ tpid} -> [0]}}, $ indexes {$ tpid} -> [1] + 1, 0, @ {$ lists {$ tpid}};
                # Delete the list as unnecessary
                delete $ lists {$ tpid};
            }
            # Putting a new PID
            $ tpid = $ row -> {pid};
        }
    }
    # We will have a ready-made list under the key that we specified for the root nodes.
    my @result = @ {$ lists {root}};
    # Let's see for verification
    foreach my $ row (@result) {
        print $ row -> {id}, "\ t", $ row -> {pid}, "\ t", $ row -> {ord}, ​​"\ t", $ row -> {level}, "\ t ", $ row -> {data}," \ n "
    }
    1;
        


    Explanations

    Initial sorting is required only for PID (in reverse order) only because you don’t need to stick the list of root nodes anywhere. Otherwise I would have after the completion of the cycle "dokleit" last spisok.Takzhe I implemented the algorithm has calculated the level of nodes, as in the algorithm Adjacency List of fields for no opredeleniyu.Kstati, in the hash % lists except root will list lists artifacts, nor which are not attached.
    original

    Also popular now: