PHP Classes
elePHPant
Icontem

MemNestedSet: Manage a nested set of elements stored in arrays

Recommend this page to a friend!
  Info   Screenshots Screenshots   View files View files (5)   DownloadInstall with Composer Download .zip   Reputation   Support forum   Blog    
Last Updated Ratings Unique User Downloads Download Rankings
2008-09-10 (8 years ago) RSS 2.0 feedNot yet rated by the usersTotal: 614 All time: 4,871 This week: 1,042Up
Version License PHP version Categories
nestedsetarray 3GNU General Publi...5.1Data types
Description Author

This class can be used to manage a nested set of elements stored in arrays.

It can manage an hierarchic tree of elements stored as array.

The class can perform several types of operations to store and retrieve the tree elements like:

- Creating the tree structure from a string with the definition of the elements.
- Set the values of tree elements given its path in the tree
- Get elements that have a given tree path
- Return a graph with the representation of the elements in tree

Innovation Award
PHP Programming Innovation award nominee
September 2008
Number 4


Prize: One book of choice from Manning
A nested set is usually associated to a method created by Joe Celko to store hierarchic data structures in a relational database in a way that is more efficient to perform several types of operations to store and retrieve nodes in a tree structure.

This class provides an implementation of nested set manipulation stored in the memory as array nodes.

Manuel Lemos
Picture of Alan H. Lake
Name: Alan H. Lake <contact>
Classes: 3 packages by
Country: Finland Finland
Innovation award
Innovation award
Nominee: 1x

Details
Purpose
  The purpose of this class is to provide a nested set in an array.

Version 3

Use
  With this nested set, you may create an indeterminant number of elements with
various relationships to one another and store them in one field.

Definition of "nested set"
  A nested set is also known as a Celko tree.  It provides for items to be nested
within other items and to be placed to the left or right of other items.

Appearance of "nested set"
  The show() function created the following drawing by referencing the location
of the items in the array as determined by their left and right positions.

|----------------------------------------- 300002 -----------------------------------------|
1                                                                                         18
   |---------------- categories ----------------|  |------------ companies -------------|
   2                                            9  10                                  17
      |-- 7019 --|  |-- 7004 --|  |-- 7023 --|        |----------- 10056 ------------|
      3          4  5          6  7          8        11                            16
                                                         |-- 3004 --|  |-- 3005 --|
                                                         12        13  14        15

The array consists of a number of elements, each of which contains left and right values
for positioning the data.  The data itself is just a string or a number that will
usually just reference some other data.  The above nested set could be initialized in a
PHP array as
array(array(1,18,300002),array(2,9,"categories"),array(3,4,7019),array(5,6,7004),
      array(7,8,7023),array(10,17,"companies"),array(11,16,10056),array(12,13,3004),
      array(14,15,3005))
but you really wouldn't want to calculate those left and right positions.  Furthermore,
that array declaration can't be easily manipulated.  The class provides a string
representation of the array that looks similar to this:
1,18,300002|2,9,categories|3,4,7019|5,6,7004|7,8,7023|10,17,companies|11,16,10056|12,13,3004|14,15,3005

The class functions
  The test suite provides a detailed look at the use of the class' public functions.
