Class: SortedContainers::SortedArray

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/sorted_containers/sorted_array.rb

Overview

SortedArray is an array that maintains its elements in sorted order.

It contains most of the same methods as a regular Array, but some methods have been removed because they would not make sense for a sorted array. For example, the #rotate, #shuffle, and #reverse methods have been removed.

SortedArray also has the additional following methods:

  • #add

  • #update

  • #bisect_left

  • #bisect_right

There are also methods that have been obtimized using the sorted nature of the array. For example, the #include? method has been optimized to use binary search.

Constant Summary collapse

DEFAULT_LOAD_FACTOR =

The default load factor for the array. Sublists are split when they exceed 2 * load_factor

1000

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(iterable = [], load_factor: DEFAULT_LOAD_FACTOR) ⇒ SortedArray

Initializes a new SortedArray object.

Parameters:

  • iterable (Enumerable) (defaults to: []) —

    An optional iterable object to initialize the array with.

  • load_factor (Integer) (defaults to: DEFAULT_LOAD_FACTOR) —

    The load factor for the array.



36
37
38
39
40
41
42
43
44
 
# File 'lib/sorted_containers/sorted_array.rb', line 36

def initialize(iterable = [], load_factor: DEFAULT_LOAD_FACTOR)
  @lists = []
  @maxes = []
  @array_index = []
  @offset = 0
  @load_factor = load_factor
  @size = 0
  update(iterable)
end

Instance Attribute Details

#load_factor ⇒ Object (readonly)

Returns the value of attribute load_factor.



29
30
31
 
# File 'lib/sorted_containers/sorted_array.rb', line 29

def load_factor
  @load_factor
end

#size ⇒ Object Also known as: length

Returns the value of attribute size.



29
30
31
 
# File 'lib/sorted_containers/sorted_array.rb', line 29

def size
  @size
end

Class Method Details

.[](*args) ⇒ SortedArray

Returns a new SortedArray populated with the given objects.

Parameters:

  • args (Array) —

    The objects to populate the array with.

Returns:



50
51
52
 
# File 'lib/sorted_containers/sorted_array.rb', line 50

def self.[](*args)
  new(args)
end

Instance Method Details

#+(other) ⇒ SortedArray

Returns a new SortedArray with the values from both arrays.

Parameters:

Returns:



76
77
78
 
# File 'lib/sorted_containers/sorted_array.rb', line 76

def +(other)
  self.class.new(to_a + other.to_a, load_factor: @load_factor)
end

#<=>(other) ⇒ Integer

Returns -1, 0, or 1 if self is less than, equal to, or greater than other. For each index i in self, evaluates self <=> other

Parameters:

Returns:

  • (Integer) —

    -1, 0, or 1 as self is less than, equal to, or greater than other.



94
95
96
97
98
99
100
101
102
 
# File 'lib/sorted_containers/sorted_array.rb', line 94

def <=>(other)
  return size <=> other.size if size != other.size

  each_with_index do |value, index|
    return value <=> other[index] if value != other[index]
  end

  0
end

#==(other) ⇒ Boolean

Returns true if the arrays size and values are equal.

Parameters:

Returns:

  • (Boolean) —

    True if the arrays are equal, false otherwise.



108
109
110
111
112
 
# File 'lib/sorted_containers/sorted_array.rb', line 108

def ==(other)
  return false unless other.is_a?(SortedArray)

  size == other.size && each_with_index.all? { |value, index| value == other[index] }
end

#[]=(index, value) ⇒ Object, Array #[]=(range, value) ⇒ Object, Array #[]=(start, length, value) ⇒ Object, Array

Sets the value at the specified index or range.

If a single index is provided, sets the value at that index.

If a range is provided, sets the values in that range.

If a start index and length are provided, sets the values starting from the start index and continuing for the given length.

Overloads:

  • #[]=(index, value) ⇒ Object, Array

    Parameters:

    • index (Integer) —

      The index of the value to set.

    • value (Object) —

      The value to set.

  • #[]=(range, value) ⇒ Object, Array

    Parameters:

    • range (Range) —

      The range of values to set.

    • value (Object) —

      The value to set.

  • #[]=(start, length, value) ⇒ Object, Array

    Parameters:

    • start (Integer) —

      The index to start from.

    • length (Integer) —

      The length of the values to set.

    • value (Object, Array) —

      The value or values to set.

Returns:

  • (Object, Array) —

    The value or values at the specified index or range.

Raises:

  • (ArgumentError) 


225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
 
# File 'lib/sorted_containers/sorted_array.rb', line 225

def []=(*args)
  raise ArgumentError, "wrong number of arguments (given #{args.size}, expected 2..3)" if args.size < 2

  value = args.pop
  case args.size
  when 1
    if args[0].is_a?(Integer)
      index = args[0]
      delete_at(index)
      add(value)
    elsif args[0].is_a?(Range)
      range = args[0]
      values = get_values_from_range(range)
      values.each { |val| delete(val) }
      if value.is_a?(Array)
        value.each { |val| add(val) }
      else
        add(value)
      end
    else
      raise TypeError, "no implicit conversion of #{args[0].class} into Integer"
    end
  when 2
    start, length = args
    values = get_values_from_start_and_length(start, length)
    values.each { |val| delete(val) }
    add(value)
  else
    raise ArgumentError, "wrong number of arguments (given #{args.size}, expected 2..3)"
  end
end

#abbrev(pattern = nil) ⇒ Hash

Calculates the set of unambiguous abbreviations for the strings in self.

require 'abbrev'
SortedArray.new(%w{ car cone }).abbrev
#=> {"car"=>"car", "ca"=>"car", "cone"=>"cone", "con"=>"cone", "co"=>"cone"}

The optional pattern parameter is a pattern or a string. Only input strings that match the pattern or start with the string are included in the output hash.

SortedArray.new(%w{ fast boat day }).abbrev(/^.a/)
#=> {"fast"=>"fast", "fas"=>"fast", "fa"=>"fast", "day"=>"day", "da"=>"day"}

See also Abbrev.abbrev

Parameters:

  • pattern (Regexp, String) (defaults to: nil) —

    The pattern to match.

Returns:

  • (Hash) —

    The set of unambiguous abbreviations.



278
279
280
 
# File 'lib/sorted_containers/sorted_array.rb', line 278

def abbrev(pattern = nil)
  to_a.abbrev(pattern)
end

#add(value) ⇒ Object Also known as: <<, push, append

Adds a value to the sorted array.

Parameters:

  • value (Object) —

    The value to add.



288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
 
# File 'lib/sorted_containers/sorted_array.rb', line 288

def add(value)
  if @maxes.empty?
    @lists.append([value])
    @maxes.append(value)
  else
    raise ArgumentError, "value must be comparable" unless @maxes[0] <=> value

    pos = internal_bisect_right(@maxes, value)

    if pos == @maxes.size
      pos -= 1
      @lists[pos].push(value)
      @maxes[pos] = value
    else
      sub_pos = internal_bisect_right(@lists[pos], value)
      @lists[pos].insert(sub_pos, value)
    end
    expand(pos)
  end
  @size += 1
  self
end

#assoc(obj) ⇒ Array

Returns the first element in self that is an Array whose first element == obj:

Parameters:

  • obj (Object) —

    The object to search for.

Returns:

  • (Array) —

    The first element in self that is an Array whose first element == obj.



321
322
323
324
 
# File 'lib/sorted_containers/sorted_array.rb', line 321

def assoc(obj)
  index = bsearch_index { |x| x.is_a?(Array) && x.first >= obj }
  index.nil? ? nil : self[index]
end

#at(index) ⇒ Object

Returns the element at Integer offset index; does not modify self. If index is negative, counts from the end of self. Returns nil if the index is out of range. Will raise TypeError if the index is not an Integer.

Parameters:

  • index (Integer) —

    The index of the value to retrieve.

Returns:

  • (Object) —

    The value at the specified index.

Raises:

  • (TypeError) 


333
334
335
336
337
 
# File 'lib/sorted_containers/sorted_array.rb', line 333

def at(index)
  raise TypeError, "no implicit conversion of #{index.class} into Integer" unless index.is_a?(Integer)

  self[index.to_i]
end

#bisect_left(value) ⇒ Integer

Returns an index to insert value in the sorted list.

If the value is already present, the insertion point will be before (to the left of) any existing values.

Runtime complexity: O(log(n)) – approximate.

Parameters:

  • value (Object) —

    The value to insert.

Returns:

  • (Integer) —

    The index to insert the value.



820
821
822
823
824
825
826
827
828
829
 
# File 'lib/sorted_containers/sorted_array.rb', line 820

def bisect_left(value)
  return 0 if @maxes.empty?

  pos = internal_bisect_left(@maxes, value)

  return @size if pos == @maxes.size

  idx = internal_bisect_left(@lists[pos], value)
  loc(pos, idx)
end

#bisect_right(value) ⇒ Integer

Returns an index to insert value in the sorted list.

If the value is already present, the insertion point will be after (to the right of) any existing values.

Runtime complexity: O(log(n)) – approximate.

Parameters:

  • value (Object) —

    The value to insert.

Returns:

  • (Integer) —

    The index to insert the value.



840
841
842
843
844
845
846
847
848
849
 
# File 'lib/sorted_containers/sorted_array.rb', line 840

def bisect_right(value)
  return 0 if @maxes.empty?

  pos = internal_bisect_right(@maxes, value)

  return @size if pos == @maxes.size

  idx = internal_bisect_right(@lists[pos], value)
  loc(pos, idx)
end

#bsearch {|value| ... } ⇒ Object

Returns an element from self selected by a binary search.

Yields:

  • (value) —

    The block to search with.

Returns:

  • (Object) —

    The value selected by the binary search.



343
344
345
346
347
348
349
 
# File 'lib/sorted_containers/sorted_array.rb', line 343

def bsearch(&block)
  index_result = bsearch_index(&block)

  return nil if index_result.nil?

  self[index_result]
end

#bsearch_index {|value| ... } ⇒ Integer

Returns an index of an element from self selected by a binary search.

Yields:

  • (value) —

    The block to search with.

Returns:

  • (Integer) —

    The index of the value selected by the binary search.



355
356
357
358
359
360
361
362
363
364
 
# File 'lib/sorted_containers/sorted_array.rb', line 355

def bsearch_index(&block)
  return nil if @maxes.empty?

  pos = @maxes.bsearch_index(&block)

  return nil if pos.nil?

  idx = @lists[pos].bsearch_index(&block)
  loc(pos, idx)
end

#clear ⇒ SortedArray

Clears the sorted array, removing all values.

Returns:



369
370
371
372
373
374
375
376
377
 
# File 'lib/sorted_containers/sorted_array.rb', line 369

def clear
  @lists.map(&:clear)
  @lists.clear
  @maxes.clear
  @array_index.clear
  @offset = 0
  @size = 0
  self
end

#concat(*other_arrays) ⇒ SortedArray

Adds the elements of one or more arrays to the SortedArray.

Parameters:

  • other_arrays (Array) —

    The arrays to concatenate.

Returns:

  • (SortedArray) —

    self. The SortedArray with the concatenated values.



405
406
407
408
409
410
 
# File 'lib/sorted_containers/sorted_array.rb', line 405

def concat(*other_arrays)
  other_arrays.each do |array|
    update(array)
  end
  self
end

#count(value = nil) {|value| ... } ⇒ Integer

Returns the count of elements, based on an argument or block criterion, if given. With no argument and no block given, returns the number of elements: With argument object given, returns the number of elements that are == to object: Uses binary search to find the first and last index of the value.

Parameters:

  • value (Object) (defaults to: nil) —

    The value to count.

Yields:

  • (value) —

    The block to count with.

Returns:

  • (Integer) —

    The count of elements.



420
421
422
423
424
425
426
427
428
 
# File 'lib/sorted_containers/sorted_array.rb', line 420

def count(value = nil)
  # If block is given, we call super to use the Enumerable#count method
  return super() if block_given?
  return @size unless value

  left_index = bisect_left(value)
  right_index = bisect_right(value)
  right_index - left_index
end

#delete(value) ⇒ Object

Deletes a value from the sorted array.

Parameters:

  • value (Object) —

    The value to delete.



433
434
435
436
437
438
439
440
441
442
443
 
# File 'lib/sorted_containers/sorted_array.rb', line 433

def delete(value)
  return if @maxes.empty?

  pos = internal_bisect_left(@maxes, value)

  return if pos == @maxes.size

  idx = internal_bisect_left(@lists[pos], value)

  internal_delete(pos, idx) if @lists[pos][idx] == value
end

#delete_at(index) ⇒ Object

Deletes the value at the specified index.

Parameters:

  • index (Integer) —

    The index of the value to delete.



448
449
450
451
452
453
 
# File 'lib/sorted_containers/sorted_array.rb', line 448

def delete_at(index)
  return nil if index.abs >= @size

  pos, idx = pos(index)
  internal_delete(pos, idx)
end

#delete_if {|value| ... } ⇒ SortedArray

Removes each element from the array for which block evaluates to true.

Yields:

  • (value) —

    The block to delete with.

Returns:

  • (SortedArray) —

    self. The array with the deleted values.



459
460
461
462
463
464
465
466
467
468
 
# File 'lib/sorted_containers/sorted_array.rb', line 459

def delete_if
  return to_enum(:delete_if) unless block_given?

  to_delete = []
  each do |value|
    to_delete << value if yield(value)
  end
  to_delete.each { |value| delete(value) }
  self
end

#difference(other) ⇒ SortedArray Also known as: -

Returns a new SortedArray with the values from the difference of the two arrays.

Parameters:

Returns:



84
85
86
 
# File 'lib/sorted_containers/sorted_array.rb', line 84

def difference(other)
  self.class.new(to_a - other.to_a, load_factor: @load_factor)
end

#dig(index, *identifiers) ⇒ Object

Finds and returns the object in nested objects that is specified by index and identifiers. The nested objects may be instances of various classes. See Dig methods.

Parameters:

  • index (Integer) —

    The index of the value to retrieve.

  • identifiers (Array) —

    The identifiers to retrieve the value.

Returns:

  • (Object) —

    The value at the specified index.



476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
 
# File 'lib/sorted_containers/sorted_array.rb', line 476

def dig(index, *identifiers)
  result = self[index]
  return nil if result.nil?

  identifiers.each do |identifier|
    raise TypeError, "#{result.class} does not have #dig method" unless result.respond_to?(:dig)

    # rubocop:disable Style/SingleArgumentDig
    result = result.dig(identifier)
    # rubocop:enable Style/SingleArgumentDig
    return nil if result.nil?
  end

  result
end

#drop(n) ⇒ SortedArray

Returns a new SortedArray containing all but the first n elements, where n is a non-negative integer. Does not modify the self.

Parameters:

  • n (Integer) —

    The number of elements to drop.

Returns:

Raises:

  • (ArgumentError) 


499
500
501
502
503
504
 
# File 'lib/sorted_containers/sorted_array.rb', line 499

def drop(n)
  raise ArgumentError, "attempt to drop negative size" if n.negative?
  return self.class.new(load_factor: @load_factor) if n >= @size

  self.class.new(to_a.drop(n), load_factor: @load_factor)
end

#drop_while {|value| ... } ⇒ SortedArray, Enumerator

Returns a new SortedArray containing all but the first elements for which the block returns true. Does not modify the self. If no block is given, an Enumerator is returned instead.

Yields:

  • (value) —

    The block to drop with.

Returns:

  • (SortedArray, Enumerator) —

    The array with the dropped values.



514
515
516
517
518
 
# File 'lib/sorted_containers/sorted_array.rb', line 514

def drop_while
  return to_enum(:drop_while) unless block_given?

  self.class.new(super(), load_factor: @load_factor)
end

#dup ⇒ SortedArray

Returns a new SortedArray with the same values.

Returns:



929
930
931
932
933
934
935
936
937
938
939
 
# File 'lib/sorted_containers/sorted_array.rb', line 929

def dup
  # Create a new instance of SortedList with the same values
  new_instance = self.class.new
  new_instance.lists = @lists.map(&:dup)
  new_instance.maxes = @maxes.dup
  new_instance.array_index = @array_index.dup
  new_instance.offset = @offset
  new_instance.load_factor = @load_factor
  new_instance.size = @size
  new_instance
end

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

Iterates over each value in the sorted array.

Yields:

  • (value) —

    Gives each value to the block.

Returns:

  • (Enumerator) —

    If no block is given, an Enumerator is returned.



524
525
526
527
528
529
530
 
# File 'lib/sorted_containers/sorted_array.rb', line 524

def each(&block)
  return to_enum(:each) unless block_given?

  @lists.each do |sublist|
    sublist.each(&block)
  end
end

#each_index {|index| ... } ⇒ Enumerator

Iterates over each index in the sorted array.

Yields:

  • (index) —

    Gives each index to the block.

Returns:

  • (Enumerator) —

    If no block is given, an Enumerator is returned.



536
537
538
539
540
 
# File 'lib/sorted_containers/sorted_array.rb', line 536

def each_index(&block)
  return to_enum(:each_index) unless block_given?

  0.upto(@size - 1, &block)
end

#empty? ⇒ Boolean

Checks if Array is empty

Returns:

  • (Boolean) 


545
546
547
 
# File 'lib/sorted_containers/sorted_array.rb', line 545

def empty?
  @size.zero?
end

#eql?(other) ⇒ Boolean

Returns true if for every element in self there is a corresponding element in other that are equal using Object#eql?.

This method is different from method SortedArray#==, which compares using method Object#==

Parameters:

Returns:

  • (Boolean) —

    True if the arrays are equal, false otherwise.



557
558
559
560
561
 
# File 'lib/sorted_containers/sorted_array.rb', line 557

def eql?(other)
  return false unless other.is_a?(SortedArray)

  size == other.size && each_with_index.all? { |value, index| value.eql?(other[index]) }
end

#fetch(index, *args) ⇒ Object

Returns the element at the specified index, or returns a default value if the index is out of range. Raises an IndexError if the index is out of range and no default is given. If a block is given, it is called with the index. The block will supplant the default value if both are given.

Parameters:

  • index (Integer) —

    The index of the value to retrieve.

  • args (Object) —

    The default value to return if the index is out of range.

Raises:

  • (IndexError) 


569
570
571
572
573
574
575
576
577
 
# File 'lib/sorted_containers/sorted_array.rb', line 569

def fetch(index, *args)
  return self[index] if index.abs < @size

  return yield(index) if block_given?

  return args[0] if args.size.positive?

  raise IndexError, "index #{index} outside of array bounds: #{-size}...#{size}"
end

#fill(value) ⇒ SortedArray #fill(value, start) ⇒ SortedArray #fill(value, start, length) ⇒ SortedArray #fill(value, range) ⇒ SortedArray #fill {|index| ... } ⇒ SortedArray #fill(start) {|index| ... } ⇒ SortedArray #fill(start, length) {|index| ... } ⇒ SortedArray #fill(range) {|index| ... } ⇒ SortedArray

Fills the array with the given value.

Overloads:

  • #fill(value) ⇒ SortedArray

    Parameters:

    • value (Object) —

      The value to fill the array with.

  • #fill(value, start) ⇒ SortedArray

    Parameters:

    • value (Object) —

      The value to fill the array with.

    • start (Integer) —

      The index to start filling from.

  • #fill(value, start, length) ⇒ SortedArray

    Parameters:

    • value (Object) —

      The value to fill the array with.

    • start (Integer) —

      The index to start filling from.

    • length (Integer) —

      The length of the values to fill.

  • #fill(value, range) ⇒ SortedArray

    Parameters:

    • value (Object) —

      The value to fill the array with.

    • range (Range) —

      The range of values to fill.

  • #fill {|index| ... } ⇒ SortedArray

    Yields:

    • (index) —

      The block to fill with.

  • #fill(start) {|index| ... } ⇒ SortedArray

    Parameters:

    • start (Integer) —

      The index to start filling from.

    Yields:

    • (index) —

      The block to fill with.

  • #fill(start, length) {|index| ... } ⇒ SortedArray

    Parameters:

    • start (Integer) —

      The index to start filling from.

    • length (Integer) —

      The length of the values to fill.

    Yields:

    • (index) —

      The block to fill with.

  • #fill(range) {|index| ... } ⇒ SortedArray

    Parameters:

    • range (Range) —

      The range of values to fill.

    Yields:

    • (index) —

      The block to fill with.

Returns:



610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
 
# File 'lib/sorted_containers/sorted_array.rb', line 610

def fill(*args, &block)
  unless block_given?
    value = args.shift
    block = proc { value }
  end

  case args.size
  when 0
    fill_range_unsafe(0..@size - 1, block)
  when 1
    if args[0].is_a?(Integer)
      start = args[0]
      start += @size if start.negative?
      fill_range_unsafe(start..@size - 1, block)
    elsif args[0].is_a?(Range)
      fill_range_unsafe(args[0], block)
    end
  when 2
    start, length = args
    start += @size if start.negative?
    fill_range_unsafe(start...(start + length), block)
  end

  sort! # resort will re-initialize the index and maxes
  self
end

#find_index(value) ⇒ Integer #find_index {|value| ... } ⇒ Integer Also known as: index

