-
Notifications
You must be signed in to change notification settings - Fork 0
/
priorityq.py
77 lines (64 loc) · 2.12 KB
/
priorityq.py
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
from min_heap import MinHeap
from functools import total_ordering
@total_ordering
class PrioritizedItem(object):
def __init__(self, pri, value):
self.pri, self.value = pri, value
self._order = 0
def __eq__(self, other):
if hasattr(other, 'pri'):
if self.pri == other.pri:
if hasattr(other, '_order'):
return self._order == other._order
return False
def __lt__(self, other):
# this should cover __gt__ implicitly
if hasattr(other, 'pri'):
if self.pri == other.pri:
if hasattr(other, '_order'):
return self._order < other._order
else:
raise AttributeError(
"right-most object must have an _order attr")
return self.pri < other.pri
raise AttributeError("right-most object must have a pri attribute")
def __str__(self):
return "[Pri:{},Value:{},_Order:{}]".format(
str(self.pri),
str(self.value),
str(self._order))
class PriorityQueue(object):
def __init__(self):
self._heap = MinHeap()
self._num_inserted = 0
def _gen_order(self):
self._num_inserted += 1
return self._num_inserted
def insert(self, prioritized_item):
prioritized_item._order = self. _gen_order()
self._heap.push(prioritized_item)
def pop(self):
return self._heap.pop()
def peek(self):
return self._heap.peek()
def __str__(self):
s = []
[s.append(str(item)) for item in self._heap._list]
return "".join(s)
if __name__ == '__main__':
pq = PriorityQueue()
pq.insert(PrioritizedItem(3, 'A'))
print pq
pq.insert(PrioritizedItem(1, 'B'))
print pq
pq.insert(PrioritizedItem(3, 'C'))
print pq
pq.insert(PrioritizedItem(2, 'D'))
print pq
pq.insert(PrioritizedItem(3, 'E'))
print pq
print pq.pop().value # expect B
print pq.pop().value # expect D
print pq.pop().value # expect A
print pq.pop().value # expect C
print pq.pop().value # expect E