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.



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

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.



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

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
 
# File 'lib/sorted_containers/sorted_array.rb', line 355

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

  pos = @maxes.bsearch_index(&block) || 0

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

#clear ⇒ SortedArray

Clears the sorted array, removing all values.

Returns:



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

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.



403
404
405
406
407
408
 
# File 'lib/sorted_containers/sorted_array.rb', line 403

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.



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

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.



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

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.



446
447
448
449
450
451
 
# File 'lib/sorted_containers/sorted_array.rb', line 446

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.



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

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.



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

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) 


497
498
499
500
501
502
 
# File 'lib/sorted_containers/sorted_array.rb', line 497

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.



512
513
514
515
516
 
# File 'lib/sorted_containers/sorted_array.rb', line 512

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:



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

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.



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

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.



534
535
536
537
538
 
# File 'lib/sorted_containers/sorted_array.rb', line 534

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) 


543
544
545
 
# File 'lib/sorted_containers/sorted_array.rb', line 543

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.



555
556
557
558
559
 
# File 'lib/sorted_containers/sorted_array.rb', line 555

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) 


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

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:



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

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.



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

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.



684
685
686
687
688
 
# File 'lib/sorted_containers/sorted_array.rb', line 684

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:



697
698
699
 
# File 'lib/sorted_containers/sorted_array.rb', line 697

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:



708
709
710
711
712
713
 
# File 'lib/sorted_containers/sorted_array.rb', line 708

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.



719
720
721
 
# File 'lib/sorted_containers/sorted_array.rb', line 719

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.



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

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.



739
740
741
742
 
# File 'lib/sorted_containers/sorted_array.rb', line 739

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



749
750
751
752
753
754
 
# File 'lib/sorted_containers/sorted_array.rb', line 749

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.



760
761
762
 
# File 'lib/sorted_containers/sorted_array.rb', line 760

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.



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

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.



782
783
784
785
786
 
# File 'lib/sorted_containers/sorted_array.rb', line 782

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:



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

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.



942
943
944
 
# File 'lib/sorted_containers/sorted_array.rb', line 942

def max
  @lists.last&.last
end

#min ⇒ Object

Returns the minimum value in the sorted array.

Returns:

  • (Object) —

    The minimum value in the array.



949
950
951
 
# File 'lib/sorted_containers/sorted_array.rb', line 949

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.



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

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


977
978
979
 
# File 'lib/sorted_containers/sorted_array.rb', line 977

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.



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

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:



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

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.



1029
1030
1031
1032
 
# File 'lib/sorted_containers/sorted_array.rb', line 1029

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:



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

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:



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

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.



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

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.



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

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).



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

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:



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

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.



852
853
854
855
856
 
# File 'lib/sorted_containers/sorted_array.rb', line 852

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:



908
909
910
911
 
# File 'lib/sorted_containers/sorted_array.rb', line 908

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:



917
918
919
920
921
922
 
# File 'lib/sorted_containers/sorted_array.rb', line 917

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.



899
900
901
 
# File 'lib/sorted_containers/sorted_array.rb', line 899

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.



805
806
807
 
# File 'lib/sorted_containers/sorted_array.rb', line 805

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:



1134
1135
1136
 
# File 'lib/sorted_containers/sorted_array.rb', line 1134

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:



1142
1143
1144
 
# File 'lib/sorted_containers/sorted_array.rb', line 1142

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.



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

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.



863
864
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
 
# File 'lib/sorted_containers/sorted_array.rb', line 863

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.



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

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.



1181
1182
1183
 
# File 'lib/sorted_containers/sorted_array.rb', line 1181

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