Class: VCAP::PriorityQueueFIFO

Inherits:
Object
  • Object
show all
Defined in:
lib/vcap/priority_queue.rb

Direct Known Subclasses

PrioritySet

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ PriorityQueueFIFO

Returns a new instance of PriorityQueueFIFO.



32
33
34
35
36
 
# File 'lib/vcap/priority_queue.rb', line 32

def initialize
  @heap_arr = []
  @p2b = {} #hash mapping priorities to buckets
  @size = 0
end

Instance Attribute Details

#size ⇒ Object (readonly)

Returns the value of attribute size.



30
31
32
 
# File 'lib/vcap/priority_queue.rb', line 30

def size
  @size
end

Instance Method Details

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


38
39
40
 
# File 'lib/vcap/priority_queue.rb', line 38

def empty?
  size == 0
end

#insert(item, priority = 0) ⇒ Object

Raises:

  • (ArgumentError) 


42
43
44
45
46
47
48
49
 
# File 'lib/vcap/priority_queue.rb', line 42

def insert(item, priority = 0)
  raise ArgumentError, "priority can not be negative: #{priority}" if priority < 0

  unless append_to_existing_priority_bucket(item, priority)
    add_bucket_at_the_end_and_shift_up(item, priority)
  end
  @size += 1
end

#remove ⇒ Object 



51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
 
# File 'lib/vcap/priority_queue.rb', line 51

def remove
  return nil if empty?
  bucket = top_bucket
  priority = top_priority
  elem = bucket.shift
  @size -= 1
  if empty?
    @heap_arr.clear
    @p2b.clear
  elsif bucket.empty?
    @heap_arr[0] = @heap_arr.pop
    @p2b.delete(priority)
    shift_down
  else
    #do nothing, we just shifted a value from a bucket and it still isn't empty, so no rearrangement is needed
  end
  elem
end