class Garcon::MutexPriorityQueue
A queue collection in which the elements are sorted based on their comparison (spaceship) operator ‘<=>`. Items are added to the queue at a position relative to their priority. On removal the element with the “highest” priority is removed. By default the sort order is from highest to lowest, but a lowest-to-highest sort order can be set on construction.
The API is based on the ‘Queue` class from the Ruby standard library.
Public Class Methods
Create a new priority queue from the given list.
@param [Enumerable] list
The list to build the queue from.
@param [Hash] opts
The options for creating the queue.
@return [PriorityQueue]
The newly created and populated queue.
# File lib/garcon/task/priority_queue.rb, line 164 def self.from_list(list, opts = {}) queue = new(opts) list.each { |item| queue << item } queue end
Create a new priority queue with no items.
@param [Hash] opts
The options for creating the queue.
@option opts [Symbol] :order (:max)
dictates the order in which items are stored: from highest to lowest when `:max` or `:high`; from lowest to highest when `:min` or `:low`
# File lib/garcon/task/priority_queue.rb, line 41 def initialize(opts = {}) order = opts.fetch(:order, :max) @comparator = [:min, :low].include?(order) ? -1 : 1 clear end
Public Instance Methods
Removes all of the elements from this priority queue.
# File lib/garcon/task/priority_queue.rb, line 49 def clear @queue = [nil] @length = 0 true end
Deletes all items from ‘self` that are equal to `item`.
@param [Object] item
The item to be removed from the queue.
@return [Object]
True if the item is found else false.
# File lib/garcon/task/priority_queue.rb, line 63 def delete(item) original_length = @length k = 1 while k <= @length if @queue[k] == item swap(k, @length) @length -= 1 sink(k) @queue.pop else k += 1 end end @length != original_length end
Returns ‘true` if `self` contains no elements.
@return [Boolean]
True if there are no items in the queue else false.
# File lib/garcon/task/priority_queue.rb, line 84 def empty? size == 0 end
Returns ‘true` if the given item is present in `self` (that is, if any element == `item`), otherwise returns false.
@param [Object] item
The item to search for
@return [Boolean]
True if the item is found else false.
# File lib/garcon/task/priority_queue.rb, line 97 def include?(item) @queue.include?(item) end
The current length of the queue.
@return [Fixnum]
The number of items in the queue.
# File lib/garcon/task/priority_queue.rb, line 107 def length @length end
Retrieves, but does not remove, the head of this queue, or returns ‘nil` if this queue is empty.
@return [Object]
The head of the queue or `nil` when empty.
# File lib/garcon/task/priority_queue.rb, line 118 def peek @queue[1] end
Retrieves and removes the head of this queue, or returns ‘nil` if this queue is empty.
@return [Object]
The head of the queue or `nil` when empty.
# File lib/garcon/task/priority_queue.rb, line 128 def pop max = @queue[1] swap(1, @length) @length -= 1 sink(1) @queue.pop max end
Inserts the specified element into this priority queue.
@param [Object]
Item the item to insert onto the queue.
# File lib/garcon/task/priority_queue.rb, line 144 def push(item) @length += 1 @queue << item swim(@length) true end