Acts As Nested Set

The information below is copied from the API documentation in the source code
http://api.akelos.org/ActiveRecord/Behaviours/AkActsAsNestedSet.html

This acts provides Nested Set functionality. Nested Set is similiar to Tree, but with the added feature that you can select the children and all of it's descendants with a single query. A good use case for this is a threaded post system, where you want to display every reply to a comment without multiple selects.

A google search for “Nested Set” should point you in the direction to explain the data base theory. I figured a bunch of this from

http://threebit.net/tutorials/nestedset/tutorial1.html

Instead of picturing a leaf node structure with child pointing back to their parent, the best way to imagine how this works is to think of the parent entity surrounding all of it's children, and it's parent surrounding it, etc. Assuming that they are lined up horizontally, we store the left and right boundaries in the database.

Imagine:

 root
   |_ Child 1
     |_ Child 1.1
     |_ Child 1.2
   |_ Child 2
     |_ Child 2.1
     |_ Child 2.2

If my circles in circles description didn't make sense, check out this sweet ASCII art:

   ___________________________________________________________________
  |  Root                                                             |
  |    ____________________________    ____________________________   |
  |   |  Child 1                  |   |  Child 2                  |   |
  |   |   __________   _________  |   |   __________   _________  |   |
  |   |  |  C 1.1  |  |  C 1.2 |  |   |  |  C 2.1  |  |  C 2.2 |  |   |
  1   2  3_________4  5________6  7   8  9_________10 11_______12 13  14
  |   |___________________________|   |___________________________|   |
  |___________________________________________________________________| 

The numbers represent the left and right boundaries. The table them might look like this:

So, to get all children of an entry, you

SELECT * WHERE CHILD.LEFT IS BETWEEN PARENT.LEFT AND PARENT.RIGHT

To get the count, it's (RIGHT - LEFT - 1) / 2, etc.

To get the direct parent, it falls back to using the PARENT_ID field.

There are instance methods for all of these.

The structure is good if you need to group things together; the downside is that keeping data integrity is a pain, and both adding and removing and entry require a full table write.

This sets up a beforeDestroy() trigger to prune the tree correctly if one of it’s elements gets deleted.

• parent_column - specifies the column name to use for keeping the position integer (default: parent_id)
• left_column - column name for left boundary data, default “lft”
• right_column - column name for right boundary data, default “rgt”
• scope - restricts what is to be considered a list. Example:

actsAsList(array('scope' => array('todo_list_id = ? AND completed = 0',$todo_list_id)));

• Acts as

This section will create and maintain a nested set table for addresses. It may have a single root node or multiple root nodes. It's structure may be like this:

addresses                    Single root node
|-- Finland
|   |-- Espoo
|   |   |-- Soukka
|   |   `-- Tapiola
|   |-- Helsinki
|   |   |-- Haaga
|   |   |-- Keskusta
|   |   `-- Pasila
|   `-- Vantaa
`-- United States
    |-- New York
    |   |-- New York
    |   |   |-- Queens
    |   |   |-- Harlem
    |   |   `-- Brooklyn
    |   |-- Buffalo
    |   `-- Rochester
    `-- Texas
        |-- Austin
        |-- El Paso
        `-- Houston

or like this:

Finland                      One root node
|-- Helsinki
|    `-- Keskusta
`-- Riihimäki
     `-- Keskusta

United States               Another root node
`-- New York
     |-- Buffalo
     |-- New York
     |    `-- Harlem
     `-- Rochester

At the risk of stating the obvious, the levels are:

1. country
2. state (if any)
3. city
4. city section (if any)

The Acts As Nested Set Feature provides the ability to create and place data in the nested set and to move that data around within the nested set. What it does not do is to provide the ability to perform tasks usually associated with nested sets. Those features will be shown here and illustrated with tested code. Here are some examples:

• When a node is added, it is simply placed as the first among the children of the parent. It may need to be moved to a different position among its siblings. In this sample code, the added child will be placed among its siblings so that the names are in alphabetical order.
• If a node is edited, there's a chance that its location in the nested set will change also. Adjustment of the location of a node's children are taken care of automatically. Cool!
• If a node is deleted, it's children are deleted automatically. If you don't want that to happen, you must do something with all descendent nodes, children, grandchildren, etc.

