Advertisement
Guest User

Untitled

a guest
Apr 23rd, 2019
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 9.21 KB | None | 0 0
  1. import time
  2. import random
  3. import os
  4. #============== TreeNode class =================
  5.  
  6. class TreeNode:
  7. def __init__(self, val, parent=None):
  8. self.height = 1
  9. self.val = val
  10. self.parent = parent
  11. self.leftChild = None
  12. self.rightChild = None
  13. self.height1 = 1
  14. self.balancefactor = 0
  15.  
  16. def hasLeftChild(self):
  17. return self.leftChild
  18.  
  19. def hasRightChild(self):
  20. return self.rightChild
  21.  
  22. def isRoot(self):
  23. return not self.parent
  24.  
  25. def isRightChild(self):
  26. return self.parent and self.parent.rightChild == self
  27.  
  28. def isLeftChild(self):
  29. return self.parent and self.parent.leftChild == self
  30.  
  31. def treeheight(self):
  32. if self is None:
  33. return 0
  34. else:
  35. return max(TreeNode.treeheight(self.leftChild),
  36. TreeNode.treeheight(self.rightChild)) + 1
  37.  
  38. def balanceupdate(self):
  39. if self.hasLeftChild() is None and self.hasRightChild() is None:
  40. self.balancefactor = 0
  41. return
  42. elif self.hasLeftChild() is None:
  43. self.balancefactor = - self.rightChild.height1
  44. elif self.hasRightChild() is None:
  45. self.balancefactor = self.leftChild.height1
  46. else:
  47. self.balancefactor = self.leftChild.height1 - self.rightChild.height1
  48.  
  49.  
  50. # ============== PQ class =================
  51.  
  52. class PQ:
  53. def add(self, val):
  54. raise NotImplemented
  55.  
  56. def peekMin(self):
  57. raise NotImplemented
  58.  
  59. def getMin(self):
  60. raise NotImplemented
  61.  
  62. def __len__(self):
  63. raise NotImplemented
  64.  
  65.  
  66. # ============== LIST CLASS ==================
  67.  
  68. class ListPQ(PQ):
  69. def __init__(self):
  70. self.items = []
  71.  
  72. def __len__(self):
  73. return len(self.items)
  74.  
  75. def add(self, val):
  76. self.items.append(val)
  77.  
  78. def peekMin(self):
  79. return self.getMin(False)
  80.  
  81. def getMin(self, toRemove=True):
  82. if (self.items == []):
  83. return None
  84. minIdx = 0
  85. sz = len(self.items)
  86. for idx in range(sz):
  87. if priority(self.items[idx]) < priority(self.items[minIdx]):
  88. minIdx = idx
  89. minItem = self.items[minIdx]
  90. if toRemove:
  91. del self.items[minIdx]
  92. return minItem
  93.  
  94. def draw(self):
  95. print(self.items)
  96.  
  97.  
  98. # ============== BST CLASS ==================
  99.  
  100. class BST(PQ):
  101.  
  102. def __init__(self):
  103. self.root = None
  104. self.size = 0
  105. self.newNode = None
  106.  
  107. def __len__(self):
  108. return self.size
  109.  
  110. ## Part 2
  111. def add(self, val):
  112. def _add(root, val, rootparent):
  113. if root == None:
  114. x = TreeNode(val, parent=rootparent)
  115. self.newNode = x
  116. return x
  117. if val < root.val:
  118. root.leftChild = _add(root.leftChild, val, root)
  119. else:
  120. root.rightChild = _add(root.rightChild, val, root)
  121. return root
  122.  
  123. self.root = _add(self.root, val, None)
  124. self.size += 1
  125. return self.newNode
  126.  
  127. def peekMin(self):
  128. return self.getMin(False)
  129.  
  130. def getMin(self, toRemove=True):
  131. curNode = self.root
  132. if not curNode:
  133. return None
  134. while curNode.leftChild != None:
  135. curNode = curNode.leftChild
  136. if toRemove:
  137. self._remove(curNode) ## TO IMPLEMENT
  138. self.size -= 1
  139. return curNode.val
  140.  
  141. ## Part 3
  142. def _remove(self, node):
  143. print("***********before removing ", node.val)
  144. if node.parent is not None:
  145. if node.rightChild:
  146. node.rightChild.parent = node.parent
  147. node.parent.leftChild = node.rightChild
  148. node.parent = None
  149. else:
  150. node.parent.leftChild = None
  151. else:
  152. if node.rightChild:
  153. node = node.rightChild
  154. node.parent = None
  155. self.root = node
  156. else:
  157. self.root = None
  158. self.draw()
  159.  
  160. def draw(self):
  161. drawTree(self.root, 0, True)
  162.  
  163.  
  164. # ================ class BalancedBST ===============
  165. class Queue:
  166. def __init__(self):
  167. self.items = []
  168.  
  169. def isEmpty(self):
  170. return self.items == []
  171.  
  172. def enqueue(self, item):
  173. self.items.insert(0, item)
  174.  
  175. def dequeue(self):
  176. return self.items.pop()
  177.  
  178. def size(self):
  179. return len(self.items)
  180.  
  181. def peek(self):
  182. return self.items[0]
  183.  
  184.  
  185. class BalancedBST(BST):
  186.  
  187. ## Part 4
  188. def add(self, val): ## TO IMPLEMENT
  189. newNode = BST.add(self, val)
  190. BalancedBST.traversalHeight(self, self.root)
  191. BalancedBST.traversalBalance(self, newNode)
  192. self.size += 1
  193. return newNode
  194.  
  195. def rotateLeft(self, rotRoot):
  196. newRoot = rotRoot.rightChild
  197. rotRoot.rightChild = newRoot.leftChild
  198. if newRoot.leftChild != None:
  199. newRoot.leftChild.parent = rotRoot
  200. newRoot.parent = rotRoot.parent
  201. if rotRoot.isRoot():
  202. self.root = newRoot
  203. else:
  204. if rotRoot.isLeftChild():
  205. rotRoot.parent.leftChild = newRoot
  206. else:
  207. rotRoot.parent.rightChild = newRoot
  208. newRoot.leftChild = rotRoot
  209. rotRoot.parent = newRoot
  210. BalancedBST.traversalHeight(self, self.root)
  211. BalancedBST.traversalBalanceRoot(self, self.root)
  212.  
  213. def rotateRight(self, rotRoot):
  214. newRoot = rotRoot.leftChild
  215. rotRoot.leftChild = newRoot.rightChild
  216. if newRoot.rightChild != None:
  217. newRoot.rightChild.parent = rotRoot
  218. newRoot.parent = rotRoot.parent
  219. if rotRoot.isRoot():
  220. self.root = newRoot
  221. else:
  222. if rotRoot.isRightChild():
  223. rotRoot.parent.rightChild = newRoot
  224. else:
  225. rotRoot.parent.leftChild = newRoot
  226. newRoot.rightChild = rotRoot
  227. rotRoot.parent = newRoot
  228. BalancedBST.traversalHeight(self, self.root)
  229. BalancedBST.traversalBalanceRoot(self, self.root)
  230.  
  231. def draw(self):
  232. drawTree(self.root, 0, True)
  233.  
  234. def traversalHeight(self, node):
  235. if node is not None:
  236. node.height1 = node.treeheight()
  237. BalancedBST.traversalHeight(self, node.leftChild)
  238. BalancedBST.traversalHeight(self, node.rightChild)
  239. else:
  240. return
  241.  
  242. def traversalBalance(self, node):
  243. if node:
  244. node.balanceupdate()
  245. if abs(node.balancefactor) > 1:
  246. BalancedBST.rebalance(self, node)
  247. BalancedBST.traversalBalance(self, node.parent)
  248. else:
  249. return
  250.  
  251. def traversalBalanceRoot(self, root):
  252. if root:
  253. root.balanceupdate()
  254. BalancedBST.traversalBalanceRoot(self, root.leftChild)
  255. BalancedBST.traversalBalanceRoot(self, root.rightChild)
  256. else:
  257. return
  258.  
  259. def rebalance(self, node):
  260. if node.balancefactor < 0:
  261. if node.rightChild.balancefactor > 0:
  262. self.rotateRight(node.rightChild)
  263. self.rotateLeft(node)
  264. else:
  265. self.rotateLeft(node)
  266. elif node.balancefactor > 0:
  267. if node.leftChild.balancefactor < 0:
  268. self.rotateLeft(node.leftChild)
  269. self.rotateRight(node)
  270. else:
  271. self.rotateRight(node)
  272. # ============== simulator ======================
  273.  
  274. class Simulator:
  275.  
  276. def __init__ (self, newPQ, isLoud=True):
  277. self.pq = newPQ
  278. self.limit = -1
  279. self.clock = 0
  280. self.log = None
  281. self.addTime = 0
  282. self.getTime = 0
  283. self.isLoud = isLoud
  284.  
  285. def setLimit(self, num):
  286. self.limit = num
  287.  
  288. def useLog(self, log):
  289. self.log = log
  290.  
  291. def _getNextEvent(self):
  292. self.clock += 1 # timestamps start at 1 and go up
  293. if self.log:
  294. idx = self.clock - 1
  295. if idx >= len(self.log):
  296. return None
  297. line = self.log[self.clock -1 ]
  298. #print ("found line", line)
  299. if line[0] == 'g':
  300. return ()
  301. else:
  302. nums = line[2:-1].split(',')
  303. return (int(nums[0]), int(nums[1]))
  304. else: # either generate a new task or get existing task to process
  305. num = random.randint(1,22)
  306. isNew = (num % 7 < 4) # 4/7 of the time we have new task
  307. if isNew:
  308. return (num, self.clock)
  309. else:
  310. return ()
  311.  
  312. def run(self):
  313. if self.isLoud:
  314. print("Simulation starting, PQ is ", type(self.pq), ", using log:", bool(self.log), ", limit is", self.limit)
  315. log = []
  316. while (self.limit == -1 or self.clock < self.limit):
  317. val = self._getNextEvent()
  318. if val == None:
  319. break
  320. elif len(val) > 0: # a new task has been generated for processing
  321. if self.isLoud:
  322. print("New task", val, "has been generated")
  323. startTime = time.time()
  324. self.pq.add(val)
  325. endTime = time.time()
  326. log.append("n" + str(val))
  327. self.addTime += endTime - startTime
  328. else:
  329. startTime = time.time()
  330. val = self.pq.getMin() # system is ready to process next task
  331. endTime = time.time()
  332. if self.isLoud:
  333. print(val, "is being processed next")
  334. log.append("g" + str(val))
  335. self.getTime += endTime - startTime
  336. if self.isLoud:
  337. self.pq.draw()
  338. print("Simulation finished,", type(self.pq), "has size", len(self.pq))
  339. return log
  340.  
  341. # ============== additional methods ==================
  342.  
  343. ## Part 1
  344. def priority(val):
  345. return val
  346.  
  347. def drawTree(node, indent=0, showHeight=False):
  348. if node == None:
  349. return
  350. drawTree(node.rightChild, indent+1, showHeight)
  351. if node.rightChild:
  352. print(" " * indent, " / ")
  353. if showHeight:
  354. print(" " * indent, node.val, ", height", node.height1)
  355. else:
  356. print(" " * indent, node.val)
  357. if node.leftChild:
  358. print(" " * indent, " \ ")
  359. drawTree(node.leftChild, indent+1, showHeight)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement