##// END OF EJS Templates
jro_apps » redmine
RSS
Replace the hardcoded "CodeRay" css class name for highlighted elements....
Replace the hardcoded "CodeRay" css class name for highlighted elements. git-svn-id: svn+ssh://rubyforge.org/var/svn/redmine/trunk@3585 e93f8b46-1217-0410-a6f0-8f06a7374b81
Eric Davis - - Load All Authors

File last commit:

r2976:1f06cf889990
r3471:ad487bf7cc4b
Show More
tree.rb
539 lines | 16.1 KiB | text/x-ruby | RubyLexer
/ vendor / gems / rubytree-0.5.2 / lib / tree.rb
History | Source | Raw |Copy content |Copy permalink
Eric Davis
Converted Menus to a Tree structure to allow submenus....
 r2976 # 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.
#