The installer has this code:

<?php
class AddressInstaller extends AkInstaller
{
    function up_1()
    {
        $this->createTable('addresses',
            'id,'.
            'name,'.
            'parent_id I index,'.
            'lft I index,'.
            'rgt I index'
        );
    }
 
    function down_1()
    {
        $this->dropTable('addresses');
    }
}
?>

The fields specific to the nested set are parent_id, lft and rgt.

Create the table with a migration.

./script/migrate address install

./script/generate scaffold address

This creates the following:

• The model file

nested_set/app/models/address.php

• The controller file

nested_set/app/controllers/address_controller.php

• The views files

nested_set/app/views/layouts/address.tpl
nested_set/app/views/address/add.tpl
nested_set/app/views/address/destroy.tpl
nested_set/app/views/address/edit.tpl
nested_set/app/views/address/listing.tpl
nested_set/app/views/address/show.tpl
nested_set/app/views/address/_form.tpl

• The test files

nested_set/test/unit/app/models/address.php
nested_set/test/fixtures/app/models/address.php
nested_set/test/fixtures/app/installers/address_installer.php

• The helper file

nested_set/app/helpers/address_helper.php

<?php
 
class Address extends ActiveRecord
{
    var $acts_as = 'nested_set';
 
    function validate()
    {
        $this->validatesPresenceOf('name');
    }
 
}
?>

The validations state what condition the 'name' field, critical to the functioning of the nested set must meet. The data is organized by name within the nested set. Therefore, each record must have one.

We must specify whether or not the nested set has one root node or multiple root nodes. The specification is for this example code only, so we can switch back and forth by changing this value. You may want to write your code to assume one or the other. You may even have both kinds of nested sets in one program.

We're putting this specification in config/config.php as

define('AK_PROJECT_OPTION','multiple'); // single, multiple

This file is address_controller.php.
It begins like any other controller and has the same functions, plus a few others:

class AddressController extends ApplicationController
{
    function index()
    {
        $this->redirectToAction('listing');
    }

When you execute this action, the data is listed in the order that it was entered. It will show the lft and rgt fields, but Akelos doesn't show fields that end in ”'id'”, so the parent_id field is not shown. This could be overridden, but I didn't bother. As more data is added, observing the logical order becomes more difficult, so we've added a new action, display_vertical().

    function listing()
    {
        // We'll create a nested set root node only if AK_PROJECT_OPTION in config/config.php is "single".
        if(AK_PROJECT_OPTION == 'single') {
            if($this->Address->count() == 0) {
                $root =& new Address;
                $root->setAttributes(array('name' => 'addresses'));
                if(!$root->save()) {
                   die ("Root->save() failed<br>\n");
                }
            }
        }
 
        // not relative to nested set
        $this->address_pages = 
            $this->pagination_helper->getPaginator($this->Address, array('items_per_page' => 10));
        $options = $this->pagination_helper->getFindOptions($this->Address);
        $this->addresses =& $this->Address->find('all', $options);
    }

Note the use of the word node. The definition of node is a nested set object, which can be further defined as an instance of a nested set class. A nested set class is what we are creating here. What may be a little confusing is that we are able to create nodes from within the nested set class definition, which is exactly what we are doing by saying $Root =& new Address;.

This is unchanged from that which is generated.

    function show()
    {
    }

The code for the add and edit functions must take into account the data needed to place the node in its proper place in the nested set.

