From: Robert Klemme <shortcutter@...>
Date: 2011-07-22T00:49:10+09:00
Subject: Re: Building a tree from the leaves down

Thomas Sawyer wrote in post #1012175:
> Have a algorithmic problem, I can't quite get a clear idea of how to
> handle it.
>
> I have a list of objects that respond to `#case` that will return nil
> or a case object. Each case object also responds to `#case` and may
> return nil or a case object, and so on. Basically I have to build a
> tree from the bottom up (top down?) out of this list keyed on cases.
>
> Basic example, let's use this class:
>
>   class CaseObject
>     attr :case
>     def initialize(parent_case)
>       @case = parent_case
>     end
>   end
>
> And this has been defined:
>
>   c1 = CaseObject.new(nil)
>   c11 = CaseObject.new(c1)
>   c12 = CaseObject.new(c1)
>   c121 = CaseObject.new(c12)
>   c122 = CaseObject.new(c12)
>   d1 = CaseObject.new(nil)
>   d11 = CaseObject.new(d1)
>   d12 = CaseObject.new(d1)
>
> Then I am given all the _leaf_ nodes in a list:
>
>   [c11, c121, c122, d11, d12]
>
> I need to reconstruct the hierarchy into a tree (ie. a Hash):

A single Hash can never be a tree.

>   {
>     c1 => {
>       c11 => nil,
>       c12 => {
>         c121 => nil,
>         c122 => nil
>       }
>     },
>     d1 => {
>       d11 => nil,
>       d12 => nil
>     }
>   }
>
> There's probably some simple way to do this that I am overlooking, but
> it's alluding me at the moment.

Hmm...

cache = Hash.new {|h,k| h[k] = {}}

[c11, c121, c122, d11, d12].each do |x|
  cache[x.case][x] = cache[x]
end

Now you only need to find the roots. :-)

tree = Hash[*all_nodes.select {|x| x.case.nil?}.map {|root|
cache[root]}]

Roughly and untested.

Kind regards

robert

-- 
Posted via http://www.ruby-forum.com/.