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 runningcomposer 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 callrefresh()
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
- Computer Services
- 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
- Computer Services
- 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:
- Array (will return a set of nested arrays, much like what you pass to
mapTree()
). - Unordered List
- Ordered List
- 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.