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