comments_tree.rb

require "pp"

def generate_timestamps(count)
  8.times.inject([Time.now]) do |memo, current|
    memo << memo.last + current * (10 * rand).to_i + 10
  end
end

timestamps = generate_timestamps(8)

comments = [
  {id: 1, content: "I'm a comment.", parent_id: nil, created_at: timestamps[0]},
  {id: 2, content: "You are wrong!", parent_id: 1, created_at: timestamps[2]},
  {id: 3, content: "I agree.", parent_id: 1, created_at: timestamps[4]},
  {id: 4, content: "This article sucks big time!", parent_id: nil, created_at: timestamps[1]},
  {id: 5, content: "E i Marò?", parent_id: 8, created_at: timestamps[6]},
  {id: 6, content: "#escilo", parent_id: 8, created_at: timestamps[7]},
  {id: 7, content: "LOL", parent_id: 4, created_at: timestamps[3]},
  {id: 8, content: "Spam, ergo sum.", parent_id: 7, created_at: timestamps[5]},
]

# creation order: 1, 4, 2, 7, 3, 8, 5, 6

# expected tree:
# nil
#   1
#     2
#     3
#   4
#     7
#       8
#         5
#         6

identity_map = {} # used to store the mapping between comment IDs and comment data

tree = []
parent_references = {nil => tree}
comments.sort_by { |comment| comment[:created_at] }.each do |comment|
  slot = parent_references[comment[:parent_id]]
  container = []
  slot << {comment[:id] => container}
  parent_references[comment[:id]] = container
  identity_map[comment[:id]] = comment
end

# pp tree
# [{1=>[{2=>[]}, {3=>[]}]}, {4=>[{7=>[{8=>[{5=>[]}, {6=>[]}]}]}]}]

# pp parent_references
# {nil=>[{1=>[{2=>[]}, {3=>[]}]}, {4=>[{7=>[{8=>[{5=>[]}, {6=>[]}]}]}]}],
# 1=>[{2=>[]}, {3=>[]}],
# 4=>[{7=>[{8=>[{5=>[]}, {6=>[]}]}]}],
# 2=>[],
# 7=>[{8=>[{5=>[]}, {6=>[]}]}],
# 3=>[],
# 8=>[{5=>[]}, {6=>[]}],
# 5=>[],
# 6=>[]}

def walk_tree(items: [], nesting: 0, identity_map:)
  items.each do |item|
    comment_id, children = item.to_a[0]
    comment = identity_map[comment_id]
    puts "#{" " * nesting * 2} #{comment[:id]} => \"#{comment[:content]}\" on #{comment[:created_at]}"
    if children.any?
      walk_tree(
        items: children,
        nesting: nesting + 1,
        identity_map: identity_map
      )
    end
  end
end

walk_tree(
  items: tree,
  identity_map: identity_map
)
# 1 => "I'm a comment." on 2015-11-19 15:42:52 +0100
#   2 => "You are wrong!" on 2015-11-19 15:43:20 +0100
#   3 => "I agree." on 2015-11-19 15:44:14 +0100
# 4 => "This article sucks big time!" on 2015-11-19 15:43:02 +0100
#   7 => "LOL" on 2015-11-19 15:43:40 +0100
#     8 => "Spam, ergo sum." on 2015-11-19 15:44:52 +0100
#       5 => "E i Marò?" on 2015-11-19 15:45:32 +0100
#       6 => "#escilo" on 2015-11-19 15:46:24 +0100