Algorithm for sorting a nested/adjecency model in Ruby

Question

I've been trying to find a good way of doing this, either on the client side in Javascript or at the last minute within the server. This is a Rails application but it is a pretty generic question. I have a model that is hierarchical, and is currently stored in a nested set model. The model then has:

parent_id, lft, and rgt

I would like to pull out all of the models in one select statement from the database, therefore giving me a flat list of models, and then sort them on the fly into a tree hierarchy. I have not found a clean way to do this that would not require recursion. I'm sure there is a nice algorithm out there for this. Thanks.

Answer 1

http://dev.mysql.com/tech-resources/articles/hierarchical-data.html

Answer 2

I don't know of a algorithm without recursion. Thought i'd share my sitemap view helper anyhow:

def tree_from_set(set, &node_text)
  buf = '<ul>'
  siblings = set.select{|n| n.parent_id == set[0].parent_id}

  siblings.each do |node|
    children = set.select{|n| n.lft > node.lft and n.rgt < node.rgt }
    buf << '<li>'
      if children.blank?
        buf << yield(node)
      else
        buf << yield(node)
        buf << tree_from_set(children, &node_text)
      end
    buf << '</li>'
  end
  buf << '</ul>'
end