Improved BetterNestedSet Plugin

First the database migration used in all examples (using Rails 2.0 sexy migrations):

class CreateClassifications < ActiveRecord::Migration
  def self.up
    create_table :classifications do |t|
      t.integer :parent_id
      t.integer :lft
      t.integer :rgt
      t.string  :name
      t.text    :description
      t.timestamps
    end
  end

  def self.down
    drop_table :classifications
  end
end

Please note that the left and right columns are named in such a way that they will not conflict with database reserved words commonly used in join statements.

Then the code:

class NestedSet < ActiveRecord::Base
  acts_as_nested_set

  def self.all_parents
    self.roots.map do |root| 
      (root.full_set.collect {|child| child if child.children.size > 0}).compact.flatten
    end
  end

  def self.all_leaves
    self.roots.map do |root| 
      (root.full_set.collect {|child| child if child.children.size == 0}).compact.flatten
    end
  end

end

This code works - but works slowly and yields horrific SQL. The reason it's slow and horrific is because you need to hit each node in the tree to test for it's number of children. This is less than ideal especially if you need to do this regularly (or on a tree with hundreds of nodes) - which leads us to the next iteration:

class NestedSet < ActiveRecord::Base
  acts_as_nested_set

  def self.all_parents
    self.find(:all, :conditions => "rgt <> lft + 1")
  end

  def self.all_leaves
    self.find(:all, :conditions => "rgt = lft + 1")
  end

end

This works much better and is far more efficient. Each call to the class method makes a single query to the database. The reason the we can do this is because of the way nested sets work. A good explaination of this can be found in the BetterNestedSet README:

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  | data
    1 |           |    1 |   14 | root
    2 |         1 |    2 |    7 | Child 1
    3 |         2 |    3 |    4 | Child 1.1
    4 |         2 |    5 |    6 | Child 1.2
    5 |         1 |    8 |   13 | Child 2
    6 |         5 |    9 |   10 | Child 2.1
    7 |         5 |   11 |   12 | Child 2.2

You can also check out additional nested set explanation in an article titled "A Nested Set Implementation..." (paying special attention to the illustrations in section #3).

Going back to our example, there's one more thing we can to do make this one step better - move our methods into the plugin implementation. This makes sense as our class methods are not directly related to our application logic and pertain mainly to nested set behavior.

You can add a version of our methods to the nested set plugin by adding to the ClassMethods module in better_nested_set.rb in the lib folder of the BetterNestedSet plugin with the following:

def parents
  acts_as_nested_set_options[:class].find(:all, :conditions => "(#{acts_as_nested_set_options[:right_column]} <> #{acts_as_nested_set_options[:left_column]} + 1)", :order => "#{acts_as_nested_set_options[:left_column]}")
end

def leaves
  acts_as_nested_set_options[:class].find(:all, :conditions => "(#{acts_as_nested_set_options[:right_column]} = #{acts_as_nested_set_options[:left_column]} + 1)", :order => "#{acts_as_nested_set_options[:left_column]}")
end

Or if you're savvy you can just apply the patch I created that includes these methods along with documentation and tests:

  • download the patch
  • move the patch to the root of your BetterNestedSet plugin
  • patch -p0 < leaves_and_parents_class_methods.patch

I've also added the patch as an enhancement to the BetterNestedSet trac.

On a recent project when I was using the BetterNestedSet plugin to manage a large hierarchal set of data, I encountered a problem that required me to find all of the items in a nested set that had children and those that didn't. In nested set terms I wanted: all 'parent' nodes and all 'leaf' nodes that exist within the 'tree'.

If you want to do this through the current BetterNestedSet interface you might be tempted to do something like this: