Class: Garcon::MutexPriorityQueue

Inherits:
Object
  • Object
show all
Defined in:
lib/garcon/task/priority_queue.rb

Overview

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.

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.

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



41
42
43
44
45
 
# 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

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:



164
165
166
167
168
 
# 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

Instance Method Details

#clear ⇒ Object

Removes all of the elements from this priority queue.



49
50
51
52
53
 
# File 'lib/garcon/task/priority_queue.rb', line 49

def clear
  @queue = [nil]
  @length = 0
  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.



63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
 
# 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

#empty? ⇒ Boolean

Returns true if self contains no elements.

Returns:

  • (Boolean) —

    True if there are no items in the queue else false.



84
85
86
 
# File 'lib/garcon/task/priority_queue.rb', line 84

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:

  • item (Object) —

    The item to search for

Returns:

  • (Boolean) —

    True if the item is found else false.



97
98
99
 
# File 'lib/garcon/task/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:

  • (Fixnum) —

    The number of items in the queue.



107
108
109
 
# File 'lib/garcon/task/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:

  • (Object) —

    The head of the queue or nil when empty.



118
119
120
 
# File 'lib/garcon/task/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:

  • (Object) —

    The head of the queue or nil when empty.



128
129
130
131
132
133
134
135
 
# 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

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



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

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