Class: PQueue

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

Overview

PQueue, a 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.

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.

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

#gt ⇒ Object (readonly)

compare Proc



18
19
20
 
# File 'lib/pqueue/legacy.rb', line 18

def gt
  @gt
end

#size ⇒ Object (readonly) Also known as: length

number of elements



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

def size
  @que.size
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

#deq ⇒ Object

Add an element in the priority queue.

Alias of #pop.



114
115
116
117
118
 
# File 'lib/pqueue.rb', line 114

def push(v)
  @que << v
  reheap(@que.size-1)
  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

True if there is no more elements left in the priority queue.

Returns:

  • (Boolean) 


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

def empty?
  @que.empty?
end

#enq ⇒ Object

Add an element in the priority queue.

Alias of #push.



88
89
90
91
92
 
# File 'lib/pqueue.rb', line 88

def push(v)
  @que << v
  reheap(@que.size-1)
  self
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 print



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 instanciation time.

The deletion time is O(log n), with n 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

#pop_array(n = @size) ⇒ Object

Return top n-element as a sorted array.



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

def pop_array(n=@size)
  ary = []
  n.times{ary.push(pop)}
  return ary
end

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

Add an element in the priority queue.

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



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

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

#push_all(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 to be a PQueue itself.



149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
 
# File 'lib/pqueue/legacy.rb', line 149

def push_all(elements)
  if empty?
    if elements.kind_of?(PQueue)
      initialize_copy(elements)
    else
      replace(elements)
    end
  else
    if elements.kind_of?(PQueue)
      @qarray[@size + 1, elements.size] = elements.qarray[1..-1]
      elements.size.times{ @size += 1; upheap(@size)}
    else
      ary = elements.to_a
      @qarray[@size + 1, ary.size] = ary
      ary.size.times{ @size += 1; upheap(@size)}
    end
  end
  return 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

#replace_top(v) ⇒ Object

Replace the top element with the given one, and return this top element.

Equivalent to successively calling #pop and #push(v).



221
222
223
224
225
226
227
228
229
230
231
232
233
 
# File 'lib/pqueue/legacy.rb', line 221

def replace_top(v)
  # replace top element
  if empty?
    @qarray[1] = v
    @size += 1
    return nil
  else
    res = @qarray[1]
    @qarray[1] = v
    downheap(1)
    return res
  end
end

#shift ⇒ Object

Add an element in the priority queue.

Alias of #push.



109
110
111
112
113
 
# File 'lib/pqueue.rb', line 109

def push(v)
  @que << v
  reheap(@que.size-1)
  self
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 Also known as: sort

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

Return the element with the highest priority.



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

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