Returns the first index of the value in the sorted array, or returns the first index that returns true when passed to the block.

This method will binary search if value is given, if a block is given, it will iterate through the array.

Overloads:

  • #find_index(value) ⇒ Integer

    Parameters:

    • value (Object) —

      The value to find.

  • #find_index {|value| ... } ⇒ Integer

    Yields:

    • (value) —

      The block to find with.

Returns:

  • (Integer) —

    The index of the value.



671
672
673
674
675
676
677
678
679
680
 
# File 'lib/sorted_containers/sorted_array.rb', line 671

def find_index(value = nil)
  return nil if @size.zero?

  if block_given?
    each_with_index { |val, idx| return idx if yield(val) }
    nil
  else
    bsearch_index { |val| val >= value }
  end
end

#first ⇒ Object

Retrieves the first value in the sorted array.

Returns:

  • (Object) —

    The first value in the array.



686
687
688
689
690
 
# File 'lib/sorted_containers/sorted_array.rb', line 686

def first
  return nil if @size.zero?

  @lists.first.first
end

#flatten(level = nil) ⇒ SortedArray

Returns a new SortedArray that is a recursive flattening of the array.

Each non-array element is unchanged, and each array element is recursively flattened. When the optional level argument is given, the recursion is limited to that level.

Parameters:

  • level (Integer) (defaults to: nil) —

    The level to flatten to.

Returns:



699
700
701
 
# File 'lib/sorted_containers/sorted_array.rb', line 699

def flatten(level = nil)
  self.class.new(to_a.flatten(level), load_factor: @load_factor)
end

#flatten!(level = nil) ⇒ SortedArray

Flattens the array in place.

Each non-array element is unchanged, and each array element is recursively flattened. When the optional level argument is given, the recursion is limited to that level.

Parameters:

  • level (Integer) (defaults to: nil) —

    The level to flatten to.

Returns:



710
711
712
713
714
715
 
# File 'lib/sorted_containers/sorted_array.rb', line 710

def flatten!(level = nil)
  values = to_a.flatten(level)
  clear
  update(values)
  self
end

#hash ⇒ Integer

Returns the integer hash value for the sorted array. Two arrays with the same content will have the same hash value.

Returns:

  • (Integer) —

    The hash value.



721
722
723
 
# File 'lib/sorted_containers/sorted_array.rb', line 721

def hash
  @lists.hash
end

#include?(value) ⇒ Boolean

Checks if the sorted array contains a value.

Parameters:

  • value (Object) —

    The value to check.

Returns:

  • (Boolean) —

    True if the value is found, false otherwise.



729
730
731
732
733
734
735
736
 
# File 'lib/sorted_containers/sorted_array.rb', line 729

def include?(value)
  i = internal_bisect_left(@maxes, value)
  return false if i == @maxes.size

  sublist = @lists[i]
  idx = internal_bisect_left(sublist, value)
  idx < sublist.size && sublist[idx] == value
end

#inspect ⇒ String

Returns a string representation of the sorted array.

Returns:

  • (String) —

    A string representation of the sorted array.



741
742
743
744
 
# File 'lib/sorted_containers/sorted_array.rb', line 741

def inspect
  "#<#{self.class} size=#{@size} array_index=#{@array_index} " \
    "offset=#{@offset} maxes=#{@maxes} items=#{@lists}>"
end

#intersect?(other) ⇒ Boolean

Returns true if the SortedArray and other have at least one element in common, otherwise returns false Elements are compared using eql?

Parameters:

Returns:

  • (Boolean) —

    true if the array and other have at least one element in common, otherwise false



751
752
753
754
755
756
 
# File 'lib/sorted_containers/sorted_array.rb', line 751

def intersect?(other)
  each do |value|
    return true if other.include_eql?(value)
  end
  false
end

#intersection(other) ⇒ SortedArray Also known as: &

Returns a new SortedArray with the values from the union of the two arrays.

Parameters:

  • other (SortedArray) —

    The other array to union with.

Returns:



58
59
60
 
# File 'lib/sorted_containers/sorted_array.rb', line 58

def intersection(other)
  self.class.new(to_a & other.to_a, load_factor: @load_factor)
end

#join(separator = $OUTPUT_FIELD_SEPARATOR) ⇒ String

Returns a String formed by joining each element of the array with the given separator.

Parameters:

  • separator (String) (defaults to: $OUTPUT_FIELD_SEPARATOR) —

    The separator to join the elements with.

Returns:

  • (String) —

    The joined string.



762
763
764
 
# File 'lib/sorted_containers/sorted_array.rb', line 762

def join(separator = $OUTPUT_FIELD_SEPARATOR)
  to_a.join(separator)
end

#keep_if {|value| ... } ⇒ SortedArray, Enumerator

Retains those elements for which the block returns a truthy value; deletes all other elements; returns self

Returns an Enumerator if no block is given.

Yields:

  • (value) —

    The block to keep with.

Returns:

  • (SortedArray, Enumerator) —

    The array with the kept values.



772
773
774
775
776
777
778
779
 
# File 'lib/sorted_containers/sorted_array.rb', line 772

def keep_if
  return to_enum(:keep_if) unless block_given?

  (@size - 1).downto(0) do |index|
    delete_at(index) unless yield(self[index])
  end
  self
end

#last ⇒ Object

Retrieves the last value in the sorted array.

Returns:

  • (Object) —

    The last value in the array.



784
785
786
787
788
 
