The London Perl and Raku Workshop takes place on 26th Oct 2024. If your company depends on Perl, please consider sponsoring and/or attending.


Data::NestedSet - calculate left - right values from depth (modified preorder tree traversal algorithm)




    use Data::NestedSet; 

    ##let's pretend that you get that from a spreadsheet...
    my $data = [
           #go on....

    my $nodes   = new Data::NestedSet($data,2)->create_nodes();

    #now $nodes contains : 

    #       [1,'MUSIC',0,1,14],
    #       [2,'M-GUITARS',1,2,11],
    #       [3,'M-G-GIBSON',2,3,6],
    #       [4,'M-G-G-SG',3,4,5],
    #       [5,'M-G-FENDER',2,7,10],
    #       [6,'M-G-F-TELECASTER',3,8,9],
    #       [7,'M-PIANOS',1,12,13],


Based on the depth,the Data::NestedSet allows you to get the left and right values for a modified preorder tree.


You've decided to deal with hiearachical data within your database by using the nested set model (adjacency list model is an other way of doing so) but you do not want to write all the left and right values by hand. It is manageable when the depth and number of categories is small like the above example but when it changes into hundreds of categories with a lot of depth level, this can become a real nightmare (don't even mention reorganisation of the tree!).

If you want third parts to deal with this system thru an easy-to-go process, you may have a hard time explaining the nested model concept:

Basically each rows can be considered the branch or the leaf of a tree where the left and right value of a row represents all the sub categories within this category... Therefore when the right value minus the left value is equal to 1, you can say that this category does not contain any sub categories, you see? ... ...

But explaining that categories nest with depth can be easily understood:

The first category is at level 0. The next category within the first category is at level 1 and so on and so forth.

You should see in the eyes of your listener a glow of understanding.

If so, let your user fill in an excel file and let this module do the job for you!


Even if these advantages are related to the nested set model rather than to this module, it is interesting to notice that:

- You can build an entire tree in a snap.

- You can rebuilt the entire tree structure in a snap too:

If you insert for the first time the newly created nested model in your favorite database and then needs to change many categories depth, reorder the tree, just export the data with ids (serial, autoincrement value),depth and any relevant business logic data into a csv file or better a spreadsheet (xls,ods, you pick), let your user reorder the tree by modifying the depth and reimport! Use the module to recreate the left and right values and then update or even insert if necessary the new tree.

- You can change the order of the tree very easily.

How many times did a client come over you asking you to reorder the categories? The nested set model allows to order the categories by their left (or right) value. You can therefore reorder the categories and reimport them very easily and reorder the entire tree.


As for now, the module is using an oo interface even if a simple procedural interface could do the job,several methods dealing with the tree structure (get_descendents, get_children, get_root,etc...) may be added for easy mocking.

new(Arrayref of ref,depth offset)

Takes an array ref of array ref as its first argument and the position of the depth as its second. Each row within the array ref should have the same number of 'columns'. The data should always contain the entire tree with the first row containing the root with a depth level of 0. The depth offset is where the module should look for the value of the depth.

Return a NestedModel object.


Built the tree and return an array ref of array ref with the left and right values appended at the end.


An array ref must be supplied as the first argument. Seen ...

You did not pass an array reference to the constructor as its first argument.

    my $nodes = new Data::NestedSet(@array,2);  # error
    my $nodes = new Data::NestedSet(\@array,2); # ok
The number of items within the array ref must be >=1 . Seen ...

You passed an empty reference to the constructor.

    my $nodes = new Data::NestedSet([],2);              # error
    my $nodes = new Data::NestedSet([[1,'ROOT',0]],2);  # ok
An integer must be supplied as the second argument. Seen ...

You didn't supply a proper depth's offset value within the array reference.

    my $nodes = new Data::NestedSet(\@array);         # error
    my $nodes = new Data::NestedSet(\@array,"wrong"); # error
    my $nodes = new Data::NestedSet(\@array,2);       # ok


explanation of the nested set model (Managing Hierarchical Data in MySQL)

Even though, it is written for mysql rdb, the explanations are worth a look.

Table::ParentChild Tree::DAG_Node Sort::Tree DBIx::Tree DBIx::Tree::NestedSet

None of this modules allows you to create a nested model from the depth but are related to some extends.








If you do me the favor to _use_ this module and find a bug, please email me i will try to do my best to fix it (patches welcome)!


Shirirules <shiriru0111[arobas]>


This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself.