jro_apps/redmine Files · vendor/gems/rubytree-0.5.2/lib/tree/binarytree.rb

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

Download file

             binarytree.rb
        
                    131 lines
            
             | 4.5 KiB
            
                | text/x-ruby
            
             |
                RubyLexer
            
             / vendor / gems / rubytree-0.5.2 / lib / tree / binarytree.rb
          
                    History
                
                 |
                  Source
                 | Raw
                 |Copy content
                 |Copy permalink

        Eric Davis
    
Converted Menus to a Tree structure to allow submenus....

              r2976
            
      # binarytree.rb

      #

      # $Revision: 1.5 $ by $Author: anupamsg $

      # $Name:  $

      #

      # = binarytree.rb - Binary 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) 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.

      #

      require 'tree'

      module Tree

        # Provides a Binary tree implementation. This tree node allows only two child

        # nodes (left and right childs). It also provides direct access to the left

        # and right children, including assignment to the same.

        class BinaryTreeNode < TreeNode

          # Adds the specified child node to the receiver node.  The child node's

          # parent is set to be the receiver.  The child nodes are added in the order

          # of addition, i.e., the first child added becomes the left node, and the

          # second child will be the second node.

          # If only one child is present, then this will be the left child.

          def add(child)

            raise "Already has two child nodes" if @children.size == 2

            super(child)

          end

          # Returns the left child node. Note that

          # left Child == first Child

          def leftChild

            children.first

          end

          # Returns the right child node. Note that

          # right child == last child unless there is only one child.

          # Returns nil if the right child does not exist.

          def rightChild

            children[1]

          end

          # Sets the left child. If a previous child existed, it is replaced.

          def leftChild=(child)

            @children[0] = child

            @childrenHash[child.name] = child if child # Assign the name mapping

          end

          # Sets the right child. If a previous child existed, it is replaced.

          def rightChild=(child)

            @children[1] = child

            @childrenHash[child.name] = child if child # Assign the name mapping

          end

          # Returns true if this is the left child of its parent. Always returns false

          # if this is the root node.

          def isLeftChild?

            return nil if isRoot?

            self == parent.leftChild

          end

          # Returns true if this is the right child of its parent. Always returns false

          # if this is the root node.

          def isRightChild?

            return nil if isRoot?

            self == parent.rightChild

          end

          # Swaps the left and right children with each other

          def swap_children

            tempChild = leftChild

            self.leftChild= rightChild

            self.rightChild= tempChild

          end

        end

      end

      # $Log: binarytree.rb,v $

      # Revision 1.5  2007/12/18 23:11:29  anupamsg

      # Minor documentation changes in the binarytree class.

      #

      # Revision 1.4  2007/08/30 22:08:58  anupamsg

      # Added a new swap_children method for Binary Tree. Also added minor

      # documentation and test updates.

      #

      # Revision 1.3  2007/07/21 03:24:25  anupamsg

      # Minor edits to parameter names. User visible functionality does not change.

      #

      # Revision 1.2  2007/07/18 20:15:06  anupamsg

      # Added two predicate methods in BinaryTreeNode to determine whether a node

      # is a left or a right node.

      #

      # Revision 1.1  2007/07/18 19:33:27  anupamsg

      # Added a new binary tree implementation.

      #

	Site-wide shortcuts
/	Use quick search box
g h	Goto home page
g g	Goto my private gists page
g G	Goto my public gists page
g 0-9	Goto bookmarked items from 0-9
n r	New repository page
n g	New gist page

	Repositories
g s	Goto summary page
g c	Goto changelog page
g f	Goto files page
g F	Goto files page with file search activated
g p	Goto pull requests page
g o	Goto repository settings
g O	Goto repository access permissions settings
t s	Toggle sidebar on some pages

Eric Davis Converted Menus to a Tree structure to allow submenus....	r2976	# binarytree.rb
		#
		# $Revision: 1.5 $ by $Author: anupamsg $
		# $Name: $
		#
		# = binarytree.rb - Binary 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) 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.
		#

		require 'tree'

		module Tree

		# Provides a Binary tree implementation. This tree node allows only two child
		# nodes (left and right childs). It also provides direct access to the left
		# and right children, including assignment to the same.
		class BinaryTreeNode < TreeNode

		# Adds the specified child node to the receiver node. The child node's
		# parent is set to be the receiver. The child nodes are added in the order
		# of addition, i.e., the first child added becomes the left node, and the
		# second child will be the second node.
		# If only one child is present, then this will be the left child.
		def add(child)
		raise "Already has two child nodes" if @children.size == 2

		super(child)
		end

		# Returns the left child node. Note that
		# left Child == first Child
		def leftChild
		children.first
		end

		# Returns the right child node. Note that
		# right child == last child unless there is only one child.
		# Returns nil if the right child does not exist.
		def rightChild
		children[1]
		end

		# Sets the left child. If a previous child existed, it is replaced.
		def leftChild=(child)
		@children[0] = child
		@childrenHash[child.name] = child if child # Assign the name mapping
		end

		# Sets the right child. If a previous child existed, it is replaced.
		def rightChild=(child)
		@children[1] = child
		@childrenHash[child.name] = child if child # Assign the name mapping
		end

		# Returns true if this is the left child of its parent. Always returns false
		# if this is the root node.
		def isLeftChild?
		return nil if isRoot?
		self == parent.leftChild
		end

		# Returns true if this is the right child of its parent. Always returns false
		# if this is the root node.
		def isRightChild?
		return nil if isRoot?
		self == parent.rightChild
		end

		# Swaps the left and right children with each other
		def swap_children
		tempChild = leftChild
		self.leftChild= rightChild
		self.rightChild= tempChild
		end
		end

		end

		# $Log: binarytree.rb,v $
		# Revision 1.5 2007/12/18 23:11:29 anupamsg
		# Minor documentation changes in the binarytree class.
		#
		# Revision 1.4 2007/08/30 22:08:58 anupamsg
		# Added a new swap_children method for Binary Tree. Also added minor
		# documentation and test updates.
		#
		# Revision 1.3 2007/07/21 03:24:25 anupamsg
		# Minor edits to parameter names. User visible functionality does not change.
		#
		# Revision 1.2 2007/07/18 20:15:06 anupamsg
		# Added two predicate methods in BinaryTreeNode to determine whether a node
		# is a left or a right node.
		#
		# Revision 1.1 2007/07/18 19:33:27 anupamsg
		# Added a new binary tree implementation.
		#