Class: BinarySearch::List

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/binary_search/list.rb

Overview

A self-balancing binary search tree implementation of a list

This class provides a list-like interface backed by a Red-Black Tree, which ensures O(log n) time complexity for most operations.

Examples:

Creating and using a BinarySearch::List

list = BinarySearch::List.new([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5])
list.to_a  # => [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]
list.include?(4)  # => true
list.delete(1)  # Removes all instances of 1
list.to_a  # => [2, 3, 3, 4, 5, 5, 5, 6, 9]

Instance Method Summary collapse

Constructor Details

#initialize(from = []) ⇒ List

Initialize a new BinarySearch::List

Examples:

Create an empty list

list = BinarySearch::List.new

Create a list from an array

list = BinarySearch::List.new([1, 2, 3, 4, 5])

Parameters:

  • from (Array) (defaults to: []) —

    An array to initialize the list with



27
28
29
30
 
# File 'lib/binary_search/list.rb', line 27

def initialize(from = [])
  @tree = BinarySearch::RedBlackTree.new
  build_tree(from)
end

Instance Method Details

#&(other) ⇒ BinarySearch::List

Compute the intersection of two lists

This method returns a new list containing elements common to both lists, taking into account the number of occurrences of each element. It has a time complexity of O(n log n + m log m), where n and m are the sizes of the lists.

Examples:

Compute the intersection

list1 = BinarySearch::List.new([1, 2, 2, 3, 4, 5])
list2 = BinarySearch::List.new([2, 2, 4, 6])
(list1 & list2).to_a  # => [2, 2, 4]

Parameters:

Returns:



420
421
422
 
# File 'lib/binary_search/list.rb', line 420

def &(other)
  self.class.new(to_a & other.to_a)
end

#+(other) ⇒ BinarySearch::List

Concatenate two lists

This method returns a new list containing all elements from both lists. It has a time complexity of O(n + m), where n and m are the sizes of the lists.

Examples:

Concatenate lists

list1 = BinarySearch::List.new([1, 2, 3])
list2 = BinarySearch::List.new([4, 5, 6])
(list1 + list2).to_a  # => [1, 2, 3, 4, 5, 6]

Parameters:

Returns:



374
375
376
 
# File 'lib/binary_search/list.rb', line 374

def +(other)
  self.class.new(to_a + other.to_a)
end

#-(other) ⇒ BinarySearch::List

Compute the difference between two lists

This method returns a new list containing elements that are in the current list but not in the other list, taking into account the number of occurrences of each element. It has a time complexity of O(n log n + m log m), where n and m are the sizes of the lists.

Examples:

Compute the difference

list1 = BinarySearch::List.new([1, 2, 2, 3, 4, 5])
list2 = BinarySearch::List.new([2, 4, 6])
(list1 - list2).to_a  # => [1, 2, 3, 5]

Parameters:

Returns:

  • (BinarySearch::List) —

    A new list containing elements in this list but not in the other



391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
 
# File 'lib/binary_search/list.rb', line 391

def -(other)
  result = self.class.new
  self_counts = Hash.new(0)
  other_counts = Hash.new(0)

  self.each { |item| self_counts[item] += 1 }
  other.each { |item| other_counts[item] += 1 }

  self_counts.each do |item, count|
    diff = count - other_counts[item]
    diff.times { result.insert(item) } if diff > 0
  end

  result
end

#==(other) ⇒ Boolean

Compare two lists for equality

This method checks if two lists have the same elements in the same order. It has a time complexity of O(n), where n is the size of the lists.

Examples:

Compare lists

list1 = BinarySearch::List.new([1, 2, 3, 4, 5])
list2 = BinarySearch::List.new([1, 2, 3, 4, 5])
list3 = BinarySearch::List.new([5, 4, 3, 2, 1])
list1 == list2  # => true
list1 == list3  # => false

Parameters:

  • other (Object) —

    The object to compare with

Returns:

  • (Boolean) —

    True if the lists are equal, false otherwise



454
455
456
457
458
 
# File 'lib/binary_search/list.rb', line 454

def ==(other)
  return false unless other.is_a?(BinarySearch::List)
  return true if self.equal?(other)
  self.to_a == other.to_a
end

#[](arg) ⇒ Object, ...

Access elements by index or range

This method allows accessing elements by index or range, similar to Array. It has a time complexity of O(n) in the worst case.

Examples:

Access by index

list = BinarySearch::List.new([1, 2, 3, 4, 5])
list[2]  # => 3

Access by range

list[1..3]  # => #<BinarySearch::List: [2, 3, 4]>

Parameters:

  • arg (Integer, Range) —

    The index or range to access

Returns:

  • (Object, BinarySearch::List, nil) —

    The element(s) at the given index or range, or nil if out of bounds

Raises:

  • (ArgumentError) —

    If the argument is not an Integer or Range



149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
 
# File 'lib/binary_search/list.rb', line 149

def [](arg)
  case arg
  when Integer
    return nil if arg < 0 || arg >= size
    to_a[arg]
  when Range
    start = arg.begin
    finish = arg.end
    start = size + start if start < 0
    finish = size + finish if finish < 0
    finish -= 1 if arg.exclude_end?

    return nil if start < 0 || start >= size

    result = []
    (start..finish).each do |i|
      break if i >= size
      result << to_a[i]
    end
    self.class.new(result)
  else
    raise ArgumentError, "Invalid argument type: #{arg.class}"
  end
end

#clear ⇒ BinarySearch::List

Clear all elements from the list

This method removes all elements from the list, leaving it empty. It has a time complexity of O(1).

Examples:

Clear the list

list = BinarySearch::List.new([1, 2, 3, 4, 5])
list.clear  # => #<BinarySearch::List: []>
list.empty?  # => true

Returns:



200
201
202
203
204
 
# File 'lib/binary_search/list.rb', line 200

def clear
  @tree = BinarySearch::RedBlackTree.new
  @size = 0
  self
end

#delete(value) ⇒ Boolean

Delete all occurrences of a value from the list

This method removes all instances of the specified value from the list. It has a time complexity of O(log n) for each deletion.

Examples:

Delete a value

list = BinarySearch::List.new([1, 2, 2, 3, 4])
list.delete(2)  # => true
list.to_a  # => [1, 3, 4]

Parameters:

  • value (Object) —

    The value to delete

Returns:

  • (Boolean) —

    True if any elements were deleted, false otherwise



64
65
66
67
68
69
70
71
72
 
# File 'lib/binary_search/list.rb', line 64

def delete(value)
  deleted = false
  while @tree.find(value)
    @tree.remove(value)
    @size -= 1 if @size
    deleted = true
  end
  deleted
end

#each {|Object| ... } ⇒ Enumerator

Iterate over each element in the list

This method yields each element in the list to the given block. It has a time complexity of O(n).

Examples:

Iterate over elements

list = BinarySearch::List.new([1, 2, 3, 4, 5])
list.each { |x| puts x }  # Prints each number on a new line

Yields:

  • (Object) —

    Gives each element in the list to the block

Returns:

  • (Enumerator) —

    If no block is given



185
186
187
 
# File 'lib/binary_search/list.rb', line 185

def each(&block)
  to_a.each(&block)
end

#empty? ⇒ Boolean

Check if the list is empty

This method checks if the list contains no elements. It has a time complexity of O(1).

Examples:

Check if empty

list = BinarySearch::List.new
list.empty?  # => true
list.insert(1)
list.empty?  # => false

Returns:

  • (Boolean) —

    True if the list is empty, false otherwise



130
131
132
 
# File 'lib/binary_search/list.rb', line 130

def empty?
  @tree.root.nil?
end

#find {|Object| ... } ⇒ Object?

Find the first element that satisfies the given condition

This method returns the first element for which the given block returns true. It has a time complexity of O(n) in the worst case.

Examples:

Find an element

