baum

Baum

Baum is an implementation of the Nested Set pattern for Laravel 5's Eloquent ORM.

For Laravel 4.2.x compatibility, check the 1.0.x branch branch or use the latest 1.0.x tagged release.

Documentation

• About Nested Sets
• The theory behind, a TL;DR version
• Installation
• Getting started
• Usage
• Further information
• Contributing

About Nested Sets

A nested set is a smart way to implement an ordered tree that allows for fast, non-recursive queries. For example, you can fetch all descendants of a node in a single query, no matter how deep the tree. The drawback is that insertions/moves/deletes require complex SQL, but that is handled behind the curtains by this package!

Nested sets are appropriate for ordered trees (e.g. menus, commercial categories) and big trees that must be queried efficiently (e.g. threaded posts).

See the wikipedia entry for nested sets for more info. Also, this is a good introductory tutorial: http://www.evanpetersen.com/item/nested-sets.html

The theory behind, a TL;DR version

An easy way to visualize how a nested set works is to think of a parent entity surrounding all of its children, and its parent surrounding it, etc. So this tree:

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

Could be visualized like this:

 ___________________________________________________________________
|  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 then might look like this:

id | parent_id | lft  | rgt  | depth | data
 1 |           |    1 |   14 |     0 | root
 2 |         1 |    2 |    7 |     1 | Child 1
 3 |         2 |    3 |    4 |     2 | Child 1.1
 4 |         2 |    5 |    6 |     2 | Child 1.2
 5 |         1 |    8 |   13 |     1 | Child 2
 6 |         5 |    9 |   10 |     2 | Child 2.1
 7 |         5 |   11 |   12 |     2 | Child 2.2

To get all children of a parent node, you

SELECT * WHERE lft IS BETWEEN parent.lft AND parent.rgt

To get the number of children, it's

(right - left - 1)/2

To get a node and all its ancestors going back to the root, you

SELECT * WHERE node.lft IS BETWEEN lft AND rgt

As you can see, queries that would be recursive and prohibitively slow on ordinary trees are suddenly quite fast. Nifty, isn't it?

Installation

Baum works with Laravel 5 onwards. You can add it to your composer.json file with:

"baum/baum": "~1.1"

Run composer install to install it.

As with most Laravel 5 packages you'll then need to register the Baum service provider. To do that, head over your config/app.php file and add the following line into the providers array:

'Baum\Providers\BaumServiceProvider',

Getting started

After the package is correctly installed the easiest way to get started is to run the provided generator:

php artisan baum:install MODEL

Replace model by the class name you plan to use for your Nested Set model.

The generator will install a migration and a model file into your application configured to work with the Nested Set behaviour provided by Baum. You SHOULD take a look at those files, as each of them describes how they can be customized.

Next, you would probably run artisan migrate to apply the migration.

Model configuration

In order to work with Baum, you must ensure that your model class extends Baum\Node.

This is the easiest it can get:

class Category extends Baum\Node {

}

This is a slightly more complex example where we have the column names customized:

class Dictionary extends Baum\Node {

  protected $table = 'dictionary';

  // 'parent_id' column name
  protected $parentColumn = 'parent_id';

  // 'lft' column name
  protected $leftColumn = 'lidx';

  // 'rgt' column name
  protected $rightColumn = 'ridx';

  // 'depth' column name
  protected $depthColumn = 'nesting';

  // guard attributes from mass-assignment
  protected $guarded = array('id', 'parent_id', 'lidx', 'ridx', 'nesting');

}

Remember that, obviously, the column names must match those in the database table.

Migration configuration

You must ensure that the database table that supports your Baum models has the following columns:

• parent_id: a reference to the parent (int)
• lft: left index bound (int)
• rgt: right index bound (int)
• depth: depth or nesting level (int)

Here is a sample migration file:

class Category extends Migration {

  public function up() {
    Schema::create('categories', function(Blueprint $table) {
      $table->increments('id');

      $table->integer('parent_id')->nullable();
      $table->integer('lft')->nullable();
      $table->integer('rgt')->nullable();
      $table->integer('depth')->nullable();

      $table->string('name', 255);

      $table->timestamps();
    });
  }

  public function down() {
    Schema::drop('categories');
  }

}

You may freely modify the column names, provided you change them both in the migration and the model.

Usage

After you've configured your model and run the migration, you are now ready to use Baum with your model. Below are some examples.

