http://opensource.symetrie.com/svn/better_nested_set/trunk/README

This plugin provides an enhanced acts_as_nested_set mixin for ActiveRecord, the object-db mapping layer of the framework RubyOnRails. The original nested set feature seems to be quite old and missed some necessary functionalities.

Provides Nested Set functionality. Nested Set is a smart way to implement an ordered tree, with the added feature that you can select the children and all of their descendants with a single query.

Nested sets are appropriate each time you want either an ordered tree (menus, commercial categories) or an efficient way of querying big trees (threaded posts).

== Small nested set theory reminder

Instead of picturing a leaf node structure with children pointing back to their parent, the best way to imagine how this works is to think of the parent entity surrounding all of its children, and its parent surrounding it, etc. Assuming that they are lined up horizontally, we store the left and right boundries in the database.

Imagine:

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

If my cirlces in circles description didn't make sense, check out this sweet ASCII art:

    ___________________________________________________________________
   |  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 boundries. The table then might look like this:

   id | parent_is | left | right | 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

So, to get all children of an entry 'parent', you

    SELECT * WHERE left IS BETWEEN parent.left AND parent.right

To get the count, it's (right - left - 1)/2, etc. To get the direct parent, it falls back to using the parent_id field. There are instance methods for all of these.

[edit] API

Methods names are aligned on Tree's ones as much as possible, to make replacement from one by another easier, except for the creation:

in acts_as_tree:

  item.children.create(:name => "child1")

in acts_as_nested_set:

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

You can use:

• move_to_child_of
• move_to_right_of
• move_to_left_of

and pass them an id or an object.

Other methods added by this mixin are:

• 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
• siblings - array of all siblings, that are the items sharing the same parent and level
• self_and_siblings - array of itself and all siblings
• children_count - count of all immediate children
• children - array of all immediate childrens
• all_children - array of all children and nested children
• full_set - array of itself and all children and nested children

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

[edit] Dissection: move_to_child_of()

vendor/plugins/better_nested_set/lib/better_nested_set.rb

        def move_to_child_of(node)
            self.move_to node, :child
        end

        def move_to(target, position)
          ...

          # compute new left/right for self
          if position == :child
            if target_left < cur_left
              new_left  = target_left + 1
              new_right = target_left + extent
            else
              new_left  = target_left - extent + 1
              new_right = target_left
            end

target is the node that you want to become the new parent of self.

Note that self will become the left-most node of target (new_left = target_left + 1).

I would have preferred that it become the right-most node of target (new_right = target_right - 1), or at least to have the option as to which side it should be inserted on, but currently I don't yet have the confidence to make that change.

[edit] Questions

[edit] Has there been any effort to get this included in core Rails?

If it's better than the core ActsAsNestedSet, then this should replace it and become the new ActsAsNestedSet?

[edit] Has anyone documented the exact differences between ActsAsNestedSet and BetterNestedSet?

And if so, have they tracked any changes...? (Or do I have to do that here...?)

For instance, perhaps Core has added all the features that BetterNestedSet has, rendering BetterNestedSet no longer useful...?

[edit] [ActiveRecord / Single table inheritance (category)] and trees

[edit] Bugs

http://dev.rubyonrails.org/ticket/7775

1. 7775 (Derived class types aren't kept when using STI for acts_as_tree) - Rails Trac - Trac

When you create a base class with the acts_as_tree association in it, the class type isn't kept with the children.

class Shape < ActiveRecord::Base
    acts_as_tree
end

class Circle < Shape end

circles = Circle.create!
circles.children.create!

puts circles.class
circles.children.each {|c| puts c.class}

The first will print 'Circle' and the children will print 'Shape'. In my opinion, when a child is created it should look to it's parent to see what it's type should be. Therefore, all nodes in the tree are of the same type.

[edit] Introduction

Let's assume that we have an acts_as_tree model called MenuItem stored in table menu_items and we want to convert it into acts_as_nested_set (I'm actually using BetterNestedSet in this example).

I don't think this migration is possible (easily) without having two models (and thus two tables) -- one with acts_as_tree that we read from and one with acts_as_nested_set that we insert into. I can't imagine trying to transform the data into a nested set by simply doing updates on a single table. It might be possible, but it would require rewriting a lot of the logic for dealing with these two different data structures -- better just to use the code we already have for reading and manipulating them!

Once we've migrated the data to the new table, we can drop the old table and rename the new table to whatever name the old table had.

[edit] Details

class MenuItem < ActiveRecord::Base
  acts_as_list :scope => :parent_id
  acts_as_tree :order => :position

  def preorder_traverse(prev_return_value = nil, *args, &visitor)
    cur_return_value = yield self, prev_return_value, *args
    children.each do |item|
      item.preorder_traverse(cur_return_value, *args, &visitor)
    end
  end
  def render_as_text
    preorder_traverse &render_as_text_proc
  end
  def render_as_text_proc
    lambda { |node, *args|
      puts '  '*node.level + "(##{node.id}; #{node.position})" + '. ' +
        "#{node.display_name.to_s.gsub(/./,'*')}" +
        "#{node.name.to_s}"
    }
  end
  def level(i = 0)
    parent ? parent.level(i+1) : i
  end
