This class models the nodes for an N-ary tree data structue. The nodes are
named
and have a place-holder for the node data (i.e.,
`content' of the node). The node names are required to be
unique within the tree.
The node content is not required to be unique across different nodes in the
tree, and can be nil
as well.
The class provides various traversal methods to navigate the tree, methods to modify contents of the node or to change position of the node in the tree and methods to change structure of the tree.
A node can have any number of child nodes attached to it and hence can be used to create N-ary trees. Access to the child nodes can be made in order (with the conventional left to right access), or randomly.
The node also provides direct access to its parent and other superior
parents in the path to root of the tree. In addition, a node can also
access its sibling nodes, if present. Note that while this implementation
does not explicitly support directed graphs, the class itself makes no
restrictions on associating a node's CONTENT
with multiple
nodes in the tree.
The following example implements this tree structure: +------------+ | ROOT | +-----+------+ +-------------+------------+ | | +-------+-------+ +-------+-------+ | CHILD 1 | | CHILD 2 | +-------+-------+ +---------------+ | | +-------+-------+ | GRANDCHILD 1 | +---------------+
require 'tree'
root_node = ::new(“ROOT”, “Root Content”)
root_node << ::new(“CHILD1”, “Child1 Content”) << ::new(“GRANDCHILD1”, “GrandChild1 Content”)
root_node << ::new(“CHILD2”, “Child2 Content”)
root_node.printTree
child1 = root_node
grand_child1 = root_node[“GRANDCHILD1”]
siblings_of_child1 = child1.siblings
children_of_root = root_node.children
# Process all nodes
root_node.each { |node| node.content.reverse }
root_node.remove!(child1) # Remove the child
Content of this node. Can be nil
.
Name of this node. Expected to be unique within the tree.
Parent of this node. Will be nil
for root nodes.
Constructor which expects the name of the node. Name of the node is expected to be unique across the tree.
The content can be of any type, defaults to nil
.
# File lib/tree.rb, line 136 def initialize(name, content = nil) raise "Node name HAS to be provided" if name == nil @name = name @content = content self.setAsRoot! @childrenHash = Hash.new @children = [] end
Convenience synonym for #add method.
This method allows an easy method to add node hierarchies to the tree on a given path via chaining the method calls to successive child nodes.
Example: root << child << grand_child
Returns the added child node.
# File lib/tree.rb, line 194 def <<(child) add(child) end
Provides a comparision operation for the nodes.
Comparision is based on the natural character-set ordering of the *node name*.
# File lib/tree.rb, line 494 def <=>(other) return +1 if other == nil self.name <=> other.name end
Returns the requested node from the set of immediate children.
If the argument is numeric, then the in-sequence array of children is accessed (see Tree#children). If the argument is NOT numeric, then it is assumed to be name of the child node to be returned.
Raises an exception is the requested child node is not found.
# File lib/tree.rb, line 354 def [](name_or_index) raise "Name_or_index needs to be provided" if name_or_index == nil if name_or_index.kind_of?(Integer) @children[name_or_index] else @childrenHash[name_or_index] end end
Adds the specified child node to the receiver node.
This method can also be used for grafting a subtree into the receiver node's tree, if the specified child node is the root of a subtree (i.e., has child nodes under it).
The receiver node becomes parent of the node passed in as the argument, and the child is added as the last child (“right most”) in the current set of children of the receiver node.
Returns the added child node.
An exception is raised if another child node with the same name exists.
# File lib/tree.rb, line 210 def add(child) raise "Child already added" if @childrenHash.has_key?(child.name) @childrenHash[child.name] = child @children << child child.parent = self return child end
Returns breadth of the tree at the receiver node's level. A single node without siblings has a breadth of 1.
Breadth is defined to be:
Number of sibling nodes to this node + 1 (this node itself), i.e., the number of children the parent of this node has.
# File lib/tree.rb, line 589 def breadth isRoot? ? 1 : parent.children.size end
Performs breadth first traversal of the tree starting at the receiver node. The traversal at a given level is from left to right.
# File lib/tree.rb, line 327 def breadth_each &block node_queue = [self] # Create a queue with self as the initial entry # Use a queue to do breadth traversal until node_queue.empty? node_to_traverse = node_queue.shift yield node_to_traverse # Enqueue the children from left to right. node_to_traverse.children { |child| node_queue.push child } end end
Returns an array of all the immediate children of the receiver node.
If a block is given, yields each child node to the block traversing from left to right.
# File lib/tree.rb, line 288 def children if block_given? @children.each {|child| yield child} else @children end end
Returns depth of the tree from the receiver node. A single leaf node has a depth of 1.
This method is DEPRECATED and may be removed in the subsequent releases. Note that the value returned by this method is actually the:
height + 1 of the node, NOT the depth.
For correct and conventional behavior, please use #nodeDepth and #nodeHeight methods instead.
# File lib/tree.rb, line 571 def depth begin require 'structured_warnings' # To enable a nice way of deprecating of the depth method. warn DeprecatedMethodWarning, 'This method is deprecated. Please use nodeDepth() or nodeHeight() instead (bug # 22535)' rescue LoadError # Oh well. Will use the standard Kernel#warn. Behavior will be identical. warn 'Tree::TreeNode#depth() method is deprecated. Please use nodeDepth() or nodeHeight() instead (bug # 22535)' end return 1 if isLeaf? 1 + @children.collect { |child| child.depth }.max end
Returns a copy of the receiver node, with its parent and children links removed. The original node remains attached to its tree.
# File lib/tree.rb, line 148 def detached_copy Tree::TreeNode.new(@name, @content ? @content.clone : nil) end
Traverses every node (including the receiver node) from the (sub)tree by yielding the node to the specified block.
The traversal is depth-first and from left to right in pre-ordered sequence.
# File lib/tree.rb, line 314 def each &block # :yields: node yield self children { |child| child.each(&block) } end
Yields all leaf nodes from the receiver node to the specified block.
May yield this node as well if this is a leaf node. Leaf traversal is depth-first and left to right.
# File lib/tree.rb, line 343 def each_leaf &block self.each { |node| yield(node) if node.isLeaf? } end
Returns the first child of the receiver node.
Will return nil
if no children are present.
# File lib/tree.rb, line 299 def firstChild children.first end
Returns the first sibling for the receiver node. If this is the root node, returns itself.
'First' sibling is defined as follows:
The left-most child of the receiver's parent, which may be the receiver itself
# File lib/tree.rb, line 417 def firstSibling isRoot? ? self : parent.children.first end
Freezes all nodes in the (sub)tree rooted at the receiver node.
# File lib/tree.rb, line 500 def freezeTree! each {|node| node.freeze} end
Returns true
if the receiver node has any immediate child
nodes.
# File lib/tree.rb, line 275 def hasChildren? @children.length != 0 end
Returns true
if the receiver node has any associated content.
# File lib/tree.rb, line 257 def hasContent? @content != nil end
Returns true if the receiver node is the first sibling.
# File lib/tree.rb, line 422 def isFirstSibling? firstSibling == self end
Returns true if the receivere node is the last sibling.
# File lib/tree.rb, line 440 def isLastSibling? lastSibling == self end
Returns true
if the receiver node is a 'leaf' - i.e.,
one without any children.
# File lib/tree.rb, line 281 def isLeaf? !hasChildren? end
Returns true if the receiver node is the only child of its parent.
# File lib/tree.rb, line 467 def isOnlyChild? parent.children.size == 1 end
Returns true
if the receiver is a root node. Note that
orphaned children will also be reported as root nodes.
# File lib/tree.rb, line 270 def isRoot? @parent == nil end
Returns the last child of the receiver node.
Will return nil
if no children are present.
# File lib/tree.rb, line 306 def lastChild children.last end
Returns the last sibling for the receiver node. If this is the root node, returns itself.
'Last' sibling is defined as follows:
The right-most child of the receiver's parent, which may be the receiver itself
# File lib/tree.rb, line 435 def lastSibling isRoot? ? self : parent.children.last end
Convenience synonym for Tree#size
# File lib/tree.rb, line 374 def length size() end
Returns a marshal-dump represention of the (sub)tree rooted at the receiver node.
# File lib/tree.rb, line 505 def marshal_dump self.collect { |node| node.createDumpRep } end
Loads a marshalled dump of a tree and returns the root node of the reconstructed tree. See the Marshal class for additional details.
# File lib/tree.rb, line 521 def marshal_load(dumped_tree_array) nodes = { } for node_hash in dumped_tree_array do name = node_hash[:name] parent_name = node_hash[:parent] content = Marshal.load(node_hash[:content]) if parent_name then nodes[name] = current_node = Tree::TreeNode.new(name, content) nodes[parent_name].add current_node else # This is the root node, hence initialize self. initialize(name, content) nodes[name] = self # Add self to the list of nodes end end end
Returns the next sibling for the receiver node. The 'next' node is defined as the node to right of the receiver node.
Will return nil
if no subsequent node is present.
# File lib/tree.rb, line 475 def nextSibling if myidx = parent.children.index(self) parent.children.at(myidx + 1) end end
Returns depth of the receiver node in its tree. Depth of a node is defined as:
Length of the node's path to its root. Depth of a root node is zero.
Note that the deprecated method #depth was incorrectly computing this value. Please replace all calls to the old method with #nodeDepth instead.
# File lib/tree.rb, line 557 def nodeDepth return 0 if isRoot? 1 + parent.nodeDepth end
Returns height of the (sub)tree from the receiver node. Height of a node is defined as:
Length of the longest downward path to a leaf from the node.
Height from a root node is height of the entire tree.
The height of a leaf node is zero.
# File lib/tree.rb, line 546 def nodeHeight return 0 if isLeaf? 1 + @children.collect { |child| child.nodeHeight }.max end
Returns an array of ancestors of the receiver node in reversed order (the first element is the immediate parent of the receiver).
Returns nil
if the receiver is a root node.
# File lib/tree.rb, line 165 def parentage return nil if isRoot? parentageArray = [] prevParent = self.parent while (prevParent) parentageArray << prevParent prevParent = prevParent.parent end parentageArray end
Traverses the tree in a pre-ordered sequence. This is equivalent to #each
# File lib/tree.rb, line 321 def preordered_each &block # :yields: node each(&block) end
Returns the previous sibling for the receiver node. The 'previous' node is defined as the node to left of the receiver node.
Will return nil if no predecessor node is present.
# File lib/tree.rb, line 485 def previousSibling if myidx = parent.children.index(self) parent.children.at(myidx - 1) if myidx > 0 end end
Pretty prints the tree starting with the receiver node.
# File lib/tree.rb, line 379 def printTree(level = 0) if isRoot? print "*" else print "|" unless parent.isLastSibling? print(' ' * (level - 1) * 4) print(isLastSibling? ? "+" : "|") print "---" print(hasChildren? ? "+" : ">") end puts " #{name}" children { |child| child.printTree(level + 1)} end
Removes the specified child node from the receiver node.
This method can also be used for pruning a subtree, in cases where the removed child node is the root of the subtree to be pruned.
The removed child node is orphaned but accessible if an alternate reference exists. If accesible via an alternate reference, the removed child will report itself as a root node for its subtree.
Returns the child node.
# File lib/tree.rb, line 228 def remove!(child) @childrenHash.delete(child.name) @children.delete(child) child.setAsRoot! unless child == nil return child end
Removes all children from the receiver node.
Returns the receiver node.
# File lib/tree.rb, line 247 def removeAll! for child in @children child.setAsRoot! end @childrenHash.clear @children.clear self end
Removes the receiver node from its parent. The reciever node becomes the new root for its subtree.
If this is the root node, then does nothing.
Returns self (the removed receiver node) if the operation is successful,
and nil
otherwise.
# File lib/tree.rb, line 240 def removeFromParent! @parent.remove!(self) unless isRoot? end
Returns root node for the (sub)tree to which the receiver node belongs.
Note that a root node's root is itself (beware of any loop construct that may become infinite!)
# File lib/tree.rb, line 402 def root root = self root = root.parent while !root.isRoot? root end
Returns an array of siblings for the receiver node. The receiver node is excluded.
If a block is provided, yields each of the sibling nodes to the block. The
root always has nil
siblings.
# File lib/tree.rb, line 452 def siblings return nil if isRoot? if block_given? for sibling in parent.children yield sibling if sibling != self end else siblings = [] parent.children {|my_sibling| siblings << my_sibling if my_sibling != self} siblings end end
Returns the total number of nodes in this (sub)tree, including the receiver node.
Size of the tree is defined as:
Total number nodes in the subtree including the receiver node.
# File lib/tree.rb, line 369 def size @children.inject(1) {|sum, node| sum + node.size} end
Print the string representation of this node. This is primary for debugging purposes.
# File lib/tree.rb, line 153 def to_s "Node Name: #{@name}" + " Content: " + (@content || "<Empty>") + " Parent: " + (isRoot?() ? "<None>" : @parent.name) + " Children: #{@children.length}" + " Total Nodes: #{size()}" end