Class: SortedArrayBinary

Inherits:
Array
  • Object
show all
Defined in:
lib/sorted_array_binary.rb

Overview

Automatically sorted array (by using binary search). Nils aren’t allowed. Methods that reorder elements are not implemented, as well as #[]= and #fill.

Example

require 'sorted_array_binary'

# Use standard sorting via <=>.
array = SortedArrayBinary.new
array.push 'b', 'a' #=> ['a', 'b']

# Use custom sorting block.
array = SortedArrayBinary.new { |a, b| b <=> a }
array.push 'a', 'b' #=> ['b', 'a']

Defined Under Namespace

Classes: ComparisonState, InvalidSortBlock

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(*args, &b) ⇒ SortedArrayBinary 



53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
 
# File 'lib/sorted_array_binary.rb', line 53

def initialize *args, &b
  @sort_block = proc { |a, b| a <=> b }

  # Passed sort block.
  if args.size == 0 && block_given?
    @sort_block = b
    super()
    return
  end

  if args.size == 1
    # Passed initial array.
    if args.first.respond_to? :each
  self.class._check_for_nil *args.first
  super *args
  old_sort!
  return
    end

    # Passed size and block.
    if block_given?
  super *args, &b
  self.class._check_for_nil *self
  old_sort!
  return
    end

    # Passed size, but not obj, which means fill with nils.
    raise ArgumentError, "can't fill array with nils" \
  if args.first.is_a? Numeric
  end

  super
end

Class Method Details

._check_for_nil(*objs) ⇒ Object

:nodoc:

Raises:

  • (ArgumentError) 


43
44
45
46
 
# File 'lib/sorted_array_binary.rb', line 43

def self._check_for_nil *objs #:nodoc:
  raise ArgumentError, "nils aren't allowed into sorted array" \
    if objs.include?(nil)
end

Instance Method Details

#_add(*objs) ⇒ Object

private Name the following methods starting with underscore so as not to pollute Array namespace. They are considered private, but for testing purposes are left public.



146
147
148
149
150
151
152
 
# File 'lib/sorted_array_binary.rb', line 146

def _add *objs #:nodoc:
  self.class._check_for_nil *objs
  objs.each { |obj|
    old_insert _find_insert_position(obj), obj
  }
  self
end

#_check_can_calc_boundary? ⇒ Boolean

:nodoc:



154
155
156
 
# File 'lib/sorted_array_binary.rb', line 154

def _check_can_calc_boundary? #:nodoc:
  raise "can't calc boundary on empty array" if empty?
end

#_compare(a, b) ⇒ Object

:nodoc:



158
159
160
161
162
163
 
# File 'lib/sorted_array_binary.rb', line 158

def _compare a, b #:nodoc:
  ComparisonState.new(ret = @sort_block.call(a, b))
rescue ArgumentError
  raise InvalidSortBlock,
    "sort block returned invalid value: #{ret.inspect}"
end

#_find_insert_position(element_to_place) ⇒ Object

:nodoc:



165
166
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
196
197
198
199
200
201
 
# File 'lib/sorted_array_binary.rb', line 165

def _find_insert_position element_to_place #:nodoc:
  return 0 if empty?

  start_idx, end_idx = 0, size - 1
  loop {
    middle_idx = _middle_element_index(start_idx, end_idx)
    middle_el = self[middle_idx]
    after_middle_idx = middle_idx + 1

    comparison_state = _compare(element_to_place, middle_el)

    # 1. Equals to the middle element. Insert after el.
    return after_middle_idx if comparison_state.equal?

    # 2. Less than the middle element.
    if comparison_state.less?
  # There's nothing to the left. So insert it as the first element.
  return 0 if _left_boundary? middle_idx

  end_idx = middle_idx - 1
  next
    end

    # 3. Greater than the middle element.
    #
    # Right boundary? Put element_to_place after the last (middle) element.
    return after_middle_idx if _right_boundary? middle_idx

    # Less than after middle element? Put it right before it!
    after_middle_el = self[after_middle_idx]
    ret = _compare(element_to_place, after_middle_el)
    return after_middle_idx if ret.equal? || ret.less?

    # Proceeed to divide the right part.
    start_idx = after_middle_idx
  }
end

#_left_boundary?(idx) ⇒ Boolean

:nodoc:



203
204
205
206
 
# File 'lib/sorted_array_binary.rb', line 203

def _left_boundary? idx #:nodoc:
  _check_can_calc_boundary?
  idx == 0
end

#_middle_element_index(start, ending) ⇒ Object

:nodoc:



208
209
210
 
# File 'lib/sorted_array_binary.rb', line 208

def _middle_element_index start, ending #:nodoc:
  start + (ending - start)/2
end

#_not_implemented(*args) ⇒ Object

Not implemented methods.

The following methods are not implemented mostly because they change order of elements. The rest ([]= and fill) arguably aren’t useful on a sorted array.

Raises:

  • (NotImplementedError) 


93
94
95
 
# File 'lib/sorted_array_binary.rb', line 93

def _not_implemented *args #:nodoc:
  raise NotImplementedError
end

#_right_boundary?(idx) ⇒ Boolean

:nodoc:



212
213
214
215
 
# File 'lib/sorted_array_binary.rb', line 212

def _right_boundary? idx #:nodoc:
  _check_can_calc_boundary?
  idx == size - 1
end

#collect!(&b) ⇒ Object Also known as: map!

Same as Array#collect!, but:

  • Disallow nils in the resulting array.

  • The resulting array is sorted.



105
106
107
 
# File 'lib/sorted_array_binary.rb', line 105

def collect! &b
  replace(collect &b)
end

#concat(other_ary) ⇒ Object

Same as Array#concat, but:

  • Disallow nils in the passed array.

  • The resulting array is sorted.



113
114
115
 
# File 'lib/sorted_array_binary.rb', line 113

def concat other_ary
  _add *other_ary
end

#flatten!(*args) ⇒ Object

Same as Array#flatten!, but:

  • Disallow nils in the resulting array.

  • The resulting array is sorted.



120
121
122
 
# File 'lib/sorted_array_binary.rb', line 120

def flatten! *args
  replace(flatten *args)
end

#push(*objs) ⇒ Object Also known as: <<

Add objects to array, automatically placing them according to sort order. Disallow nils.



126
127
128
 
# File 'lib/sorted_array_binary.rb', line 126

def push *objs
  _add *objs
end

#replace(other_ary) ⇒ Object

Same as Array#replace, but:

  • Disallow nils in @other_ary.

  • The resulting array is sorted.



134
135
136
137
138
139
 
# File 'lib/sorted_array_binary.rb', line 134

def replace other_ary
  self.class._check_for_nil *other_ary
  super
  old_sort!
  self
end