Tree Nodes using array of strings

Question

I am trying to build a tree with root, children, and grandchildren nodes using an array of strings. I have an array like this

array = [
  "/capacitor/",
  "/capacitor/non_polarized/",
  "/capacitor/non_polarized/ceramic/",
  "/capacitor/polarized/",
  "/capacitor/polarized/al/",
  "/connector/",
  "/diode/",
  "/diode/normal/",
  "/optical/",
  "/optical/emmision/diode/",
  "/optical/emmision/laser/",
  "/optical/detector/",
  "/optical/detector/diode/"
]

I would like to take this array and determine the respective nodes. The ones which are like

"/capacitor/", "/connector/", "/diode/"

are the root nodes. The ones which are like

"/capacitor/non_polarized/", "/capacitor/polarized/", "/optical/detector/"

are children nodes, and finally the ones like

"/optical/detector/diode/", "/optical/emmision/laser/"

are grandchildren nodes. A strings which has two / and text in between is a root node, with three / is a child node, and with four / is a grandchildren node.

Imagine I had capacitor as my root node, now I would have root_node = "capacitor" child_node = "/capacitor/non_polarized/","/capacitor/polarized/" and grandchild_node = "/capacitor/non_polarized/ceramic/", "/capacitor/polarized/al/"

EDIT: I would like the output in such a way that the by using the root node I can determine the children and grandchildren.

what you want is start out with an array of strings, and have an output of a tree structured nodes, correct? Is there any request of what kind of class you want the output in? — Saifis
– Saifis, Commented Jul 5, 2013 at 9:58
You tagged as ruby-on-rails, and you are claiming that you do not have present?. That is contradictory. — sawa
– sawa, Commented Jul 5, 2013 at 10:21

Benoît · Accepted Answer · 2013-07-08 00:02:42Z

1

I am sure there is a much better way to do this but if this can help you

tree = array.inject({}) do |h, string|
  values = string.split('/').reject(&:empty?)
  top = values.shift
  h[top] ||= {}
  values.inject(h[top]) do |sub_h, value|
    sub_h[value] ||= {}
  end
  h
end

y tree
#--- 
#capacitor: 
#  non_polarized: 
#    ceramic: {}
#
#  polarized: 
#    al: {}
#
#connector: {}
#
#diode: 
#  normal: {}
#
#optical: 
#  emmision: 
#    diode: {}
#
#    laser: {}
#
#  detector: 
#    diode: {}

edited Jul 8, 2013 at 0:02

answered Jul 5, 2013 at 9:56

Benoît

14.5k7 gold badges65 silver badges89 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

user2071444 Over a year ago

Thank for the response. When I am trying to execute this in IRB i am getting this error "NoMethodError: undefined method `present?' for "":String"

user2071444 Over a year ago

That is may be because when we do a split some of the array values have an nil or empty string. Am i rite?

Benoît Over a year ago

@MarkV Are you not using Ruby on Rails ?

user2071444 Over a year ago

Well I am getting a hash like this:

{"capacitor"=>{:leaf=>"polarized", :children=>{:leaf=>"al", :children=>{}}}, "connector"=>{}, "diode"=>{:leaf=>"normal", :children=>{}}, "optical"=>{:leaf=>"detector", :children=>{:leaf=>"diode", :children=>{}}}}

It is missing "/capacitor/non_polarized/", "/capacitor/non_polarized/ceramic/", "/optical/emmision/diode/", "/optical/emmision/laser/"

Benoît Over a year ago

@MarkV I was away for few days. As you said there was a problem in my code and I fixed it.

|

sawa · Accepted Answer · 2013-07-05 10:33:30Z

1

roots, children, grandchildren =
array.group_by{|s| s.count("/")}.values_at(2, 3, 4)

edited Jul 5, 2013 at 10:33

answered Jul 5, 2013 at 10:28

sawa

169k51 gold badges287 silver badges398 bronze badges

3 Comments

user2071444 Over a year ago

That is really cool to use groups to split the array. But the problem in this approach is that I don't have any idea which root node has how many children and grandchildren. How to find that out. Thanks

sawa Over a year ago

That was not part of your question. If you want to ask that, you need to state that in the question.

user2071444 Over a year ago

I am sorry I am a noob, so bad at asking. I will edit my question.

Benoit Marilleau · Accepted Answer · 2013-07-05 12:36:36Z

Here's what I would do :

class TreeNode
  attr_accessor :name, :children

  def initialize(name, children_strings)
    @name = name
    @children = []
    @children << TreeNode.new(children_strings.shift, children_strings) if !children_strings.nil? and children_strings.count > 0
    self
  end

  def to_hash
    { name => children.map(&:to_hash) }
  end

  def self.process_node(root, strings_array)
    next_node = root.children.detect { |n| n.name == strings_array.first }
    if !next_node.nil?
      strings_array.shift
      process_node(next_node, strings_array)
    else
      root.children << TreeNode.new(strings_array.shift, strings_array)
    end
  end

  def self.process_array(array)
    root = TreeNode.new('root', nil)
    array.each do |string| 
      strings_array = string.split('/')
      strings_array.shift
      TreeNode.process_node(root, strings_array)
    end
    root
  end
end

root = TreeNode.process_array(array)

Collectives™ on Stack Overflow

Tree Nodes using array of strings

3 Answers 3

8 Comments

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

8 Comments

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related