Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Fetching contributors…

Cannot retrieve contributors at this time

244 lines (213 sloc) 5.336 kB
#
# Rabal Tree,rb
# A basic Tree structure
#
class Tree
include Enumerable
# The name of this Tree
attr_accessor :name
# The parent of this node. If this is nil then this Tree is a
# root.
attr_accessor :parent
# The children of this node. If this Hash is empty, then this
# Tree is a leaf.
attr_accessor :children
# An abstract data point that can be utilized by child classes
# for whatever they like. If this is non-nil and responds to
# method calls it will be searched as part of the
# 'method_missing' protocol.
attr_accessor :parameters
#
# Create a new Tree with the given object.to_s as its +name+.
#
def initialize(name)
@name = name.to_s
@parent = nil
@children = {}
@parameters = nil
end
#
# Return true if this Tree has no children.
#
def is_leaf?
@children.empty?
end
#
# Return true if this Tree has no parent.
#
def is_root?
@parent.nil?
end
#
# Return the root node of the tree
#
def root
return self if is_root?
return @parent.root
end
#
# Return the distance from the root
#
def depth
return 0 if is_root?
return (1 + @parent.depth)
end
#
# Attach the given tree at the indicated path. The path given
# is always assumed to be from the root of the Tree being
# attached to.
#
# The path is given as a string separated by '/'. Each portion
# of the string is matched against the name of the particular
# tree.
#
# Given :
#
# a --- b --- c
# \
# d - e --- f
# \
# g - h
#
# * the path +a/b/c+ will match the path to Tree +c+
# * the path +d/e/g+ will _not_ match anything as the path must start at +a+ here
# * the path +a/d/e+ will _not_ match anytthin as +e+ is not a child of +d+
# * the path +a/d/e/g+ will match node +g+
#
# Leading and trailing '/' on the path are not necessary and removed.
#
def add_at_path(path,subtree)
parent_tree = tree_at_path(path)
parent_tree << subtree
return self
end
#
# Return the Tree that resides at the given path
#
def tree_at_path(path_str)
path_str = path_str.chomp("/").reverse.chomp("/").reverse
path = path_str.split("/")
# strip of the redundant first match if it is the same as
# the current node
find_subtree(path)
end
#
# Add the given object to the Tree as a child of this node. If
# the given object is not a Tree then wrap it with a Tree.
#
def <<(subtree)
# this should not generally be the case, but wrap things
# up to be nice.
if not subtree.kind_of?(Tree) then
subtree = Tree.new(subtree)
end
subtree.parent = self
# FIXME: techinically this should no longer be called 'post_add'
# but maybe 'add_hook'
subtree.post_add
# Don't overwrite any existing children with the same name,
# just put the new subtree's children into the children of
# the already existing subtree.
if children.has_key?(subtree.name) then
subtree.children.each_pair do |subtree_child_name,subtree_child_tree|
children[subtree.name] << subtree_child_tree
end
else
children[subtree.name] = subtree
end
return self
end
alias :add :<<
#
# Allow for Enumerable to be included. This just wraps walk.
#
def each
self.walk(self,lambda { |tree| yield tree })
end
#
# Count how many items are in the tree
#
def size
inject(0) { |count,n| count + 1 }
end
#
# Walk the tree in a depth first manner, visiting the Tree
# first, then its children
#
def walk(tree,method)
method.call(tree)
tree.children.each_pair do |name,child|
walk(child,method)
end
#for depth first
#method.call(tree)
end
#
# Allow for a method call to cascade up the tree looking for a
# Tree that responds to the call.
#
def method_missing(method_id,*params,&block)
if not parameters.nil? and parameters.respond_to?(method_id) then
return parameters.send(method_id, *params, &block)
elsif not is_root? then
@parent.send method_id, *params, &block
else
raise NoMethodError, "undefined method `#{method_id}' for #{name}:Tree"
end
end
#
# allow for a hook so newly added Tree objects may do custom
# processing after being added to the tree, but before the tree
# is walked or processed
#
def post_add
end
#
# find the current path of the tree from root to here, return it
# as a '/' separates string.
#
def current_path
#
# WMAP: removed the asterixs and modified the first return
# to just return a '/'
#
return "/" if is_root?
return ([name,parent.current_path]).flatten.reverse.join("/")
end
#
# Given the initial path to match as an Array find the Tree that
# matches that path.
#
def find_subtree(path)
if path.empty? then
return self
else
possible_child = path.shift
if children.has_key?(possible_child) then
children[possible_child].find_subtree(path)
else
raise PathNotFoundError, "`#{possible_child}' does not match anything at the current path in the Tree (#{current_path})"
end
end
end
#
# Return true of false if the given subtree exists or not
#
def has_subtree?(path)
begin
find_subtree(path)
return true
rescue PathNotFoundError
return false
end
end
#
# Allow for numerable to be included. This just wraps walk
#
def each
self.walk(self,lambda { |tree| yield tree })
end
def each_datum
self.walk(self,lambda { |tree| yield tree.data})
end
end
Jump to Line
Something went wrong with that request. Please try again.