Class: VCAP::PriorityQueueFIFO
- Inherits:
-
Object
- Object
- VCAP::PriorityQueueFIFO
- Defined in:
- lib/vcap/priority_queue.rb
Direct Known Subclasses
Instance Attribute Summary collapse
-
#size ⇒ Object
readonly
Returns the value of attribute size.
Instance Method Summary collapse
- #empty? ⇒ Boolean
-
#initialize ⇒ PriorityQueueFIFO
constructor
A new instance of PriorityQueueFIFO.
- #insert(item, priority = 0) ⇒ Object
- #remove ⇒ Object
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
38 39 40 |
# File 'lib/vcap/priority_queue.rb', line 38 def empty? size == 0 end |
#insert(item, priority = 0) ⇒ Object
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 |