Cartalyst LLC.
Nested-sets by Cartalyst
0
78
0
8
2

This package requires a valid subscription. Subscribe for access.

Introduction

A modern and framework agnostic nested sets package utilizing the Modified Preorder Tree Traversal algorithm.

The package follows the FIG standard PSR-4 to ensure a high level of interoperability between shared PHP code and is fully unit-tested.

The package requires PHP 8.0+ and comes bundled with a Laravel 9 Service Provider to simplify the optional framework integration.

Have a read through the Installation Guide and on how to Integrate it with Laravel 9.

Quick Example

Making a Root Node

$countries = new Menu(['name' => 'Countries']);

$countries->makeRoot();

Make a Node a Child of Another Node

$australia = new Menu(['name' => 'Australia']);

$australia->makeLastChildOf($countries);

Make a Node a Sibling of Another Node

$england = new Menu(['name' => 'England']);

$england->makePreviousSiblingOf($newZealand);

Installation

The best and easiest way to install the Nested Sets package is with Composer.

Preparation

Open your composer.json file and add the following to the require array:

"cartalyst/nested-sets": "^8.0"

Add the following lines after the require array on your composer.json file:

"repositories": [
    {
        "type": "composer",
        "url": "https://packages.cartalyst.com"
    }
]

Note: Make sure that after the required changes your composer.json file is valid by running composer validate.

Install the dependencies

Run Composer to install or update the new requirement.

php composer install

or

php composer update

Now you are able to require the vendor/autoload.php file to autoload the package.

Integration

Laravel 9

The Nested Sets package has optional support for Laravel 9 and it comes bundled with a Service Provider for easy integration.

After installing the package, open your Laravel config file config/app.php and add the following lines.

In the $providers array add the following service provider for this package.

'Cartalyst\NestedSets\Laravel\NestedSetsServiceProvider',

Create a new Migration

Run the following command php artisan make:migration create_menus_table

Open the database/migration/xxxx_xx_xxxxxx_create_menus_table.php file

Note: the xxxx_xx_xxxxxx is your current date and you can customize the migration name to fit your own needs.

Inside the up() method add the following:

Schema::create('menus', function($table)
{
    $table->increments('id');

    $table->string('name');

    // You can rename these columns to whatever you want, just remember
    // to update them on the $reservedAttributes inside your model.
    $table->integer('lft');
    $table->integer('rgt');
    $table->integer('menu');

    // you can add your own fields here

    $table->timestamps();
    $table->engine = 'InnoDB';
    $table->unique(array('lft', 'rgt', 'menu'));
});

Note: For more information about the Schema Builder, check the Laravel docs

Once your migration is finished, you just need to run php artisan migrate.

Create a new Model

Here is a default Eloquent model that you can use

use Illuminate\Database\Eloquent\Model;
use Cartalyst\NestedSets\Nodes\NodeTrait;
use Cartalyst\NestedSets\Nodes\NodeInterface;

class Menu extends Model implements NodeInterface {

    use NodeTrait;

    /**
     * The table associated with the model.
     *
     * @var string
     */
    protected $table = 'menus';

    /**
     * The attributes that aren't mass assignable.
     *
     * @var array
     */
    protected $guarded = array('lft', 'rgt', 'menu', 'created_at', 'updated_at');

    /**
     * Array of attributes reserved for the worker. These attributes
     * cannot be set publically, only internally and shouldn't
     * really be set outside this class.
     *
     * @var array
     */
    protected $reservedAttributes = array(
        'left'  => 'lft',
        'right' => 'rgt',
        'tree'  => 'menu',
    );

}

Native

Nested Sets ships with an implementation for Eloquent out of the box, in order to use the Eloquent implementation, you must require 'illuminate/database': "^9.0" on your composer.json file and run composer update afterwards.

// Include the composer autoload file
require 'vendor/autoload.php';

// Import the necessary classes
use Illuminate\Database\Eloquent\Model;
use Cartalyst\NestedSets\Nodes\NodeTrait;
use Cartalyst\NestedSets\Nodes\NodeInterface;
use Illuminate\Database\Capsule\Manager as Capsule;

// Create the model
class Menu extends Model implements NodeInterface {

    use NodeTrait;

    protected $table = 'menus';

    protected $guarded = array('lft', 'rgt', 'menu', 'created_at', 'updated_at');

    protected $reservedAttributes = array(
        'left'  => 'lft',
        'right' => 'rgt',
        'tree'  => 'menu',
    );

}

// Establish the database connection
$capsule = new Capsule();

$capsule->addConnection([
    'driver'    => 'mysql',
    'host'      => 'localhost',
    'database'  => 'nested-sets',
    'username'  => 'username',
    'password'  => 'secret',
    'charset'   => 'utf8',
    'collation' => 'utf8_unicode_ci',
]);

$capsule->bootEloquent();

// Start using Nested Sets
$countries = new Menu(['name' => 'Countries']);
$countries->makeRoot();

$australia = new Menu(['name' => 'Australia']);
$australia->makeLastChildOf($countries);

$newZealand = new Menu(['name' => 'New Zealand']);
$newZealand->makeLastChildOf($countries);

$unitedStates = new Menu(['name' => 'United States of America']);
$unitedStates->makeLastChildOf($countries);

Usage

Configure an Eloquent Node

We make the assumption that you have read the Laravel 9 documentation on Eloquent models.

What do you need to do in addition? Not a whole lot:

Ensure that your class implements

Cartalyst\NestedSets\Nodes\NodeInterface

Ensure that your class uses the following trait

Cartalyst\NestedSets\Nodes\NodeTrait

Ensure you have the following columns in your database:

lft, rgt, tree (all integers)

Note: If you do not wish to use these names, you will need to setup your model a little bit (shown below).

An example of a basic Nested Sets Node:

<?php

use Illuminate\Database\Eloquent\Model;
use Cartalyst\NestedSets\Nodes\NodeTrait;
use Cartalyst\NestedSets\Nodes\NodeInterface;

class Category extends Model implements NodeInterface {

    use NodeTrait;

}

An example of a slightly more configured Nested Sets Node:

<?php

use Illuminate\Database\Eloquent\Model;
use Cartalyst\NestedSets\Nodes\NodeTrait;
use Cartalyst\NestedSets\Nodes\NodeInterface;

class Category extends Model implements NodeInterface {

    /**
     * The table associated with the model.
     *
     * @var string
     */
    protected $table = 'categories';

    /**
     * Array of reserved attributes used by the node. These attributes
     * cannot be set like normal attributes, they are reserved for
     * the node and nested set workers to use.
     *
     * @var array
     */
    protected $reservedAttributes = array(

        // The left column limit. "left" is a reserved word in SQL
        // databases so we default to "lft" for compatiblity.
        'left'  => 'lft',

        // The right column limit. "right" is a reserved word in SQL
        // databases so we default to "rgt" for compatiblity.
        'right' => 'rgt',

        // The tree that the node is on. This package supports multiple
        // trees within one database.
        'tree'  => 'tree',
    );

    /**
     * The worker class which the model uses.
     *
     * @var string
     */
    protected $worker = 'Cartalyst\NestedSets\Workers\IlluminateWorker';

}

That's it!

Basic Usage

A special rule to remember about using Eloquent models with Nested Sets is you probably do not want to be calling save() on a model to add it to the hierarchy. Calling save() will not automatically assign the node to any hierarchy in any tree.

A new concept to understand with Nested Sets is you insert, re-arrange nodes by placing them before or after another node (sibling) or as the first / last child of another node. In some other patterns, you may be used to setting a sort order for nodes. In Nested Sets, you set the sort order by placing a node relative to another node.

Making a Root Node

Making a node a root node (which starts a new tree in the database) is done by calling makeRoot(). This will automatically save the node in the database and setup the lft, rgt and tree properties:

<?php

use Illuminate\Database\Eloquent\Model;
use Cartalyst\NestedSets\Nodes\NodeTrait;
use Cartalyst\NestedSets\Nodes\NodeInterface;

class Menu extends Model implements NodeInterface {

    use NodeTrait;

    protected $table = 'menus';

}

// Make a new "Countries" root node
$countries = new Menu(['name' => 'Countries']);
$countries->makeRoot();

Make a Node a Child of Another Node

Leading off from our root node above, let's make a couple of child nodes. We have a choice to put the nodes as either the first or last child of the root node (Countries):

<?php

$australia = new Menu(['name' => 'Australia']);
$australia->makeLastChildOf($countries);

Nested Sets will ensure that any changes caused to the Countries record in the database are reflected in the $countries instance (the lft & rgt values are synchronized).

Let's make a couple more countries:

<?php

$newZealand = new Menu(['name' => 'New Zealand']);
$newZealand->makeLastChildOf($countries);

$unitedStates = new Menu(['name' => 'United States of America']);
$unitedStates->makeLastChildOf($countries);

As you can see, we now have three children nodes for the "Countries" tree:

1. Australia
2. New Zealand
3. United States of America

Let's add Argentina to our list of countries:

<?php

$argentina = new Menu(['name' => 'Argentina']);
$argentina->makeLastChildOf($countries);

Because we called makeLastChildOf() we now have the following list:

1. Australia
2. New Zealand
3. United States of America
4. Argentina

Let's call makeFirstChild() instead. This will ensure our new node gets put at the front of the list:

<?php

$argentina->makeFirstChildOf($countries);

We now have the following list of countries:

1. Argentina
2. Australia
3. New Zealand
4. United States of America

This is much better as it is sorted alphabetically.

Now, we've decided we want to broaden our menu listing to include England. This is where siblings come in;

Make a Node a Sibling of Another Node

Let's say you want to put a node in the hierarchy but do not want to make it the first or last child of a parent node.

Easy, just make it a sibling instead.

You can make a node the previous sibling (meaning it will be on the same left, but sorted one before) another node:

<?php

$newZealand = Menu::where('name', 'New Zealand')->first();

$england = new Menu(['name' => 'England']);
$england->makePreviousSiblingOf($newZealand);

Great! Now our list is:

1. Argentina
2. Australia
3. England
4. New Zealand
5. United States of America

You can also make a node the next sibling of another node:

<?php

$australia = Menu::where('name', 'Australia')->first();

$brazil = new Menu('name' => 'Brazil');
$brazil->makeNextSiblingOf($australia);

Note: It is important to note, while the $australia variable is updated, any other variables are not updated. You must call refresh() on those models instead, or query for them again.

Deleting a Node

When deleting a node, you need to consider any children it has. Let's assume we have the following hierarchical menu structure (of countries and their states):

1. Argentina
2. Australia
    1. New South Wales
    2. Victoria
3. England
4. New Zealand
5. United States of America
    1. California
    2. New York
    3. Washington

Note: As a safeguard, when deleting a node, Nested Sets will move it's orphaned children up to the same level as it to replace it.

For example, let's delete Australia using the delete() method

$australia->delete();

The updated list

1. Argentina
2. New South Wales
3. Victoria
4. England
5. New Zealand
6. United States of America
    1. California
    2. New York
    3. Washington

This is probably not what you want in your menu, a list of Australia's states at the same level as a country.

So, to overcome this, you need to call deleteWithChildren().

$australia->deleteWithChildren();

This will ensure the orphaned children are deleted:

1. Argentina
2. England
3. New Zealand
4. United States of America
    1. California
    2. New York
    3. Washington

Getting the Hierarchy Tree

To get the hierarchy tree we've been creating, you need to do the following:

<?php

$root = Menu::find(1);

// We need to find our children. We don't do this lazily because it can be
// advantageous to control when it happens. You may wish to provide a
// $depth limit to speed up queries even more.
$depth = 2; // This will limit to countries & states only for example
$root->findChildren($depth);

// We can now loop through our children
foreach ($root->getChildren() as $country)
{
    echo "<h3>{$country->name}</h3>";

    if (count($country->getChildren()))
    {
        echo "<p>{$country->name} has the following states registered with our system:</p>";

        echo "<ul>";

        foreach ($country->getChildren() as $state)
        {
            echo "<li>{$state->name}</li>";
        }

        echo "</ul>";
    }
}

The output from this would be (the markup below is tidied):

<h3>Argentina</h3>

<h3>England</h3>

<h3>New Zealand</h3>

<h3>United States of America</h3>

<p>United States of America has the following states registered with our system:</p>

<ul>
    <li>California</li>
    <li>New York</li>
    <li>Washington</li>
</ul>

Advanced Usage

In addition to creating, reading, updating and deleting records, there are a number of other useful things you can do with Nested Sets.

Retrieving All Root Nodes

Retrieving all root nodes is easy and is very similar to methods you may already be familiar with.

For our example, let's assume we have a Menu model, which can have any number of separate menus (trees) in it and each menu may have any given hierarchical structure of data.

Let's retrieve all root nodes (the node which holds each menu's structure):

<?php

$menus = Menu::allRoot();

echo '<h3>You have the following menus registered:</h3><ul>';

foreach ($menus as $menu)
{
    echo "<li>{$menu->name}</li>";
}

echo '</ul>';

The output of this might be:

<h3>You have the following menus registered:</h3>

<ul>
    <li>Main</li>
    <li>Sidebar</li>
    <li>Footer</li>
</ul>

You might have started to notice how you can begin buliding a menu-management system for your next application.

Retrieving All Nodes Without Children

Referred to as "leaf nodes" in the Nested Sets Model, you may find a need to find all nodes which do not have any children:

<?php

$leaf = Menu::allLeaf();

Alternatively, you may wish to see if a node has children when iterating through. An example of this could be if you wanted to display special output (such as an additional CSS class) if a node has no children:

<?php

if ($item->isLeaf())
{
    //
}

Getting the Path of a Node

You can get the path of a node quite easily in Nested Sets. The path will return an array of all the primary keys for all parent nodes up to the root item. An example of usage for this would be if you had an active menu item, $activeItem. You could build an "active path"; the path of menu items which lead to this item.

<?php

// In your controller
$activePath = $activeItem->getPath();

return View::make('foo', compact('activeItem', 'activePath'));

// In your view
if (in_array($item->getKey(), $activePath))
{
    echo 'class="active"';
}

Getting the Depth of a Node

Retrieving the depth of a node can be useful as well. You may wish to know how many parents the item has in the hierarchy tree:

<?php

// Outputs an integer, the item's depth,
// where 0 means the item has no parents,
// 1 means the item has 1 parent, 2 means
// the item's parent has 1 parent and so on.
echo $item->getDepth();

Getting the Depth of a Node Relative to Another Node

You can retrieve the depth of a node relative to another node extremely easily:

<?php

// You may wrap your own logic to find by a "slug"
// or other unique field, we will not go into detail
// on how to do that here.
$services        = Menu::find('footer-services');
$computerRepairs = Menu::find('footer-services-computer-repairs');

echo "Computer Repairs is {$computerRepairs->relativeDepth($services)} levels deeper than Services";

Mapping a Tree of Nodes (Mass-Assignment)

Because Nested Sets can involve a number of queries and API calls to build a hierarchy structure (through setting children & siblings), we have provided a convenient method which will match the supplied array of nodes (or simple arrays) and create a hierarchy tree from them.

It is intelligent enough to only create the nodes which do not exist, otherwise it will shuffle around or delete existing nodes accordingly.

Let's say we have the following menu on our website:

  • Home
  • About
  • Services
    • Computer Services
      • Computer Repairs
      • Virus Removal
    • Website Development
    • Graphic Design
  • Contact Us

This could be represented through the following dataset:

<?php

$tree = [
    ['id' => 1, 'name' => 'Home'],
    ['id' => 2, 'name' => 'About'],
    ['id' => 3, 'name' => 'Services', 'children' => [
        ['id' => 4, 'name' => 'Computer Services', 'children' => [
            ['id' => 5, 'name' => 'Computer Repairs'],
            ['id' => 6, 'name' => 'Virus Removal'],
        ]],
        ['id' => 7, 'name' => 'Website Development'],
        ['id' => 8, 'name' => 'Graphic Design'],
    ]],
    ['id' => 9, 'name' => 'Contact Us'],
];

// Map the tree to our database
$footer = Menu::find('footer');
$footer->maptree($tree);

Now, let's pretend we want to break down website development into our two favorite jobs - building Cartalyst websites and Laravel applications. Additionally let's pretend our graphic designer has moved to a new city and is no longer working with us. We will stop advertising that service now.

