From: Kendall Gifford <zettabyte@...>
Date: 2011-07-22T05:30:07+09:00
Subject: Re: Building a tree from the leaves down

--000e0cd571f2d7dd7d04a89a367e
Content-Type: text/plain; charset=UTF-8

On Thu, Jul 21, 2011 at 9:49 AM, Robert Klemme
<shortcutter@googlemail.com>wrote:

> 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
>
>
For fun, here's my OO-oriented approach with inspiration (though different)
from Robert's solution:

class CaseObject
  attr_reader :case
  attr_reader :name
  def initialize(parent, name)
    @case = parent
    @name = name
  end
  def inspect
    @name
  end
end

class Hash
  INDENT = " " * 2
  def inspect(indent = "")
    result    = "{\n"
    processed = 0
    total     = count()
    each do |k, v|
      total  += 1
      v       = v.is_a?(Hash) ? v.inspect(indent + INDENT) : v.inspect
      result << indent + INDENT + "#{k.inspect} => #{v}"
      result << "," if processed < total
      result << "\n"
    end
    "#{result}#{indent}}"
  end
end

class Tree
  attr_reader :registry
  def initialize(parent = :parent)
    @parent   = parent
    @registry = {}
  end
  def register(node)
    parent = node.send(@parent)
    if parent
      @registry[parent]     ||= {}
      @registry[parent][node] = @registry[node]
      register(parent)
    end
  end
  def to_hash
    @registry.select { |k, v| k.send(@parent_method).nil? }
  end
end

all_nodes = [
  c1   = CaseObject.new(nil, :c1),
  c11  = CaseObject.new(c1,  :c11),
  c12  = CaseObject.new(c1,  :c12),
  c121 = CaseObject.new(c12, :c121),
  c122 = CaseObject.new(c12, :c122),
  d1   = CaseObject.new(nil, :d1),
  d11  = CaseObject.new(d1,  :d11),
  d12  = CaseObject.new(d1,  :d12)
]
leaves = [c11, c121, c122, d11, d12]

puts "All Nodes: #{all_nodes.inspect}"
puts "Leaves:    #{leaves.inspect}"

tree = Tree.new(:case)
leaves.each { |x| tree.register(x) }
hash = tree.to_hash

puts "\nCache Hash:\n#{tree.registry.inspect}"
puts "\nTree Hash:\n#{hash.inspect}"

-- 
Kendall Gifford
zettabyte@gmail.com

--000e0cd571f2d7dd7d04a89a367e--