annotate .svn/pristine/d4/d4053288db720e7328efde6be5005ae9fef364cf.svn-base @ 1519:afce8026aaeb redmine-2.4-integration

Merge from branch "live"
author Chris Cannam
date Tue, 09 Sep 2014 09:34:53 +0100
parents cbb26bc654de
children
rev   line source
Chris@909 1 # binarytree.rb
Chris@909 2 #
Chris@909 3 # $Revision: 1.5 $ by $Author: anupamsg $
Chris@909 4 # $Name: $
Chris@909 5 #
Chris@909 6 # = binarytree.rb - Binary Tree implementation
Chris@909 7 #
Chris@909 8 # Provides a generic tree data structure with ability to
Chris@909 9 # store keyed node elements in the tree. The implementation
Chris@909 10 # mixes in the Enumerable module.
Chris@909 11 #
Chris@909 12 # Author:: Anupam Sengupta (anupamsg@gmail.com)
Chris@909 13 #
Chris@909 14
Chris@909 15 # Copyright (c) 2007 Anupam Sengupta
Chris@909 16 #
Chris@909 17 # All rights reserved.
Chris@909 18 #
Chris@909 19 # Redistribution and use in source and binary forms, with or without modification,
Chris@909 20 # are permitted provided that the following conditions are met:
Chris@909 21 #
Chris@909 22 # - Redistributions of source code must retain the above copyright notice, this
Chris@909 23 # list of conditions and the following disclaimer.
Chris@909 24 #
Chris@909 25 # - Redistributions in binary form must reproduce the above copyright notice, this
Chris@909 26 # list of conditions and the following disclaimer in the documentation and/or
Chris@909 27 # other materials provided with the distribution.
Chris@909 28 #
Chris@909 29 # - Neither the name of the organization nor the names of its contributors may
Chris@909 30 # be used to endorse or promote products derived from this software without
Chris@909 31 # specific prior written permission.
Chris@909 32 #
Chris@909 33 # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
Chris@909 34 # AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
Chris@909 35 # IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
Chris@909 36 # DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
Chris@909 37 # ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
Chris@909 38 # (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
Chris@909 39 # LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
Chris@909 40 # ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
Chris@909 41 # (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
Chris@909 42 # SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
Chris@909 43 #
Chris@909 44
Chris@909 45 require 'tree'
Chris@909 46
Chris@909 47 module Tree
Chris@909 48
Chris@909 49 # Provides a Binary tree implementation. This tree node allows only two child
Chris@909 50 # nodes (left and right childs). It also provides direct access to the left
Chris@909 51 # and right children, including assignment to the same.
Chris@909 52 class BinaryTreeNode < TreeNode
Chris@909 53
Chris@909 54 # Adds the specified child node to the receiver node. The child node's
Chris@909 55 # parent is set to be the receiver. The child nodes are added in the order
Chris@909 56 # of addition, i.e., the first child added becomes the left node, and the
Chris@909 57 # second child will be the second node.
Chris@909 58 # If only one child is present, then this will be the left child.
Chris@909 59 def add(child)
Chris@909 60 raise "Already has two child nodes" if @children.size == 2
Chris@909 61
Chris@909 62 super(child)
Chris@909 63 end
Chris@909 64
Chris@909 65 # Returns the left child node. Note that
Chris@909 66 # left Child == first Child
Chris@909 67 def leftChild
Chris@909 68 children.first
Chris@909 69 end
Chris@909 70
Chris@909 71 # Returns the right child node. Note that
Chris@909 72 # right child == last child unless there is only one child.
Chris@909 73 # Returns nil if the right child does not exist.
Chris@909 74 def rightChild
Chris@909 75 children[1]
Chris@909 76 end
Chris@909 77
Chris@909 78 # Sets the left child. If a previous child existed, it is replaced.
Chris@909 79 def leftChild=(child)
Chris@909 80 @children[0] = child
Chris@909 81 @childrenHash[child.name] = child if child # Assign the name mapping
Chris@909 82 end
Chris@909 83
Chris@909 84 # Sets the right child. If a previous child existed, it is replaced.
Chris@909 85 def rightChild=(child)
Chris@909 86 @children[1] = child
Chris@909 87 @childrenHash[child.name] = child if child # Assign the name mapping
Chris@909 88 end
Chris@909 89
Chris@909 90 # Returns true if this is the left child of its parent. Always returns false
Chris@909 91 # if this is the root node.
Chris@909 92 def isLeftChild?
Chris@909 93 return nil if isRoot?
Chris@909 94 self == parent.leftChild
Chris@909 95 end
Chris@909 96
Chris@909 97 # Returns true if this is the right child of its parent. Always returns false
Chris@909 98 # if this is the root node.
Chris@909 99 def isRightChild?
Chris@909 100 return nil if isRoot?
Chris@909 101 self == parent.rightChild
Chris@909 102 end
Chris@909 103
Chris@909 104 # Swaps the left and right children with each other
Chris@909 105 def swap_children
Chris@909 106 tempChild = leftChild
Chris@909 107 self.leftChild= rightChild
Chris@909 108 self.rightChild= tempChild
Chris@909 109 end
Chris@909 110 end
Chris@909 111
Chris@909 112 end
Chris@909 113
Chris@909 114 # $Log: binarytree.rb,v $
Chris@909 115 # Revision 1.5 2007/12/18 23:11:29 anupamsg
Chris@909 116 # Minor documentation changes in the binarytree class.
Chris@909 117 #
Chris@909 118 # Revision 1.4 2007/08/30 22:08:58 anupamsg
Chris@909 119 # Added a new swap_children method for Binary Tree. Also added minor
Chris@909 120 # documentation and test updates.
Chris@909 121 #
Chris@909 122 # Revision 1.3 2007/07/21 03:24:25 anupamsg
Chris@909 123 # Minor edits to parameter names. User visible functionality does not change.
Chris@909 124 #
Chris@909 125 # Revision 1.2 2007/07/18 20:15:06 anupamsg
Chris@909 126 # Added two predicate methods in BinaryTreeNode to determine whether a node
Chris@909 127 # is a left or a right node.
Chris@909 128 #
Chris@909 129 # Revision 1.1 2007/07/18 19:33:27 anupamsg
Chris@909 130 # Added a new binary tree implementation.
Chris@909 131 #