Documentation
Overview of the functionality of Kohana MPTT.
Introduction
Nested sets or modified preorder tree traversal (mptt) is a way to store hierarchies in a database.
The easiest implementation of hierarchies in a database is the adjacency list model. This means a record has a field named something like 'parent_id' which stores the id of the parent of the record. The parent can have another parent and so on and so forth. Problem with retrieving the lineage of a record is that when there are several levels in the hierarchy the queries can become quite expensive.
The mptt approach solves this, the place of a record in the hierarchy is set when the record is created or moved and selecting the record and its lineage is thus less expensive. Result is, however, that moving/ deleting or creating records in the tree is expensive query-wise. Also, when the hierarchy is incorrectly set in the record the hierachy tree might be lost.
Major advantage is easy retrieval of multiple levels and speed in doing so. Edits are more costly so use only when the selects outnumber the updates,deletes and inserts by far.
There are much better explanations of the mptt and adjacency list model on the internet and I would strongly advice you to read those. They have diagrams and clear examples which make understanding mptt much easier. Also, I do not feel it is my place to explain mptt.
Some reading material * http://dev.mysql.com/tech-resources/articles/hierarchical-data.html * http://www.sitepoint.com/article/hierarchical-data-database * http://phpriot.com/articles/nested-trees-1
I think it is important to know how mptt works when using this class so you know what happens.
MPTT library
The MPTT library for Kohana makes it easier to work with nested sets. It takes care of most of the logic for you. Also, it works with the ORM library of Kohana and extends it. This means you can use the normal ORM syntax while working with nested sets.
Note: at present this library does not lock tables. This means the integrity of the tree might be at stake with multiple edits happening at once.
Some notes on the jargon
Below a list of words used in the library and documentation which may be unclear. * tree - the hierarchy of several nodes visualized as a tree * node - a record in the tree, can have one and only one parent * parent - parent of a node * children - the direct children of a node (not grandchildren) * descendants - children of a node, and their children, and their children, etc. etc. * siblings - parent has children x,y x is sibling of y, y is sibling of x * leaf - last node in a tree, has no children * root - the sole parent in a tree, has no parents * scope - each node in the tree has an identifier to see which scope it has, this way you can have multiple trees in one table * path - ancestry of a node
Configuration
The MPTT.php file can be retrieved from svn http://kohana-mptt.googlecode.com/svn/trunk/MPTT.php The file should be placed in a libraries folder.
Models are stored in the /models directory. The model of an mptt table will look something like this ``` class Place_Model extends MPTT {
protected $left_column = 'lft'; //database column where left values are stored
protected $right_column = 'rgt';//database colunn where right values are stored
protected $parent_column = 'parent_id';//database column where parent ids are stored
protected $scope_column = 'scope';//database column where the scope is stored
function __construct($id = FALSE)
{
parent::__construct($id);
}
} ``` The name of the model uses the ORM conventions of Kohana. {singular_of_table}Model extends MPTT/
Make sure the 4 columns listed above are present in the table.
The values above are also the default values, if these are your values you do not need to supply them in the model.
Other notes
A node of whom its children are retrieved stores these children in ->children These children store their parent in ->parent
``` //Earth root node has id#1 $earth=new Place_Model(1);
$earth->get_children(); foreach($earth->children as $child) { echo $child->name; echo $child->parent->name; } ```
Retrieving a node
You can retrieve a single node by supplying its id to the constructor
$earth=new Place_Model(1);
But also by other ORM methods. I have not tested the overloading of where_key(), this thus might not work at all times.
Documentation
As an example I will work with a table called 'places'. The root node is 'Earth', its children something like 'North-America','Europe','Asia', children of Europe 'UK','Germany','France', children of France might be 'Paris','Bordeaux','Lyon' etc. This is what roughly will be used.
Creating the tree
make_root()
To create a tree you have to create a root node.
$root=new Place_Model();
$root->name='Earth';
$root->make_root();
Scope defaults to 1, with only 1 tree there's no need set it manually.
Inserting childs
Earth
Asia Europe
Say you want to insert a child named North-America, its place can be left of Asia, right of Asia or right of Europe.
``` //Earth root node has id#1 $earth=new Place_Model(1);
$na=new Place_Model(); $na->name='North-America'; $na->insert_as_first_child_of($earth); ``` Inserts the child before Asia
insert_as_last_child_of()``` //Earth root node has id#1 $earth=new Place_Model(1);
$na=new Place_Model(); $na->name='North-America'; $na->insert_as_last_child_of($earth); ``` Inserts the child after Asia
insert_as_next_sibling_of()``` //Asia node has id#2 $asia=new Place_Model(2);
$na=new Place_Model(); $na->name='North-America'; $na->insert_as_next_sibling_of($asia); ``` Inserts the child to the right of Asia.
insert_as_prev_sibling_of()See insert_next_sibling_of() but then it adds it to the right of Asia
Retrieval methods
get_children($return)
If $return is true it will return an array of the children of the current node. In either case the current node has a property ->children with the array of children. Each child also has the parent property with the parent object stored in it.
Earth has children Asia, Europe, North-America ``` //Earth root node has id#1 $earth=new Place_Model(1);
$earth->get_children(); foreach($earth->children as $child) { echo $child->name; echo $child->parent->name; }
$children=$earth->get_children(true); foreach($children as $child) { echo $child->name;
}
```
get_decendants()
Stores the children of the current node in $node->children
all the way done. Grandchildren are stored in the $child->children
property. With a recursion you can thus display the entire tree.
get_leaves()
Returns an array of the leaves of the current tree.
get_path()
Returns an array with the path towards the current node.
get_root()
Returns the root of the current tree as an object. ```
$earth=new Place_Model(); $earth=$earth->get_root();
$earth->get_descendants(); //$earth now has the entire tree sored in it ```
get_first_child()
Returns first child of current node
get_last_child()
Returns last child of current node
get_prev_sibling()
Returns previous sibling of current node.
get_next_sibling
Returns next sibling of current node.
get_parent
Returns parent of current node.
get_tree($parent_node)
Returns object with tree. You can supply it with an id or a node object. Tree can be supplied to mptt->debug_tree();
Deleting methods
delete_tree()
Deletes an tree of the current scope, use with caution
delete_node($children)
Deletes current node and any children when $children is true. Default = true It will not delete the children when $children is false and will then move up the children in the hierarchy.
delete_descendants()
Deletes descendants of current node but not the node itself
delete_children()
Will just delete children of current node but not its descendants so descendants move up the tree.
Scope
The scope of an object will be retrieved from the record when the object is created.
get_scope()
Returns scope of current object
set_scope
Set scope of current object, only works on new objects. ``` //Asia node has id#2 $asia=new Place_Model(2);
$na=new Place_Model(); $na->set_scope(2); $na->name='North-America'; $na->insert_as_next_sibling_of($asia); ```
Informational methods
get_number_of_descendants()
Returns number of descendants of current node
get_number_of_children()
Returns number of children of current node
get_level()
Returns level of current node, root is 0
Helper methods
is_valid_node()
Superficial way of checking the node is valid
has_parent()
has_next_sibling()
has_prev_sibling()
has_descendants()
is_root()
is_leaf()
is_descendant_of()
is_child_of()
is_equal_to
is_descendant_of_or_equal_to()
Moving methods
This should work but has not yet been thoroughly tested. It should be self explanatory. Also moves children of the current node to the target
move_to_next_sibling_of($target)
move_to_prev_sibling_of($target)
move_to_first_child_of($target)
move_to_last_child_of($target)
Utility functions
debug_tree($tree,$disp_col)
Outputs the tree, ids, left and right values and parent ids, + the column you want to display.
rebuild_tree($parent_id,$left)
Rebuild the mptt tree according to the parent_ids. Supply with id of the root node and its left value: 1