class Timers::PriorityHeap

A priority queue implementation using a standard binary minheap. It uses straight comparison of its contents to determine priority. This works because a Handle from Timers::Events implements the '<' operation by comparing the expiry time. See <en.wikipedia.org/wiki/Binary_heap> for explanations of the main methods.

Public Class Methods

new() click to toggle source
# File lib/timers/priority_heap.rb, line 30
def initialize
        # The heap is represented with an array containing a binary tree. See
        # https://en.wikipedia.org/wiki/Binary_heap#Heap_implementation for how this array
        # is built up.
        @contents = []
end

Public Instance Methods

peek() click to toggle source

Returns the earliest timer or nil if the heap is empty.

# File lib/timers/priority_heap.rb, line 38
def peek
        @contents[0]
end
pop() click to toggle source

Returns the earliest timer if the heap is non-empty and removes it from the heap. Returns nil if the heap is empty. (and doesn't change the heap in that case)

# File lib/timers/priority_heap.rb, line 49
def pop
        # If the heap is empty:
        if @contents.empty?
                return nil
        end
        
        # If we have only one item, no swapping is required:
        if @contents.size == 1
                return @contents.pop
        end
        
        # Take the root of the tree:
        value = @contents[0]
        
        # Remove the last item in the tree:
        last = @contents.pop
        
        # Overwrite the root of the tree with the item:
        @contents[0] = last
        
        # Bubble it down into place:
        bubble_down(0)
        
        # validate!
        
        return value
end
push(element) click to toggle source

Inserts a new timer into the heap, then rearranges elements until the heap invariant is true again.

# File lib/timers/priority_heap.rb, line 78
def push(element)
        # Insert the item at the end of the heap:
        @contents.push(element)
        
        # Bubble it up into position:
        bubble_up(@contents.size - 1)
        
        # validate!
        
        return self
end
size() click to toggle source

Returns the number of elements in the heap

# File lib/timers/priority_heap.rb, line 43
def size
        @contents.size
end

Private Instance Methods

bubble_down(index) click to toggle source
# File lib/timers/priority_heap.rb, line 135
def bubble_down(index)
        swap_value = 0
        swap_index = nil
        
        while true
                left_index = (2 * index) + 1
                left_value = @contents[left_index]
                
                if left_value.nil?
                        # This node has no children so it can't bubble down any further.
                        # We're done here!
                        return
                end
                
                # Determine which of the child nodes has the smallest value:
                right_index = left_index + 1
                right_value = @contents[right_index]
                
                if right_value.nil? or right_value > left_value
                        swap_value = left_value
                        swap_index = left_index
                else
                        swap_value = right_value
                        swap_index = right_index
                end
                
                if @contents[index] < swap_value
                        # No need to swap, the minheap invariant is already satisfied:
                        return
                else
                        # At least one of the child node has a smaller value than the current node, swap current node with that child and update current node for if it might need to bubble down even further:
                        # swap(index, swap_index)
                        @contents[index], @contents[swap_index] = @contents[swap_index], @contents[index]
                        
                        index = swap_index
                end
        end
end
bubble_up(index) click to toggle source
# File lib/timers/priority_heap.rb, line 119
def bubble_up(index)
        parent_index = (index - 1) / 2 # watch out, integer division!
        
        while index > 0 && @contents[index] < @contents[parent_index]
                # if the node has a smaller value than its parent, swap these nodes
                # to uphold the minheap invariant and update the index of the 'current'
                # node. If the node is already at index 0, we can also stop because that
                # is the root of the heap.
                # swap(index, parent_index)
                @contents[index], @contents[parent_index] = @contents[parent_index], @contents[index]
                
                index = parent_index
                parent_index = (index - 1) / 2 # watch out, integer division!
        end
end
swap(i, j) click to toggle source
# File lib/timers/priority_heap.rb, line 115
def swap(i, j)
        @contents[i], @contents[j] = @contents[j], @contents[i]
end
validate!(index = 0) click to toggle source

Validate the heap invariant.

# File lib/timers/priority_heap.rb, line 93
def validate!(index = 0)
        if value = @contents[index]
                left_index = index*2 + 1
                if left_value = @contents[left_index]
                        unless value < left_value
                                raise "Invalid left index from #{index}!"
                        end
                        
                        validate!(left_index)
                end
                
                right_index = left_index + 1
                if right_value = @contents[right_index]
                        unless value < right_value
                                raise "Invalid right index from #{index}!"
                        end
                        
                        validate!(right_index)
                end
        end
end