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:
