Class: Ferret::Utils::PriorityQueue

Inherits:
Object
  • Object
show all
Defined in:
lib/ferret/utils/priority_queue.rb,
ext/priority_queue.c

Overview

A PriorityQueue maintains a partial ordering of its objects such that the least object can always be found in constant time. push()‘s and pop()’s require log(size) time. The objects in this priority queue must be Comparable

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(rsize) ⇒ PriorityQueue

Subclass constructors must call this.



14
15
16
17
18
 
# File 'lib/ferret/utils/priority_queue.rb', line 14

def initialize(max_size)
  @size = 0
  @heap = Array.new(max_size + 1)
  @max_size = max_size
end

Instance Attribute Details

#size ⇒ Object (readonly)

Returns the value of attribute size.



183
184
185
 
# File 'ext/priority_queue.c', line 183

def size
  @size
end

Instance Method Details

#adjust_top ⇒ Object

resets the queue after the top has been changed



82
83
84
 
# File 'lib/ferret/utils/priority_queue.rb', line 82

def adjust_top()
  down_heap()
end

#clear ⇒ Object

Removes all entries from the PriorityQueue.



70
71
72
73
74
75
 
# File 'lib/ferret/utils/priority_queue.rb', line 70

def clear() 
  (1..@size).each do |i|
    @heap[i] = nil
  end
  @size = 0
end

#insert(e) ⇒ Object

Adds object to the PriorityQueue in log(size) time if either the PriorityQueue is not full, or not less_than(object, top()).

object

the object to be inserted

return true if object is added, false otherwise.



36
37
38
39
40
41
42
43
44
45
46
47
 
# File 'lib/ferret/utils/priority_queue.rb', line 36

def insert(object)
 if(@size < @max_size)
   push(object)
   return true
 elsif (@size > 0 and less_than(top, object))
   @heap[1] = object
   down_heap()
   return true
 else
   return false
 end
end

#less_than(a, b) ⇒ Object 



9
10
11
 
# File 'lib/ferret/utils/priority_queue.rb', line 9

def less_than(a, b)
  a < b
end

#pop ⇒ Object

Removes and returns the least object of the PriorityQueue in log(size) time.



56
57
58
59
60
61
62
63
64
65
66
67
 
# File 'lib/ferret/utils/priority_queue.rb', line 56

def pop() 
  if (@size > 0) 
    result = @heap[1]        # save first value
    @heap[1] = @heap[@size]  # move last to first
    @heap[@size] = nil;      # permit GC of objects
    @size -= 1
    down_heap()              # adjust heap
    return result
  else
    return nil
  end
end

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

Adds an Object to a PriorityQueue in log(size) time.

If one tries to add more objects than max_size from initialize a RuntimeException (ArrayIndexOutOfBound) is thrown.



24
25
26
27
28
 
# File 'lib/ferret/utils/priority_queue.rb', line 24

def push(object) 
  @size += 1
  @heap[@size] = object
  up_heap()
end

#put_heap ⇒ Object 



77
78
79
 
# File 'lib/ferret/utils/priority_queue.rb', line 77

def put_heap
  puts @heap
end

#top ⇒ Object

Returns the least object of the PriorityQueue in constant time.



50
51
52
 
# File 'lib/ferret/utils/priority_queue.rb', line 50

def top
  return @heap[1]
end