24631974278

Committed 19 Apr 2026 02:58PM UTC coverage: 88.495% (-10.8%) from 99.309%

Build # 24631974278

Build Type

push

github

Committed by

evolve75

Commit Message

Backport yard minimum version fix to next

Raise the next branch floor to the patched YARD release range and refresh the lockfile from 0.9.38 to 0.9.43 to clear the vulnerable dependency state.

Coverage Stats

946 of 1344 branches covered (70.39%)

2269 of 2564 relevant lines covered (88.49%)

14493.64 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

98.53

/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-2026 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)
      if (nil_index = @children.index(nil))
        return set_child_at(child, nil_index)
      end

      raise ArgumentError, 'Already has two child nodes' if @children.size == 2

      super
    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)
      existing_children = @children.compact.size
      raise ArgumentError, 'Too many children' if hashed_subtree.size + existing_children > 2

      super
    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(:inordered_each) 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)
      validate_binary_index!(at_index)

      old_child = @children[at_index]
      detach_old_child(old_child, at_index) if old_child && old_child != child

      if child
        attach_child(child, at_index)
      else
        @children[at_index] = nil
      end

      send(:invalidate_size_cache_upwards!)
      child
    end

    protected :set_child_at

    private

    def validate_binary_index!(at_index)
      return if (0..1).include?(at_index)

      raise ArgumentError, 'A binary tree cannot have more than two children.'
    end

    def detach_old_child(old_child, at_index)
      still_present = @children.each_with_index.any? do |existing, idx|
        idx != at_index && existing.equal?(old_child)
      end
      return if still_present

      @children_hash.delete(old_child.name)
      old_child.set_as_root!
    end

    def attach_child(child, at_index)
      child.parent&.remove!(child) unless child.parent == self
      @children[at_index] = child
      @children_hash[child.name] = child
      child.parent = self
    end

    public

    # 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

1	# binarytree.rb - This file is part of the RubyTree package.
2	#
3	# = binarytree.rb - An implementation of the binary tree data structure.
4	#
5	# Provides a binary tree data structure with ability to
6	# store two node elements as children at each node in the tree.
7	#
8	# Author:: Anupam Sengupta (anupamsg@gmail.com)
9	#
10
11	# Copyright (c) 2007-2026 Anupam Sengupta. All rights reserved.
12	#
13	# Redistribution and use in source and binary forms, with or without
14	# modification, are permitted provided that the following conditions are met:
15	#
16	# - Redistributions of source code must retain the above copyright notice, this
17	# list of conditions and the following disclaimer.
18	#
19	# - Redistributions in binary form must reproduce the above copyright notice,
20	# this list of conditions and the following disclaimer in the documentation
21	# and/or other materials provided with the distribution.
22	#
23	# - Neither the name of the organization nor the names of its contributors may
24	# be used to endorse or promote products derived from this software without
25	# specific prior written permission.
26	#
27	# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
28	# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
29	# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
30	# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
31	# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
32	# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
33	# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
34	# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
35	# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
36	# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
37	#
38	# frozen_string_literal: true
39
40	require_relative '../tree'	4✔
41
42	module Tree	4✔
43	# Provides a Binary tree implementation. This node allows only two child nodes
44	# (left and right child). It also provides direct access to the left or right
45	# child, including assignment to the same.
46	#
47	# This inherits from the {Tree::TreeNode} class.
48	#
49	# @author Anupam Sengupta
50	#
51	class BinaryTreeNode < TreeNode	4✔
52	# @!group Core Attributes
53
54	# @!attribute [rw] left_child
55	# Left child of the receiver node. Note that left Child == first Child.
56	#
57	# @return [Tree::BinaryTreeNode] The left most (or first) child.
58	#
59	# @see #right_child
60	def left_child	4✔
61	children.first	6,796✔
62	end
63
64	# @!attribute [rw] right_child
65	# Right child of the receiver node. Note that right child == last child
66	# unless there is only one child.
67	#
68	# Returns +nil+ if the right child does not exist.
69	#
70	# @return [Tree::BinaryTreeNode] The right child, or +nil+ if the right side
71	# child does not exist.
72	#
73	# @see #left_child
74	def right_child	4✔
75	children[1]	5,962✔
76	end
77
78	# @!attribute left_child?
79	# +true+ if the receiver node is the left child of its parent.
80	# Always returns +false+ if it is a root node.
81	#
82	# @return [Boolean] +true+ if this is the left child of its parent.
83	def left_child?	4✔
84	return false if root?	619✔
85
86	self == parent.left_child	615✔
87	end
88
89	alias is_left_child? left_child? # @todo: Aliased for eventual replacement	4✔
90
91	# @!attribute [r] right_child?
92	# +true+ if the receiver node is the right child of its parent.
93	# Always returns +false+ if it is a root node.
94	#
95	# @return [Boolean] +true+ if this is the right child of its parent.
96	def right_child?	4✔
97	return false if root?	252✔
98
99	self == parent.right_child	248✔
100	end
101
102	alias is_right_child? right_child? # @todo: Aliased for eventual replacement	4✔
103
104	# @!group Structure Modification
105
106	# Adds the specified child node to the receiver node. The child node's
107	# parent is set to be the receiver.
108	#
109	# The child nodes are added in the order of addition, i.e., the first child
110	# added becomes the left node, and the second child added will be the second
111	# node.
112	#
113	# If only one child is present, then this will be the left child.
114	#
115	# @param [Tree::BinaryTreeNode] child The child to add.
116	#
117	# @raise [ArgumentError] This exception is raised if two children are
118	# already present.
119	def add(child)	4✔
120	if (nil_index = @children.index(nil))	156!
121	return set_child_at(child, nil_index)	×
122	end
123
124	raise ArgumentError, 'Already has two child nodes' if @children.size == 2	156✔
125
126	super	148✔
127	end
128
129	# Instantiate and insert child nodes from data in a Ruby +Hash+
130	#
131	# This method is used in conjunction with {Tree::TreeNode.from_hash} to
132	# provide a convenient way of building and inserting child nodes present
133	# in a Ruby hashes.
134	#
135	# This method will instantiate a {Tree::TreeNode} instance for each top-
136	# level key of the input hash, to be inserted as children of the receiver
137	# instance.
138	#
139	# Nested hashes are expected and further child nodes will be created and
140	# added accordingly. If a hash key is a single value that value will be
141	# used as the name for the node. If a hash key is an Array, both node
142	# name and content will be populated.
143	#
144	# A leaf element of the tree should be represented as a hash key with
145	# corresponding value nil or {}.
146	#
147	# @example
148	# root = Tree::TreeNode.new(:A, "Root content!")
149	# root.add_from_hash({:B => {:D => {}}, [:C, "C content!"] => {}})
150	#
151	# @param [Hash] hashed_subtree The hash of child subtrees.
152	#
153	# @raise [ArgumentError] This exception is raised if hash contains too
154	# many children.
155	# =>
156	# @raise [ArgumentError] This exception is raised if a non-hash is passed.
157	# @return [Array] Array of child nodes added
158	def add_from_hash(hashed_subtree)	4✔
159	existing_children = @children.compact.size	72✔
160	raise ArgumentError, 'Too many children' if hashed_subtree.size + existing_children > 2	72✔
161
162	super	56✔
163	end
164
165	# Performs in-order traversal (including this node).
166	#
167	# @yieldparam node [Tree::BinaryTreeNode] Each node (in-order).
168	#
169	# @return [Tree::BinaryTreeNode] This node, if a block is given
170	# @return [Enumerator] An enumerator on this tree, if a block is not given
171	#
172	# @since 0.9.0
173	#
174	# @see #each
175	# @see #preordered_each
176	# @see #postordered_each
177	# noinspection RubyUnusedLocalVariable
178	def inordered_each	4✔
179	return to_enum(:inordered_each) unless block_given?	192✔
180
181	node_stack = []	184✔
182	current_node = self	184✔
183
184	until node_stack.empty? && current_node.nil?	184✔
185	if current_node	1,424✔
186	node_stack.push(current_node)	712✔
187	current_node = current_node.left_child	712✔
188	else	712✔
189	current_node = node_stack.pop	712✔
190	yield current_node	712✔
191	current_node = current_node.right_child	712✔
192	end
193	end
194
195	self if block_given?	184!
196	end
197
198	# A protected method to allow insertion of child nodes at the specified
199	# location. Note that this method allows insertion of +nil+ nodes.
200	#
201	# @param [Tree::BinaryTreeNode] child The child to add at the specified
202	# location.
203	#
204	# @param [Integer] at_index The location to add the entry at (0 or 1).
205	#
206	# @return [Tree::BinaryTreeNode] The added child.
207	#
208	# @raise [ArgumentError] If the index is out of limits.
209	def set_child_at(child, at_index)	4✔
210	validate_binary_index!(at_index)	2,089✔
211
212	old_child = @children[at_index]	2,085✔
213	detach_old_child(old_child, at_index) if old_child && old_child != child	2,085✔
214
215	if child	2,085✔
216	attach_child(child, at_index)	1,573✔
217	else	512✔
218	@children[at_index] = nil	512✔
219	end
220
221	send(:invalidate_size_cache_upwards!)	2,085✔
222	child	2,085✔
223	end
224
225	protected :set_child_at	4✔
226
227	private	4✔
228
229	def validate_binary_index!(at_index)	4✔
230	return if (0..1).include?(at_index)	2,089✔
231
232	raise ArgumentError, 'A binary tree cannot have more than two children.'	4✔
233	end
234
235	def detach_old_child(old_child, at_index)	4✔
236	still_present = @children.each_with_index.any? do \|existing, idx\|	717✔
237	idx != at_index && existing.equal?(old_child)	1,199✔
238	end
239	return if still_present	717✔
240
241	@children_hash.delete(old_child.name)	713✔
242	old_child.set_as_root!	713✔
243	end
244
245	def attach_child(child, at_index)	4✔
246	child.parent&.remove!(child) unless child.parent == self	1,573✔
247	@children[at_index] = child	1,573✔
248	@children_hash[child.name] = child	1,573✔
249	child.parent = self	1,573✔
250	end
251
252	public	4✔
253
254	# Sets the left child of the receiver node. If a previous child existed, it
255	# is replaced.
256	#
257	# @param [Tree::BinaryTreeNode] child The child to add as the left-side
258	# node.
259	#
260	# @return [Tree::BinaryTreeNode] The assigned child node.
261	#
262	# @see #left_child
263	# @see #right_child=
264	def left_child=(child)	4✔
265	set_child_at child, 0	1,148✔
266	end
267
268	# Sets the right child of the receiver node. If a previous child existed, it
269	# is replaced.
270	#
271	# @param [Tree::BinaryTreeNode] child The child to add as the right-side
272	# node.
273	#
274	# @return [Tree::BinaryTreeNode] The assigned child node.
275	#
276	# @see #right_child
277	# @see #left_child=
278	def right_child=(child)	4✔
279	set_child_at child, 1	937✔
280	end
281
282	# Swaps the left and right child nodes of the receiver node with each other.
283	def swap_children	4✔
284	self.left_child, self.right_child = right_child, left_child	4✔
285	end
286	end
287	end

evolve75 / RubyTree / 24631974278

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous