The node class for the tree representation. the nodes are named and have a place-holder for the node data (i.e., the `content’ of the node). The node names are expected to be unique. In addition, the node provides navigation methods to traverse the tree.
The nodes can have any number of child nodes attached to it. Note that while this implementation does not support directed graphs, the class itself makes no restrictions on associating a node’s CONTENT with multiple parent nodes.
The following code-snippet implements this tree structure: +------------+ | ROOT | +-----+------+ +-------------+------------+ | | +-------+-------+ +-------+-------+ | CHILD 1 | | CHILD 2 | +-------+-------+ +---------------+ | | +-------+-------+ | GRANDCHILD 1 | +---------------+
require ‘tree’
myTreeRoot = ::new(“ROOT”, “Root Content”)
myTreeRoot << ::new(“CHILD1”, “Child1 Content”) << ::new(“GRANDCHILD1”, “GrandChild1 Content”)
myTreeRoot << ::new(“CHILD2”, “Child2 Content”)
myTreeRoot.printTree
child1 = myTreeRoot
grandChild1 = myTreeRoot[“GRANDCHILD1”]
siblingsOfChild1Array = child1.siblings
immediateChildrenArray = myTreeRoot.children
# Process all nodes
myTreeRoot.each { |node| node.content.reverse }
myTreeRoot.remove!(child1) # Remove the child
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, and is defaulted to nil.
# File lib/tree.rb, line 118 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 a convenient method to add children hierarchies in the tree.
E.g. root << child << grand_child
# File lib/tree.rb, line 167 def <<(child) add(child) end
Provides a comparision operation for the nodes. Comparision is based on the natural character-set ordering for the node names.
# File lib/tree.rb, line 417 def <=>(other) return +1 if other == nil self.name <=> other.name end
Returns the requested node from the set of immediate children.
If the parameter is numeric, then the in-sequence array of children is accessed (see Tree#children). If the parameter is not numeric, then it is assumed to be the name of the child node to be returned.
# File lib/tree.rb, line 301 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. The child node’s parent is set to be the receiver. The child is added as the last child in the current list of children for the receiver node.
# File lib/tree.rb, line 174 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 this node level. A single node has a breadth of 1.
# File lib/tree.rb, line 467 def breadth return 1 if isRoot? parent.children.size end
Performs breadth first traversal of the tree rooted at this node. The traversal in a given level is from left to right.
# File lib/tree.rb, line 277 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. If a block is given, yields each child node to the block.
# File lib/tree.rb, line 241 def children if block_given? @children.each {|child| yield child} else @children end end
Returns depth of the tree from this node. A single leaf node has a depth of 1.
# File lib/tree.rb, line 460 def depth return 1 if isLeaf? 1 + @children.collect { |child| child.depth }.max end
Returns a copy of this node, with the parent and children links removed.
# File lib/tree.rb, line 129 def detached_copy Tree::TreeNode.new(@name, @content ? @content.clone : nil) end
Returns every node (including the receiver node) from the tree to the specified block. The traversal is depth first and from left to right in pre-ordered sequence.
# File lib/tree.rb, line 264 def each &block yield self children { |child| child.each(&block) } end
Yields all leaf nodes from this node to the specified block. May yield this node as well if this is a leaf node. Leaf traversal depth first and left to right.
# File lib/tree.rb, line 292 def each_leaf &block self.each { |node| yield(node) if node.isLeaf? } end
Returns the first child of this node. Will return nil if no children are present.
# File lib/tree.rb, line 251 def firstChild children.first end
Returns the first sibling for this node. If this is the root node, returns itself.
# File lib/tree.rb, line 349 def firstSibling if isRoot? self else parent.children.first end end
Freezes all nodes in the tree
# File lib/tree.rb, line 423 def freezeTree! each {|node| node.freeze} end
Indicates whether this node has any immediate child nodes.
# File lib/tree.rb, line 229 def hasChildren? @children.length != 0 end
Indicates whether this node has any associated content.
# File lib/tree.rb, line 213 def hasContent? @content != nil end
Returns true if this node is the first sibling.
# File lib/tree.rb, line 358 def isFirstSibling? firstSibling == self end
Returns true if his node is the last sibling
# File lib/tree.rb, line 373 def isLastSibling? lastSibling == self end
Indicates whether this node is a ‘leaf’ - i.e., one without any children
# File lib/tree.rb, line 235 def isLeaf? !hasChildren? end
Returns true if this node is the only child of its parent
# File lib/tree.rb, line 394 def isOnlyChild? parent.children.size == 1 end
Indicates whether this node is a root node. Note that orphaned children will also be reported as root nodes.
# File lib/tree.rb, line 224 def isRoot? @parent == nil end
Returns the last child of this node. Will return nil if no children are present.
# File lib/tree.rb, line 257 def lastChild children.last end
Returns the last sibling for this node. If this node is the root, returns itself.
# File lib/tree.rb, line 364 def lastSibling if isRoot? self else parent.children.last end end
Convenience synonym for Tree#size
# File lib/tree.rb, line 318 def length size() end
Creates the marshal-dump represention of the tree rooted at this node.
# File lib/tree.rb, line 428 def marshal_dump self.collect { |node| node.createDumpRep } end
Loads a marshalled dump of the tree and returns the root node of the reconstructed tree. See the Marshal class for additional details.
# File lib/tree.rb, line 439 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 this node. Will return nil if no subsequent node is present.
# File lib/tree.rb, line 400 def nextSibling if myidx = parent.children.index(self) parent.children.at(myidx + 1) end end
Returns an array of ancestors in reversed order (the first element is the immediate parent). Returns nil if this is a root node.
# File lib/tree.rb, line 144 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 271 def preordered_each &block each(&block) end
Returns the previous sibling for this node. Will return nil if no subsequent node is present.
# File lib/tree.rb, line 408 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 323 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. The removed children nodes are orphaned but available if an alternate reference exists.
Returns the child node.
# File lib/tree.rb, line 189 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.
# File lib/tree.rb, line 203 def removeAll! for child in @children child.setAsRoot! end @childrenHash.clear @children.clear self end
Removes this node from its parent. If this is the root node, then does nothing.
# File lib/tree.rb, line 198 def removeFromParent! @parent.remove!(self) unless isRoot? end
Returns the root for this tree. Root’s root is itself.
# File lib/tree.rb, line 341 def root root = self root = root.parent while !root.isRoot? root end
Returns an array of siblings for this node. 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 380 def siblings return nil if isRoot? if block_given? for sibling in parent.children yield sibling if sibling != self end else siblings = [] parent.children {|sibling| siblings << sibling if sibling != self} siblings end end
Returns the total number of nodes in this tree, rooted at the receiver node.
# File lib/tree.rb, line 313 def size @children.inject(1) {|sum, node| sum + node.size} end
Print the string representation of this node.
# File lib/tree.rb, line 134 def to_s "Node Name: #{@name}" + " Content: " + (@content || "<Empty>") + " Parent: " + (isRoot?() ? "<None>" : @parent.name) + " Children: #{@children.length}" + " Total Nodes: #{size()}" end
Creates a dump representation and returns the same as a hash.
# File lib/tree.rb, line 433 def createDumpRep { :name => @name, :parent => (isRoot? ? nil : @parent.name), :content => Marshal.dump(@content)} end
Protected method to set the parent node. This method should NOT be invoked by client code.
# File lib/tree.rb, line 159 def parent=(parent) @parent = parent end
Protected method which sets this node as a root node.
# File lib/tree.rb, line 218 def setAsRoot! @parent = nil end