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



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

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

#clear ⇒ Object

Remove all elements from the priority queue.



173
174
175
176
 
# File 'lib/pqueue.rb', line 173

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.



130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
 
# File 'lib/pqueue.rb', line 130

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.



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

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) 


166
167
168
 
# File 'lib/pqueue.rb', line 166

def empty?
  @que.empty?
end

#include?(element) ⇒ Boolean

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

Returns:

  • (Boolean) 


204
205
206
 
# File 'lib/pqueue.rb', line 204

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

#inspect ⇒ Object

Pretty inspection string.



231
232
233
 
# File 'lib/pqueue.rb', line 231

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

#pop ⇒ Object

Return 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, shift, deq

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.



184
185
186
187
188
189
190
191
192
 
# File 'lib/pqueue.rb', line 184

def replace(elements)
  if elements.kind_of?(PQueue)
    initialize_copy(elements)
  else
    @que.replace(elements.to_a)
    sort!
  end
  self
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).



212
213
214
215
216
 
# File 'lib/pqueue.rb', line 212

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

#take(n = @size) ⇒ Object

Return top n-element as a sorted array.



157
158
159
160
161
 
# File 'lib/pqueue.rb', line 157

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

#to_a ⇒ Object

Return a sorted array, with highest priority first.



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

def to_a
  @que.dup
end

#top ⇒ Object

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



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

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