    function add()
    {
        // The _reqd_fields function will be defined later.
        if($this->_reqd_fields_are_present()) {
            if($this->Request->isPost() && !empty($this->params['address'])) {
                // parent_name is not stored in the addresses table.  
                // Therefore, it won't be returned in $this->params['address'].  
                // The nested set will use this to create a parent_id, which is in the table.
                $parent_name = trim($this->params['parent_name']);
                // If the user doesn't enter a parent_name...
                if($parent_name == '') {
                    if(AK_PROJECT_OPTION == 'single') {
                        // The new node will be stored at the root.
                        $parent = $this->address->nested_set->getRoot();
                    }else{
                        // The new node will be stored as a root.
                        $Root =& new Address(Ak::pick('name', $this->params['address']));
                        if($Root->save()) {
                            // The roots are alphabetized.  This assumes that there is more 
                            // than one root.  Of course, the data may be organized in any
                            // way you see fit.
                            // The _alphabetize function will be defined later.
                            $this->_alphabetize($Root);
                            $this->flash_options = array('seconds_to_close' => 10);
                            $this->flash['notice'] = $this->t('Address was successfully '.
                              ($action=='add'?'created':'updated'.'.'));
                        }else{
                            $this->flash_options = array('seconds_to_close' => 10);
                            $this->flash['notice'] = 'Root addition failed ';
                        }
                        $this->redirectToAction('listing');
                    }
                }else{
                    // If the parent_name from the view is not empty, the new node is a child.
                    // A simple typo in this string may keep it from being found in the database.
                    // We need to check.
                    // There is more than what meets the eye in the _in_database function.
                    // Fully qualified names are supported.  
                    // The _in_database function will be defined later.
                    if(!$parent = $this->_in_database($this->params['parent_name'])) {
                        $this->flash_options = array('seconds_to_close' => 10);
                        $this->flash['notice'] = $this->t('The "%parent_name" '.
                          'is not in the database.',
                          array('%parent_name' => $this->params['parent_name']));
                        $this->redirectToAction('listing');
                    }
                    // The name should not be duplicated in the root.  Therefore, we'll
                    // make sure that it doesn't already exist.
                    if($children = $parent->nested_set->getChildren()) {
                        foreach($children as $child) {
                            if($child->name == $this->params['address']['name']) {
                                $this->flash_options = array('seconds_to_close' => 10);
                                $this->flash['notice'] = $this->t('"%new_entry" '.
                                  'is not unique within %parent_name.',
                                  array('%new_entry' => $this->params['address']['name'],
                                   '%parent_name' => $parent_name));
                                $this->redirectToAction('listing');
                            }
                        }
                    }
                }
                $child =& new Address(Ak::pick('name', $this->params['address']));
                // We don't just use setAttributes() to save the contents of 
                // $this->params['address']. We are creating a new child node.  In this 
                // example, we could likely say $child =& new Address($this->params['address']);
                // but we'll use a similar construct in the edit function.  There, we would 
                // not want to save the parent_id, lft and rgt columns.  We might also have 
                // additional sets of this nested set data in the same table, so we're going 
                // to use Ak::pick from the outset.
                if($child->save()) {
                    $child->nested_set->moveToChildOf($parent);
                    // The new node goes to the top of the list of siblings, like so:
                    // |--------------------------------- parent --------------------------------|
                    // 1  |-- new node -- | |----- previously ------| |----- previously ------|  8
                    //    2               3 4   existing sibling    5 6   existing sibling    7
                    $this->_alphabetize($child);
                    // Siblings may need to be organized with relation to each other.  
                    // The _alphabetize() function may move the new node down the list until
                    // the names of the siblings are in alphabetical order.  Other 
                    // applications may not need the nodes to be alphabetized, but may need 
                    // something else.
                    $this->flash_options = array('seconds_to_close' => 10);
                    $this->flash['notice'] = $this->t('Address was successfully '.
                      ($action=='add'?'created':'updated'.'.'));
                }
                $this->redirectToAction('listing');
            }
        }else{
            // In preparing the view for the user, we need to initialize the data 
            // that will not come from the model.
            $this->parent_name = '';
        }
    } 
 
    function _reqd_fields_are_present()
    {
        // The name is required if we are to process data that has been entered.  
        if(empty($this->params['address'])) return false;
        if(empty($this->params['address']['name'])) return false;
        return true;
    }

Edit is like add, except that we have to allow for the preexisting data. We're not going to include notes to cover what we covered in the add function.

