Chris@909: # tree.rb
Chris@909: #
Chris@909: # $Revision: 1.29 $ by $Author: anupamsg $
Chris@909: # $Name:  $
Chris@909: #
Chris@909: # = tree.rb - Generic Multi-way Tree implementation
Chris@909: #
Chris@909: # Provides a generic tree data structure with ability to
Chris@909: # store keyed node elements in the tree. The implementation
Chris@909: # mixes in the Enumerable module.
Chris@909: #
Chris@909: # Author:: Anupam Sengupta (anupamsg@gmail.com)
Chris@909: #
Chris@909: 
Chris@909: # Copyright (c) 2006, 2007 Anupam Sengupta
Chris@909: #
Chris@909: # All rights reserved.
Chris@909: #
Chris@909: # Redistribution and use in source and binary forms, with or without modification,
Chris@909: # are permitted provided that the following conditions are met:
Chris@909: #
Chris@909: # - Redistributions of source code must retain the above copyright notice, this
Chris@909: #   list of conditions and the following disclaimer.
Chris@909: #
Chris@909: # - Redistributions in binary form must reproduce the above copyright notice, this
Chris@909: #   list of conditions and the following disclaimer in the documentation and/or
Chris@909: #   other materials provided with the distribution.
Chris@909: #
Chris@909: # - Neither the name of the organization nor the names of its contributors may
Chris@909: #   be used to endorse or promote products derived from this software without
Chris@909: #   specific prior written permission.
Chris@909: #
Chris@909: #   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
Chris@909: # AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
Chris@909: # IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
Chris@909: # DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
Chris@909: # ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
Chris@909: # (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
Chris@909: # LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
Chris@909: # ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
Chris@909: # (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
Chris@909: # SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
Chris@909: #
Chris@909: 
Chris@909: # This module provides a TreeNode class which is the primary class for all
Chris@909: # nodes represented in the Tree.
Chris@909: # This module mixes in the Enumerable module.
Chris@909: module Tree
Chris@909: 
Chris@909:   # Rubytree Package Version
Chris@909:   VERSION = '0.5.2'
Chris@909: 
Chris@909:   # == TreeNode Class Description
Chris@909:   #
Chris@909:   # The node class for the tree representation. the nodes are named and have a
Chris@909:   # place-holder for the node data (i.e., the `content' of the node). The node
Chris@909:   # names are expected to be unique.  In addition, the node provides navigation
Chris@909:   # methods to traverse the tree.
Chris@909:   #
Chris@909:   # The nodes can have any number of child nodes attached to it. Note that while
Chris@909:   # this implementation does not support directed graphs, the class itself makes
Chris@909:   # no restrictions on associating a node's CONTENT with multiple parent nodes.
Chris@909:   #
Chris@909:   #
Chris@909:   # == Example
Chris@909:   #
Chris@909:   #  The following code-snippet implements this tree structure:
Chris@909:   #
Chris@909:   #                    +------------+
Chris@909:   #                    |    ROOT    |
Chris@909:   #                    +-----+------+
Chris@909:   #            +-------------+------------+
Chris@909:   #            |                          |
Chris@909:   #    +-------+-------+          +-------+-------+
Chris@909:   #    |  CHILD 1      |          |  CHILD 2      |
Chris@909:   #    +-------+-------+          +---------------+
Chris@909:   #            |
Chris@909:   #            |
Chris@909:   #    +-------+-------+
Chris@909:   #    | GRANDCHILD 1  |
Chris@909:   #    +---------------+
Chris@909:   #
Chris@909:   # require 'tree'
Chris@909:   #
Chris@909:   # myTreeRoot = Tree::TreeNode.new("ROOT", "Root Content")
Chris@909:   #
Chris@909:   # myTreeRoot << Tree::TreeNode.new("CHILD1", "Child1 Content") << Tree::TreeNode.new("GRANDCHILD1", "GrandChild1 Content")
Chris@909:   #
Chris@909:   # myTreeRoot << Tree::TreeNode.new("CHILD2", "Child2 Content")
Chris@909:   #
Chris@909:   # myTreeRoot.printTree
Chris@909:   #
Chris@909:   # child1 = myTreeRoot["CHILD1"]
Chris@909:   #
Chris@909:   # grandChild1 = myTreeRoot["CHILD1"]["GRANDCHILD1"]
Chris@909:   #
Chris@909:   # siblingsOfChild1Array = child1.siblings
Chris@909:   #
Chris@909:   # immediateChildrenArray = myTreeRoot.children
Chris@909:   #
Chris@909:   # # Process all nodes
Chris@909:   #
Chris@909:   # myTreeRoot.each { |node| node.content.reverse }
Chris@909:   #
Chris@909:   # myTreeRoot.remove!(child1) # Remove the child
Chris@909:   class TreeNode
Chris@909:     include Enumerable
Chris@909: 
Chris@909:     attr_reader :content, :name, :parent
Chris@909:     attr_writer :content
Chris@909: 
Chris@909:     # Constructor which expects the name of the node
Chris@909:     #
Chris@909:     # Name of the node is expected to be unique across the
Chris@909:     # tree.
Chris@909:     #
Chris@909:     # The content can be of any type, and is defaulted to _nil_.
Chris@909:     def initialize(name, content = nil)
Chris@909:       raise "Node name HAS to be provided" if name == nil
Chris@909:       @name = name
Chris@909:       @content = content
Chris@909:       self.setAsRoot!
Chris@909: 
Chris@909:       @childrenHash = Hash.new
Chris@909:       @children = []
Chris@909:     end
Chris@909: 
Chris@909:     # Returns a copy of this node, with the parent and children links removed.
Chris@909:     def detached_copy
Chris@909:       Tree::TreeNode.new(@name, @content ? @content.clone : nil)
Chris@909:     end
Chris@909: 
Chris@909:     # Print the string representation of this node.
Chris@909:     def to_s
Chris@909:       "Node Name: #{@name}" +
Chris@909:         " Content: " + (@content || "<Empty>") +
Chris@909:         " Parent: " + (isRoot?()  ? "<None>" : @parent.name) +
Chris@909:         " Children: #{@children.length}" +
Chris@909:         " Total Nodes: #{size()}"
Chris@909:     end
Chris@909: 
Chris@909:     # Returns an array of ancestors in reversed order (the first element is the
Chris@909:     # immediate parent). Returns nil if this is a root node.
Chris@909:     def parentage
Chris@909:       return nil if isRoot?
Chris@909: 
Chris@909:       parentageArray = []
Chris@909:       prevParent = self.parent
Chris@909:       while (prevParent)
Chris@909:         parentageArray << prevParent
Chris@909:         prevParent = prevParent.parent
Chris@909:       end
Chris@909: 
Chris@909:       parentageArray
Chris@909:     end
Chris@909: 
Chris@909:     # Protected method to set the parent node.
Chris@909:     # This method should NOT be invoked by client code.
Chris@909:     def parent=(parent)
Chris@909:       @parent = parent
Chris@909:     end
Chris@909: 
Chris@909:     # Convenience synonym for TreeNode#add method.  This method allows a convenient
Chris@909:     # method to add children hierarchies in the tree.
Chris@909:     #
Chris@909:     # E.g. root << child << grand_child
Chris@909:     def <<(child)
Chris@909:       add(child)
Chris@909:     end
Chris@909: 
Chris@909:     # Adds the specified child node to the receiver node.  The child node's
Chris@909:     # parent is set to be the receiver.  The child is added as the last child in
Chris@909:     # the current list of children for the receiver node.
Chris@909:     def add(child)
Chris@909:       raise "Child already added" if @childrenHash.has_key?(child.name)
Chris@909: 
Chris@909:       @childrenHash[child.name]  = child
Chris@909:       @children << child
Chris@909:       child.parent = self
Chris@909:       return child
Chris@909: 
Chris@909:     end
Chris@909: 
Chris@909:     # Removes the specified child node from the receiver node.  The removed
Chris@909:     # children nodes are orphaned but available if an alternate reference
Chris@909:     # exists.
Chris@909:     #
Chris@909:     # Returns the child node.
Chris@909:     def remove!(child)
Chris@909:       @childrenHash.delete(child.name)
Chris@909:       @children.delete(child)
Chris@909:       child.setAsRoot! unless child == nil
Chris@909:       return child
Chris@909:     end
Chris@909: 
Chris@909:     # Removes this node from its parent. If this is the root node, then does
Chris@909:     # nothing.
Chris@909:     def removeFromParent!
Chris@909:       @parent.remove!(self) unless isRoot?
Chris@909:     end
Chris@909: 
Chris@909:     # Removes all children from the receiver node.
Chris@909:     def removeAll!
Chris@909:       for child in @children
Chris@909:         child.setAsRoot!
Chris@909:       end
Chris@909:       @childrenHash.clear
Chris@909:       @children.clear
Chris@909:       self
Chris@909:     end
Chris@909: 
Chris@909:     # Indicates whether this node has any associated content.
Chris@909:     def hasContent?
Chris@909:       @content != nil
Chris@909:     end
Chris@909: 
Chris@909:     # Protected method which sets this node as a root node.
Chris@909:     def setAsRoot!
Chris@909:       @parent = nil
Chris@909:     end
Chris@909: 
Chris@909:     # Indicates whether this node is a root node. Note that
Chris@909:     # orphaned children will also be reported as root nodes.
Chris@909:     def isRoot?
Chris@909:       @parent == nil
Chris@909:     end
Chris@909: 
Chris@909:     # Indicates whether this node has any immediate child nodes.
Chris@909:     def hasChildren?
Chris@909:       @children.length != 0
Chris@909:     end
Chris@909: 
Chris@909:     # Indicates whether this node is a 'leaf' - i.e., one without
Chris@909:     # any children
Chris@909:     def isLeaf?
Chris@909:       !hasChildren?
Chris@909:     end
Chris@909: 
Chris@909:     # Returns an array of all the immediate children.  If a block is given,
Chris@909:     # yields each child node to the block.
Chris@909:     def children
Chris@909:       if block_given?
Chris@909:         @children.each {|child| yield child}
Chris@909:       else
Chris@909:         @children
Chris@909:       end
Chris@909:     end
Chris@909: 
Chris@909:     # Returns the first child of this node. Will return nil if no children are
Chris@909:     # present.
Chris@909:     def firstChild
Chris@909:       children.first
Chris@909:     end
Chris@909: 
Chris@909:     # Returns the last child of this node. Will return nil if no children are
Chris@909:     # present.
Chris@909:     def lastChild
Chris@909:       children.last
Chris@909:     end
Chris@909: 
Chris@909:     # Returns every node (including the receiver node) from the tree to the
Chris@909:     # specified block. The traversal is depth first and from left to right in
Chris@909:     # pre-ordered sequence.
Chris@909:     def each &block
Chris@909:       yield self
Chris@909:       children { |child| child.each(&block) }
Chris@909:     end
Chris@909: 
Chris@909:     # Traverses the tree in a pre-ordered sequence. This is equivalent to
Chris@909:     # TreeNode#each
Chris@909:     def preordered_each &block
Chris@909:       each(&block)
Chris@909:     end
Chris@909: 
Chris@909:     # Performs breadth first traversal of the tree rooted at this node. The
Chris@909:     # traversal in a given level is from left to right.
Chris@909:     def breadth_each &block
Chris@909:       node_queue = [self]       # Create a queue with self as the initial entry
Chris@909: 
Chris@909:       # Use a queue to do breadth traversal
Chris@909:       until node_queue.empty?
Chris@909:         node_to_traverse = node_queue.shift
Chris@909:         yield node_to_traverse
Chris@909:         # Enqueue the children from left to right.
Chris@909:         node_to_traverse.children { |child| node_queue.push child }
Chris@909:       end
Chris@909:     end
Chris@909: 
Chris@909:     # Yields all leaf nodes from this node to the specified block. May yield
Chris@909:     # this node as well if this is a leaf node.  Leaf traversal depth first and
Chris@909:     # left to right.
Chris@909:     def each_leaf &block
Chris@909:       self.each { |node| yield(node) if node.isLeaf? }
Chris@909:     end
Chris@909: 
Chris@909:     # Returns the requested node from the set of immediate children.
Chris@909:     #
Chris@909:     # If the parameter is _numeric_, then the in-sequence array of children is
Chris@909:     # accessed (see Tree#children).  If the parameter is not _numeric_, then it
Chris@909:     # is assumed to be the *name* of the child node to be returned.
Chris@909:     def [](name_or_index)
Chris@909:       raise "Name_or_index needs to be provided" if name_or_index == nil
Chris@909: 
Chris@909:       if name_or_index.kind_of?(Integer)
Chris@909:         @children[name_or_index]
Chris@909:       else
Chris@909:         @childrenHash[name_or_index]
Chris@909:       end
Chris@909:     end
Chris@909: 
Chris@909:     # Returns the total number of nodes in this tree, rooted at the receiver
Chris@909:     # node.
Chris@909:     def size
Chris@909:       @children.inject(1) {|sum, node| sum + node.size}
Chris@909:     end
Chris@909: 
Chris@909:     # Convenience synonym for Tree#size
Chris@909:     def length
Chris@909:       size()
Chris@909:     end
Chris@909: 
Chris@909:     # Pretty prints the tree starting with the receiver node.
Chris@909:     def printTree(level = 0)
Chris@909: 
Chris@909:       if isRoot?
Chris@909:         print "*"
Chris@909:       else
Chris@909:         print "|" unless parent.isLastSibling?
Chris@909:         print(' ' * (level - 1) * 4)
Chris@909:         print(isLastSibling? ? "+" : "|")
Chris@909:         print "---"
Chris@909:         print(hasChildren? ? "+" : ">")
Chris@909:       end
Chris@909: 
Chris@909:       puts " #{name}"
Chris@909: 
Chris@909:       children { |child| child.printTree(level + 1)}
Chris@909:     end
Chris@909: 
Chris@909:     # Returns the root for this tree. Root's root is itself.
Chris@909:     def root
Chris@909:       root = self
Chris@909:       root = root.parent while !root.isRoot?
Chris@909:       root
Chris@909:     end
Chris@909: 
Chris@909:     # Returns the first sibling for this node. If this is the root node, returns
Chris@909:     # itself.
Chris@909:     def firstSibling
Chris@909:       if isRoot?
Chris@909:         self
Chris@909:       else
Chris@909:         parent.children.first
Chris@909:       end
Chris@909:     end
Chris@909: 
Chris@909:     # Returns true if this node is the first sibling.
Chris@909:     def isFirstSibling?
Chris@909:       firstSibling == self
Chris@909:     end
Chris@909: 
Chris@909:     # Returns the last sibling for this node.  If this node is the root, returns
Chris@909:     # itself.
Chris@909:     def lastSibling
Chris@909:       if isRoot?
Chris@909:         self
Chris@909:       else
Chris@909:         parent.children.last
Chris@909:       end
Chris@909:     end
Chris@909: 
Chris@909:     # Returns true if his node is the last sibling
Chris@909:     def isLastSibling?
Chris@909:       lastSibling == self
Chris@909:     end
Chris@909: 
Chris@909:     # Returns an array of siblings for this node.
Chris@909:     # If a block is provided, yields each of the sibling
Chris@909:     # nodes to the block. The root always has nil siblings.
Chris@909:     def siblings
Chris@909:       return nil if isRoot?
Chris@909:       if block_given?
Chris@909:         for sibling in parent.children
Chris@909:           yield sibling if sibling != self
Chris@909:         end
Chris@909:       else
Chris@909:         siblings = []
Chris@909:         parent.children {|sibling| siblings << sibling if sibling != self}
Chris@909:         siblings
Chris@909:       end
Chris@909:     end
Chris@909: 
Chris@909:     # Returns true if this node is the only child of its parent
Chris@909:     def isOnlyChild?
Chris@909:       parent.children.size == 1
Chris@909:     end
Chris@909: 
Chris@909:     # Returns the next sibling for this node. Will return nil if no subsequent
Chris@909:     # node is present.
Chris@909:     def nextSibling
Chris@909:       if myidx = parent.children.index(self)
Chris@909:         parent.children.at(myidx + 1)
Chris@909:       end
Chris@909:     end
Chris@909: 
Chris@909:     # Returns the previous sibling for this node. Will return nil if no
Chris@909:     # subsequent node is present.
Chris@909:     def previousSibling
Chris@909:       if myidx = parent.children.index(self)
Chris@909:         parent.children.at(myidx - 1) if myidx > 0
Chris@909:       end
Chris@909:     end
Chris@909: 
Chris@909:     # Provides a comparision operation for the nodes. Comparision
Chris@909:     # is based on the natural character-set ordering for the
Chris@909:     # node names.
Chris@909:     def <=>(other)
Chris@909:       return +1 if other == nil
Chris@909:       self.name <=> other.name
Chris@909:     end
Chris@909: 
Chris@909:     # Freezes all nodes in the tree
Chris@909:     def freezeTree!
Chris@909:       each {|node| node.freeze}
Chris@909:     end
Chris@909: 
Chris@909:     # Creates the marshal-dump represention of the tree rooted at this node.
Chris@909:     def marshal_dump
Chris@909:       self.collect { |node| node.createDumpRep }
Chris@909:     end
Chris@909: 
Chris@909:     # Creates a dump representation and returns the same as a hash.
Chris@909:     def createDumpRep
Chris@909:       { :name => @name, :parent => (isRoot? ? nil : @parent.name),  :content => Marshal.dump(@content)}
Chris@909:     end
Chris@909: 
Chris@909:     # Loads a marshalled dump of the tree and returns the root node of the
Chris@909:     # reconstructed tree. See the Marshal class for additional details.
Chris@909:     def marshal_load(dumped_tree_array)
Chris@909:       nodes = { }
Chris@909:       for node_hash in dumped_tree_array do
Chris@909:         name        = node_hash[:name]
Chris@909:         parent_name = node_hash[:parent]
Chris@909:         content     = Marshal.load(node_hash[:content])
Chris@909: 
Chris@909:         if parent_name then
Chris@909:           nodes[name] = current_node = Tree::TreeNode.new(name, content)
Chris@909:           nodes[parent_name].add current_node
Chris@909:         else
Chris@909:           # This is the root node, hence initialize self.
Chris@909:           initialize(name, content)
Chris@909: 
Chris@909:           nodes[name] = self    # Add self to the list of nodes
Chris@909:          end
Chris@909:       end
Chris@909:     end
Chris@909: 
Chris@909:     # Returns depth of the tree from this node. A single leaf node has a
Chris@909:     # depth of 1.
Chris@909:     def depth
Chris@909:       return 1 if isLeaf?
Chris@909:       1 + @children.collect { |child| child.depth }.max
Chris@909:     end
Chris@909: 
Chris@909:     # Returns breadth of the tree at this node level. A single node has a
Chris@909:     # breadth of 1.
Chris@909:     def breadth
Chris@909:       return 1 if isRoot?
Chris@909:       parent.children.size
Chris@909:     end
Chris@909: 
Chris@909:     protected :parent=, :setAsRoot!, :createDumpRep
Chris@909: 
Chris@909:   end
Chris@909: end
Chris@909: 
Chris@909: # $Log: tree.rb,v $
Chris@909: # Revision 1.29  2007/12/22 00:28:59  anupamsg
Chris@909: # Added more test cases, and enabled ZenTest compatibility.
Chris@909: #
Chris@909: # Revision 1.28  2007/12/20 03:19:33  anupamsg
Chris@909: # * README (Module): Modified the install instructions from source.
Chris@909: # (Module): Updated the minor version number.
Chris@909: #
Chris@909: # Revision 1.27  2007/12/20 03:00:03  anupamsg
Chris@909: # Minor code changes. Removed self_initialize from the protected methods' list.
Chris@909: #
Chris@909: # Revision 1.26  2007/12/20 02:50:04  anupamsg
Chris@909: # (Tree::TreeNode): Removed the spurious self_initialize from the protected list.
Chris@909: #
Chris@909: # Revision 1.25  2007/12/19 20:28:05  anupamsg
Chris@909: # Removed the unnecesary self_initialize method.
Chris@909: #
Chris@909: # Revision 1.24  2007/12/19 06:39:17  anupamsg
Chris@909: # Removed the unnecessary field and record separator constants.  Also updated the
Chris@909: # history.txt file.
Chris@909: #
Chris@909: # Revision 1.23  2007/12/19 06:25:00  anupamsg
Chris@909: # (Tree::TreeNode): Minor fix to the comments.  Also fixed the private/protected
Chris@909: # scope issue with the createDumpRep method.
Chris@909: #
Chris@909: # Revision 1.22  2007/12/19 06:22:03  anupamsg
Chris@909: # Updated the marshalling logic to correctly handle non-string content. This
Chris@909: # should fix the bug # 15614 ("When dumping with an Object as the content, you get
Chris@909: # a delimiter collision")
Chris@909: #
Chris@909: # Revision 1.21  2007/12/19 02:24:17  anupamsg
Chris@909: # Updated the marshalling logic to handle non-string contents on the nodes.
Chris@909: #
Chris@909: # Revision 1.20  2007/10/10 08:42:57  anupamsg
Chris@909: # Release 0.4.3
Chris@909: #
Chris@909: # Revision 1.19  2007/08/31 01:16:27  anupamsg
Chris@909: # Added breadth and pre-order traversals for the tree. Also added a method
Chris@909: # to return the detached copy of a node from the tree.
Chris@909: #
Chris@909: # Revision 1.18  2007/07/21 05:14:44  anupamsg
Chris@909: # Added a VERSION constant to the Tree module,
Chris@909: # and using the same in the Rakefile.
Chris@909: #
Chris@909: # Revision 1.17  2007/07/21 03:24:25  anupamsg
Chris@909: # Minor edits to parameter names. User visible functionality does not change.
Chris@909: #
Chris@909: # Revision 1.16  2007/07/18 23:38:55  anupamsg
Chris@909: # Minor updates to tree.rb
Chris@909: #
Chris@909: # Revision 1.15  2007/07/18 22:11:50  anupamsg
Chris@909: # Added depth and breadth methods for the TreeNode.
Chris@909: #
Chris@909: # Revision 1.14  2007/07/18 19:33:27  anupamsg
Chris@909: # Added a new binary tree implementation.
Chris@909: #
Chris@909: # Revision 1.13  2007/07/18 07:17:34  anupamsg
Chris@909: # Fixed a  issue where TreeNode.ancestors was shadowing Module.ancestors. This method
Chris@909: # has been renamed to TreeNode.parentage.
Chris@909: #
Chris@909: # Revision 1.12  2007/07/17 03:39:28  anupamsg
Chris@909: # Moved the CVS Log keyword to end of the files.
Chris@909: #