DataMapper ORM


Nested Set Methods (nestedsets)

To enable these methods, add 'nestedsets' to DataMapper's config, under 'extensions'.

Adds methods to a Datamapper ORM object to work with nested tree database structures.

Introduction to nested sets

The nested set model is a particular technique for representing nested sets (also known as trees or hierarchies) in relational databases. The term was apparently introduced by Joe Celko; others describe the same technique without naming it or using different terms. (source: Wikipedia)

A typical example of a tree structure is an organigram of an organisation. We'll be using this to explain how nested sets work.

Nested Sets Example

The above diagram is indicating that each node is aware of all its descendents, and vice versa. For example, we can see easily enough from the diagram that Ben and Angela are children of Bill. We can also see that Tim And James are children of Ben. This ultimately gives us a link between each member of the hierarchy.

For us to represent this we need to store two more values per node, that define the relationship between the nodes of the tree structure. These are shown on the diagram in blue and red.

We call these Left (Red Values) and Right (Blue Values) pointers. These values are stored on the table, this is all we need to fully represent a nested sets hierarchy.

Storing multiple tree structures

This Datamapper extension allows you to store multiple tree structures into a single database table. To make this possible, you can add a root pointer column to the table. The root pointer is the ID that identifies the tree the node belongs to.

Node symlinking

This Datamapper extension allows you to link nodes together using symlinks. This is particularly usefull to link multiple trees together into a single big tree. To make this possible, you can add a symlink pointer column to the table. The symlink pointer is the id of the node that is linked to.

Note: Currently, symlink functionality is not implemented yet.

Note that because of the left and right pointers, it is absolutely essential that you use the nested sets methods defined below to add or delete node objects.
Do NOT use the regular Datamapper methods save() or delete(). Doing so will break the pointer chain, and will render your tree useless.

tree_config($options)

You can also define the nested sets configuration inside the model. Here's how to set that up.

class Organization extends DataMapper {
    $nestedsets = array(
        'name' => 'user_name',
        'follow' => FALSE
    );
}

The following options can be set:

Name Type Description Default
name String Name of the column in the nested sets table that contains a name used in the path methods. NULL
symlink String Name of the column in the nested sets table that is used to symlink tree nodes to other nodes. "symlink_id"
left String Name of the column in the nested sets table that is used to for the nodes left pointer. "left_id"
right String Name of the column in the nested sets table that is used to for the nodes right pointer. "right_id"
root String Name of the column in the nested sets table that is used to for the nodes tree root pointer. "root_id"
value Integer If the table contains multiple trees, this value with select the tree identified by this value. NULL
follow Boolean If the table nodes contain symlink pointer, set this to TRUE to follow symlink, FALSE to ignore them. TRUE

select_root($tree_id)

Use this method to select the desired tree if your model supports multiple trees within a single table. To enable multi-tree support, your table must contain a tree root_id field, which must be defined as integer.

Usage

$tree = new Tree();
$tree->select_root(1); // select tree with root_id 1

new_root()

Creating a new root is the first action you have to execute to define a new tree.

Note: If you have enabled multi-tree support, make sure you have selected a new tree first by using the select_tree() method, passing a new root_id. Currently, this doesn't happen automatically.

Usage

$tree = new Tree();
$tree->select_root(99); // make sure root_id 99 doesn't exist yet!
$tree->new_root();

new_first_child($node)

The parameter $node is optional. If you specify it, after the call the current object will contain the new child record created. If you don't specify it, the current object is used as reference to create a new first child, and will be overwritten with the newly created object.

You can add a new first child node to any valid tree node just by calling this method. If the current node already has children, the new child node will be inserted in front of the current first child node.

Usage

$tree = new Tree();
$tree->get_root();
$tree->new_first_child(); // the root node now has a new first child

new_last_child($node)

The parameter $node is optional. If you specify it, after the call the current object will contain the new child record created. If you don't specify it, the current object is used as reference to create a new last child, and will be overwritten with the newly created object.

You can add a new last child node to any valid tree node just by calling this method. If the current node already has children, the new child node will be inserted after the current last child node.

Usage

$tree = new Tree();
$tree->get_root();
$tree->new_last_child(); // the root node now has a new last child

new_previous_sibling($node)

The parameter $node is optional. If you specify it, after the call the current object will contain the new sibling record created. If you don't specify it, the current object is used as reference to create a new previous sibling, and will be overwritten with the newly created object.

You can add a new previous sibling node to any valid tree node just by calling this method.

Note: You can not add a new previous sibling to a root node.

Usage

$tree = new Tree();
$tree->get_root();
$tree->get_first_child(); // we need a non-root node
$tree->new_previous_sibling(); // the root node now has a new first child

new_next_sibling($node)

The parameter $node is optional. If you specify it, after the call the current object will contain the new sibling record created. If you don't specify it, the current object is used as reference to create a new next sibling, and will be overwritten with the newly created object.