    function edit()
    {
        if(empty($this->params['address'])) {
            // Each nested_set node has a parent_id field.  We're using it to get the parent node.
            $parent =& $this->Address->find(@$this->Address->parent_id);
            $this->parent_name = $parent->name;
        }else{
            // There is more than what meets the eye in the _in_database function.
            // Fully qualified names are supported.
            // The result of this statement is the fully qualified parent of the
            // new node.  Later, we'll assign the new node as its child:
            // $this->Address->nested_set->moveToChildOf($parent);
            if(!$parent = $this->_in_database($this->params['parent_name'])) {
                $this->flash_options = array('seconds_to_close' => 10);
                $this->flash['notice'] = $this->t('The parent "%parent_name" '.
                  'is not in the database.',array('%parent_name' => $parent_name));
                $this->redirectToAction('listing');
            }
            // What George Foreman did in naming all of his sons "George" is not
            // permitted in this system.  We are specifying that the children
            // of any node must have unique names.
            if($children = $parent->nested_set->getChildren()) {
                foreach($children as $child) {
                    if($child->name == $this->params['address']['name']) {
                        $this->flash_options = array('seconds_to_close' => 10);
                        $this->flash['notice'] = $this->t('"%new_entry" '.
                          'is not unique within %parent_name.',
                          array('%new_entry' => $this->params['address']['name'],
                            '%parent_name' => $parent_name));
                        $this->redirectToAction('listing');
                    }
                }
            }
 
        $this->Address->setAttributes(
          Ak::pick('name', $this->params['address']));
        if($this->Request->isPost() && $this->Address->save()){
            // If data is changed in a node, this may cause its place in the 
            // nested set to be changed, too.  So, we need the next two statements.  
            // If the node's location is changed, this Acts As Nested Set
            // automatically changes the nested set fields in its children, grandchildren, etc.
            $this->Address->nested_set->moveToChildOf($parent);
            $this->_alphabetize($this->Address);
            $this->flash_options = array('seconds_to_close' => 10);
            $this->flash['notice'] = $this->t('Address was successfully updated.');
            $this->redirectToAction('listing');
        }
    }
}

There are no coding changes needed in this function. It should be noted, however, that when a node is destroyed, all descendents are automatically destroyed. You may want to modify this function to prevent a node from being destroyed if it has children. This would mean, of course, that the user would have to either destroy or move each child before destroying this node. You might also want to move all children to this node's parent before destroying it.

    function destroy()
    {
        if(!empty($this->params['id'])){
            $this->address =& $this->Address->find($this->params['id']);
            if($this->Request->isPost()){
                $this->address->destroy();
                $this->redirectTo(array('action' => 'listing'));
            }
        }
    }

This is a new action. I've added some links in views to get here. It displays the nested set in the format shown at the beginning of this section:

Finland
|-- Helsinki
|    `-- Keskusta
`-- Riihimäki
     `-- Keskusta
United States
`-- New York
     |-- Buffalo
     |-- New York
     |    `-- Harlem
     `-- Rochester

