Class: SortedContainers::SortedArray

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

Overview

The SortedArray class is a sorted array implementation.

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

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.



21
22
23
24
25
26
27
28
29
 
# File 'lib/sorted_containers/sorted_array.rb', line 21

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

Instance Attribute Details

#size ⇒ Object Also known as: length

Returns the value of attribute size.



14
15
16
 
# File 'lib/sorted_containers/sorted_array.rb', line 14

def size
  @size
end

Instance Method Details

#<<(value) ⇒ Object

Alias for add

Parameters:

  • value (Object) —

    The value to add.



61
62
63
 
# File 'lib/sorted_containers/sorted_array.rb', line 61

def <<(value)
  add(value)
end

#[](*args) ⇒ Object, Array

Tries to match the behavior of Array#[] alias for slice

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.



139
140
141
 
# File 'lib/sorted_containers/sorted_array.rb', line 139

def [](*args)
  slice(*args)
end

#add(value) ⇒ Object

Adds a value to the sorted array.

Parameters:

  • value (Object) —

    The value to add.



36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
 
# File 'lib/sorted_containers/sorted_array.rb', line 36

def add(value)
  if @maxes.empty?
    @lists.append([value])
    @maxes.append(value)
  else
    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
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.



88
89
90
91
92
93
94
95
96
97
 
# File 'lib/sorted_containers/sorted_array.rb', line 88

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.



108
109
110
111
112
113
114
115
116
117
 
# File 'lib/sorted_containers/sorted_array.rb', line 108

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

#clear ⇒ void

This method returns an undefined value.

Clears the sorted array, removing all values.



303
304
305
306
307
308
309
 
# File 'lib/sorted_containers/sorted_array.rb', line 303

def clear
  @lists.clear
  @maxes.clear
  @index.clear
  @offset = 0
  @size = 0
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.



291
292
293
294
295
296
297
298
 
# File 'lib/sorted_containers/sorted_array.rb', line 291

def count(value = nil)
  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.



122
123
124
125
126
127
128
129
130
131
132
 
# File 'lib/sorted_containers/sorted_array.rb', line 122

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.



234
235
236
237
238
239
 
# File 'lib/sorted_containers/sorted_array.rb', line 234

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

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

#dup ⇒ SortedArray

Returns a new SortedArray with the same values.

Returns:



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

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.index = @index.dup
  new_instance.offset = @offset
  new_instance.load_factor = @load_factor
  new_instance.size = @size
  new_instance
end

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

Iterates over each value in the sorted array.

Yields:

  • (value) —

    Gives each value to the block.



430
431
432
433
434
 
# File 'lib/sorted_containers/sorted_array.rb', line 430

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

#empty? ⇒ Boolean

Checks if Array is empty

Returns:

  • (Boolean) 


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

def empty?
  @size.zero?
end

#first ⇒ Object

Retrieves the first value in the sorted array.

Returns:

  • (Object) —

    The first value in the array.



225
226
227
228
229
 
# File 'lib/sorted_containers/sorted_array.rb', line 225

def first
  return nil if @size.zero?

  @lists.first.first
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.



315
316
317
318
319
320
321
322
 
# File 'lib/sorted_containers/sorted_array.rb', line 315

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

#last ⇒ Object

Retrieves the last value in the sorted array.

Returns:

  • (Object) —

    The last value in the array.



216
217
218
219
220
 
# File 'lib/sorted_containers/sorted_array.rb', line 216

def last
  return nil if @size.zero?

  @lists.last.last
end

#max ⇒ Object

Returns the maximum value in the sorted array.

Returns:

  • (Object) —

    The maximum value in the array.



416
417
418
 
# File 'lib/sorted_containers/sorted_array.rb', line 416

def max
  @lists.last&.last
end

#min ⇒ Object

Returns the minimum value in the sorted array.

Returns:

  • (Object) —

    The minimum value in the array.



423
424
425
 
# File 'lib/sorted_containers/sorted_array.rb', line 423

def min
  @lists.first&.first
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:



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

def multiply(num)
  values = @lists.flatten * num
  new_instance = self.class.new
  new_instance.update(values)
  new_instance
end

#pop ⇒ Object

Pops the last value from the sorted array.

Returns:

  • (Object) —

    The last value in the array.



246
247
248
249
250
251
252
253
254
255
256
257
258
259
 
# File 'lib/sorted_containers/sorted_array.rb', line 246

def pop
  return nil if @size.zero?

  value = @lists.last.pop
  if @lists.last.empty?
    @lists.pop
    @maxes.pop
    @index.clear
  else
    @maxes[-1] = @lists.last.last
  end
  @size -= 1
  value
end

#shift ⇒ Object

Shifts the first value from the sorted array.

Returns:

  • (Object) —

    The first value in the array.



267
268
269
270
271
272
273
274
275
276
277
278
279
280
 
# File 'lib/sorted_containers/sorted_array.rb', line 267

def shift
  return nil if @size.zero?

  value = @lists.first.shift
  if @lists.first.empty?
    @lists.shift
    @maxes.shift
    @index.clear
  else
    @maxes[0] = @lists.first.first
  end
  @size -= 1
  value
end

#slice(*args) ⇒ Object, Array

Tries to match the behavior of Array#slice

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.



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

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

Tries to match the behavior of Array#slice!

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.



180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
 
# File 'lib/sorted_containers/sorted_array.rb', line 180

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

Array is already sorted. Duplicates the sorted array and returns it.

Returns:



373
374
375
376
 
# File 'lib/sorted_containers/sorted_array.rb', line 373

def sort
  # No need to sort, already sorted
  dup
end

#sort! ⇒ SortedArray

Returns self, as the array is already sorted.

Returns:



381
382
383
384
 
# File 'lib/sorted_containers/sorted_array.rb', line 381

def sort!
  # No need to sort, already sorted
  self
end

#to_a ⇒ Array

Converts the sorted array to an array.

Returns:

  • (Array) —

    An array representation of the sorted array.



366
367
368
 
# File 'lib/sorted_containers/sorted_array.rb', line 366

def to_a
  @lists.flatten
end

#to_s ⇒ String

Returns a string representation of the sorted array.

Returns:

  • (String) —

    A string representation of the sorted array.



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

def to_s
  "SortedArray(#{to_a})"
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.



330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
 
# File 'lib/sorted_containers/sorted_array.rb', line 330

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
  @index.clear
end