PHP Classes

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    
Ratings Unique User Downloads Download Rankings
Not yet rated by the usersTotal: 624 All time: 5,040 This week: 289Up
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
Age: 81
All time rank: 11583 in Finland Finland
Week rank: 587 Up2 in Finland Finland Up
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:624
This week:0
All time:5,040
This week:289Up