    function display_vertical()
    {
        // When you have multiple roots, the first one that was added is the "real" 
        // one.  You have to get the other roots relative to this one.  getRoot()
        // is needed whether you have single or multiple roots.  
        $root = $this->address->nested_set->getRoot();
        // The code in this next block can be made simpler if you have only single roots.
        $roots = $root->nested_set->getRoots();
        $this->addresses = array();
        foreach($roots as $root) {
            $addresses =& $root->nested_set->getFullSet();
            $this->addresses = array_merge($this->addresses,$addresses);
        }
        foreach($this->addresses as $this->address) {
        // end of the block mentioned above
            $level = $this->address->nested_set->getLevel();
            $parent = $this->address->nested_set->getParent();
            if(!isset($parent->last_sib)) $parent->last_sib = false;
            if($this->address->nested_set->isChild()) {
                $siblings = $this->address->nested_set->getSiblings(true);
                $last = $siblings[count($siblings)-1];
                $this->address->last_sib = ($this->address->name == $last->name);
            }else{
                $this->address->last_sib = false;
            }
            $this->address->graphic = '';
            if($this->address->nested_set->isChild()) {
                $parents = $this->address->nested_set->getParents();
                foreach($parents as $parent) {
                    if($parent->nested_set->isChild()) {
                        $par_sibs = $parent->nested_set->getSiblings(true);
                        $par_sib_cnt = count($par_sibs);
                        if($parent->name == $par_sibs[$par_sib_cnt-1]->name) {
                            $this->address->graphic .= str_repeat('&nbsp',5);
                        }else{
                            $this->address->graphic .= '|'.str_repeat('&nbsp',4);
                        }
                    }
                }
            }
            if($this->address->last_sib) {
                $this->address->graphic .= '`--';
            }else{
                if($level > 0) $this->address->graphic .= '|--';
            }
        }  
    }

function _alphabetize($node)
{
        // This code is written to accomodate multiple roots.
        $siblings = false;
        if($node->nested_set->isChild()) {
            // This block needs to have only this line if you have a single root.
            $siblings =& $node->nested_set->getSiblings();
        }else{
            $siblings = $node->nested_set->getRoots();
        }
        // end of block
 
        // You don't want to alphabetize if there are no siblings.
        if($siblings) {
         // I don't know how much overhead is involved in repeatedly calling 
         // $node->nested_set->moveToLeftOf() or $node->nested_set->movetoRightOf() 
         // so I'll iterate to find the location where my node should be, 
         // then drop it into place.
 
         // If you have a single root, so that you got $siblings through the getSiblings()
         // function, the original location of $node is the first in the list of siblings.  
         // If this is the right place, let's just get out of here.
         // If you have multiple roots, so that you got $siblings through the getRoots()
         // function, the original location of $node is the last in the list of siblings.
         // Therefore, you don't want to do this test.
            if(AK_PROJECT_OPTION == 'single') {
                if($node->name < $siblings[0]->name) return;
            }
 
            // If the node belongs at the end of the list of siblings, let's find that 
            // out before we do any iterations.
            $last = count($siblings) - 1;
           if($node->name > $siblings[$last]->name) {
                if($node->nested_set->isChild()) {
                    $node->nested_set->moveToRightOf($siblings[$last]);
                }
            }else{
                // Here's where we iterate through the list of siblings until we find 
                // the proper place.  We stop iterating as soon as we do.
                foreach($siblings as $sibling) {
                    if($node->name < $sibling->name) {
                         $node->nested_set->moveToLeftOf($sibling);
                         break;
                    }
                }
            }
        }
    }

This function will return the fully qualified $parent when given the fully qualified $parent_names. For example, suppose that you have a nested set that looks like this:

Finland
|-- Helsinki
|   `-- Haaga
`-- Jyväskylä
    `-- Mattilanpelto

If we want to document Keskusta (downtown) as a section of Helsinki, we must say so by noting that city as the $parent_name. We don't need to enter “Finland”, although we could, for it isn't needed to fully qualify where Keskusa was to go. After adding it, our nested set will look likethis:

Finland
|-- Helsinki
|   |-- Haaga
|   `-- Keskusta
`-- Jyväskylä
    `-- Mattilanpelto

But, Jyväskylä has a Keskusta (downtown) also. When we add it, we must put the city name as the parent. After adding it, our nested set will look likethis:

Finland
|-- Helsinki
|   |-- Haaga
|   `-- Keskusta
`-- Jyväskylä
    |-- Keskusta
    `-- Mattilanpelto

Our second example begins looking like this:

United States
`-- New York
    |-- Buffalo
    |-- New York
    `-- Syracuse

The first “New York” refers to the state of New York. The second “New York” refers to the city, which is in the state. You want to add Queens to New York, not as a city in New York State, but to the city of New York as a borough in (section of) New York city. If the parent_name is just “New York”, New York state will be returned as the parent because it is highest in the data heirarchy. By providing a parent_name of “New York, New York”, the first one found will be New York state. Looking within New York state for another “New York”, New York city will be returned as parent, and Queens can then be added. It will then look like this:

United States
`-- New York
    |-- Buffalo
    |-- New York
    |   `-- Queens
    `-- Syracuse

    function _in_database($parent_names)
    {
        $parent_names = explode(',',$parent_names);
        // The first time through, we don't know where it is.
        $parent_name = trim(array_pop($parent_names));
        // If this first parent_name isn't in the database, we don't care 
        // about any other parent names.
        if(!$parent =& $this->address->findFirst(
          "name = ?", $parent_name)) return false;
        // After the first parent, all other parents must be children of each other,
        // beginning with the first parent.
        if(count($parent_names) > 0) {
            foreach($parent_names as $parent_name) {
                $left_col = $parent->nested_set->getLeftColumnName();
                $right_col = $parent->nested_set->getRightColumnName();
                // $left_col and $right_col are "lft" and "rgt" in this example.  We
                // could have assumed this fact, but because I plan to use as many nested
                // set functions as I can, I chose to set the variables.
 
                // This next statement uses the $left_col and $right_col variables, but I 
                // could have just as well written the line that uses them like this:
                // trim($parent_name),$parent->lft,$parent->rgt)) return false;
                // I might note that I had a very difficult time finding documentation in the 
                // PHP Manual telling how to write $parent->$left_col.  In fact, I figured out 
                // how by experimentation.
                // This statement assigns a value to $parent.  If the findFirst() function 
                // doesn't find anything, it returns false; otherwise, it will return the 
                // nested set AkActiveRecord.  The result of the last iteration of the
                // above "foreach" will be returned to the calling function.
                if(!$parent = $this->address->findFirst(
                  "name = ? AND $left_col > ? AND $right_col < ?",
                  trim($parent_name),$parent->$left_col,$parent->$right_col)) return false;
            }
        }
        return $parent;
    }  // This closes the _in_database function.
}  // This closes the class.

Note that the parent_name uses the $form_tag_helper instead of the sintags seen in the address_name. The reason for this is that the latter two fields are not connected to a model, but must be processed by the controller.

<?php  echo $active_record_helper->error_messages_for('address');?>
 
    <p>
        <label for="address_name">_{Name}</label><br />
        <%= input 'address', 'name' %>
    </p>
 
    <p>
        <label for="address_parent_name">_{Parent Name}</label><br />
        <?= $form_tag_helper->text_field_tag(
          'parent_name',$parent_name,array('size' => 30, 'maxlength' => 255)); ?>
        <div><br />Include enough of the parents to make the name unique, such as 
"Keskusta,Riihimäki".  Put a comma between all parents.<br /><br />(You could add 
",Finland", but it is not likely that there will be a Riihimäki in any other country.)</div>
    </p>

The only line that is different from those generated by the scaffold is the second <li> in the sidebar (line 5). This is just to give access to the display_vertical action.

<div id="sidebar">
  <h1>_{Tasks}:</h1>
  <ul>
    <li><?php  echo  $url_helper->link_to($text_helper->translate('Create new Address'), 
array('action' => 'add'))?></li>
    <li><?php  echo  $url_helper->link_to($text_helper->translate('Vertical display'), 
array('action' => 'display_vertical'))?></li>
  </ul>
</div>
 
<div id="content">
  <h1>_{Addresses}</h1>
 
  {?addresses}
  <div class="listing">
  <table cellspacing="0" summary="_{Listing available Addresses}">
 
  <tr>
    <?php  $content_columns = array_keys($Address->getContentColumns()); ?>
    {loop content_columns}
        <th scope="col"><?php  echo  $pagination_helper->sortable_link($content_column) ?></th>
    {end}
    <th colspan="3" scope="col"><span class="auraltext">_{Item actions}</span></th>
  </tr>
 
  {loop addresses}
    <tr {?address_odd_position}class="odd"{end}>
    {loop content_columns}
      <td class="field"><?php  echo  $address->get($content_column) ?></td>
    {end}
      <td class="operation"><?php  echo  $address_helper->link_to_show($address)?></td>
      <td class="operation"><?php  echo  $address_helper->link_to_edit($address)?></td>
      <td class="operation"><?php  echo  $address_helper->link_to_destroy($address)?></td>
    </tr>
  {end}
   </table>
  </div>
  {end}
 
    {?address_pages.links}
        <div id="AddressPagination">
        <div id="paginationHeader"><?php  echo translate('Showing page %page of %number_of_pages',
          array('%page'=>$address_pages->getCurrentPage(),
                '%number_of_pages'=>$address_pages->pages))?></div>
        {address_pages.links?}
        </div>
    {end}
</div>

<div id="sidebar">
  <h1>_{Tasks}:</h1>
  <ul>
    <li><?php  echo  $url_helper->link_to($text_helper->translate('Create new Address'), array('action' => 'add'))?></li>
    <li><?php  echo  $url_helper->link_to($text_helper->translate('Back to overview'), array('action' => 'listing'))?></li>
  </ul>