end

class NestedSetMenuItem < ActiveRecord::Base
  acts_as_nested_set

  def preorder_traverse(prev_return_value = nil, *args, &visitor)
    cur_return_value = yield self, prev_return_value, *args
    children.each do |item|
      item.preorder_traverse(cur_return_value, *args, &visitor)
    end
  end
  def render_as_text
    preorder_traverse &render_as_text_proc
  end
  def render_as_text_proc
    lambda { |node, *args|
      puts '  '*node.level + "(##{node.id}; #{node.lft}-#{node.rgt})" + '. ' +
        "#{node.display_name.to_s.gsub(/./,'*')}" +
        "#{node.name.to_s}"
    }
  end
end

class MigrateTreeToNestedSet < ActiveRecord::Migration
  def self.up
    # Apparently we can't do anything with the table (like add indexes to a column or insert into the table) until we commit it
    # (at least in sqlite3) -- that's why this is in >=2 transactions instead of 1.
    MenuItem.transaction do

      # Create the new table for BetterNestedSet
      create_table "nested_set_menu_items", :force => true do |t|
        t.column :type,   :text                  # For single-table inheritance
        t.column :name,   :text                  # To uniquely identify a menu item or tree
        t.column :display_name,   :text
        t.column :parent_id,      :integer       # For BetterNestedSet
        t.column :lft,            :integer       # For BetterNestedSet
        t.column :rgt,            :integer       # For BetterNestedSet

        t.column :created_at,     :datetime
        t.column :updated_at,     :datetime
      end
    end
    MenuItem.transaction do
      add_index(:nested_set_menu_items, :parent_id)
      add_index(:nested_set_menu_items, :lft)
      add_index(:nested_set_menu_items, :rgt)
      add_index(:nested_set_menu_items, :name)
    end

    MenuItem.transaction do
      # Migrate the data over to the new table

      tree_root     = MenuItem.find_by_name('Root')
      tree_root.preorder_traverse do |tree_item, nested_set_root|
        # Create a new node in the new nested set (neste_set_item) identical to the old node from the tree (tree_item) and
        # make it a child of nested_set_root (unless this is the root node).

        nested_set_item = NestedSetMenuItem.create!(
          :name => tree_item.name,
          :display_name => tree_item.display_name
        )

        if nested_set_root
          nested_set_root.add_child(nested_set_item)
          puts "Added #{nested_set_item.display_name} to #{nested_set_root.display_name}"
        else
          puts "Added #{nested_set_item.display_name} as root"
        end

        nested_set_item
      end

      # Proof that the trees look the same before and after the migration.
      tree_root.render_as_text
      puts '------------------'
      nested_set_root = NestedSetMenuItem.find_by_name('Root')
      nested_set_root.render_as_text

      drop_table 'menu_items'
      rename_table 'nested_set_menu_items', 'menu_items'
    end
  end

  def self.down
    raise IrreversibleMigration
  end
end

== MigrateTreeToNestedSet: migrating ==========================================
-- add_index(:nested_set_menu_items, :parent_id)
   -> 0.0031s
-- add_index(:nested_set_menu_items, :lft)
   -> 0.0014s
-- add_index(:nested_set_menu_items, :rgt)
   -> 0.0014s
-- add_index(:nested_set_menu_items, :name)
   -> 0.0014s
