Class: PQueue

Inherits:
Object
  • Object
show all
Defined in:
lib/pqueue.rb

Overview

Priority queue with array based heap.

A priority queue is like a standard queue, except that each inserted elements is given a certain priority, based on the result of the comparison block given at instantiation time. Also, retrieving an element from the queue will always return the one with the highest priority (see #pop and #top).

The default is to compare the elements in repect to their #<=> method. For example, Numeric elements with higher values will have higher priorities.

Note that as of version 2.0 the internal queue is kept in the reverse order from how it was kept in previous version. If you had used #to_a in the past then be sure to adjust for the priorities to be ordered back-to-front instead of the oterh way around.

Constant Summary collapse

VERSION =

:erb: VERSION = “<%= version %>”

"2.1.0"

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(elements = nil, &block) ⇒ PQueue

Returns a new priority queue.

If elements are given, build the priority queue with these initial values. The elements object must respond to #to_a.

If a block is given, it will be used to determine the priority between the elements. The block must must take two arguments and return ‘1`, `0`, or `-1` or `true`, `nil` or `false. It should return `0` or `nil` if the two arguments are considered equal, return `1` or `true` if the first argument is considered greater than the later, and `-1` or `false` if the later is considred to be greater than the first.

By default, the priority queue retrieves maximum elements first using the #<=> method.



39
40
41
42
43
 
# File 'lib/pqueue.rb', line 39

def initialize(elements=nil, &block) # :yields: a, b
  @que = []
  @cmp = block || lambda{ |a,b| a <=> b }
  replace(elements) if elements
end

Instance Attribute Details

#cmp ⇒ Object (readonly)

Priority comparison procedure.



57
58
59
 
# File 'lib/pqueue.rb', line 57

def cmp
  @cmp
end

Instance Method Details

#==(other) ⇒ Object

Return true if the queues contain equal elements.



262
263
264
 
# File 'lib/pqueue.rb', line 262

def ==(other)
  size == other.size && to_a == other.to_a
end

#bottom ⇒ Object

Returns the element with the lowest priority, but does not remove it from the queue.



144
145
146
147
 
# File 'lib/pqueue.rb', line 144

def bottom
  return nil if empty?
  return @que.first
end

#clear ⇒ Object

Remove all elements from the priority queue.



197
198
199
200
 
# File 'lib/pqueue.rb', line 197

def clear
  @que.clear
  self
end

#concat(elements) ⇒ Object Also known as: merge!

Add more than one element at the same time. See #push.

The elements object must respond to #to_a, or be a PQueue itself.



154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
 
# File 'lib/pqueue.rb', line 154

def concat(elements)
  if empty?
    if elements.kind_of?(PQueue)
      initialize_copy(elements)
    else
      replace(elements)
    end
  else
    if elements.kind_of?(PQueue)
      @que.concat(elements.que)
      sort!
    else
      @que.concat(elements.to_a)
      sort!
    end
  end
  return self
end

#each_pop ⇒ Object

Iterate over the ordered elements, destructively.



245
246
247
248
249
250
 
# File 'lib/pqueue.rb', line 245

def each_pop #:yields: popped
  until empty?
    yield pop
  end
  nil
end

#empty? ⇒ Boolean

Returns true if there is no more elements left in the queue.

Returns:

  • (Boolean) 


190
191
192
 
# File 'lib/pqueue.rb', line 190

def empty?
  @que.empty?
end

#include?(element) ⇒ Boolean

Return true if the given object is present in the queue.

Returns:

  • (Boolean) 


228
229
230
 
# File 'lib/pqueue.rb', line 228

def include?(element)
  @que.include?(element)
end

#inspect ⇒ Object

Pretty inspection string.



255
256
257
 
# File 'lib/pqueue.rb', line 255

def inspect
  "<#{self.class}: size=#{size}, top=#{top || "nil"}>"
end

#pop ⇒ Object Also known as: deq

Get the element with the highest priority and remove it from the queue.

The highest priority is determined by the block given at instantiation time.

The deletion time is O(log n), with n is the size of the queue.

Return nil if the queue is empty.



101
102
103
104
 
# File 'lib/pqueue.rb', line 101

def pop
  return nil if empty?
  @que.pop
end

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

Add an element in the priority queue.



74
75
76
77
78
 
# File 'lib/pqueue.rb', line 74

def push(v)
  @que << v
  reheap(@que.size-1)
  self
end

#replace(elements) ⇒ Object

Replace the content of the heap by the new elements.

The elements object must respond to #to_a, or to be a PQueue itself.



208
209
210
211
212
213
214
215
216
 
# File 'lib/pqueue.rb', line 208

def replace(elements)
  if elements.kind_of?(PQueue)
    initialize_copy(elements)
  else
    @que.replace(elements.to_a)
    sort!
  end
  self
end

#shift ⇒ Object

Get the element with the lowest priority and remove it from the queue.

The lowest priority is determined by the block given at instantiation time.

The deletion time is O(log n), with n is the size of the queue.

Return nil if the queue is empty.



121
122
123
124
 
# File 'lib/pqueue.rb', line 121

def shift
  return nil if empty?
  @que.shift
end

#size ⇒ Object Also known as: length

Returns the size of the queue.



62
63
64
 
# File 'lib/pqueue.rb', line 62

def size
  @que.size
end

#swap(v) ⇒ Object

Push element onto queue while popping off and returning the next element. This is qquivalent to successively calling #pop and #push(v).



236
237
238
239
240
 
# File 'lib/pqueue.rb', line 236

def swap(v)
  r = pop
  push(v)
  r
end

#take(n = @size) ⇒ Object

Return top n-element as a sorted array.



181
182
183
184
185
 
# File 'lib/pqueue.rb', line 181

def take(n=@size)
  a = []
  n.times{a.push(pop)}
  a
end

#to_a ⇒ Object

Return a sorted array, with highest priority first.



221
222
223
 
# File 'lib/pqueue.rb', line 221

def to_a
  @que.dup
end

#top ⇒ Object Also known as: peek

Returns the element with the highest priority, but does not remove it from the queue.



130
131
132
133
 
# File 'lib/pqueue.rb', line 130

def top
  return nil if empty?
  return @que.last
end