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

Christoph Schiessl picture Christoph Schiessl · Sep 3, 2009 · Viewed 8.6k times · Source

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.

Answer

John F. Miller picture John F. Miller · Sep 5, 2009

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