Class: PQueue

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

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



81
82
83
84
85
86
 
# File 'lib/more/facets/pqueue.rb', line 81

def initialize(elements=nil, &block) # :yields: a, b
  @qarray = [nil]
  @size = 0
  @gt = block || lambda {|a,b| a > b}
  replace(elements) if elements
end

Instance Attribute Details

#gt ⇒ Object (readonly)

compare Proc



67
68
69
 
# File 'lib/more/facets/pqueue.rb', line 67

def gt
  @gt
end

#size ⇒ Object (readonly)

number of elements



65
66
67
 
# File 'lib/more/facets/pqueue.rb', line 65

def size
  @size
end

Instance Method Details

#==(other) ⇒ Object

Return true if the queues contain equal elements.



306
307
308
 
# File 'lib/more/facets/pqueue.rb', line 306

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

#clear ⇒ Object

Remove all elements from the priority queue.



235
236
237
238
239
 
# File 'lib/more/facets/pqueue.rb', line 235

def clear
  @qarray.replace([nil])
  @size = 0
  return self
end

#each_pop ⇒ Object

Iterate over the ordered elements, destructively.



290
291
292
293
294
295
 
# File 'lib/more/facets/pqueue.rb', line 290

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

#empty? ⇒ Boolean

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

Returns:

  • (Boolean) 


230
231
232
 
# File 'lib/more/facets/pqueue.rb', line 230

def empty?
  return @size.zero?
end

#include?(element) ⇒ Boolean

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

Returns:

  • (Boolean) 


285
286
287
 
# File 'lib/more/facets/pqueue.rb', line 285

def include?(element)
  return @qarray.include?(element)
end

#inspect ⇒ Object

Pretty print



298
299
300
 
# File 'lib/more/facets/pqueue.rb', line 298

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.



180
181
182
183
184
185
186
187
 
# File 'lib/more/facets/pqueue.rb', line 180

def pop
  return nil if empty?
  res = @qarray[1]
  @qarray[1] = @qarray[@size]
  @size -= 1
  downheap(1)
  return res
end

#pop_array(n = @size) ⇒ Object

Return top n-element as a sorted array.



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

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.



162
163
164
165
166
167
 
# File 'lib/more/facets/pqueue.rb', line 162

def push(v)
  @size += 1
  @qarray[@size] = v
  upheap(@size)
  return 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.



198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
 
# File 'lib/more/facets/pqueue.rb', line 198

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.



244
245
246
247
248
249
250
251
252
253
 
# File 'lib/more/facets/pqueue.rb', line 244

def replace(elements)
  if elements.kind_of?(PQueue)
    initialize_copy(elements)
  else
    @qarray.replace([nil] + elements.to_a)
    @size = @qarray.size - 1
    heapify
  end
  return 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).



270
271
272
273
274
275
276
277
278
279
280
281
282
 
# File 'lib/more/facets/pqueue.rb', line 270

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

#to_a ⇒ Object Also known as: sort

Return a sorted array, with highest priority first.



256
257
258
259
260
261
262
263
 
# File 'lib/more/facets/pqueue.rb', line 256

def to_a
  old_qarray = @qarray.dup
  old_size = @size
  res = pop_array
  @qarray = old_qarray
  @size = old_size
  return res
end

#top ⇒ Object

Return the element with the highest priority.



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

def top
  return nil if empty?
  return @qarray[1]
end