You can add a new next sibling node to any valid tree node just by calling this method.

Note: You can not add a new next sibling to a root node.

Usage

$tree = new Tree();
// you can use object chaining on most nestedsets methods
$tree->get_root()->get_last_child()->new_next_sibling();

get_root()

If your model supports multi-tree, make sure to select the desired tree first using select_tree(). If you don't, or you have the tree selection explictly disabled by calling select_tree( NULL ), all tree root will be returned. You can iterate through the results the same way as will every other Datamapper resultset.

Usage

$tree = new Tree();
$tree->get_root();
if ( $tree->exists() )
{
    // the root node was found
}

get_parent($node)

The parameter $node is optional. If you specify it, after the call the current object will contain the record of the parent of the object passed. If you don't specify it, the parent of the current object will be loaded, which means you will loose the content of the current object.

Usage

$tree = new Tree();
$tree->get_root();
$tree->get_first_child(); // we need a non-root node
$tree->get_parent(); // $tree should now contain the root again

// alternatively, you can pass an object

$child = new Tree();
$child->get_root()->get_first_child(); // we need a non-root node
$parent = new Tree();
$parent->get_parent( $child ); // $parent should contain the root, $child is unmodified

get_node_where_left($left_id)

Use this method to select a tree tree directly by left pointer. If your model supports multiple trees within a single table, make sure you select a tree first.

Usage

$tree = new Tree();
$tree->select_root(1); // select tree with root_id 1
$tree->get_node_where_left(1); // select node with left pointer 1 (tree root)

get_node_where_right($right_id)

Use this method to select a tree tree directly by right pointer. If your model supports multiple trees within a single table, make sure you select a tree first.

Usage

$tree = new Tree();
$tree->select_root(1); // select tree with root_id 1
$tree->get_node_where_right(1); // select node with right pointer 1 (never exists!)

get_first_child($node)

The parameter $node is optional. If you specify it, after the call the current object will contain the record of the first child of the object passed. If you don't specify it, the first child of the current object will be loaded, which means you will loose the content of the current object.

Usage

$tree = new Tree();
$tree->get_root(); // get the root
$tree->get_first_child(); // $tree now contains the child requested

// alternatively, you can pass an object

$root = new Tree();
$root->get_root(); // get the root
$child = new Tree();
$child->get_first_child( $root ); // $child should contain the child requested, $root is unmodified

get_last_child($node)

The parameter $node is optional. If you specify it, after the call the current object will contain the record of the last child of the object passed. If you don't specify it, the last child of the current object will be loaded, which means you will loose the content of the current object.

Usage

$tree = new Tree();
$tree->get_root(); // get the root
$tree->get_last_child(); // $tree now contains the child requested

// alternatively, you can pass an object

$root = new Tree();
$root->get_root(); // get the root
$child = new Tree();
$child->get_last_child( $root ); // $child should contain the child requested, $root is unmodified

get_previous_sibling($node)

The parameter $node is optional. If you specify it, after the call the current object will contain the record of the previous sibling of the object passed. If you don't specify it, the previous sibling of the current object will be loaded, which means you will loose the content of the current object.

Usage

$tree = new Tree();
$tree->get_root(); // get the root
$tree->get_last_child()->get_previous_sibling(); // $tree now contains the second to last child of the root

// alternatively, you can pass an object

$root = new Tree();
$root->get_root(); // get the root
$lastchild = new Tree();
$lastchild->get_last_child( $root );
$sibling= new Tree();
$sibling->get_previous_sibling( $lastchild ); // $sibling should contain the node requested, $root and $lastchild are unmodified

get_next_sibling($node)

The parameter $node is optional. If you specify it, after the call the current object will contain the record of the next sibling of the object passed. If you don't specify it, the next sibling of the current object will be loaded, which means you will loose the content of the current object.

Usage

$tree = new Tree();
$tree->get_root(); // get the root
$tree->get_first_child()->get_next_sibling(); // $tree now contains the second child of the root

// alternatively, you can pass an object

$root = new Tree();
$root->get_root(); // get the root
$firstchild = new Tree();
$firstchild->get_first_child( $root );
$sibling= new Tree();
$sibling->get_next_sibling( $firstchild ); // $sibling should contain the node requested, $root and $firstchild are unmodified

is_valid_node()

An object is considered to be a valid node if:

Usage

if ( $node->is_valid_node() )
{
    // the node was a valid nested sets node
}

is_root()

A tree root node is identified by the fact that it's left pointer is always 1.

Usage

if ( $node->is_root() )
{
    // the node is a nested sets tree root node
}

is_leaf()

A tree leaf node is identified by the fact that it's doesn't have any children, which means that the difference between the 'right' and 'left' pointers is always 1.

Usage

if ( $node->is_leaf() )
{
    // the node is a nested sets tree node that doesn't have any children
}

