Class: Concurrent::MutexPriorityQueue

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:

Direct Known Subclasses

PriorityQueue

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(opts = {}) ⇒ MutexPriorityQueue

Create a new priority queue with no items.

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

Parameters:

  • (defaults to: {})

    the options for creating the queue



43
44
45
46
47
 
# File 'lib/concurrent/collection/priority_queue.rb', line 43

def initialize(opts = {})
  order = opts.fetch(:order, :max)
  @comparator = [:min, :low].include?(order) ? -1 : 1
  clear
end

Class Method Details

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



161
162
163
164
165
 
# File 'lib/concurrent/collection/priority_queue.rb', line 161

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.



52
53
54
55
56
 
# File 'lib/concurrent/collection/priority_queue.rb', line 52

def clear
  @queue = [nil]
  @length = 0
  true
end

#delete(item) ⇒ Object

Deletes all items from self that are equal to item.

Parameters:

  • the item to be removed from the queue

Returns:

  • true if the item is found else false



64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
 
# File 'lib/concurrent/collection/priority_queue.rb', line 64

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

#empty? ⇒ Boolean

Returns true if self contains no elements.

Returns:

  • true if there are no items in the queue else false



85
86
87
 
# File 'lib/concurrent/collection/priority_queue.rb', line 85

def empty?
  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:

  • the item to search for

Returns:

  • true if the item is found else false



97
98
99
 
# File 'lib/concurrent/collection/priority_queue.rb', line 97

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

#length ⇒ Fixnum Also known as: size

The current length of the queue.

Returns:

  • the number of items in the queue



107
108
109
 
# File 'lib/concurrent/collection/priority_queue.rb', line 107

def length
  @length
end

#peek ⇒ Object

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

Returns:

  • the head of the queue or nil when empty



118
119
120
 
# File 'lib/concurrent/collection/priority_queue.rb', line 118

def peek
  @queue[1]
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:

  • the head of the queue or nil when empty



128
129
130
131
132
133
134
135
 
# File 'lib/concurrent/collection/priority_queue.rb', line 128

def pop
  max = @queue[1]
  swap(1, @length)
  @length -= 1
  sink(1)
  @queue.pop
  max
end

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

Inserts the specified element into this priority queue.

Parameters:

  • the item to insert onto the queue



144
145
146
147
148
149
 
# File 'lib/concurrent/collection/priority_queue.rb', line 144

def push(item)
  @length += 1
  @queue << item
  swim(@length)
  true
end