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