# File 'lib/sorted_containers/sorted_array.rb', line 784

def last
  return nil if @size.zero?

  @lists.last.last
end

#map! {|value| ... } ⇒ SortedArray, Enumerator Also known as: collect!

Calls the block, if given, with each element of self; returns self after the block has been executed.

If no block is given, returns an Enumerator.

Yields:

  • (value) —

    The block to map with.

Returns:



386
387
388
389
390
391
392
393
394
395
396
397
398
 
# File 'lib/sorted_containers/sorted_array.rb', line 386

def map!
  return to_enum(:map!) unless block_given?

  new_values = []
  # rubocop:disable Style/MapIntoArray
  each { |value| new_values << yield(value) }
  # rubocop:enable Style/MapIntoArray
  clear
  # Experimitation shows that it's faster to add all values at once
  # rather than adding them one by one
  update(new_values)
  self
end

#max ⇒ Object

Returns the maximum value in the sorted array.

Returns:

  • (Object) —

    The maximum value in the array.



944
945
946
 
# File 'lib/sorted_containers/sorted_array.rb', line 944

def max
  @lists.last&.last
end

#min ⇒ Object

Returns the minimum value in the sorted array.

Returns:

  • (Object) —

    The minimum value in the array.



951
952
953
 
# File 'lib/sorted_containers/sorted_array.rb', line 951

def min
  @lists.first&.first
end

#minmax {|value| ... } ⇒ Array

Returns a 2-element array containing the minimum and maximum values in the sorted array. If a block is given, the result of the block is computed for each value in the array, and the minimum and maximum values are computed from the result.

Yields:

  • (value) —

    The block to compute with.

Returns:

  • (Array) —

    A 2-element array containing the minimum and maximum values.



961
962
963
964
965
966
967
968
969
970
971
 
# File 'lib/sorted_containers/sorted_array.rb', line 961

def minmax
  if block_given?
    each.reduce([nil, nil]) do |(min_value, max_value), value|
      min_value = value if min_value.nil? || yield(value, min_value).negative?
      max_value = value if max_value.nil? || yield(value, max_value).positive?
      [min_value, max_value]
    end
  else
    [min, max]
  end
end

#multiply(num) ⇒ SortedArray Also known as: *

When non-negative, multiplies returns a new Array with each value repeated ‘int` times.

Parameters:

  • num (Integer) —

    The integer to multiply the array by.

Returns:



67
68
69
 
# File 'lib/sorted_containers/sorted_array.rb', line 67

def multiply(num)
  self.class.new(to_a * num, load_factor: @load_factor)
end

#pack(template, buffer: nil) ⇒ String

Packs the values in the array into a binary sequence.

Parameters:

  • template (String) —

    The template to pack the values with.

  • buffer (String) (defaults to: nil) —

    The buffer to pack the values into.

Returns:

  • (String) —

    The packed values.

See Also:

  • Array#pack


979
980
981
 
# File 'lib/sorted_containers/sorted_array.rb', line 979

def pack(template, buffer: nil)
  to_a.pack(template, buffer: buffer)
end

#pop(n = nil) ⇒ Object

Pops the last value from the sorted array.

Parameters:

  • n (Integer) (defaults to: nil) —

    The number of values to pop.

Returns:

  • (Object) —

    The last value in the array.



990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
 
# File 'lib/sorted_containers/sorted_array.rb', line 990

def pop(n = nil)
  return nil if @size.zero?

  if n.nil?
    index = @size - 1
    delete_at(index)
  else
    values = []
    n.times do
      return values if @size.zero?

      index = @size - 1
      values.prepend(delete_at(index))
    end
    values
  end
end

#product(*other_arrays) {|value| ... } ⇒ SortedArray

Computes and returns or yields all combinations of elements from all the Arrays, including both self and other_arrays.

Parameters:

  • other_arrays (SortedArray) —

    The arrays to combine with.

Yields:

  • (value) —

    The block to combine with.

Returns:



1017
1018
1019
1020
1021
1022
1023
 
# File 'lib/sorted_containers/sorted_array.rb', line 1017

def product(*other_arrays, &block)
  arrays = other_arrays.map(&:to_a)
  self.class.new(
    to_a.product(*arrays, &block),
    load_factor: @load_factor
  )
end

#rassoc(obj) ⇒ Array

Returns the first element in self that is an Array whose second element == obj:

Time complexity: O(n)

Parameters:

  • obj (Object) —

    The object to search for.

Returns:

  • (Array) —

    The first element in self that is an Array whose second element == obj.



1031
1032
1033
1034
 
# File 'lib/sorted_containers/sorted_array.rb', line 1031

def rassoc(obj)
  index = find_index { |x| x.is_a?(Array) && x[1] >= obj }
  index.nil? ? nil : self[index]
end

#reject! {|value| ... } ⇒ SortedArray, Enumerator

Deletes every element of self for which block evaluates to true.

Returns self if any changes were made, otherwise returns nil.

Returns an Enumerator if no block is given.

Yields:

  • (value) —

    The block to reject with.

Returns:



1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
 
# File 'lib/sorted_containers/sorted_array.rb', line 1044

def reject!
  return to_enum(:reject!) unless block_given?

  indexes_to_delete = []
  each_with_index do |value, index|
    indexes_to_delete << index if yield(value)
  end
  return nil if indexes_to_delete.empty?

  indexes_to_delete.reverse.each { |index| delete_at(index) }
  self
end

#replace(other) ⇒ SortedArray

Replaces the contents of self with the contents of other.

Parameters:

  • other (SortedArray) —

    The other array to replace with.

Returns:



794
795
796
797
798
799
800
801
802
 
# File 'lib/sorted_containers/sorted_array.rb', line 794

def replace(other)
  @lists = other.lists.map(&:dup)
  @maxes = other.maxes.dup
  @array_index = other.array_index.dup
  @offset = other.offset
  @load_factor = other.load_factor
  @size = other.size
  self
end

#reverse_each {|value| ... } ⇒ Enumerator

Iterates over the sorted array in reverse order.

Yields:

  • (value) —

    Gives each value to the block.

Returns:

  • (Enumerator) —

    If no block is given, an Enumerator is returned.



1061
1062
1063
1064
1065
1066
1067
 
# File 'lib/sorted_containers/sorted_array.rb', line 1061

def reverse_each(&block)
  return to_enum(:reverse_each) unless block_given?

  @lists.reverse_each do |sublist|
    sublist.reverse_each(&block)
  end
end

#rindex(value) ⇒ Integer #rindex {|value| ... } ⇒ Integer

Returns the index of the last element for which object == element.

Returns an Enumerator if no block or value is given.

When a block is given but no value, the block is used to find the last element.

Overloads:

  • #rindex(value) ⇒ Integer

    Parameters:

    • value (Object) —

      The value to find.

  • #rindex {|value| ... } ⇒ Integer

    Yields:

    • (value) —

      The block to find with.

Returns:

  • (Integer) —

    The index of the value.



1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
 
# File 'lib/sorted_containers/sorted_array.rb', line 1085

def rindex(value = nil)
  return to_enum(:rindex, value) unless block_given? || value
  return nil if @size.zero?

  if value.nil?
    reverse_each.with_index do |val, idx|
      return @size - idx - 1 if yield(val)
    end
    nil
  else
    warn "given block not used" if block_given?
    index = bisect_right(value)
    self[index - 1] == value ? index - 1 : nil
  end
end

#sample(n = nil, random: Random) ⇒ Object, Array

Returns random elements from self.

If n is given, returns an array of n random elements. If n is not given, returns a single random element.

Parameters:

  • n (Integer) (defaults to: nil) —

    The number of random elements to return.

  • random (Random) (defaults to: Random) —

    The random number generator to use.

Returns:

  • (Object, Array) —

    The random element(s).



1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
 
# File 'lib/sorted_containers/sorted_array.rb', line 1116

def sample(n = nil, random: Random)
  return nil if @size.zero?

  if n.nil?
    index = random.rand(@size)
    self[index]
  else
    raise ArgumentError, "negative sample number" if n.negative?

    n.times.map { self[random.rand(@size)] }
  end
end

#select! {|value| ... } ⇒ SortedArray, Enumerator Also known as: filter!

Calls the block, if given, with each element of self; returns self with the elements for which the block returns a truthy value.

If no block is given, returns an Enumerator.

Yields:

  • (value) —

    The block to filter with.

Returns:



648
649
650
651
652
653
654
655
656
657
 
# File 'lib/sorted_containers/sorted_array.rb', line 648

def select!
  return to_enum(:select!) unless block_given?

  indexes_to_delete = []
  each_with_index do |value, index|
    indexes_to_delete << index unless yield(value)
  end
  indexes_to_delete.reverse.each { |index| delete_at(index) }
  self
end

#shift ⇒ Object

Shifts the first value from the sorted array.

Returns:

  • (Object) —

    The first value in the array.



854
855
856
857
858
 
# File 'lib/sorted_containers/sorted_array.rb', line 854

def shift
  return nil if @size.zero?

  delete_at(0)
end

#slice(*args) ⇒ Object, Array Also known as: []

Returns elements from array at the specified index or range. Does not modify the array.

If a single index is provided, returns the value at that index.

If a range is provided, returns the values in that range.

If a start index and length are provided, returns the values starting from the start index and continuing for the given length.

Parameters:

  • args (Integer, Range, Enumerator::ArithmeticSequence) —

    The index or range of values to retrieve.

Returns:

  • (Object, Array) —

    The value or values at the specified index or range.



127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
 
# File 'lib/sorted_containers/sorted_array.rb', line 127

def slice(*args)
  case args.size
  when 1
    arg = args[0]
    case arg
    when Integer
      get_value_at_index(arg)
    when Range
      get_values_from_range(arg)
    when Enumerator::ArithmeticSequence
      get_values_from_arithmetic_sequence(arg)
    else
      raise TypeError, "no implicit conversion of #{arg.class} into Integer"
    end
  when 2
    start, length = args
    get_values_from_start_and_length(start, length)
  else
    raise ArgumentError, "wrong number of arguments (given #{args.size}, expected 1..2)"
  end
end

#slice!(*args) ⇒ Object, Array

Removes elements from array at the specified index or range and returns them. Modifies the array.

If a single index is provided, returns the value at that index.

If a range is provided, returns the values in that range.

If a start index and length are provided, returns the values starting from the start index and continuing for the given length.

Parameters:

  • args (Integer, Range, Enumerator::ArithmeticSequence) —

    The index or range of values to retrieve.

Returns:

  • (Object, Array) —

    The value or values at the specified index or range.



167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
 
# File 'lib/sorted_containers/sorted_array.rb', line 167

def slice!(*args)
  case args.size
  when 1
    arg = args[0]
    case arg
    when Integer
      value = get_value_at_index(arg)
      delete_at(arg)
      value
    when Range
      values = get_values_from_range(arg)
      values.each { |val| delete(val) }
      values
    when Enumerator::ArithmeticSequence
      values = get_values_from_arithmetic_sequence(arg)
      values.each { |val| delete(val) }
      values
    else
      raise TypeError, "no implicit conversion of #{arg.class} into Integer"
    end
  when 2
    start, length = args
    values = get_values_from_start_and_length(start, length)
    values.each { |val| delete(val) }
    values
  else
    raise ArgumentError, "wrong number of arguments (given #{args.size}, expected 1..2)"
  end
end

#sort ⇒ SortedArray

Creates a new SortedArray and resorts the values. Usefull when the values are modified and the array needs to be resorted.

Returns:



910
911
912
913
 
# File 'lib/sorted_containers/sorted_array.rb', line 910

def sort
  values = to_a
  self.class.new(values, load_factor: @load_factor)
end

#sort! ⇒ SortedArray

Resorts the values in the array. Usefull when the values are modified and the array needs to be resorted.

Returns:



919
920
921
922
923
924
 
# File 'lib/sorted_containers/sorted_array.rb', line 919

def sort!
  values = to_a
  clear
  update(values)
  self
end

#to_a ⇒ Array Also known as: to_ary

Converts the sorted array to an array.

Returns:

  • (Array) —

    An array representation of the sorted array.



901
902
903
 
# File 'lib/sorted_containers/sorted_array.rb', line 901

def to_a
  @lists.flatten(1)
end

#to_s ⇒ String

Returns a string representation of the sorted array.

Returns:

  • (String) —

    A string representation of the sorted array.



807
808
809
 
# File 'lib/sorted_containers/sorted_array.rb', line 807

def to_s
  "SortedArray(#{to_a})"
end

#union(*other_arrays) ⇒ SortedArray Also known as: |

Returns a new SortedArray that is the union of self and other_arrays. Duplicates are removed.

Parameters:

  • other_arrays (Array) —

    The arrays to union with.

Returns:



1136
1137
1138
 
# File 'lib/sorted_containers/sorted_array.rb', line 1136

def union(*other_arrays)
  self.class.new(to_a | other_arrays.flatten, load_factor: @load_factor)
end

#uniq(&block) ⇒ SortedArray

Returns a new SortedArray containing the unique values in self.

Returns:



1144
1145
1146
 
# File 'lib/sorted_containers/sorted_array.rb', line 1144

def uniq(&block)
  self.class.new(to_a.uniq(&block), load_factor: @load_factor)
end

#uniq! {|value| ... } ⇒ SortedArray?

Removes duplicate values from the sorted array. Returns self if any changes were made, otherwise returns nil. If a block is given, it will use the block to determine uniqueness.

Yields:

  • (value) —

    The block to determine uniqueness.

Returns:

  • (SortedArray, nil) —

    The array with the unique values.



1154
1155
1156
1157
1158
1159
1160
1161
1162
 
# File 'lib/sorted_containers/sorted_array.rb', line 1154

def uniq!(&block)
  values = to_a.uniq(&block)

  return nil if values.size == @size

  clear
  update(values)
  self
end

#update(iterable) ⇒ Object

Updates the sorted array with values from an iterable object.

Parameters:

  • iterable (Enumerable) —

    The iterable object to update the array with.



865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
 
# File 'lib/sorted_containers/sorted_array.rb', line 865

def update(iterable)
  # Convert the iterable to an array and sort it
  values = iterable.to_a.sort

  # If maxes are already defined and not empty
  unless @maxes.empty?
    if values.length * 4 >= @size
      # If the new values are significant in number, merge all lists and re-sort
      @lists << values
      values = @lists.flatten.sort
      clear
    else
      # Otherwise, add each item individually
      values.each { |val| add(val) }
      return
    end
  end

  # Break sorted values into chunks of size @load_factor and extend lists
  @lists += values.each_slice(@load_factor).to_a

  # Update maxes based on the last element of each sublist
  @maxes = @lists.map(&:last)

  # Update the total length of the list
  @size = values.length

  # Clear the index as it might be outdated
  @array_index.clear
end

#values_at(*indexes) ⇒ Array

Returns a new SortedArray containing the values from the given indexes and ranges.

Parameters:

  • indexes (Integer, Range) —

    The indexes and ranges to get values from.

Returns:

  • (Array) —

    The values from the given indexes and ranges.



1168
1169
1170
1171
1172
1173
1174
1175
1176
 
# File 'lib/sorted_containers/sorted_array.rb', line 1168

def values_at(*indexes)
  indexes.map do |index|
    if index.is_a?(Range)
      get_values_from_range(index)
    else
      get_value_at_index(index)
    end
  end.flatten
end

#zip(*other_arrays, &block) ⇒ SortedArray

Combines each element of the sorted array with the corresponding elements from other arrays.

Parameters:

  • other_arrays (Array) —

    The other arrays to zip with the sorted array.

  • block (Proc) —

    An optional block to apply to each zipped element.

Returns:

  • (SortedArray) —

    A new SortedArray containing the zipped elements.



1183
1184
1185
 
# File 'lib/sorted_containers/sorted_array.rb', line 1183

def zip(*other_arrays, &block)
  self.class.new(to_a.zip(*other_arrays, &block), load_factor: @load_factor)
end