socialNetworksProject/PriorityQueue.py at master · pdsteele/socialNetworksProject · GitHub

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
class Queue():
	def __init__(self):
		self._head  = None
		self._tail  = None
		self._count = 0

	def __len__(self):
		return self._count

	def isEmpty(self):
		return self._head is None

	def enqueue(self, data):
		if self._head is None:
			self._head      = _Node(data)
			self._tail      = self._head

		else:
			self._tail.next = _Node(data)

		self._count += 1


	def dequeue(self):
		assert not self.isEmpty()

		curNode      = self._head
		self._head   = self._head.next
		curNode.next = None
		self._count -= 1

		return curNode


class PriorityQueue():
	def __init__(self):
		self._head  = None
		self._tail  = None
		self._count = 0

	def __len__(self):
		return self._count

	def isEmpty(self):
		return self._head is None

	def enqueue(self, data, prob):
		if self._head is None:
			self._head = _PNode(data, prob)
			self._tail = self._head

		else:
			Node       = _PNode(data, prob)
			breakVal   = 0

			if self._head.prob < Node.prob:
				Node.next   = self._head
				self._head  = Node
				breakVal    = 1

			elif self._tail.prob >= Node.prob:
				self._tail.next   = Node
				self._tail        = self._tail.next
				breakVal 		  = 1

			curNode    = self._head
			while (breakVal == 0): # and (curNode is not None)
				if curNode.next.prob >= Node.prob:
					curNode      = curNode.next
				else:
					Node.next    = curNode.next
					curNode.next = Node
					breakVal = 1


		self._count += 1


	def dequeue(self):
		assert not self.isEmpty()

		curNode      = self._head
		self._head   = self._head.next
		curNode.next = None
		self._count -= 1

		return curNode


class _Node():
	def __init__(self, data):
		self.data = data
		self.next = None


class _PNode():
	def __init__(self, data, prob):
		self.data = data
		self.prob = prob
		self.next = None