is_child()

A child node is identified by the fact that it's 'left' pointer is larger than 1. Note that besides the root node, all nodes are children.

Usage

if ( $node->is_child() )
{
    // the node is a nested sets tree node is a child node
}

is_child_of($node)

Checks if the current object is a child of the object passed as a parameter.

Usage

if ( $child->is_child_of( $parent ) )
{
    // $child is a child of the $parent node
}

is_parent_of($node)

Checks if the current object is the parent of the object passed as a parameter.

Usage

if ( $parent->is_parent_of( $child ) )
{
    // $parent is the parent of the $child node
}

has_parent()

This method is an alias for is_child().

has_children()

This method is an alias for ! is_leaf() (a leaf node doesn't have any children).

has_previous_sibling()

Checks if the current object has a previous sibling (i.e. is not the first child).

Usage

if ( $child->has_previous_sibling() )
{
    // $child is not the first child node
}

has_next_sibling()

Checks if the current object has a next sibling (i.e. is not the last child).

Usage

if ( $child->has_next_sibling() )
{
    // $child is not the last child node
}

count_children()

Note that this method counts all child nodes, not only the direct descendants of the current node object!

Usage

if ( $parent->count_children() == 0 )
{
    // $parent doesn't have any children
}

level()

This method calculates the tree depth of the current object. The tree root will have level 0, every level of children adds one to the nesting level. So grandchildren of the root node will have level 2.

Usage

if ( $node->level() == 2 )
{
    // $node is a grandchild of the tree root
}

make_next_sibling_of($node)

This method allows you to move the current node object from it's location in the tree as the next sibling of the node object passed as parameter.

Note: If you have enabled multi-tree support, both $object and $node must be part of the same tree. If not, this method returns FALSE.

Usage

// move child A as sibling next to child B
$child_a->make_next_sibling_of( $child_b );

make_previous_sibling_of($node)

This method allows you to move the current node object from it's location in the tree as the previous sibling of the node object passed as parameter.

Note: If you have enabled multi-tree support, both $object and $node must be part of the same tree. If not, this method returns FALSE.

Usage

// move child A as sibling previous to child B
$child_a->make_previous_sibling_of( $child_b );

make_first_child_of($node)

This method allows you to move the current node object from it's location in the tree as the first child of the node object passed as parameter.

Note: If you have enabled multi-tree support, both $object and $node must be part of the same tree. If not, this method returns FALSE.

Usage

// move child A as first child of parent B
$child_a->make_first_child_of( $parent_b );

make_last_child_of($node)

This method allows you to move the current node object from it's location in the tree as the last child of the node object passed as parameter.

Note: If you have enabled multi-tree support, both $object and $node must be part of the same tree. If not, this method returns FALSE.

Usage

// move child A as last child of parent B
$child_a->make_last_child_of( $parent_b );

dump_tree($fields, $type, $skip_root)

You can use this method to dump the tree into different types of ouput, starting with the current object as root of the tree to dump. You can use the $fields array to specify which columns should be part of the result. If you want to include all column names, use the value NULL. If you pass an empty array, only the ID fields, and the 'name' field (if defined in the config) will be included in the result.

The following output types are defined:

Type Description
'array' All nodes in the resultset will be returned as array elements. If no nodes were found, an empty array is returned.
'html' Returns a string containing a dump of the tree structure with indentation in HTML format.
'tab' Returns a string containing a dump of the tree structure with indentation using tab characters.
'csv' Returns a string. Per node a line is returned, with the column values separated by commas.

Usage

// output the tree structure in html, including the root
echo $root->dump_tree( array('title', 'description'), 'html' , FALSE );

dump_dropdown($field, $skip_root)

If $field is not specified, the 'name' field configured will be used as description. If no 'name' is configured, this method returns FALSE.

Usage

// generate the html for an html dropdown
$dropdown = $root->dump_dropdown( 'title');

echo "<select name='dropdown' value='0'>\n";
foreach ( $dropdown as $key => $value )
{
    echo "<option value='", $key, "'>", $value, "</option>\n";
}
echo "</select>\n";

remove_tree($root_id)

You use this method to delete a single tree, or all trees in the table. If multi-tree support is not enabled for the model, all records will be removed from the table, since they will all belong to the same tree. If multi-tree is enabled, and no parameter is passed, the tree selected using the select_tree() method will be removed.

If the model is multi-tree enabled, and NO tree id is passed as parameter, the tree the current node belongs to will be deleted. If no 'root' column name is defined in the config, all trees will be removed!

Usage

// delete tree with ID 16
$object->remove_tree( 16 );

remove_node()

Deletes the current node object.

Note that you should NOT use the standard Datamapper delete() methods to delete a nested tree node. If you do that, the pointer sequence is broken and tree navigation no longer works.

Usage

// delete the current node
$node->remove_node();