• Creating a root node
• Inserting nodes
• Deleting nodes
• Getting the nesting level of a node
• Moving nodes around
• Asking questions to your nodes
• Relations
• Root and Leaf scopes
• Accessing the ancestry/descendancy chain
• Limiting levels of children returned
• Custom sorting column
• Dumping the hierarchy tree
• Model events: moving and moved
• Scope support
• Validation
• Tree rebuilding
• Soft deletes
• Seeding/Mass assignment
• Misc/Utility functions

Creating a root node

By default, all nodes are created as roots:

$root = Category::create(['name' => 'Root category']);

Alternatively, you may find yourself in the need of converting an existing node into a root node:

$node->makeRoot();

You may also nullify it's parent_id column to accomplish the same behaviour:

// This works the same as makeRoot()
$node->parent_id = null;
$node->save();

Inserting nodes

// Directly with a relation
$child1 = $root->children()->create(['name' => 'Child 1']);

// with the `makeChildOf` method
$child2 = Category::create(['name' => 'Child 2']);
$child2->makeChildOf($root);

Deleting nodes

$child1->delete();

Descendants of deleted nodes will also be deleted and all the lft and rgt bound will be recalculated. Pleases note that, for now, deleting and deleted model events for the descendants will not be fired.

Getting the nesting level of a node

The getLevel() method will return current nesting level, or depth, of a node.

$node->getLevel() // 0 when root

Moving nodes around

Baum provides several methods for moving nodes around:

• moveLeft(): Find the left sibling and move to the left of it.
• moveRight(): Find the right sibling and move to the right of it.
• moveToLeftOf($otherNode): Move to the node to the left of ...
• moveToRightOf($otherNode): Move to the node to the right of ...
• makeNextSiblingOf($otherNode): Alias for moveToRightOf.
• makeSiblingOf($otherNode): Alias for makeNextSiblingOf.
• makePreviousSiblingOf($otherNode): Alias for moveToLeftOf.
• makeChildOf($otherNode): Make the node a child of ...
• makeFirstChildOf($otherNode): Make the node the first child of ...
• makeLastChildOf($otherNode): Alias for makeChildOf.
• makeRoot(): Make current node a root node.

For example:

$root = Creatures::create(['name' => 'The Root of All Evil']);

$dragons = Creatures::create(['name' => 'Here Be Dragons']);
$dragons->makeChildOf($root);

$monsters = new Creatures(['name' => 'Horrible Monsters']);
$monsters->save();

$monsters->makeSiblingOf($dragons);

$demons = Creatures::where('name', '=', 'demons')->first();
$demons->moveToLeftOf($dragons);

Asking questions to your nodes

You can ask some questions to your Baum nodes:

• isRoot(): Returns true if this is a root node.
• isLeaf(): Returns true if this is a leaf node (end of a branch).
• isChild(): Returns true if this is a child node.
• isDescendantOf($other): Returns true if node is a descendant of the other.
• isSelfOrDescendantOf($other): Returns true if node is self or a descendant.
• isAncestorOf($other): Returns true if node is an ancestor of the other.
• isSelfOrAncestorOf($other): Returns true if node is self or an ancestor.
• equals($node): current node instance equals the other.
• insideSubtree($node): Checks whether the given node is inside the subtree defined by the left and right indices.
• inSameScope($node): Returns true if the given node is in the same scope as the current one. That is, if every column in the scoped property has the same value in both nodes.

Using the nodes from the previous example:

$demons->isRoot(); // => false

$demons->isDescendantOf($root) // => true

Relations

Baum provides two self-referential Eloquent relations for your nodes: parent and children.

$parent = $node->parent()->get();

$children = $node->children()->get();

Root and Leaf scopes

Baum provides some very basic query scopes for accessing the root and leaf nodes:

// Query scope which targets all root nodes
Category::roots()

// All leaf nodes (nodes at the end of a branch)
Category:allLeaves()

You may also be interested in only the first root:

$firstRootNode = Category::root();

Accessing the ancestry/descendancy chain

There are several methods which Baum offers to access the ancestry/descendancy chain of a node in the Nested Set tree. The main thing to keep in mind is that they are provided in two ways:

First as query scopes, returning an Illuminate\Database\Eloquent\Builder instance to continue to query further. To get actual results from these, remember to call get() or first().

• ancestorsAndSelf(): Targets all the ancestor chain nodes including the current one.
• ancestors(): Query the ancestor chain nodes excluding the current one.
• siblingsAndSelf(): Instance scope which targets all children of the parent, including self.
• siblings(): Instance sco