Chris@0: # binarytree.rb
Chris@0: #
Chris@0: # $Revision: 1.5 $ by $Author: anupamsg $
Chris@0: # $Name:  $
Chris@0: #
Chris@0: # = binarytree.rb - Binary Tree implementation
Chris@0: #
Chris@0: # Provides a generic tree data structure with ability to
Chris@0: # store keyed node elements in the tree. The implementation
Chris@0: # mixes in the Enumerable module.
Chris@0: #
Chris@0: # Author:: Anupam Sengupta (anupamsg@gmail.com)
Chris@0: #
Chris@0: 
Chris@0: # Copyright (c) 2007 Anupam Sengupta
Chris@0: #
Chris@0: # All rights reserved.
Chris@0: #
Chris@0: # Redistribution and use in source and binary forms, with or without modification,
Chris@0: # are permitted provided that the following conditions are met:
Chris@0: #
Chris@0: # - Redistributions of source code must retain the above copyright notice, this
Chris@0: #   list of conditions and the following disclaimer.
Chris@0: #
Chris@0: # - Redistributions in binary form must reproduce the above copyright notice, this
Chris@0: #   list of conditions and the following disclaimer in the documentation and/or
Chris@0: #   other materials provided with the distribution.
Chris@0: #
Chris@0: # - Neither the name of the organization nor the names of its contributors may
Chris@0: #   be used to endorse or promote products derived from this software without
Chris@0: #   specific prior written permission.
Chris@0: #
Chris@0: #   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
Chris@0: # AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
Chris@0: # IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
Chris@0: # DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
Chris@0: # ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
Chris@0: # (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
Chris@0: # LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
Chris@0: # ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
Chris@0: # (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
Chris@0: # SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
Chris@0: #
Chris@0: 
Chris@0: require 'tree'
Chris@0: 
Chris@0: module Tree
Chris@0: 
Chris@0:   # Provides a Binary tree implementation. This tree node allows only two child
Chris@0:   # nodes (left and right childs). It also provides direct access to the left
Chris@0:   # and right children, including assignment to the same.
Chris@0:   class BinaryTreeNode < TreeNode
Chris@0: 
Chris@0:     # Adds the specified child node to the receiver node.  The child node's
Chris@0:     # parent is set to be the receiver.  The child nodes are added in the order
Chris@0:     # of addition, i.e., the first child added becomes the left node, and the
Chris@0:     # second child will be the second node.
Chris@0:     # If only one child is present, then this will be the left child.
Chris@0:     def add(child)
Chris@0:       raise "Already has two child nodes" if @children.size == 2
Chris@0: 
Chris@0:       super(child)
Chris@0:     end
Chris@0: 
Chris@0:     # Returns the left child node. Note that
Chris@0:     # left Child == first Child
Chris@0:     def leftChild
Chris@0:       children.first
Chris@0:     end
Chris@0: 
Chris@0:     # Returns the right child node. Note that
Chris@0:     # right child == last child unless there is only one child.
Chris@0:     # Returns nil if the right child does not exist.
Chris@0:     def rightChild
Chris@0:       children[1]
Chris@0:     end
Chris@0: 
Chris@0:     # Sets the left child. If a previous child existed, it is replaced.
Chris@0:     def leftChild=(child)
Chris@0:       @children[0] = child
Chris@0:       @childrenHash[child.name] = child if child # Assign the name mapping
Chris@0:     end
Chris@0: 
Chris@0:     # Sets the right child. If a previous child existed, it is replaced.
Chris@0:     def rightChild=(child)
Chris@0:       @children[1] = child
Chris@0:       @childrenHash[child.name] = child if child # Assign the name mapping
Chris@0:     end
Chris@0: 
Chris@0:     # Returns true if this is the left child of its parent. Always returns false
Chris@0:     # if this is the root node.
Chris@0:     def isLeftChild?
Chris@0:       return nil if isRoot?
Chris@0:       self == parent.leftChild
Chris@0:     end
Chris@0: 
Chris@0:     # Returns true if this is the right child of its parent. Always returns false
Chris@0:     # if this is the root node.
Chris@0:     def isRightChild?
Chris@0:       return nil if isRoot?
Chris@0:       self == parent.rightChild
Chris@0:     end
Chris@0: 
Chris@0:     # Swaps the left and right children with each other
Chris@0:     def swap_children
Chris@0:       tempChild = leftChild
Chris@0:       self.leftChild= rightChild
Chris@0:       self.rightChild= tempChild
Chris@0:     end
Chris@0:   end
Chris@0: 
Chris@0: end
Chris@0: 
Chris@0: # $Log: binarytree.rb,v $
Chris@0: # Revision 1.5  2007/12/18 23:11:29  anupamsg
Chris@0: # Minor documentation changes in the binarytree class.
Chris@0: #
Chris@0: # Revision 1.4  2007/08/30 22:08:58  anupamsg
Chris@0: # Added a new swap_children method for Binary Tree. Also added minor
Chris@0: # documentation and test updates.
Chris@0: #
Chris@0: # Revision 1.3  2007/07/21 03:24:25  anupamsg
Chris@0: # Minor edits to parameter names. User visible functionality does not change.
Chris@0: #
Chris@0: # Revision 1.2  2007/07/18 20:15:06  anupamsg
Chris@0: # Added two predicate methods in BinaryTreeNode to determine whether a node
Chris@0: # is a left or a right node.
Chris@0: #
Chris@0: # Revision 1.1  2007/07/18 19:33:27  anupamsg
Chris@0: # Added a new binary tree implementation.
Chris@0: #