The test suite also tests some of the private functions (whose names begin with an
underscore (_).  They are not declared private in the program.

A syntactical overview follows:

$mns = new MemNestedSet([$set]);
    Obviously, an instance of the class must be made to use it.  $set is optional.
If used, it must be a string representation of a nested set.  It will initialize
the nested set array.
        $mns = new MemNestedSet();
        $mns = new MemNestedSet('1,2,companies');

$mns->import($set);
    $set is a string representation of the set.  It will initialize the nested set array.
It is used as an alternative to initializing the set array while creating the instance.

$result = $mns->set($parameter);
    The set function is used to place an element in the nested set while specifying
its location relative to other elements.
    $parameter is a string that contains the following: element [position...]
    "element" is a string or number (in string format) that describes the element to
      be inserted into the array.
    "position" is optional.  If included, there may be one or more occurrences of it.
      It consists of a preposition, ("in", "before" or "after") followed by an
      element that already exists in the nested set.
        $mns->set('companies'); inserts "companies" at the end of the top level of the
          nested set.
        $mns->set('10058 in companies'); inserts "10058" as a second level element
          within "companies".
        $mns->set('10056 in companies'); inserts "10056" as a second level element
          within "companies" after "10058".
        $mns->set('3004 in 10056'); inserts "3004" as a third level element within
          "10056", which is within "companies".
        $mns->set("3005 in 10058"); inserts "3005" as a third level element within
          "10058", which is within "companies".

        The $result of the execution of the set function will be a string representation
        of the nested set.  Therefore the last set() above will return
        '1,10,companies|2,5,10058|3,4,3005|6,9,10056|7,8,3004'.

        If there is an error, such as a positional element not existing or being in
        the wrong place, set() will return a null value, but an error message will
        be available.  Go ahead.  It won't hurt you to experiment.

$error_string = $mns->get_errors();
    This is used to fetch the $error_string.

$result = $mns->get($parameter);
    $parameter consists of the element whose children you wish to retrieve followed
    by zero or more qualifiers.
    qualifier is an "->" or a "-" followed by an element.  "->" specifies that a
    further qualification follows.  "-" specifies that the following element should
    not be returned, even if it is found.

    This function returns an array with the names of the elements in the level
    below the specified element.  Here is a nested set:
|----------------------------------------- 300002 -----------------------------------------|
1                                                                                         18
   |---------------- categories ----------------|  |------------ companies -------------|
   2                                            9  10                                  17
      |-- 7019 --|  |-- 7004 --|  |-- 7023 --|        |----------- 10056 ------------|
      3          4  5          6  7          8        11                            16
                                                         |-- 7004 --|  |-- 3005 --|
                                                         12        13  14        15
    $mns->get('300002'); returns array('categories','companies');
    $mns->get('300002 -> categories'); returns array(7019,7004,7023);
    $mns->get('300002 -> companies -> 10056); returns array(7004,3005);
    $mns->get('300002 - companies'); returns array('categories');
    $mns->get('300004'); returns null.  It's not in the nested set.

$mns->show($orientation='v',$eol="\n");
  The parameters as shown are the defaults.  If $orientation is set to anything beginning
with "v", such as "vert" or "vertical", it will be read as "v".  If $orientation does not
begin with "v", such as "h", "horz", "horiz" "horizontal" or "foo", it will be read as "h".
  Executing show() with $orientation specified (or implied) as "h" draws a graphical
representation of the nested set array as shown above.  Executing show with $orientation
specified (or implied) as "v" will draw the nested set array as shown here:
  1  18 300002
  2   9 | categories
  3   4 | | 7019
  5   6 | | 7004
  7   8 | | 7023
 10  17 | companies
 11  16 | | 10056
 12  13 | | | 3004
 14  15 | | | 3005
This option is especially useful with larger nested sets.
  The $eol parameter need not be specified if the nested set is to be shown in a
terminal window.  
  The $eol parameter should be set to something beginning with "<" if the nested set is 
to be shown in a browser.  Don't do this with a horizontal orientation, for the graphical 
layout doesn't do well in a browser.  In the case of a vertical layout and an $eol of "<",
the output should be displayed between a <table> and </table> pair, for each row will be 
output with the format 
"<tr><td id='lft'>%3s</td><td id='rgt'>%3s</td><td>%-s</td></tr>".
Notice the first <td id='lft'> and the second <td id='rgt'> is written so that CSS may
be written to right justify the numbers.

Caveat:
  This class has a replacement for strlen called ustrlen.  It is necessary when the
data has characters with more than one byte in them, such as ä and ö.  This function is
slo-o-o-ow!  That's the bad news.  The good news is that this function isn't called if
you call show($str,'v') (the vertical orientation).  If you wish to use the horizontal
orientation and know that your data has only one byte characters in it, you can
replace the contents of ustrlen() to return strlen();
  If you know of a faster way to return the number of characters in a multi-byte
string, please let me know at alan.lake@lakeinfoworks.com.

The following functions are for internal use, but may be useful in debugging:
    $loc = $mns->look_for($param,$pix,$loc);
      Input:
        $param is a parameter in the syntax of the set() function.
        $pix is an index into $param pointing the the element in $param that is to
        be looked for.
        $loc is an array containing a left and right value which delimit the scope
        of the search.
      Output:
        $loc is an array.  If the element is found where it is expected, its left
        and right values will be returned.  If the element is not found in the
        expected position, look_for will return array(0,0).

      In the test suite, the functions test_look_for_nbr1(), test_look_for_nbr2(),
      test_look_for_nbr3(), and test_look_for_nbr4() show a more detailed use
      of this function.

    $str = $mns->array_to_str($ary);
    $ary = $mns->str_to_array($str);
      In both of these functions, $str is a string representation of a nested set
      and $ary is a nested set array.

You don't have to enjoy using this class, although I hope you do.
Just be glad that you didn't have to write it yourself.
Screenshots  
  • nested_set_in_memory.jpg
  Files folder image Files  
File Role Description
Plain text file change_log.txt Doc. A change log for the class
Plain text file LICENSE.txt Lic. License
Plain text file nested_set_mem.php Class MemNestedSet class
Plain text file README Doc. Documentation
Plain text file test_nested_set_mem.php Test Test MemNestedSet

 Version Control Unique User Downloads Download Rankings  
 0%
Total:614
This week:0
All time:4,871
This week:1,042Up