Class: SortedContainers::SortedArray
- Inherits:
-
Object
- Object
- SortedContainers::SortedArray
- 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
-
#load_factor ⇒ Object
readonly
Returns the value of attribute load_factor.
-
#size ⇒ Object
(also: #length)
readonly
Returns the value of attribute size.
Class Method Summary collapse
-
.[](*args) ⇒ SortedArray
Returns a new SortedArray populated with the given objects.
Instance Method Summary collapse
-
#+(other) ⇒ SortedArray
Returns a new SortedArray with the values from both arrays.
-
#<=>(other) ⇒ Integer
Returns -1, 0, or 1 if
self
is less than, equal to, or greater than other. -
#==(other) ⇒ Boolean
Returns true if the arrays size and values are equal.
-
#[]=(*args) ⇒ Object, Array
Sets the value at the specified index or range.
-
#abbrev(pattern = nil) ⇒ Hash
Calculates the set of unambiguous abbreviations for the strings in
self
. -
#add(value) ⇒ Object
(also: #<<, #push, #append)
Adds a value to the sorted array.
-
#assoc(obj) ⇒ Array
Returns the first element in
self
that is anArray
whose first element ==obj
:. -
#at(index) ⇒ Object
Returns the element at
Integer
offsetindex
; does not modifyself
. -
#bisect_left(value) ⇒ Integer
Returns an index to insert
value
in the sorted list. -
#bisect_right(value) ⇒ Integer
Returns an index to insert
value
in the sorted list. -
#bsearch {|value| ... } ⇒ Object
Returns an element from
self
selected by a binary search. -
#bsearch_index {|value| ... } ⇒ Integer
Returns an index of an element from
self
selected by a binary search. -
#clear ⇒ SortedArray
Clears the sorted array, removing all values.
-
#concat(*other_arrays) ⇒ SortedArray
Adds the elements of one or more arrays to the SortedArray.
-
#count(value = nil) {|value| ... } ⇒ Integer
Returns the count of elements, based on an argument or block criterion, if given.
-
#delete(value) ⇒ Object
Deletes a value from the sorted array.
-
#delete_at(index) ⇒ Object
Deletes the value at the specified index.
-
#delete_if {|value| ... } ⇒ SortedArray
Removes each element from the array for which block evaluates to true.
-
#difference(other) ⇒ SortedArray
(also: #-)
Returns a new SortedArray with the values from the difference of the two arrays.
-
#dig(index, *identifiers) ⇒ Object
Finds and returns the object in nested objects that is specified by
index
andidentifiers
. -
#drop(n) ⇒ SortedArray
Returns a new SortedArray containing all but the first
n
elements, wheren
is a non-negative integer. -
#drop_while {|value| ... } ⇒ SortedArray, Enumerator
Returns a new SortedArray containing all but the first elements for which the block returns true.
-
#dup ⇒ SortedArray
Returns a new SortedArray with the same values.
-
#each {|value| ... } ⇒ Enumerator
Iterates over each value in the sorted array.
-
#each_index {|index| ... } ⇒ Enumerator
Iterates over each index in the sorted array.
-
#empty? ⇒ Boolean
Checks if Array is empty.
-
#eql?(other) ⇒ Boolean
Returns
true
if for every element inself
there is a corresponding element inother
that are equal using Object#eql?. -
#fetch(index, *args) ⇒ Object
Returns the element at the specified index, or returns a default value if the index is out of range.
-
#fill(*args, &block) ⇒ SortedArray
Fills the array with the given value.
-
#find_index(value = nil) ⇒ Integer
(also: #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.
-
#first ⇒ Object
Retrieves the first value in the sorted array.
-
#flatten(level = nil) ⇒ SortedArray
Returns a new SortedArray that is a recursive flattening of the array.
-
#flatten!(level = nil) ⇒ SortedArray
Flattens the array in place.
-
#hash ⇒ Integer
Returns the integer hash value for the sorted array.
-
#include?(value) ⇒ Boolean
Checks if the sorted array contains a value.
-
#initialize(iterable = [], load_factor: DEFAULT_LOAD_FACTOR) ⇒ SortedArray
constructor
Initializes a new SortedArray object.
-
#inspect ⇒ String
Returns a string representation of the sorted array.
-
#intersect?(other) ⇒ Boolean
Returns
true
if the SortedArray andother
have at least one element in common, otherwise returnsfalse
Elements are compared usingeql?
. -
#intersection(other) ⇒ SortedArray
(also: #&)
Returns a new SortedArray with the values from the union of the two arrays.
-
#join(separator = $OUTPUT_FIELD_SEPARATOR) ⇒ String
Returns a
String
formed by joining each element of the array with the given separator. -
#keep_if {|value| ... } ⇒ SortedArray, Enumerator
Retains those elements for which the block returns a truthy value; deletes all other elements; returns
self
. -
#last ⇒ Object
Retrieves the last value in the sorted array.
-
#map! {|value| ... } ⇒ SortedArray, Enumerator
(also: #collect!)
Calls the block, if given, with each element of
self
; returnsself
after the block has been executed. -
#max ⇒ Object
Returns the maximum value in the sorted array.
-
#min ⇒ Object
Returns the minimum value in the sorted array.
-
#minmax {|value| ... } ⇒ Array
Returns a 2-element array containing the minimum and maximum values in the sorted array.
-
#multiply(num) ⇒ SortedArray
(also: #*)
When non-negative, multiplies returns a new Array with each value repeated ‘int` times.
-
#pack(template, buffer: nil) ⇒ String
Packs the values in the array into a binary sequence.
-
#pop(n = nil) ⇒ Object
Pops the last value from the sorted array.
-
#product(*other_arrays) {|value| ... } ⇒ SortedArray
Computes and returns or yields all combinations of elements from all the Arrays, including both
self
andother_arrays
. -
#rassoc(obj) ⇒ Array
Returns the first element in
self
that is anArray
whose second element ==obj
:. -
#reject! {|value| ... } ⇒ SortedArray, Enumerator
Deletes every element of
self
for which block evaluates to true. -
#replace(other) ⇒ SortedArray
Replaces the contents of
self
with the contents ofother
. -
#reverse_each {|value| ... } ⇒ Enumerator
Iterates over the sorted array in reverse order.
-
#rindex(value = nil) ⇒ Integer
Returns the index of the last element for which object == element.
-
#sample(n = nil, random: Random) ⇒ Object, Array
Returns random elements from
self
. -
#select! {|value| ... } ⇒ SortedArray, Enumerator
(also: #filter!)
Calls the block, if given, with each element of
self
; returnsself
with the elements for which the block returns a truthy value. -
#shift ⇒ Object
Shifts the first value from the sorted array.
-
#slice(*args) ⇒ Object, Array
(also: #[])
Returns elements from array at the specified index or range.
-
#slice!(*args) ⇒ Object, Array
Removes elements from array at the specified index or range and returns them.
-
#sort ⇒ SortedArray
Creates a new SortedArray and resorts the values.
-
#sort! ⇒ SortedArray
Resorts the values in the array.
-
#to_a ⇒ Array
(also: #to_ary)
Converts the sorted array to an array.
-
#to_s ⇒ String
Returns a string representation of the sorted array.
-
#union(*other_arrays) ⇒ SortedArray
(also: #|)
Returns a new SortedArray that is the union of
self
andother_arrays
. -
#uniq(&block) ⇒ SortedArray
Returns a new SortedArray containing the unique values in
self
. -
#uniq! {|value| ... } ⇒ SortedArray?
Removes duplicate values from the sorted array.
-
#update(iterable) ⇒ Object
Updates the sorted array with values from an iterable object.
-
#values_at(*indexes) ⇒ Array
Returns a new SortedArray containing the values from the given indexes and ranges.
-
#zip(*other_arrays, &block) ⇒ SortedArray
Combines each element of the sorted array with the corresponding elements from other arrays.
Constructor Details
#initialize(iterable = [], load_factor: DEFAULT_LOAD_FACTOR) ⇒ SortedArray
Initializes a new SortedArray object.
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.
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.
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
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.
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.
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
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.
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 (pos) end @size += 1 self end |
#assoc(obj) ⇒ Array
Returns 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
.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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
.
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.
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.
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.
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.
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
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#==
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.
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.
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.
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.
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.
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.
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.
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.
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.
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?
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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
.
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)
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.
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
.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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
.
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.
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.
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.
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.
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 |