How to render all records from a nested set into a real html tree

Question

I'm using the awesome_nested_set plugin in my Rails project. I have two models that look like this (simplified):

class Customer < ActiveRecord::Base
  has_many :categories
end

class Category < ActiveRecord::Base
  belongs_to :customer

  # Columns in the categories table: lft, rgt and parent_id
  acts_as_nested_set :scope => :customer_id

  validates_presence_of :name
  # Further validations...
end

The tree in the database is constructed as expected. All the values of parent_id, lft and rgt are correct. The tree has multiple root nodes (which is of course allowed in awesome_nested_set).

Now, I want to render all categories of a given customer in a correctly sorted tree like structure: for example nested <ul> tags. This wouldn't be too difficult but I need it to be efficient (the less sql queries the better).

Update: Figured out that it is possible to calculate the number of children for any given Node in the tree without further SQL queries: number_of_children = (node.rgt - node.lft - 1)/2. This doesn't solve the problem but it may prove to be helpful.

Bloodstain

Answer 1

It would be nice if nested sets had better features out of the box wouldn't it.

The trick as you have discovered is to build the tree from a flat set:

• start with a set of all node sorted by lft
• the first node is a root add it as the root of the tree move to next node
• if it is a child of the previous node (lft between prev.lft and prev.rht) add a child to the tree and move forward one node
• otherwise move up the tree one level and repeat test

see below:

def tree_from_set(set) #set must be in order
  buf = START_TAG(set[0])
  stack = []
  stack.push set[0]
  set[1..-1].each do |node|
    if stack.last.lft < node.lft < stack.last.rgt
      if node.leaf? #(node.rgt - node.lft == 1)
        buf << NODE_TAG(node)
      else
        buf << START_TAG(node)
        stack.push(node)
      end
    else#
      buf << END_TAG
      stack.pop
      retry
    end
  end
  buf <<END_TAG
end

def START_TAG(node) #for example
  "<li><p>#{node.name}</p><ul>"
end

def NODE_TAG(node)
  "<li><p>#{node.name}</p></li>"
end

def END_TAG
  "</li></ul>"
end 

Conflagrant

This works. You are right regarding awesome_nested_set too. I can't help to wonder why this isn't built into the plugin in the first place. Thx! – Bloodstain

Forgot to mention: The essential point about your solution is, that it requires only one single SQL query! – Bloodstain

Answer 2

I answered a similar question for php recently (nested set == modified preorder tree traversal model).

The basic concept is to get the nodes already ordered and with a depth indicator by means of one SQL query. From there it's just a question of rendering the output via loop or recursion, so it should be easy to convert this to ruby.

I'm not familiar with the awesome_nested_set plug in, but it might already contain an option to get the depth annotated, ordered result, as it is a pretty standard operation/need when dealing with nested sets.

Hide

Answer 3

Since september 2009 awesome nested set includes a special method to do this: https://github.com/collectiveidea/awesome_nested_set/commit/9fcaaff3d6b351b11c4b40dc1f3e37f33d0a8cbe

This method is much more efficent than calling level because it doesn't require any additional database queries.

Example: Category.each_with_level(Category.root.self_and_descendants) do |o, level|

Dombrowski

Answer 4

You have to recursively render a partial that will call itself. Something like this:

# customers/show.html.erb
<p>Name: <%= @customer.name %></p>
<h3>Categories</h3>
<ul>
  <%= render :partial => @customer.categories %>
</ul>

# categories/_category.html.erb
<li>
  <%= link_to category.name, category %>
  <ul>
    <%= render :partial => category.children %>
  </ul>
</li>

This is Rails 2.3 code. You'll have to call the routes and name the partial explicitely before that.

Philemol

Yeah, I came up with the same solution myself. The problem is that EVERY call to children executes an extra SQL query (100 subtrees = 100 SQL queries). Results in a classical N+1 problem. That's exactly what I'm trying to avoid. Besides: The first render partial call should be something like <%= render :partial => @customer.categories.roots %> – Bloodstain

Answer 5

_tree.html.eb

@set = Category.root.self_and_descendants
<%= render :partial => 'item', :object => @set[0] %>

_item.html.erb

<% @set.shift %>
<li><%= item.name %>
<% unless item.leaf? %>
<ul>
  <%= render :partial => 'item', :collection => @set.select{|i| i.parent_id == item.id} %>
</ul>
<% end %>
</li>

You can also sort their:

  <%= render :partial => 'item', :collection => @set.select{|i| i.parent_id == item.id}.sort_by(&:name) %>

but in that case you should REMOVE this line:

<% @set.shift %>

Incandesce

Answer 6

Maybe a bit late but I'd like to share my solution for awesome_nested_set based on closure_tree gem nested hash_tree method:

def build_hash_tree(tree_scope)
  tree = ActiveSupport::OrderedHash.new
  id_to_hash = {}

  tree_scope.each do |ea|
    h = id_to_hash[ea.id] = ActiveSupport::OrderedHash.new
    (id_to_hash[ea.parent_id] || tree)[ea] = h
  end
  tree
end

This will work with any scope ordered by lft

Than use helper to render it:

def render_hash_tree(tree)
  content_tag :ul do
    tree.each_pair do |node, children|
      content = node.name
      content += render_hash_tree(children) if children.any?
      concat content_tag(:li, content.html_safe)
    end
  end
end

Gualtiero

Answer 7

I couldn't get to work the accepted answer because of old version of ruby it was written for, I suppose. Here is the solution working for me:

def tree_from_set(set)
    buf = ''

    depth = -1
    set.each do |node|
        if node.depth > depth
            buf << "<ul><li>#{node.title}"
        else
            buf << "</li></ul>" * (depth - node.depth)
            buf << "</li><li>#{node.title}"
        end

        depth = node.depth
    end

    buf << "</li></ul>" * (depth + 1)

    buf.html_safe
end

It's simplified by using the optional depth information. (Advantage of this approach is that there is no need for the input set to be the whole structure to the leaves.)

More complex solution without depths can be found on github wiki of the gem:

https://github.com/collectiveidea/awesome_nested_set/wiki/How-to-generate-nested-unordered-list-tags-with-one-DB-hit

Catamaran