</div>
 
<div id="content">
  <h1>_{Addresses}</h1>
 
  {?addresses}
  <div class="listing">
  {loop addresses}
      {address.graphic} {address.name}<br />
  {end}
  </div>
  {end}
</div>
<div id="sidebar">
  <h1>_{Tasks}:</h1>
  <ul>
    <li><?php  echo  $url_helper->link_to($text_helper->translate('Create new Address'), array('action' => 'add'))?></li>
    <li><?php  echo  $url_helper->link_to($text_helper->translate('Back to overview'), array('action' => 'listing'))?></li>
  </ul>
</div>

See? Nothing to it.

This is under construction.

The intent of this example is to show how to put a single piece of data into more than one nested set. Our example will show people. Each person will have an address and work for a company. We'll be able to list the people who have a certain address or part thereof (a given section of a city, a given zip code, etc.) We'll be able to list the people who work for a certain company or part thereof, such as a given department. And we'll be able to list combinations of addresses and companies.

This example will be built from the previous example's code, so the comments here will not be duplicates of that in the addresses example. We'll list just those functions that are changed from it.

The data will contain name, address and company. address and company will be in nested sets where the heirarchy will be created as needed.

The address heirarchy will contain section, city, state and country. The company heirarchy will consist of department, division and company.

Beside the “native” nested set data, we will produce a full alphabetic list of people, a list of people by city, a list of people by company and a list of people by city and company.

A nested set table must have three special fields: lft, rgt and parent_id. In my first attempt at solving this problem, I tried to have two sets of these fields:

$this->createTable('people',
    'id,'.
    'name,'.
    'address,'.
    'company,'.
    'addr_parent_id I index,'.
    'addr_lft I index,'.
    'addr_rgt I,'.
    'co_parent_id I index,'.
    'co_lft I index,'.
    'co_rgt I'
);

I would use the functions

$this->person->nested_set->setLeftColumnName($type.'_lft');
$this->person->nested_set->setParentColumnName($type.'_parent_id');
$this->person->nested_set->setRightColumnName($type.'_rgt');

along with the corresponding functions

$lft = $this->person->nested_set->getLeftColumnName();
$parent_id = $this->person->nested_set->getParentColumnName();
$rgt = $this->person->nested_set->getRightColumnName();

This didn't work, for Akelos requires that a nested set table have the three fields precisely as named: lft, rgt and parent_id. I figured that I would include them, but wouldn't use them:

$this->createTable('people',
    'id,'.
    'name,'.
    'address,'.
    'company,'.
    'parent_id I index,'.
    'lft I index,'.
    'rgt I,'.
    'addr_parent_id I index,'.
    'addr_lft I index,'.
    'addr_rgt I,'.
    'co_parent_id I index,'.
    'co_lft I index,'.
    'co_rgt I'
);

What I discovered was that you can't update both sets of nested set fields with code like this (in the add method of the constructor):

$child =& new Person(Ak::pick('name,address,company', $this->params['person']));
$child->nested_set->setLeftColumnName('addr_lft');
$child->nested_set->setParentColumnName('addr_parent_id');
$child->nested_set->setRightColumnName('addr_rgt');
if($child->save()) {
    $child->nested_set->moveToChildOf($parent);  // $parent has been defined previously
}
$child->nested_set->setLeftColumnName('co_lft');
$child->nested_set->setParentColumnName('co_parent_id');
$child->nested_set->setRightColumnName('co_rgt');
if($child->save()) {
    $child->nested_set->moveToChildOf($parent);  // $parent has been defined previously
}

The co_lft, co_parent_id and co_rgt fields were not updated. Other data in the record was updated. I also tried to replace the second $child→save() with $child→update($id,$attr), but this didn't help.

I'm going to attempt another approach: we'll have two nested set tables that are linked to one another. Stay tuned to see how this works…

This section is not complete.

In the following text, a node is an instance of the object. For example in the code in address_controller.php, the node will be an instance of address.

These nested set functions are:

$this->object->nested_set->addChild(&$child);

