Sort an array of objects in ruby

Question

First of all full disclosure. I attempted to solve this issue at this thread but I wanted to repost in hopes of getting some help in Ruby:

best way to sort an array of objects by category and infinite subcategory

I have made a feeble attempt a that solution but can't even get close and it's not even worth showing. Below is my attempt. It would mean the world to me if someone could give some good direction on this.

data = [{id: 1, name: "parent test 1", parent_id: nil, top_level_category_id: nil},
        {id: 2, name: "test 2", parent_id: 1, top_level_category_id: 1},
        {id: 3, name: "test 3", parent_id: 1, top_level_category_id: 1},
        {id: 4, name: "parent test 4", parent_id: nil, top_level_category_id: nil},
        {id: 5, name: "test 5", parent_id: 3, top_level_category_id: 4},
        {id: 6, name: "test 6", parent_id: 4, top_level_category_id: 4},
        {id: 7, name: "test 7", parent_id: 4, top_level_category_id: 4}]

This is what I am hoping to accomplish

parent test 1
  test 2
  test 3
    test 5
parent test 2
  test 6
  test 7

-

ord_cat = {}

for item in data
  if item[:parent_id] == nil
    ord_cat[item[:id]] = {:name => item[:name], :children => {}}
  end
end

# fill child directories
for item in data
  if item[:parent_id] != nil
    ord_cat[item[:top_level_category_id]][:children].merge!({item[:id] => item[:name]})
  end
end


puts ord_cat

This is the output

{1=>{:name=>"parent test 1", :children=>{2=>"test 2", 3=>"test 3", 5=>"test 5"}}, 4=>{:name=>"parent test 4", :children=>{6=>"test 6", 7=>"test 7"}}}

This is clearly not nesting "test 5" properly. I'm not thrilled with the structure of the object.

possible duplicate of tree struture in ruby with parent child in array format without gems? — mu is too short
– mu is too short, Commented Mar 14, 2014 at 5:05
Yes, that was indeed the answer. There is a little tweaking to do but that definitely does the heavy lifting. I learned a little something too. Thank you, very much! — bonum_cete
– bonum_cete, Commented Mar 14, 2014 at 5:52
Cool, I thought this "unflatten a tree" problem looked familiar. — mu is too short
– mu is too short, Commented Mar 14, 2014 at 6:08

vikramv · Accepted Answer · 2014-03-14 06:01:04Z

We can construct the ancestor list for each node and sorting based on that list, in effect giving a depth-first traversal of the tree.

A bit lengthy solution, but would solve the problem I believe. Have used hash more to avoid scanning the array multiple times.

data = [{id: 1, name: "parent test 1", parent_id: nil, top_level_category_id: nil},
        {id: 2, name: "test 2", parent_id: 1, top_level_category_id: 1},
        {id: 3, name: "test 3", parent_id: 1, top_level_category_id: 1},
        {id: 4, name: "parent test 4", parent_id: nil, top_level_category_id: nil},
        {id: 5, name: "test 5", parent_id: 3, top_level_category_id: 4},
        {id: 6, name: "test 6", parent_id: 4, top_level_category_id: 4},
        {id: 7, name: "test 7", parent_id: 4, top_level_category_id: 4}]

# Amount of indentation for printing each node's nesting
INDENTATION_PER_LEVEL = 1

id_to_data_map = {}
id_to_parent_id_map = {}

data.each { |d|
    id_to_data_map[d[:id]] = d
    id_to_parent_id_map[d[:id]] = d[:parent_id]
}

data_with_ancestors = {}

data.each do |record|
    ancestors = [record[:name]]

    # Temporary parent
    parent = record

    while true do
        parent_id = id_to_parent_id_map[parent[:id]]

        break if parent_id.nil? # Hit the root - get out.
        parent = id_to_data_map[parent_id]

        ancestors << parent[:name]
    end

    # Construct a list of ancestors for the node, with the oldest ancestor first.
    data_with_ancestors[record[:name]] = ancestors.reverse
end

# Sort the flattened list based on the ancestor string constructed by joining all the parent names.
sorted_list = data_with_ancestors.sort_by {|name, ancestors| ancestors.join(" ")}

# Add indentation for the record names based on their nesting in the tree.
print_info = sorted_list.collect {|name, ancestors| (" " * (ancestors.size - 1) * INDENTATION_PER_LEVEL) + name}

print_info.each { |record| puts record }

Lengthy maybe, but it is working perfectly. Thanks! However, now that I have it this far I want to wrap it in html list tags. Easy enough except I'm having trouble plugging the <ul> in the right place i.e. each parent needs a <ul> and a closing </ul> after it's last child .

Collectives™ on Stack Overflow

Sort an array of objects in ruby

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related