Class: Ibex::Runtime::RepairPriorityQueue

Inherits:
Object
  • Object
show all
Defined in:
lib/ibex/runtime/repair_priority_queue.rb,
sig/ibex/runtime/repair_priority_queue.rbs

Overview

Minimal binary heap ordered by an immutable Array priority.

Instance Method Summary collapse

Constructor Details

#initialize ⇒ RepairPriorityQueue

Returns a new instance of RepairPriorityQueue.

RBS:

  • () -> void



11
12
13
 
# File 'lib/ibex/runtime/repair_priority_queue.rb', line 11

def initialize
  @entries = []
end

Instance Method Details

#compare(left, right) ⇒ Integer

RBS:

  • ([Array[untyped], untyped] left, [Array[untyped], untyped] right) -> Integer

Parameters:

  • left ([ Array[untyped], untyped ])
  • right ([ Array[untyped], untyped ])

Returns:

  • (Integer) 


55
56
57
 
# File 'lib/ibex/runtime/repair_priority_queue.rb', line 55

def compare(left, right)
  (left.fetch(0) <=> right.fetch(0)) || 0
end

#empty? ⇒ Boolean

RBS:

  • () -> bool

Returns:

  • (Boolean) 


16
 
# File 'lib/ibex/runtime/repair_priority_queue.rb', line 16

def empty? = @entries.empty?

#pop ⇒ [ Array[untyped], untyped ]?

RBS:

  • () -> [Array[untyped], untyped]?

Returns:

  • ([ Array[untyped], untyped ], nil) 


34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
# File 'lib/ibex/runtime/repair_priority_queue.rb', line 34

def pop
  first = @entries.first
  tail = @entries.pop
  return first if @entries.empty? || !first || !tail

  index = 0
  while (child = (index * 2) + 1) < @entries.length
    right = child + 1
    child = right if right < @entries.length && compare(@entries[right], @entries[child]).negative?
    break if compare(tail, @entries[child]) <= 0

    @entries[index] = @entries[child]
    index = child
  end
  @entries[index] = tail
  first
end

#push(priority, value) ⇒ void

This method returns an undefined value.

RBS:

  • (Array[untyped] priority, untyped value) -> void

Parameters:

  • priority (Array[untyped])
  • value (Object) 


19
20
21
22
23
24
25
26
27
28
29
30
31
 
# File 'lib/ibex/runtime/repair_priority_queue.rb', line 19

def push(priority, value)
  entry = [priority, value] #: [Array[untyped], untyped]
  @entries << entry
  index = @entries.length - 1
  while index.positive?
    parent = (index - 1) / 2
    break if compare(@entries[parent], entry) <= 0

    @entries[index] = @entries[parent]
    index = parent
  end
  @entries[index] = entry
end