Class: Winloop::MinHeap

Inherits:
Object
  • Object
show all
Defined in:
lib/winloop/scheduler.rb

Overview

A tiny binary min-heap keyed on the node's #deadline. Enough for timers.

Instance Method Summary collapse

Constructor Details

#initialize ⇒ MinHeap

Returns a new instance of MinHeap.



609
610
611
 
# File 'lib/winloop/scheduler.rb', line 609

def initialize
  @a = []
end

Instance Method Details

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


613
 
# File 'lib/winloop/scheduler.rb', line 613

def empty? = @a.empty?

#peek ⇒ Object 



615
 
# File 'lib/winloop/scheduler.rb', line 615

def peek = @a[0]

#pop ⇒ Object 



629
630
631
632
633
634
635
636
637
638
 
# File 'lib/winloop/scheduler.rb', line 629

def pop
  return nil if @a.empty?
  top = @a[0]
  last = @a.pop
  unless @a.empty?
    @a[0] = last
    sift_down(0)
  end
  top
end

#push(node) ⇒ Object 



617
618
619
620
621
622
623
624
625
626
627
 
# File 'lib/winloop/scheduler.rb', line 617

def push(node)
  @a << node
  i = @a.size - 1
  while i > 0
    parent = (i - 1) / 2
    break if @a[parent].deadline <= @a[i].deadline
    @a[parent], @a[i] = @a[i], @a[parent]
    i = parent
  end
  node
end

#size ⇒ Object 



614
 
# File 'lib/winloop/scheduler.rb', line 614

def size = @a.size