This will add a child to this object in the tree. If this object hasn't been initialized, it gets set up as a root node. Otherwise, this method will update all of the other elements in the tree and shift them to the right, keeping everything balanced.

$this->object->nested_set->beforeCreate(&$other_object);

When $other_object is created, this function automatically sets the active left and right pointers to the end of the tree. This doesn't need to be called specifically.

$this->object->nested_set->beforeDestroy(&$other_object);

When $other_object is destroyed, this function shifts all of the lefts and rights to the right of it to eliminate any gaps in the left and right pointers. This doesn't need to be called specifically.

$nbr = $this->object->nested_set->countChildren();

Returns the number of all nested children of this object.

$array_of_nested_sets = $this->object->nested_set->getAllChildren();

Returns a set of all of its children and nested children.

$array_of_nested_sets =& $this->object->nested_set->getAncestors();

Returns an array of all parents.

$array_of_nested_sets = $this->object->nested_set->getChildren();

Returns a set of only this entry's immediate children.

getFullSet ([$exclude = null]) // Returns a set of itself and all of its nested children
getLevel () // Returns the level of this object in the tree
&getParent () // Returns the parent Object
&getParents () // Returns an array of parent Objects.  This is useful in making breadcrumb like stuctures
getRoot () // Returns the single root

$array_of_nested_sets = $this->object->nested_set->getRoots();

If $this→object has no parents, getRoots() will return all other objects that have no parents.

getScopeCondition ()
getScopedColumn ( $column)
&getSelfAndAncestors () // Returns an array containing all parents and self
getSelfAndSiblings () 
// Returns an array containing all nodes that are children of the parent, including self.
// In the address controller, you would write
//         $self_and_siblings = $this->address->nested_set->getSelfAndSiblings();

$array_of_nested_sets = $this->object->nested_set->getSiblings([$search_for_self = false]);

Returns an array containing all children of the parent. The default is to exclude the self.

Consider the situation where your set has data arranged by countries, but each country has no parent. These are multiple roots. If getSiblings() is used on a set of multiple roots, an error will result. Only the first node in a set of multiple roots will return a true for isRoot(). (Keep that in mind if you sort them.) When you have two or more multiple roots, all those after the first will return a true for isUnknown(). Only a node with a parent will return a true for isChild();

To get the siblings for multiple roots, use getRoots();

Another thing to keep in mind is that when you save a new child node, you will follow the save() with $child→nested_set→moveToChildOf($parent); This will put the child at the front of the list of siblings. When you save a new node that doesn't have a parent, you won't use the moveToChildOf() function, so the new node will be at the end of the list of siblings gotten with the getRoots() function.

$var = $this->object->nested_set->getType();

Returns the type of AkActiveRecord. In this context, it returns “nested set”.

init([$options = array()])

$bool = $this->object->nested_set->isChild();

Returns true if this node is linked to a parent.

$bool = $this->object->nested_set->isRoot();

Returns true if this is the only node in the set.

$bool = $this->object->nested_set->isUnknown();

Returns true if this is neither a root nor a child node. This is the case of multiple roots (nodes with no parents) after the first in the set.

moveTo ($target,$position)

$this->object->nested_set->moveToChildOf($parent);

Move $this→object so that it is a child of $parent. It will be at the front of the list when getSiblings() is executed.

$this->object->nested_set->moveToLeftOf($node);

Move $this→object to the left of $node. This is often used when sorting a list of siblings.

$this->object->nested_set->moveToRightOf($node);

Move $this→object to the right of $node. This is often used when sorting a list of siblings.

void reloadActiveRecordInstance ( &$nodeInstance)
void setScopeCondition ( $scope_condition)

$this->nested_set->setLeftColumnName($left_column_name);
$this->nested_set->setParentColumnName($parent_column_name);
$this->nested_set->setRightColumnName($right_column_name);
 
$left_column_name = $this->nested_set->getLeftColumnName();
$parent_column_name = $this->nested_set->getParentColumnName();
$right_column_name = $this->nested_set->getRightColumnName();

These functions do not replace the need for the lft, rgt and parent_id columns. Moreover, the AkActsAsNestedSet class will not update more than one set of these fields.