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']

Instance Method Summary collapse

Constructor Details

#initialize(*args, &b) ⇒ SortedArrayBinary

Returns a new instance of SortedArrayBinary.



24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
 
# File 'lib/sorted_array_binary.rb', line 24

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
  super *args
  old_sort!
  return
    end

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

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



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

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

#_find_insert_position(element_to_place) ⇒ Object

:nodoc:



109
110
111
 
# File 'lib/sorted_array_binary.rb', line 109

def _find_insert_position element_to_place #:nodoc:
  bsearch_upper_boundary { |el| @sort_block.call el, element_to_place }
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) 


58
59
60
 
# File 'lib/sorted_array_binary.rb', line 58

def _not_implemented *args #:nodoc:
  raise NotImplementedError
end

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

:nodoc:



67
68
69
 
# File 'lib/sorted_array_binary.rb', line 67

def collect! &b #:nodoc:
  replace(collect &b)
end

#concat(other_ary) ⇒ Object

:nodoc:



72
73
74
 
# File 'lib/sorted_array_binary.rb', line 72

def concat other_ary #:nodoc:
  _add *other_ary
end

#flatten!(*args) ⇒ Object

:nodoc:



76
77
78
 
# File 'lib/sorted_array_binary.rb', line 76

def flatten! *args #:nodoc:
  replace(flatten *args)
end

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

Add objects to array, automatically placing them according to sort order (via <=> by default).



82
83
84
 
# File 'lib/sorted_array_binary.rb', line 82

def push *objs
  _add *objs
end

#replace(other_ary) ⇒ Object

:nodoc:



88
89
90
91
92
 
# File 'lib/sorted_array_binary.rb', line 88

def replace other_ary #:nodoc:
  super
  old_sort! &@sort_block
  self
end

#sort! ⇒ Object

:nodoc:



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

def sort! #:nodoc:
end