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

from_list(list, opts = {}) click to toggle source

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
new(opts = {}) click to toggle source

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

<<(item)
Alias for: push
clear() click to toggle source

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
delete(item) click to toggle source

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
deq()
Alias for: pop
empty?() click to toggle source

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
enq(item)
Alias for: push
has_priority?(item)
Alias for: include?
include?(item) click to toggle source

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
Also aliased as: has_priority?
length() click to toggle source

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
Also aliased as: size
peek() click to toggle source

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
pop() click to toggle source

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
Also aliased as: deq, shift
push(item) click to toggle source

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
Also aliased as: <<, enq
shift()
Alias for: pop
size()
Alias for: length