Class: Concurrent::JavaPriorityQueue

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

Overview

Note:

This implementation is not thread safe and performs no blocking.

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`.

See Also:

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(opts = {}) ⇒ JavaPriorityQueue

Create a new priority queue with no items.

Parameters:

  • opts (Hash) (defaults to: {}) —

    the options for creating the queue

Options Hash (opts):

  • :order (Symbol) — default: :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`



228
229
230
231
232
233
234
235
 
# File 'lib/concurrent/collection/priority_queue.rb', line 228

def initialize(opts = {})
  order = opts.fetch(:order, :max)
  if [:min, :low].include?(order)
    @queue = java.util.PriorityQueue.new(11) # 11 is the default initial capacity
  else
    @queue = java.util.PriorityQueue.new(11, java.util.Collections.reverseOrder())
  end
end

Class Method Details

.from_list(list, opts = {}) ⇒ PriorityQueue

Create a new priority queue from the given list.

Parameters:

  • list (Enumerable) —

    the list to build the queue from

  • opts (Hash) (defaults to: {}) —

    the options for creating the queue

Returns:



289
290
291
292
293
 
# File 'lib/concurrent/collection/priority_queue.rb', line 289

def self.from_list(list, opts = {})
  queue = new(opts)
  list.each{|item| queue << item }
  queue
end

Instance Method Details

#clear ⇒ Object

Removes all of the elements from this priority queue.



238
239
240
241
 
# File 'lib/concurrent/collection/priority_queue.rb', line 238

def clear
  @queue.clear
  true
end

#delete(item) ⇒ Object

Deletes all items from ‘self` that are equal to `item`.

Parameters:

  • item (Object) —

    the item to be removed from the queue

Returns:

  • (Object) —

    true if the item is found else false



244
245
246
247
248
249
250
 
# File 'lib/concurrent/collection/priority_queue.rb', line 244

def delete(item)
  found = false
  while @queue.remove(item) do
    found = true
  end
  found
end

#empty? ⇒ Boolean

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

Returns:

  • (Boolean) —

    true if there are no items in the queue else false



253
254
255
 
# File 'lib/concurrent/collection/priority_queue.rb', line 253

def empty?
  @queue.size == 0
end

#include?(item) ⇒ Boolean Also known as: has_priority?

Returns ‘true` if the given item is present in `self` (that is, if any element == `item`), otherwise returns false.

Parameters:

  • item (Object) —

    the item to search for

Returns:

  • (Boolean) —

    true if the item is found else false



258
259
260
 
# File 'lib/concurrent/collection/priority_queue.rb', line 258

def include?(item)
  @queue.contains(item)
end

#length ⇒ Fixnum Also known as: size

The current length of the queue.

Returns:

  • (Fixnum) —

    the number of items in the queue



264
265
266
 
# File 'lib/concurrent/collection/priority_queue.rb', line 264

def length
  @queue.size
end

#peek ⇒ Object

Retrieves, but does not remove, the head of this queue, or returns ‘nil` if this queue is empty.

Returns:

  • (Object) —

    the head of the queue or ‘nil` when empty



270
271
272
 
# File 'lib/concurrent/collection/priority_queue.rb', line 270

def peek
  @queue.peek
end

#pop ⇒ Object Also known as: deq, shift

Retrieves and removes the head of this queue, or returns ‘nil` if this queue is empty.

Returns:

  • (Object) —

    the head of the queue or ‘nil` when empty



275
276
277
 
# File 'lib/concurrent/collection/priority_queue.rb', line 275

def pop
  @queue.poll
end

#push(item) ⇒ Object Also known as: <<, enq

Inserts the specified element into this priority queue.

Parameters:

  • item (Object) —

    the item to insert onto the queue



282
283
284
 
# File 'lib/concurrent/collection/priority_queue.rb', line 282

def push(item)
  @queue.add(item)
end