-
Notifications
You must be signed in to change notification settings - Fork 351
/
priority_queue.rb
113 lines (100 loc) · 2.93 KB
/
priority_queue.rb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
require 'containers/heap'
=begin rdoc
A Priority Queue is a data structure that behaves like a queue except that elements have an
associated priority. The #next and #pop methods return the item with the next highest priority.
Priority Queues are often used in graph problems, such as Dijkstra's Algorithm for shortest
path, and the A* search algorithm for shortest path.
This container is implemented using the Fibonacci heap included in the Collections library.
=end
class Containers::PriorityQueue
include Enumerable
# Create a new, empty PriorityQueue
def initialize(&block)
# We default to a priority queue that returns the largest value
block ||= lambda { |x, y| (x <=> y) == 1 }
@heap = Containers::Heap.new(&block)
end
# Returns the number of elements in the queue.
#
# q = Containers::PriorityQueue.new
# q.size #=> 0
# q.push("Alaska", 1)
# q.size #=> 1
def size
@heap.size
end
alias_method :length, :size
# Add an object to the queue with associated priority.
#
# q = Containers::PriorityQueue.new
# q.push("Alaska", 1)
# q.pop #=> "Alaska"
def push(object, priority)
@heap.push(priority, object)
end
# Clears all the items in the queue.
def clear
@heap.clear
end
# Returns true if the queue is empty, false otherwise.
def empty?
@heap.empty?
end
# call-seq:
# has_priority? priority -> boolean
#
# Return true if the priority is in the queue, false otherwise.
#
# q = PriorityQueue.new
# q.push("Alaska", 1)
#
# q.has_priority?(1) #=> true
# q.has_priority?(2) #=> false
def has_priority?(priority)
@heap.has_key?(priority)
end
# call-seq:
# next -> object
#
# Return the object with the next highest priority, but does not remove it
#
# q = Containers::PriorityQueue.new
# q.push("Alaska", 50)
# q.push("Delaware", 30)
# q.push("Georgia", 35)
# q.next #=> "Alaska"
def next
@heap.next
end
# call-seq:
# pop -> object
#
# Return the object with the next highest priority and removes it from the queue
#
# q = Containers::PriorityQueue.new
# q.push("Alaska", 50)
# q.push("Delaware", 30)
# q.push("Georgia", 35)
# q.pop #=> "Alaska"
# q.size #=> 2
def pop
@heap.pop
end
alias_method :next!, :pop
# call-seq:
# delete(priority) -> object
# delete(priority) -> nil
#
# Delete an object with specified priority from the queue. If there are duplicates, an
# arbitrary object with that priority is deleted and returned. Returns nil if there are
# no objects with the priority.
#
# q = PriorityQueue.new
# q.push("Alaska", 50)
# q.push("Delaware", 30)
# q.delete(50) #=> "Alaska"
# q.delete(10) #=> nil
def delete(priority)
@heap.delete(priority)
end
end