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}"
···
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] = cache
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
--
Kendall Gifford
zettabyte@gmail.com