Parent

Files

Class/Module Index [+]

Quicksearch

Concurrent::Collection::MutexPriorityQueue

@!macro [attach] priority_queue

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.

The pure Ruby implementation, `MutexPriorityQueue` uses a heap algorithm
stored in an array. The algorithm is based on the work of Robert Sedgewick
and Kevin Wayne.

The JRuby native implementation is a thin wrapper around the standard
library `java.util.PriorityQueue`.

When running under JRuby the class `PriorityQueue` extends `JavaPriorityQueue`.
When running under all other interpreters it extends `MutexPriorityQueue`.

@note This implementation is *not* thread safe.

@see http://en.wikipedia.org/wiki/Priority_queue
@see http://ruby-doc.org/stdlib-2.0.0/libdoc/thread/rdoc/Queue.html

@see http://algs4.cs.princeton.edu/24pq/index.php#2.6
@see http://algs4.cs.princeton.edu/24pq/MaxPQ.java.html

@see http://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html

@!visibility private @!macro internal_implementation_note

Constants

PriorityQueueImplementation

@!visibility private @!macro internal_implementation_note

Public Class Methods

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

@!macro [attach] priority_queue_method_from_list

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/concurrent/collection/priority_queue.rb, line 165
def self.from_list(list, opts = {})
  queue = new(opts)
  list.each{|item| queue << item }
  queue
end
new(opts = {}) click to toggle source

@!macro [attach] priority_queue_method_initialize

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/concurrent/collection/priority_queue.rb, line 47
def initialize(opts = {})
  order = opts.fetch(:order, :max)
  @comparator = [:min, :low].include?(order) ? -1 : 1
  clear
end

Public Instance Methods

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

@!macro [attach] priority_queue_method_clear

Removes all of the elements from this priority queue.
# File lib/concurrent/collection/priority_queue.rb, line 56
def clear
  @queue = [nil]
  @length = 0
  true
end
delete(item) click to toggle source

@!macro [attach] priority_queue_method_delete

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/concurrent/collection/priority_queue.rb, line 68
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() click to toggle source
Alias for: pop
empty?() click to toggle source

@!macro [attach] priority_queue_method_empty

Returns `true` if `self` contains no elements.

@return [Boolean] true if there are no items in the queue else false
# File lib/concurrent/collection/priority_queue.rb, line 89
def empty?
  size == 0
end
enq(item) click to toggle source
Alias for: push
has_priority?(item) click to toggle source
Alias for: include?
include?(item) click to toggle source

@!macro [attach] priority_queue_method_include

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/concurrent/collection/priority_queue.rb, line 101
def include?(item)
  @queue.include?(item)
end
Also aliased as: has_priority?
length() click to toggle source

@!macro [attach] priority_queue_method_length

The current length of the queue.

@return [Fixnum] the number of items in the queue
# File lib/concurrent/collection/priority_queue.rb, line 111
def length
  @length
end
Also aliased as: size
peek() click to toggle source

@!macro [attach] priority_queue_method_peek

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/concurrent/collection/priority_queue.rb, line 122
def peek
  @queue[1]
end
pop() click to toggle source

@!macro [attach] priority_queue_method_pop

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/concurrent/collection/priority_queue.rb, line 132
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

@!macro [attach] priority_queue_method_push

Inserts the specified element into this priority queue.

@param [Object] item the item to insert onto the queue
# File lib/concurrent/collection/priority_queue.rb, line 148
def push(item)
  @length += 1
  @queue << item
  swim(@length)
  true
end
Also aliased as: <<, enq
shift() click to toggle source
Alias for: pop
size() click to toggle source
Alias for: length

Protected Instance Methods

ordered?(x, y) click to toggle source

Are the items at the given indexes ordered based on the priority order specified at construction?

@param [Integer] x the first index from which to retrieve a comparable value @param [Integer] y the second index from which to retrieve a comparable value

@return [Boolean] true if the two elements are in the correct priority order

else false

@!visibility private

# File lib/concurrent/collection/priority_queue.rb, line 195
def ordered?(x, y)
  (@queue[x] <=> @queue[y]) == @comparator
end
sink(k) click to toggle source

Percolate down to maintain heap invariant.

@param [Integer] k the index at which to start the percolation

@!visibility private

# File lib/concurrent/collection/priority_queue.rb, line 204
  def sink(k)
    while (j = (2 * k)) <= @length do
      j += 1 if j < @length && ! ordered?(j, j+1)
      break if ordered?(k, j)
      swap(k, j)
      k = j
    end
  end

  # Percolate up to maintain heap invariant.
  # 
  # @param [Integer] k the index at which to start the percolation
  # 
  # @!visibility private
  def swim(k)
    while k > 1 && ! ordered?(k/2, k) do
      swap(k, k/2)
      k = k/2
    end
  end
end
swap(x, y) click to toggle source

Exchange the values at the given indexes within the internal array.

@param [Integer] x the first index to swap @param [Integer] y the second index to swap

@!visibility private

# File lib/concurrent/collection/priority_queue.rb, line 179
def swap(x, y)
  temp = @queue[x]
  @queue[x] = @queue[y]
  @queue[y] = temp
end
swim(k) click to toggle source

Percolate up to maintain heap invariant.

@param [Integer] k the index at which to start the percolation

@!visibility private

# File lib/concurrent/collection/priority_queue.rb, line 218
def swim(k)
  while k > 1 && ! ordered?(k/2, k) do
    swap(k, k/2)
    k = k/2
  end
end

[Validate]

Generated with the Darkfish Rdoc Generator 2.