list = BinarySearch::List.new([1, 2, 3, 4, 5])
list.find { |x| x > 3 }  # => 4

Yields:

  • (Object) —

    Gives each element to the block

Returns:

  • (Object, nil) —

    The first element for which the block returns true, or nil if none found



343
344
345
346
 
# File 'lib/binary_search/list.rb', line 343

def find
  each { |element| return element if yield(element) }
  nil
end

#first ⇒ Object?

Get the first element in the list

This method returns the smallest element in the list. It has a time complexity of O(log n).

Examples:

Get the first element

list = BinarySearch::List.new([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5])
list.first  # => 1

Returns:

  • (Object, nil) —

    The first element, or nil if the list is empty



216
217
218
219
 
# File 'lib/binary_search/list.rb', line 216

def first
  return nil if empty?
  leftmost_node(@tree.root).key
end

#include?(value) ⇒ Boolean

Check if a value is in the list

This method checks if the list contains the specified value. It has a time complexity of O(log n).

Examples:

Check for a value

list = BinarySearch::List.new([1, 2, 3, 4, 5])
list.include?(3)  # => true
list.include?(6)  # => false

Parameters:

  • value (Object) —

    The value to check for

Returns:

  • (Boolean) —

    True if the value is in the list, false otherwise



86
87
88
 
# File 'lib/binary_search/list.rb', line 86

def include?(value)
  !@tree.find(value).nil?
end

#insert(value) ⇒ BinarySearch::List Also known as: append, push, <<

Insert a value into the list

This method inserts a value into the list, maintaining the sorted order. It has a time complexity of O(log n).

Examples:

Insert a value

list.insert(4)  # => #<BinarySearch::List: ...>
list << 5  # => #<BinarySearch::List: ...>

Parameters:

  • value (Object) —

    The value to insert

Returns:



43
44
45
46
47
 
# File 'lib/binary_search/list.rb', line 43

def insert(value)
  @tree.insert(value)
  @size = nil
  self
end

#inspect ⇒ String

Provide a string representation of the list

This method returns a concise string representation of the list, showing the class name and the size of the list.

Examples:

Inspect the list

list = BinarySearch::List.new([1, 2, 3, 4, 5])
list.inspect  # => "#<BinarySearch::List: (5 elements)>"

Returns:

  • (String) —

    A string representation of the list



470
471
472
 
# File 'lib/binary_search/list.rb', line 470

def inspect
  "#<#{self.class}: (#{size} elements)>"
end

#last ⇒ Object?

Get the last element in the list

This method returns the largest element in the list. It has a time complexity of O(log n).

Examples:

Get the last element

list = BinarySearch::List.new([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5])
list.last  # => 9

Returns:

  • (Object, nil) —

    The last element, or nil if the list is empty



231
232
233
234
 
# File 'lib/binary_search/list.rb', line 231

def last
  return nil if empty?
  rightmost_node(@tree.root).key
end

#max ⇒ Object?

Get the maximum value in the list

This method returns the largest element in the list. It has a time complexity of O(log n).

Examples:

Get the maximum value

list = BinarySearch::List.new([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5])
list.max  # => 9

Returns:

  • (Object, nil) —

    The maximum value, or nil if the list is empty



300
301
302
 
# File 'lib/binary_search/list.rb', line 300

def max
  last
end

#min ⇒ Object?

Get the minimum value in the list

This method returns the smallest element in the list. It has a time complexity of O(log n).

Examples:

Get the minimum value

list = BinarySearch::List.new([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5])
list.min  # => 1

Returns:

  • (Object, nil) —

    The minimum value, or nil if the list is empty



314
315
316
 
# File 'lib/binary_search/list.rb', line 314

def min
  first
end

#pop ⇒ Object?

Remove and return the last element in the list

This method removes and returns the largest element in the list. It has a time complexity of O(log n).

Examples:

Remove the last element

list = BinarySearch::List.new([1, 2, 3, 4, 5])
list.pop  # => 5
list.to_a  # => [1, 2, 3, 4]

