Class: Lite::Containers::SortedArray

Inherits:
Object
  • Object
show all
Includes:
Enumerable, Abstract::Collection, Abstract::Deque, Abstract::ImplicitKey, Abstract::SortedMap
Defined in:
lib/lite/containers/sorted_array.rb,
lib/lite/containers/sorted_array/binary_search.rb

Overview

rubocop:disable Metrics/ClassLength

Defined Under Namespace

Modules: BinarySearch Classes: Error

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Methods included from Abstract::ImplicitKey

#<<

Methods included from Abstract::Collection

#count, #empty?, #length

Constructor Details

#initialize(array, comparison, merge) ⇒ SortedArray

Returns a new instance of SortedArray.



73
74
75
76
77
 
# File 'lib/lite/containers/sorted_array.rb', line 73

def initialize(array, comparison, merge)
  @comparison = comparison
  @merge = merge
  @array = array.freeze
end

Instance Attribute Details

#comparator ⇒ Object (readonly)

Returns the value of attribute comparator.



23
24
25
 
# File 'lib/lite/containers/sorted_array.rb', line 23

def comparator
  @comparator
end

Class Method Details

.from_sorted(type, array, key_extractor: nil, merge: nil) ⇒ Object 



31
32
33
34
35
 
# File 'lib/lite/containers/sorted_array.rb', line 31

def self.from_sorted(type, array, key_extractor: nil, merge: nil)
  comparison = comparison(type, key_extractor)
  sorted = ensure_sorted!(array, comparison)
  construct(sorted, comparison, merge)
end

.from_sorted_unsafe(type, sorted, key_extractor: nil, merge: nil) ⇒ Object 



37
38
39
40
 
# File 'lib/lite/containers/sorted_array.rb', line 37

def self.from_sorted_unsafe(type, sorted, key_extractor: nil, merge: nil)
  comparison = comparison(type, key_extractor)
  construct(sorted, comparison, merge)
end

.from_unsorted(type, array, key_extractor: nil, merge: nil) ⇒ Object 



25
26
27
28
29
 
# File 'lib/lite/containers/sorted_array.rb', line 25

def self.from_unsorted(type, array, key_extractor: nil, merge: nil)
  comparison = comparison(type, key_extractor)
  sorted = array.sort { |a, b| comparison.compare(a, b) }
  construct(sorted, comparison, merge)
end

Instance Method Details

#[](index) ⇒ Object 



133
134
135
 
# File 'lib/lite/containers/sorted_array.rb', line 133

def [](index)
  array[index]
end

#back ⇒ Object 



123
124
125
 
# File 'lib/lite/containers/sorted_array.rb', line 123

def back
  array.first
end

#drain! ⇒ Object 



79
80
81
82
83
 
# File 'lib/lite/containers/sorted_array.rb', line 79

def drain!
  array = @array
  @array = []
  array.reverse
end

#each(&block) ⇒ Object 



100
101
102
103
104
105
106
107
 
# File 'lib/lite/containers/sorted_array.rb', line 100

def each(&block)
  if block
    array.each(&block)
    self
  else
    array.each
  end
end

#find(key) ⇒ Object 



142
143
144
145
 
# File 'lib/lite/containers/sorted_array.rb', line 142

def find(key)
  found, index = BinarySearch.position_of(@array, key, comparison: comparison)
  self[index] if found
end

#find_or_nearest_backwards(key) ⇒ Object 



147
148
149
150
151
152
153
 
# File 'lib/lite/containers/sorted_array.rb', line 147

def find_or_nearest_backwards(key)
  found, position = BinarySearch.position_of(@array, key, comparison: comparison)
  return self[position] if found
  return if position.zero?

  self[position - 1]
end

#find_or_nearest_forwards(key) ⇒ Object 



155
156
157
158
 
# File 'lib/lite/containers/sorted_array.rb', line 155

def find_or_nearest_forwards(key)
  _, position = BinarySearch.position_of(@array, key, comparison: comparison)
  self[position]
end

#front ⇒ Object 



113
114
115
 
# File 'lib/lite/containers/sorted_array.rb', line 113

def front
  array.last
end

#index_of(item) ⇒ Object 



89
90
91
92
93
94
 
# File 'lib/lite/containers/sorted_array.rb', line 89

def index_of(item)
  found, index = position_of(item)
  return unless found

  index
end

#key?(key) ⇒ Boolean

Returns:

  • (Boolean) 


137
138
139
140
 
# File 'lib/lite/containers/sorted_array.rb', line 137

def key?(key)
  found, = BinarySearch.position_of(@array, key, comparison: comparison)
  found
end

#pop_back ⇒ Object 



127
128
129
130
131
 
# File 'lib/lite/containers/sorted_array.rb', line 127

def pop_back
  item, *rest = @array
  @array = rest.freeze
  item
end

#pop_front ⇒ Object 



117
118
119
120
121
 
# File 'lib/lite/containers/sorted_array.rb', line 117

def pop_front
  *rest, item = @array
  @array = rest.freeze
  item
end

#position_of(item) ⇒ Object 



96
97
98
 
# File 'lib/lite/containers/sorted_array.rb', line 96

def position_of(item)
  BinarySearch.find_position(@array, comparison.for_item(item))
end

#push(item) ⇒ Object 



170
171
172
173
174
175
176
177
 
# File 'lib/lite/containers/sorted_array.rb', line 170

def push(item)
  found, position = position_of(item)
  item = handle_duplicate(position, item) if found
  before = array[0...position]
  keep_from = found ? position + 1 : position
  after = array[keep_from..]
  @array = [*before, item, *after].freeze
end

#remove_at(index) ⇒ Object 



160
161
162
163
164
165
166
167
168
 
# File 'lib/lite/containers/sorted_array.rb', line 160

def remove_at(index)
  return if index.negative?

  before = array[0...index]
  to_remove = array[index]
  after = array[(index + 1)..]
  @array = [*before, *after].freeze
  to_remove
end

#size ⇒ Object 



85
86
87
 
# File 'lib/lite/containers/sorted_array.rb', line 85

def size
  @array.size
end

#to_array ⇒ Object 



109
110
111
 
# File 'lib/lite/containers/sorted_array.rb', line 109

def to_array
  array
end