(#1; 1). **************
  (#2; 2). **********************
    (#41; 4). *******************
      (#20; 4). **************************
        (#32; 4). **************
          (#37; 4). ***************************
            (#42; 4). ****************
            (#44; 4). ***********
            (#45; 4). ********
          (#38; 4). ********************
          (#43; 4). ******************
        (#33; 4). *********************
          (#39; 4). **********
          (#40; 4). **********
        (#34; 4). ******************
      (#24; 4). *****
        (#35; 4). ******
        (#36; 4). ******
  (#3; 2). *****
    (#9; 4). ********
      (#18; 4). *************
  (#19; 4). *********
    (#30; 4). ************
      (#46; 4). *******
      (#47; 4). *********
      (#48; 4). ****************
    (#31; 4). *************
      (#49; 4). *********
      (#50; 4). *********
      (#51; 4). ************
      (#52; 4). **********
      (#53; 4). ***********
------------------
(#1; 1-64). **************
  (#2; 2-35). **********************
    (#3; 3-34). *******************
      (#4; 4-27). **************************
        (#5; 5-18). **************
          (#6; 6-13). ***************************
            (#7; 7-8). ****************
            (#8; 9-10). ***********
            (#9; 11-12). ********
          (#10; 14-15). ********************
          (#11; 16-17). ******************
        (#12; 19-24). *********************
          (#13; 20-21). **********
          (#14; 22-23). **********
        (#15; 25-26). ******************
      (#16; 28-33). *****
        (#17; 29-30). ******
        (#18; 31-32). ******
  (#19; 36-41). *****
    (#20; 37-40). ********
      (#21; 38-39). *************
  (#22; 42-63). *********
    (#23; 43-50). ************
      (#24; 44-45). *******
      (#25; 46-47). *********
      (#26; 48-49). ****************
    (#27; 51-62). *************
      (#28; 52-53). *********
      (#29; 54-55). *********
      (#30; 56-57). ************
      (#31; 58-59). **********
      (#32; 60-61). ***********
-- drop_table("menu_items")
   -> 0.0020s
-- rename_table("nested_set_menu_items", "menu_items")
   -> 0.0020s
== MigrateTreeToNestedSet: migrated (2.0795s) =================================

After you run the migration, all you have to do is get rid of the old model and move the new, ActsAsTree-powered model into its place...

svn rm app/models/menu_item.rb
svn mv app/models/nested_set_menu_item.rb app/models/menu_item.rb

[edit]

Most of this is a specialization of Rails / Sortable lists.

[edit] Scriptaculous's Sortable's tree:true option

Demo: http://script.aculo.us/playground/test/functional/sortable_tree_test.html

Also here: http://svn.tylerrick.com/public/rails/examples/ajax/ajax_examples/app/views/scriptaculous_sortables/tree.rhtml

It's really neat! But... I found it a bit hard to use, actually. Too easy to accidentally move a node up or down a level to a different subtree. Having whole (large) subtrees bumping down dynamically to make room for the element I'm dragging is kind of "neat", but quite distracting and confusing, especially since it does this for every single element as you drag over it, which means it's doing it for a lot of elements...

Conclusion: Don't use the tree:true option. I think generally I would prefer to only allow "easy"/"quick" re-ordering (using the Scriptaculous "Sortable") for nodes at the same level. The user interface to move a node to a different subtree can be accomplished with "plain old" Draggables -- only updating the view after the Ajax request (to assign a new parent) has been processed and the server responds with some RJS to update the view.

A bit laggy perhaps, but it's better than having the [skitterish] feeling of having everything constantly moving/jumping around as you're dragging a node. Ideally, it would be updated on the client-side immediately and then maybe highlighted when the Ajax request completes, but I don't (currently) how easy that would be...

[edit] Sur's AjaxTree

Source Code For Ajax Based Drag Drop Navigation Tree in Ruby on Rails (http://ajaxonrails.wordpress.com/2006/08/18/sorce-code-for-ajax-based-drag-drop-navigation-tree-for-rails/) (2006-11-26). Retrieved on 2007-05-11 11:18.

...

http://ajaxonrails.wordpress.com/2006/11/26/ajaxonrailsdragdroptree/ (the source code for the above)

http://svn.tylerrick.com/public/rails/examples/ajaxtree

Comments:

• You can drag and drop a node to a different parent but not to a different position (well, of course, because it doesn't even keep track of position -- it uses acts_as_tree, which is an unordered tree)
• It has +/- icons for each node that let you collapse/expand that subtree
• When you drag and drop, it reloads the entire tree, expanding the subtree that you dropped onto and collapsing all (non-ancestor) trees.
• There is no indication when you are over a droppable element.
• Bug: If you drag onto a collapsed node (say 'item4'), it won't just add it as a child of item4, but will actually add it as a child of the last child of item4, which is item4.3 in the demo.
• By the author's own admission [2], this code has "lagged behind the current trends followed in Rails development" and he was new to Rails when he started it, so it may not use the best conventions...

[edit] Sortable tree addition / discussion on Rails-spinoffs list

http://lists.rubyonrails.org/pipermail/rails-spinoffs/2006-March/002890.html [Rails-spinoffs] sortable tree?

http://wrath.rubyonrails.org/pipermail/rails-spinoffs/2006-February/subject.html#2632 The Rails-spinoffs February 2006 Archive by subject

[edit] sortable tree fix and enhancement for acts_as_nested_set+better_nested_set plugin

http://dev.rubyonrails.org/ticket/7807

1. 7807 ([PATCH] Sortable tree fixes for #4691 (adding sub-items to empty branches)) - Rails Trac - Trac

1. #4691 fix: you may add any branch under any node and, thus, create new branch. 2. acts_as_nested_set & better_nested_set plugin integration. onChange provides 2 more arguments: movement type and reference object (drop-on-element). Three movements are supported: "left_to", "right_to" and "to_child_of".

http://dev.rubyonrails.org/attachment/ticket/7807/sortable_tree_fix_and_enhancement.2.diff