lib/tree/binarytree.rb
# binarytree.rb - This file is part of the RubyTree package.
#
# = binarytree.rb - An implementation of the binary tree data structure.
#
# Provides a binary tree data structure with ability to
# store two node elements as children at each node in the tree.
#
# Author:: Anupam Sengupta (anupamsg@gmail.com)
#
# Copyright (c) 2007-2022 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.
#
# frozen_string_literal: true
require_relative '../tree'
module Tree
# Provides a Binary tree implementation. This node allows only two child nodes
# (left and right child). It also provides direct access to the left or right
# child, including assignment to the same.
#
# This inherits from the {Tree::TreeNode} class.
#
# @author Anupam Sengupta
#
class BinaryTreeNode < TreeNode
# @!group Core Attributes
# @!attribute [rw] left_child
# Left child of the receiver node. Note that left Child == first Child.
#
# @return [Tree::BinaryTreeNode] The left most (or first) child.
#
# @see #right_child
def left_child
children.first
end
# @!attribute [rw] right_child
# Right child of the receiver node. Note that right child == last child
# unless there is only one child.
#
# Returns +nil+ if the right child does not exist.
#
# @return [Tree::BinaryTreeNode] The right child, or +nil+ if the right side
# child does not exist.
#
# @see #left_child
def right_child
children[1]
end
# @!attribute left_child?
# +true+ if the receiver node is the left child of its parent.
# Always returns +false+ if it is a root node.
#
# @return [Boolean] +true+ if this is the left child of its parent.
def left_child?
return false if root?
self == parent.left_child
end
alias is_left_child? left_child? # @todo: Aliased for eventual replacement
# @!attribute [r] right_child?
# +true+ if the receiver node is the right child of its parent.
# Always returns +false+ if it is a root node.
#
# @return [Boolean] +true+ if this is the right child of its parent.
def right_child?
return false if root?
self == parent.right_child
end
alias is_right_child? right_child? # @todo: Aliased for eventual replacement
# @!group Structure Modification
# 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 added will be the second
# node.
#
# If only one child is present, then this will be the left child.
#
# @param [Tree::BinaryTreeNode] child The child to add.
#
# @raise [ArgumentError] This exception is raised if two children are
# already present.
def add(child)
raise ArgumentError, 'Already has two child nodes' if @children.size == 2
super(child)
end
# Instantiate and insert child nodes from data in a Ruby +Hash+
#
# This method is used in conjunction with {Tree::TreeNode.from_hash} to
# provide a convenient way of building and inserting child nodes present
# in a Ruby hashes.
#
# This method will instantiate a {Tree::TreeNode} instance for each top-
# level key of the input hash, to be inserted as children of the receiver
# instance.
#
# Nested hashes are expected and further child nodes will be created and
# added accordingly. If a hash key is a single value that value will be
# used as the name for the node. If a hash key is an Array, both node
# name and content will be populated.
#
# A leaf element of the tree should be represented as a hash key with
# corresponding value nil or {}.
#
# @example
# root = Tree::TreeNode.new(:A, "Root content!")
# root.add_from_hash({:B => {:D => {}}, [:C, "C content!"] => {}})
#
# @param [Hash] hashed_subtree The hash of child subtrees.
#
# @raise [ArgumentError] This exception is raised if hash contains too
# many children.
# =>
# @raise [ArgumentError] This exception is raised if a non-hash is passed.
# @return [Array] Array of child nodes added
def add_from_hash(hashed_subtree)
raise ArgumentError, 'Too many children'\
if hashed_subtree.size + @children.size > 2
super(hashed_subtree)
end
# Performs in-order traversal (including this node).
#
# @yieldparam node [Tree::BinaryTreeNode] Each node (in-order).
#
# @return [Tree::BinaryTreeNode] This node, if a block is given
# @return [Enumerator] An enumerator on this tree, if a block is *not* given
#
# @since 0.9.0
#
# @see #each
# @see #preordered_each
# @see #postordered_each
# noinspection RubyUnusedLocalVariable
def inordered_each
return to_enum unless block_given?
node_stack = []
current_node = self
until node_stack.empty? && current_node.nil?
if current_node
node_stack.push(current_node)
current_node = current_node.left_child
else
current_node = node_stack.pop
yield current_node
current_node = current_node.right_child
end
end
self if block_given?
end
# A protected method to allow insertion of child nodes at the specified
# location. Note that this method allows insertion of +nil+ nodes.
#
# @param [Tree::BinaryTreeNode] child The child to add at the specified
# location.
#
# @param [Integer] at_index The location to add the entry at (0 or 1).
#
# @return [Tree::BinaryTreeNode] The added child.
#
# @raise [ArgumentError] If the index is out of limits.
def set_child_at(child, at_index)
raise ArgumentError 'A binary tree cannot have more than two children.'\
unless (0..1).include? at_index
@children[at_index] = child
@children_hash[child.name] = child if child # Assign the name mapping
child.parent = self if child
child
end
protected :set_child_at
# Sets the left child of the receiver node. If a previous child existed, it
# is replaced.
#
# @param [Tree::BinaryTreeNode] child The child to add as the left-side
# node.
#
# @return [Tree::BinaryTreeNode] The assigned child node.
#
# @see #left_child
# @see #right_child=
def left_child=(child)
set_child_at child, 0
end
# Sets the right child of the receiver node. If a previous child existed, it
# is replaced.
#
# @param [Tree::BinaryTreeNode] child The child to add as the right-side
# node.
#
# @return [Tree::BinaryTreeNode] The assigned child node.
#
# @see #right_child
# @see #left_child=
def right_child=(child)
set_child_at child, 1
end
# Swaps the left and right child nodes of the receiver node with each other.
def swap_children
self.left_child, self.right_child = right_child, left_child
end
end
end