SHARE
TWEET

Untitled

a guest Apr 23rd, 2019 81 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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.  
  159.     self.size -= 1
  160.     self.draw()
  161.  
  162.   def draw(self):
  163.     drawTree(self.root, 0, True)
  164.  
  165.  
  166. # ================ class BalancedBST ===============
  167. class Queue:
  168.   def __init__(self):
  169.     self.items = []
  170.  
  171.   def isEmpty(self):
  172.     return self.items == []
  173.  
  174.   def enqueue(self, item):
  175.     self.items.insert(0, item)
  176.  
  177.   def dequeue(self):
  178.     return self.items.pop()
  179.  
  180.   def size(self):
  181.     return len(self.items)
  182.  
  183.   def peek(self):
  184.     return self.items[0]
  185.  
  186.  
  187. class BalancedBST(BST):
  188.  
  189.   ## Part 4
  190.   def add(self, val):  ## TO IMPLEMENT
  191.     newNode = BST.add(self, val)
  192.     BalancedBST.traversalHeight(self, self.root)
  193.     BalancedBST.traversalBalance(self, newNode)
  194.     self.size += 1
  195.     return newNode
  196.  
  197.   def rotateLeft(self, rotRoot):
  198.     newRoot = rotRoot.rightChild
  199.     rotRoot.rightChild = newRoot.leftChild
  200.     if newRoot.leftChild != None:
  201.       newRoot.leftChild.parent = rotRoot
  202.     newRoot.parent = rotRoot.parent
  203.     if rotRoot.isRoot():
  204.       self.root = newRoot
  205.     else:
  206.       if rotRoot.isLeftChild():
  207.         rotRoot.parent.leftChild = newRoot
  208.       else:
  209.         rotRoot.parent.rightChild = newRoot
  210.     newRoot.leftChild = rotRoot
  211.     rotRoot.parent = newRoot
  212.     BalancedBST.traversalHeight(self, self.root)
  213.     BalancedBST.traversalBalanceRoot(self, self.root)
  214.  
  215.   def rotateRight(self, rotRoot):
  216.     newRoot = rotRoot.leftChild
  217.     rotRoot.leftChild = newRoot.rightChild
  218.     if newRoot.rightChild != None:
  219.       newRoot.rightChild.parent = rotRoot
  220.     newRoot.parent = rotRoot.parent
  221.     if rotRoot.isRoot():
  222.       self.root = newRoot
  223.     else:
  224.       if rotRoot.isRightChild():
  225.         rotRoot.parent.rightChild = newRoot
  226.       else:
  227.         rotRoot.parent.leftChild = newRoot
  228.     newRoot.rightChild = rotRoot
  229.     rotRoot.parent = newRoot
  230.     BalancedBST.traversalHeight(self, self.root)
  231.     BalancedBST.traversalBalanceRoot(self, self.root)
  232.  
  233.   def draw(self):
  234.     drawTree(self.root, 0, True)
  235.  
  236.   def traversalHeight(self, node):
  237.     if node is not None:
  238.       node.height1 = node.treeheight()
  239.       BalancedBST.traversalHeight(self, node.leftChild)
  240.       BalancedBST.traversalHeight(self, node.rightChild)
  241.     else:
  242.       return
  243.  
  244.   def traversalBalance(self, node):
  245.     if node:
  246.       node.balanceupdate()
  247.       if abs(node.balancefactor) > 1:
  248.         BalancedBST.rebalance(self, node)
  249.       BalancedBST.traversalBalance(self, node.parent)
  250.     else:
  251.       return
  252.  
  253.   def traversalBalanceRoot(self, root):
  254.     if root:
  255.       root.balanceupdate()
  256.       BalancedBST.traversalBalanceRoot(self, root.leftChild)
  257.       BalancedBST.traversalBalanceRoot(self, root.rightChild)
  258.     else:
  259.       return
  260.  
  261.   def rebalance(self, node):
  262.     if node.balancefactor < 0:
  263.       if node.rightChild.balancefactor > 0:
  264.         self.rotateRight(node.rightChild)
  265.         self.rotateLeft(node)
  266.       else:
  267.         self.rotateLeft(node)
  268.     elif node.balancefactor > 0:
  269.       if node.leftChild.balancefactor < 0:
  270.         self.rotateLeft(node.leftChild)
  271.         self.rotateRight(node)
  272.       else:
  273.         self.rotateRight(node)
  274. # ============== simulator ======================
  275.  
  276. class Simulator:
  277.  
  278.   def __init__ (self, newPQ, isLoud=True):
  279.     self.pq = newPQ
  280.     self.limit = -1
  281.     self.clock = 0
  282.     self.log = None
  283.     self.addTime = 0
  284.     self.getTime = 0
  285.     self.isLoud = isLoud
  286.  
  287.   def setLimit(self, num):
  288.     self.limit = num
  289.  
  290.   def useLog(self, log):
  291.     self.log = log
  292.  
  293.   def _getNextEvent(self):
  294.     self.clock += 1  # timestamps start at 1 and go up
  295.     if self.log:
  296.       idx = self.clock - 1
  297.       if idx >= len(self.log):
  298.         return None
  299.       line = self.log[self.clock -1 ]
  300.       #print ("found line", line)
  301.       if line[0] == 'g':
  302.         return ()
  303.       else:
  304.         nums = line[2:-1].split(',')
  305.         return (int(nums[0]), int(nums[1]))
  306.     else:  # either generate a new task or get existing task to process
  307.       num = random.randint(1,22)
  308.       isNew = (num % 7 < 4)  # 4/7 of the time we have new task
  309.       if isNew:
  310.         return (num, self.clock)
  311.       else:
  312.         return ()
  313.  
  314.   def run(self):
  315.     if self.isLoud:
  316.         print("Simulation starting, PQ is ", type(self.pq), ", using log:", bool(self.log), ", limit is", self.limit)
  317.     log = []
  318.     while (self.limit == -1 or self.clock < self.limit):
  319.       val = self._getNextEvent()
  320.       if val == None:
  321.         break
  322.       elif len(val) > 0: # a new task has been generated for processing
  323.         if self.isLoud:
  324.           print("New task", val, "has been generated")
  325.         startTime = time.time()
  326.         self.pq.add(val)
  327.         endTime = time.time()
  328.         log.append("n" + str(val))
  329.         self.addTime += endTime - startTime
  330.       else:
  331.         startTime = time.time()
  332.         val = self.pq.getMin() # system is ready to process next task
  333.         endTime = time.time()
  334.         if self.isLoud:
  335.           print(val, "is being processed next")
  336.         log.append("g" + str(val))
  337.         self.getTime += endTime - startTime
  338.     if self.isLoud:
  339.       self.pq.draw()
  340.     print("Simulation finished,", type(self.pq), "has size", len(self.pq))
  341.     return log
  342.  
  343. # ============== additional methods ==================
  344.  
  345. ## Part 1
  346. def priority(val):
  347.   return val
  348.  
  349. def drawTree(node, indent=0, showHeight=False):
  350.   if node == None:
  351.     return
  352.   drawTree(node.rightChild, indent+1, showHeight)
  353.   if node.rightChild:
  354.     print("     " * indent, "  / ")
  355.   if showHeight:
  356.     print("     " * indent, node.val, ", height", node.height1)
  357.   else:
  358.     print("     " * indent, node.val)
  359.   if node.leftChild:
  360.     print("     " * indent, "  \ ")
  361.   drawTree(node.leftChild, indent+1, showHeight)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top