Class: TraceVisualization::Data::SortedArray

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

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(array = nil) ⇒ SortedArray

Returns a new instance of SortedArray.



8
9
10
 
# File 'lib/trace_visualization/data/sorted_array.rb', line 8

def initialize(array = nil)
  super( array.sort ) if array
end

Class Method Details

.[](*array) ⇒ Object 



4
5
6
 
# File 'lib/trace_visualization/data/sorted_array.rb', line 4

def self.[] *array
  SortedArray.new(array)
end

Instance Method Details

#<<(value) ⇒ Object Also known as: push, shift 



12
13
14
 
# File 'lib/trace_visualization/data/sorted_array.rb', line 12

def << value
  insert index_of_last_LE(value), value
end

#index(value) ⇒ Object 



34
35
36
37
38
39
40
41
 
# File 'lib/trace_visualization/data/sorted_array.rb', line 34

def index value
  idx = index_of_last_LE(value)
  
  if idx != 0 && self[idx - 1] == value
    idx -= 1 while idx != 0 && self[idx - 1] == value
    idx
  end
end

#index_of_last_LE(value) ⇒ Object 



19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
# File 'lib/trace_visualization/data/sorted_array.rb', line 19

def index_of_last_LE value
  l, r = 0, length - 1
  while l <= r
    m = (r + l) / 2
    
    if value < self[m]
      r = m - 1
    else
      l = m + 1
    end
  end
  
  l
end