convert from a 2d array to nested_set in Ruby on rails

Question

I have a tree structure in a .csv file (nodes are of type text), and after reading the csv i want to store the data in a ruby object. I went through a few tree plugins and i think nested_set would serve the purpose for me. However, i am facing problem with fixing a format of csv file, so that i can read it and convert into tree object. Is there any direct way of converting a csv file or 2 dimensional array, into a tree data structure??

Answer 1

After you clarified that you don't need to store this tree in database, I suggest to throw away NestedSets (they're to store nested sets of objects on RDBMS, which you don't need). What you need i simple tree

class Node
  attr_accessor :parent, :children, :text

  def initialize(text)
    @text = text
    @children = []
  end
end

As I have right to choose format of CSV file, then I suggest sth like this:

id,parent,text
1,,"1"
2,1,"1.1"
3,1,"1.2"
3,2,"1.1.1"

Tree root is first row, without parent, and there is always order that parent is declared before its children. That way you can build tree

def build_tree(rows)
  nodes = {}
  rows.each do |row|
    node = Node.new(row[:text])
    nodes[row[:id]] = node

    node.parent = nodes[row[:parent]]
    nodes[row[:parent]].children << node if row[:parent]
  end

  nodes.values.find {|node| node.parent.nil? }
end

root = build_tree(rows)
root.text #=> "1"
root.children.map(&:text) #=> ["1.1", "1.2"]
root.children[0].children.map(&:text) #=> ["1.1.1"]

If you need to get all texts from subnodes, then you need to use more tricks

def get_nodes(tree_node)
  [ tree_node, tree_node.children.map{|node| get_nodes(node)} ].flatten
end

get_nodes(root).map(&:text) #=> ["1", "1.1", "1.1.1", "1.2"]

Answer 2

Seems that you don't need to use ORM at all. Why don't you make your tree logic yourself, with a dynamic language such as Ruby, it's pretty easy:

require 'set'

# expects an array of [parent, child] pairs, returns the root element of a tree
def make_tree a
  tree = {}

  a.each do |p, c|
    tree[p] ||= {:value => p}
    tree[p][:children] ||= Set.new
    tree[c] ||= {:value => c}
    tree[c][:parent] = tree[p]
    tree[p][:children] << tree[c]
  end

  tree.values.find{|e| e[:parent].nil?}
end

root = make_tree [[1,2],[3,4],[1,3],[4,5]]

puts root.inspect
puts root[:value]

Or, if you want it more OO, you can make TreeNode class instead of Hash above.

Oh, and if you need to access particular tree nodes directly by their key (in this case the integer value itself), change the method to return tree hash instead of just the root element.