Returns:

  • (Object, nil) —

    The last element, or nil if the list is empty



247
248
249
250
251
252
253
 
# File 'lib/binary_search/list.rb', line 247

def pop
  return nil if empty?
  last_value = last
  @tree.remove(last_value)
  @size -= 1 if @size
  last_value
end

#shift ⇒ Object?

Remove and return the first element in the list

This method removes and returns the smallest element in the list. It has a time complexity of O(log n).

Examples:

Remove the first element

list = BinarySearch::List.new([1, 2, 3, 4, 5])
list.shift  # => 1
list.to_a  # => [2, 3, 4, 5]

Returns:

  • (Object, nil) —

    The first element, or nil if the list is empty



266
267
268
269
270
271
272
 
# File 'lib/binary_search/list.rb', line 266

def shift
  return nil if empty?
  first_value = first
  @tree.remove(first_value)
  @size -= 1 if @size
  first_value
end

#size ⇒ Integer

Get the size of the list

This method returns the number of elements in the list. It has a time complexity of O(1) if the size is cached, or O(n) otherwise.

Examples:

Get the size

list = BinarySearch::List.new([1, 2, 3, 4, 5])
list.size  # => 5

Returns:

  • (Integer) —

    The number of elements in the list



114
115
116
 
# File 'lib/binary_search/list.rb', line 114

def size
  @size ||= inorder_traversal(@tree.root).size
end

#sum ⇒ Numeric

Calculate the sum of all elements in the list

This method returns the sum of all elements in the list. It has a time complexity of O(n).

Examples:

Calculate the sum

list = BinarySearch::List.new([1, 2, 3, 4, 5])
list.sum  # => 15

Returns:

  • (Numeric) —

    The sum of all elements



328
329
330
 
# File 'lib/binary_search/list.rb', line 328

def sum
  to_a.sum
end

#to_a ⇒ Array

Convert the list to an array

This method returns an array representation of the list in sorted order. It has a time complexity of O(n).

Examples:

Convert to array

list = BinarySearch::List.new([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5])
list.to_a  # => [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

Returns:

  • (Array) —

    An array representation of the list



100
101
102
 
# File 'lib/binary_search/list.rb', line 100

def to_a
  inorder_traversal(@tree.root)
end

#uniq ⇒ BinarySearch::List

Create a new list with duplicate elements removed

This method returns a new list with all duplicate elements removed. It has a time complexity of O(n log n).

Examples:

Remove duplicates

list = BinarySearch::List.new([1, 2, 2, 3, 3, 3, 4, 5])
list.uniq.to_a  # => [1, 2, 3, 4, 5]

Returns:



358
359
360
 
# File 'lib/binary_search/list.rb', line 358

def uniq
  self.class.new(to_a.uniq)
end

#unshift(value) ⇒ BinarySearch::List

Insert a value at the beginning of the list

This method inserts a value at the beginning of the list. It has a time complexity of O(log n).

Examples:

Insert at the beginning

list = BinarySearch::List.new([2, 3, 4, 5])
list.unshift(1)  # => #<BinarySearch::List: [1, 2, 3, 4, 5]>

Parameters:

  • value (Object) —

    The value to insert

Returns:



285
286
287
288
 
# File 'lib/binary_search/list.rb', line 285

def unshift(value)
  insert(value)
  self
end

#|(other) ⇒ BinarySearch::List

Compute the union of two lists

This method returns a new list containing unique elements from both lists. It has a time complexity of O(n log n + m log m), where n and m are the sizes of the lists.

Examples:

Compute the union

list1 = BinarySearch::List.new([1, 2, 3, 4])
list2 = BinarySearch::List.new([3, 4, 5, 6])
(list1 | list2).to_a  # => [1, 2, 3, 4, 5, 6]

Parameters:

Returns:



436
437
438
 
# File 'lib/binary_search/list.rb', line 436

def |(other)
  self.class.new(to_a | other.to_a)
end