SoundSoftware Code Site

# 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.

#