Ruby on Rails
BetterNestedSet (Version #35)

This Rails plugin is an extension of ActsAsNestedSet that adds some enhancements in response to confusion about the use of ActsAsNestedSet.

You might use this plugin to model a threaded discussion board. The underlying implementation uses Modified Preorder Tree Traversal for efficiency and scalability.

Homepage
API docs

Table Schema

create table tree_item (
  id int(11) unsigned not null auto_increment,
  parent_id int(11),
  lft int(11),
  rgt int(11),
  // add your custom fields here
  primary key (id)
);

...or as a migration…

def self.up
  create_table :tree_item, :force => true do |t|
    t.column :parent_id, :int
    t.column :lft, :int
    t.column :rgt, :int
    // add your custom fields here
  end
end

def self.down
  drop_table :tree_item
end

Usage

As with ActsAsNestedSet, use this line in your model:

class TreeItem < ActiveRecord::Base
  acts_as_nested_set
end

The root of the tree is the item(s) where parent_id is null. You can have multiple roots (for threads in mails lists, or base items of menus). The first item always has a left value of 1.

New items are added to the end of the tree: new_left = max(existing_right). So you need one more operation than with acts_as_tree to add an item:

# adds a new item at the "end" of the tree, i.e. with child.left = max(tree.right)+1
child = MyClass.new(:name => "child1")
# save to populate left and right
child.save
# now move the item to its right place
child.move_to_child_of my_item
add_child is deprecated and will be removed soon.

New methods

  • root – root item of the tree (the one that has a nil parent; should have left_column = 1 too)
  • roots – root items, in case of multiple roots (the ones that have a nil parent)
  • level – number indicating the level (a root being level 0)
  • ancestors – array of all parents, with root as first item
  • self_and_ancestors – array of all parents and self, with root as first item
  • siblings – array of all direct children of the node’s parent (i.e. having same parent and level)
  • self_and_siblings – array of itself and all siblings
  • parent – the parent node, if it exists
  • children_count – count of all immediate children
  • children – array of immediate children
  • all_children – array of all children and nested children (all descendants)
  • full_set – array of itself and all children and nested children (this plus descendants)

Use these to manipulate the tree (pass them an id or an object):

  • move_to_left_of
  • move_to_right_of
  • move_to_child_of

These should not be useful, except if you want to write direct SQL:

  • left_col_name – name of the left column passed on the declaration line
  • right_col_name – name of the right column passed on the declaration line
  • parent_col_name – name of the parent column passed on the declaration line

Having more than one tree/root in the table

If you wish to store multiple trees (and therefore multiple roots) in a single db table, you must use the :scope label to identify the column whose value differentiates them.

class ThreadedDiscussion < ActiveRecord::Base
  has_many :threaded_discussion_post
end

class ThreadedDiscussionPost < ActiveRecord::Base
  acts_as_nested_set :scope => :discussion
  belongs_to :threaded_discussion
end

In this example, there exists one row in the threaded_discussion table for each discussion (perhaps on a blog post, or a forum topic). The threaded_discussion_post table has a foreign key discussion_id. The :scope label specified that the discussion_id column is used to differentiate trees.

Another example, showing use of root_id for scope

You don’t need to use root_id as your scope, but it is convenient.

id | root_id | parent_id |lft|rgt| name
---------------------------------------------------------
 1 |       1 |           | 1 | 2 | ruby
 2 |       2 |           | 1 | 2 | rails
 3 |       3 |           | 1 | 6 | computers
 4 |       3 |         3 | 2 | 3 | apple
 5 |       3 |         3 | 4 | 5 | dell
 6 |       6 |           | 1 | 8 | rails plug-ins
 7 |       6 |         6 | 2 | 3 | better_nested_set
 8 |       8 |           | 1 | 2 | frameworks
 9 |       6 |         6 | 4 | 5 | restful_authentication
10 |       6 |         6 | 6 | 7 | authorization
11 |      11 |           | 1 | 2 | databases

For this table, you’d use the declaration:

acts_as_nested_set :scope => :root_id

Note that if the column being used is configured as a foreign key recognised by ActiveRecord, then you can drop the _id suffix, leaving :scope => :root (this method is used in the first example given).

Displaying a tree

You can use style="margin-left:<%= item.level %>em;" in your view to have items indented according to their level. Displaying vertical lines like in a mail thread is harder.

Installation

script/plugin source svn://rubyforge.org/var/svn/betternestedset
script/plugin install betternestedset

Migrating from acts_as_tree

In reference to migrating from acts_as_tree Krishna Dole said, “If you have multiple trees in your table, it is a little more complicated. You first need to give each tree scope (add a tree_id column) and then run the above method on a member of each tree.”

Not completely understanding that statement, I set out to implement it in a migration. Here is my result which appears to work. In this example, I am using a model named Categories:

class ConvertCategoriesToNestedSet < ActiveRecord::Migration
  def self.up
    add_column :categories, :lft, :integer
    add_column :categories, :rgt, :integer
    add_column :categories, :root_id, :integer

    # Convert existing tree to nested set with scope
    Category.renumber_all
    Category.roots.each do |r|
      r.all_children.each do |c|
        c.update_attribute(:root_id, r.id)
      end
      r.update_attribute(:root_id, r.id)
    end
  end

  def self.down
    remove_column :categories, :lft
    remove_column :categories, :rgt
    remove_column :categories, :root_id
  end
end

Future

From Krishna Dole on betternestedset-talk@rubyforge.org:

...there has been talk on the rails list of writing a tree plugin that uses materialized paths for improved write performance, but that hasn’t happened yet. The good news is that the materialized path API should be fully compatible with BetterNestedSet, so you can swap one for the other to fit your needs.

License

BetterNestedSet is released under the MIT license.

Questions

This is so much better than the built-in acts_as_nested_set – why not add it to core Rails?

How do I display the tree without having to request db for each node in the tree?

Answer: caching

Comments

This plugin is fantastic! Great work!

It’s silly that you can’t assign parent_id and use an after_create method to automatically move_to_child_of parent_id. Removing those module_evaled method definitions allows you to do this.

Nice, but…
Is it only me or are some examples missing? Especially for the functions recurse_result_set, result_to_array and result_to_xml, what kind of Block to give?
Whatever i try i get some error about calling protected select or something like this.
I’m new to ruby and this recursive block stuff is kinda difficult for me. Somebody care to give an example? Thanks in advance, Chris

To add acts_as_list methods see http://www.vaporbase.com/postings/List_methods_for_nested_sets

This Rails plugin is an extension of ActsAsNestedSet that adds some enhancements in response to confusion about the use of ActsAsNestedSet.

You might use this plugin to model a threaded discussion board. The underlying implementation uses Modified Preorder Tree Traversal for efficiency and scalability.

Homepage
API docs

Table Schema

create table tree_item (
  id int(11) unsigned not null auto_increment,
  parent_id int(11),
  lft int(11),
  rgt int(11),
  // add your custom fields here
  primary key (id)
);

...or as a migration…

def self.up
  create_table :tree_item, :force => true do |t|
    t.column :parent_id, :int
    t.column :lft, :int
    t.column :rgt, :int
    // add your custom fields here
  end
end

def self.down
  drop_table :tree_item
end

Usage

As with ActsAsNestedSet, use this line in your model:

class TreeItem < ActiveRecord::Base
  acts_as_nested_set
end

The root of the tree is the item(s) where parent_id is null. You can have multiple roots (for threads in mails lists, or base items of menus). The first item always has a left value of 1.

New items are added to the end of the tree: new_left = max(existing_right). So you need one more operation than with acts_as_tree to add an item:

# adds a new item at the "end" of the tree, i.e. with child.left = max(tree.right)+1
child = MyClass.new(:name => "child1")
# save to populate left and right
child.save
# now move the item to its right place
child.move_to_child_of my_item
add_child is deprecated and will be removed soon.

New methods

  • root – root item of the tree (the one that has a nil parent; should have left_column = 1 too)
  • roots – root items, in case of multiple roots (the ones that have a nil parent)
  • level – number indicating the level (a root being level 0)
  • ancestors – array of all parents, with root as first item
  • self_and_ancestors – array of all parents and self, with root as first item
  • siblings – array of all direct children of the node’s parent (i.e. having same parent and level)
  • self_and_siblings – array of itself and all siblings
  • parent – the parent node, if it exists
  • children_count – count of all immediate children
  • children – array of immediate children
  • all_children – array of all children and nested children (all descendants)
  • full_set – array of itself and all children and nested children (this plus descendants)

Use these to manipulate the tree (pass them an id or an object):

  • move_to_left_of
  • move_to_right_of
  • move_to_child_of

These should not be useful, except if you want to write direct SQL:

  • left_col_name – name of the left column passed on the declaration line
  • right_col_name – name of the right column passed on the declaration line
  • parent_col_name – name of the parent column passed on the declaration line

Having more than one tree/root in the table

If you wish to store multiple trees (and therefore multiple roots) in a single db table, you must use the :scope label to identify the column whose value differentiates them.

class ThreadedDiscussion < ActiveRecord::Base
  has_many :threaded_discussion_post
end

class ThreadedDiscussionPost < ActiveRecord::Base
  acts_as_nested_set :scope => :discussion
  belongs_to :threaded_discussion
end

In this example, there exists one row in the threaded_discussion table for each discussion (perhaps on a blog post, or a forum topic). The threaded_discussion_post table has a foreign key discussion_id. The :scope label specified that the discussion_id column is used to differentiate trees.

Another example, showing use of root_id for scope

You don’t need to use root_id as your scope, but it is convenient.

id | root_id | parent_id |lft|rgt| name
---------------------------------------------------------
 1 |       1 |           | 1 | 2 | ruby
 2 |       2 |           | 1 | 2 | rails
 3 |       3 |           | 1 | 6 | computers
 4 |       3 |         3 | 2 | 3 | apple
 5 |       3 |         3 | 4 | 5 | dell
 6 |       6 |           | 1 | 8 | rails plug-ins
 7 |       6 |         6 | 2 | 3 | better_nested_set
 8 |       8 |           | 1 | 2 | frameworks
 9 |       6 |         6 | 4 | 5 | restful_authentication
10 |       6 |         6 | 6 | 7 | authorization
11 |      11 |           | 1 | 2 | databases

For this table, you’d use the declaration:

acts_as_nested_set :scope => :root_id

Note that if the column being used is configured as a foreign key recognised by ActiveRecord, then you can drop the _id suffix, leaving :scope => :root (this method is used in the first example given).

Displaying a tree

You can use style="margin-left:<%= item.level %>em;" in your view to have items indented according to their level. Displaying vertical lines like in a mail thread is harder.

Installation

script/plugin source svn://rubyforge.org/var/svn/betternestedset
script/plugin install betternestedset

Migrating from acts_as_tree

In reference to migrating from acts_as_tree Krishna Dole said, “If you have multiple trees in your table, it is a little more complicated. You first need to give each tree scope (add a tree_id column) and then run the above method on a member of each tree.”

Not completely understanding that statement, I set out to implement it in a migration. Here is my result which appears to work. In this example, I am using a model named Categories:

class ConvertCategoriesToNestedSet < ActiveRecord::Migration
  def self.up
    add_column :categories, :lft, :integer
    add_column :categories, :rgt, :integer
    add_column :categories, :root_id, :integer

    # Convert existing tree to nested set with scope
    Category.renumber_all
    Category.roots.each do |r|
      r.all_children.each do |c|
        c.update_attribute(:root_id, r.id)
      end
      r.update_attribute(:root_id, r.id)
    end
  end

  def self.down
    remove_column :categories, :lft
    remove_column :categories, :rgt
    remove_column :categories, :root_id
  end
end

Future

From Krishna Dole on betternestedset-talk@rubyforge.org:

...there has been talk on the rails list of writing a tree plugin that uses materialized paths for improved write performance, but that hasn’t happened yet. The good news is that the materialized path API should be fully compatible with BetterNestedSet, so you can swap one for the other to fit your needs.

License

BetterNestedSet is released under the MIT license.

Questions

This is so much better than the built-in acts_as_nested_set – why not add it to core Rails?

How do I display the tree without having to request db for each node in the tree?

Answer: caching

Comments

This plugin is fantastic! Great work!

It’s silly that you can’t assign parent_id and use an after_create method to automatically move_to_child_of parent_id. Removing those module_evaled method definitions allows you to do this.

Nice, but…
Is it only me or are some examples missing? Especially for the functions recurse_result_set, result_to_array and result_to_xml, what kind of Block to give?
Whatever i try i get some error about calling protected select or something like this.
I’m new to ruby and this recursive block stuff is kinda difficult for me. Somebody care to give an example? Thanks in advance, Chris

To add acts_as_list methods see http://www.vaporbase.com/postings/List_methods_for_nested_sets

Created on March 22, 2008 13:01 by Anonymous Coward (88.76.86.205)
Rollback | Forward in time (1 more) | Back in time (34 more)