Let's adjust the array which we map:

<?php

$tree = [
    ['id' => 1, 'name' => 'Home'],
    ['id' => 2, 'name' => 'About'],
    ['id' => 3, 'name' => 'Services', 'children' => [
        ['id' => 4, 'name' => 'Computer Services', 'children' => [
            ['id' => 5, 'name' => 'Computer Repairs'],
            ['id' => 6, 'name' => 'Virus Removal'],
        ]],
        ['id' => 7, 'name' => 'Website Development', 'children' => [

            // Note how we are not providing a primary key here,
            // these items will be created
            ['name' => 'Cartalyst Websites'],
            ['name' => 'Laravel Applications'],
        ]],


        // Let's comment out Graphic Design, it will be removed.
        // ['id' => 8, 'name' => 'Graphic Design'],
    ]],
    ['id' => 9, 'name' => 'Contact Us'],
];

$footer = Menu::find('footer');
$footer->mapTree($tree);

We would now have the following menu:

  • Home
  • About
  • Services
    • Computer Services
      • Computer Repairs
      • Virus Removal
    • Website Development
      • Cartalyst Websites
      • Laravel Applications
  • Contact Us

Presenting a Node (Debugging / Outputting)

Sometimes, you may not wish to write your own custom logic for outputting your trees. Thankfully, the hard work has already been done for many custom operations. We call it the presenting - and it's dead simple to use.

There are currently four ways to present your nodes:

  1. Array (will return a set of nested arrays, much like what you pass to mapTree()).
  2. Unordered List
  3. Ordered List
  4. JSON

You may choose to present a node's children or include the node itself. The methods to call are presentChildrenAs() and presentAs() respectively.

Both methods take a second parameter, which is the name of the attribute to be presented. Alternatively, you may pass through a Closure which is called for every element the presenter iterates through, where you must return a string which is the value outputted for that node.

And last but not least, you can set a limit for how far you want to loop.

Let's grab our footer menu from the previous example:

$footer = Menu::find('footer');

// We will create an unordered list, limited to 1 level deep
// where the value of the 'name' property is outputted
echo $footer->presentChildrenAs('ol', 'name', 1);

The result of this would look something like:

<ol>
    <li>Home</li>
    <li>About</li>
    <li>Services</li>
    <li>Contact Us</li>
</ol>

let's say we want to build our navigation for our website without adding the complexity of loading views. Let's combine some of the knowledge we have learned to quickly scaffold up our website's navigation:

<?php

$footer = Menu::find('footer');

// We will present our items, providing a callback for
// each item so we can custom render it's output. We
// are limiting depth to two levels deep.
echo $footer->presentChildrenAs('ul', function($item)
{
    $output = '';

    // Create the start tag for our anchor
    $output .= '<a href="'.URL::to($item->uri).'"';
    if ($item->isLeaf()) $output .= ' class="no-children"';
    $output .= '>';

    // Output our name
    $output .= $item->name;

    // Close our anchor tag
    $output .= '</a>';

    return $output;
}, 2);

The result of this would be:

<ul>
    <li>
        <a href="http://www.example.com/" class="no-children">Home</a>
    </li>
    <li>
        <a href="http://www.example.com/about" class="no-children">About</a>
    </li>
    <li>
        <a href="http://www.example.com/services">Services</a>
        <ul>
            <li>
                <a href="http://www.example.com/services/computer-services">Computer Services</a>
            </li>
            <li>
                <a href="http://www.example.com/services/website development">Website Development</a>
            </li>
        </ul>
    </li>
    <li>
        <a href="http://www.example.com/contact-us" class="no-children">Contact Us</a>
    </li>
</ul>

You could even get fancy and pass through something like this:

echo $footer->presentChildrenAs('ul', function($item)
{
    return View::make('navigation/item', compact('item'));
}, 2);

This would not be recommended on large data sets as you will notice significant performance issues due to your computer's hard-drive I/O. A better solution would be to loop through children manually and present a new view per depth of children, not for each child. This is the best mix of separation of concerns (loading a view for view-related data) and speed.

You wont find fancy lifestyle graphics and marketing bravado here. Just cold... hard... code...

Code Well, Rock On!
Processing Payment...