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.

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.



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.



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.



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.



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.



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.



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.



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.



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