Managing Hierarchical Tree-Like Data

[x1]

Team:
I'm looking for a pragmatic way of creating a tree from a list of
items without knowing the depth of each.

For example:

max_depth = 4 #considers each unique item below the depth of 4 to be one
item_tree = {}
["CarRedFast",
"CarGreenSlow",
"Car",
"CarRedFastAgileSadCheeseBurger",
"CarRedFastAgileHappyJoy",
"GreenApplePie",
"GreenApple"
].each do |i|
items = i.gsub(/[A-Z][a-z]/) {|i| "_" + i}.gsub(/^_/, "").split("_")
end

This builds an array from items based on the case but many times, I
have needed to display this data in tree form as such:

#############################
# Desired output:
Car(2)
Red(1)
Fast(1)
Agile(2)
HappyJoy
SadCheeseBurger
Green(1)
Slow(0)
Green(1)
Apple(1)
Pie(0)
###############################


I've come across this numerous times and am pretty sure there's a
better way of doing it.

This is pretty much what I have now and it feels SO wrong to write!

#This just feels horrible writing
item_tree = {}
["CarRedFast",
"CarGreenSlow",
"Car",
"CarRedFastAgileSadCheeseBurger",
"CarRedFastAgileHappyJoy",
"GreenApplePie",
"GreenApple"
].each do |i|
items = i.gsub(/[A-Z][a-z]/) {|i| "_" + i}.gsub(/^_/, "").split("_")
items.each do |item|
if item_tree.include? item[0]
if item_tree[item[0]].include? item[1]
#yadadada
else
item_tree[item[0]][item[1]] = {}
end
else
item_tree[item[0]] = {}
end
end
end



Please.. Any suggestions at all.. All comments welcome!! TIA

 

[Phrogz]

Team:
I'm looking for a pragmatic way of creating a tree from a list of
items without knowing the depth of each.

How about this:
class Hash
def as_tree( depth=0 )
map{ |k,subtree|
me = " "*depth + "#{k} (#{subtree.length})"
if subtree.empty?
me
else
[ me, subtree.as_tree( depth+1 ) ]
end
}.flatten.join( "\n" )
end
end

hash_of_hashes = lambda { Hash.new {|h,k| h[k] = hash_of_hashes.call} }
item_tree = hash_of_hashes.call

items = [ "CarRedFast", "CarGreenSlow", "Car",
"CarRedFastAgileSadCheeseBurger", "CarRedFastAgileHappyJoy",
"GreenApplePie", "GreenApple" ]
items.each do |item|
current = item_tree
item.scan( /[A-Z][a-z]+/ ).each{ |piece|
current = current[ piece ]
}
end

puts item_tree.as_tree
#=> Green (1)
#=> Apple (1)
#=> Pie (0)
#=> Car (2)
#=> Red (1)
#=> Fast (1)
#=> Agile (2)
#=> Sad (1)
#=> Cheese (1)
#=> Burger (0)
#=> Happy (1)
#=> Joy (0)
#=> Green (1)
#=> Slow (0)

 

[x1]

Jesus! Give me an hour or so to make sense of this. I'm so glad you
provided this!! A++++++++++++

Team:
I'm looking for a pragmatic way of creating a tree from a list of
items without knowing the depth of each.

How about this:
class Hash
def as_tree( depth=0 )
map{ |k,subtree|
me = " "*depth + "#{k} (#{subtree.length})"
if subtree.empty?
me
else
[ me, subtree.as_tree( depth+1 ) ]
end
}.flatten.join( "\n" )
end
end

hash_of_hashes = lambda { Hash.new {|h,k| h[k] = hash_of_hashes.call} }
item_tree = hash_of_hashes.call

items = [ "CarRedFast", "CarGreenSlow", "Car",
"CarRedFastAgileSadCheeseBurger", "CarRedFastAgileHappyJoy",
"GreenApplePie", "GreenApple" ]
items.each do |item|
current = item_tree
item.scan( /[A-Z][a-z]+/ ).each{ |piece|
current = current[ piece ]
}
end

puts item_tree.as_tree
#=> Green (1)
#=> Apple (1)
#=> Pie (0)
#=> Car (2)
#=> Red (1)
#=> Fast (1)
#=> Agile (2)
#=> Sad (1)
#=> Cheese (1)
#=> Burger (0)
#=> Happy (1)
#=> Joy (0)
#=> Green (1)
#=> Slow (0)

 

[x1]

Ok --

Phrogz, I find your script very interesting and I'll learn a lot by
going through it over and over. Thank you!

Paul, Sorry for the crappy data (it just happened to be what I was
working w/ at the time)

One of the key items both of you two used which I was not aware of
(and am ignorant for this) is the ability to use:
current = item_tree #Phrogz
node = tree # Paul

So what this is doing, is creating a new hash at the new depth,
without having to statically reference it. Nice. Yes, I'm a newb to
OO.

Thanks guys

Jesus! Give me an hour or so to make sense of this. I'm so glad you
provided this!! A++++++++++++

Team:
I'm looking for a pragmatic way of creating a tree from a list of
items without knowing the depth of each.

How about this:
class Hash
def as_tree( depth=0 )
map{ |k,subtree|
me = " "*depth + "#{k} (#{subtree.length})"
if subtree.empty?
me
else
[ me, subtree.as_tree( depth+1 ) ]
end
}.flatten.join( "\n" )
end
end

hash_of_hashes = lambda { Hash.new {|h,k| h[k] = hash_of_hashes.call} }
item_tree = hash_of_hashes.call

items = [ "CarRedFast", "CarGreenSlow", "Car",
"CarRedFastAgileSadCheeseBurger", "CarRedFastAgileHappyJoy",
"GreenApplePie", "GreenApple" ]
items.each do |item|
current = item_tree
item.scan( /[A-Z][a-z]+/ ).each{ |piece|
current = current[ piece ]
}
end

puts item_tree.as_tree
#=> Green (1)
#=> Apple (1)
#=> Pie (0)
#=> Car (2)
#=> Red (1)
#=> Fast (1)
#=> Agile (2)
#=> Sad (1)
#=> Cheese (1)
#=> Burger (0)
#=> Happy (1)
#=> Joy (0)
#=> Green (1)
#=> Slow (0)

 

[Phrogz]

array.each do |record|
node = tree
record.each do |field|
node[field] = {} unless node[field]
node = node[field]
end
end

I like Paul's simple solution better than my
tricky-but-almost-obfuscated autovivifying Hash. One note (that I don't
think is golfing): the innermost code in the above can be rubyified as:
node[field] ||= {}
node = node[field]
or simplified further (golfed?) to:
node = ( node[field] ||= {} )

 

[poopdeville]

Team:
I'm looking for a pragmatic way of creating a tree from a list of
items without knowing the depth of each.

Here's a good algorithm for constructing a formal concept lattice.
http://lanl.arxiv.org/pdf/cs.DM/0602069

It's not particularly pragmatic, but it's fast and ultimately
equivalent to what you're trying to do.

'cid 'ooh