From: Josh Cheek <josh.cheek@...>
Date: 2011-07-22T07:50:25+09:00
Subject: Re: Building a tree from the leaves down

--0050450145389f7a0104a89c2c80
Content-Type: text/plain; charset=ISO-8859-1

On Thu, Jul 21, 2011 at 10:21 AM, Intransition <transfire@gmail.com> wrote:

> 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):
>
>  {
>    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.
>
>

This seems to work:


class CaseObject

  private
    def merge_in(hash, ancestry_chain)
      if 1 == ancestry_chain.size
        hash[ancestry_chain.pop] = nil
      else
        crnt = ancestry_chain.pop
        hash[crnt] ||= Hash.new
        merge_in hash[crnt], ancestry_chain
      end
      hash
    end
  public

  def self.as_hash(leaves)
    leaves.each.with_object(Hash.new) { |leaf, hash| merge_in hash,
leaf.ancestors }
  end

  attr :case

  def initialize(parent_case)
    @case = parent_case
  end

  def ancestors
    return [self] unless self.case
    [self] + self.case.ancestors
  end

end

# ...

CaseObject.as_hash [c11, c121, c122, d11, d12]

--0050450145389f7a0104a89c2c80--