Class: Pigeon::SortedArray

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

Defined Under Namespace

Classes: SortArgumentRequired

Instance Method Summary collapse

Constructor Details

#initialize(&sort_method) ⇒ SortedArray

Creates a new sorted array with an optional sort method supplied as a block. The sort method supplied should accept two arguments that are objects in the array to be compared and should return -1, 0, or 1 based on their sorting order. By default the comparison performed is <=>



15
16
17
18
19
20
21
22
23
24
25
26
27
 
# File 'lib/pigeon/sorted_array.rb', line 15

def initialize(&sort_method)
  sort_method ||= lambda { |a,b| a <=> b }
  
  @sort_method =
    case (sort_method && sort_method.arity)
    when 2
      sort_method
    when 1
      lambda { |a,b| sort_method.call(a) <=> sort_method.call(b) }
    else
      raise SortArgumentRequired
    end
end

Instance Method Details

#+(array) ⇒ Object

Combines another array with this one and returns the sorted result.



54
55
56
 
# File 'lib/pigeon/sorted_array.rb', line 54

def +(array)
  self.class[*super(array).sort(&@sort_method)]
end

#<<(object) ⇒ Object

Adds an object to the array by inserting it into the appropriate sorted location directly.



31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
 
# File 'lib/pigeon/sorted_array.rb', line 31

def <<(object)
  low = 0
  high = length
  
  while (low != high)
    mid = (high + low) / 2
    
    comparison = @sort_method.call(object, at(mid))
    
    if (comparison < 0)
      high = mid
    elsif (comparison > 0)
      low = mid + 1
    else
      low = mid
      break
    end
  end
  
  insert(low, object)
end