import time
import random
import os
#==============  TreeNode class  =================

class TreeNode:
  def __init__(self, val, parent=None):
    self.height = 1
    self.val = val
    self.parent = parent
    self.leftChild = None
    self.rightChild = None
    self.height1 = 1
    self.balancefactor = 0

  def hasLeftChild(self):
    return self.leftChild

  def hasRightChild(self):
    return self.rightChild

  def isRoot(self):
    return not self.parent

  def isRightChild(self):
    return self.parent and self.parent.rightChild == self

  def isLeftChild(self):
    return self.parent and self.parent.leftChild == self

  def treeheight(self):
    if self is None:
      return 0
    else:
      return max(TreeNode.treeheight(self.leftChild),
                 TreeNode.treeheight(self.rightChild)) + 1

  def balanceupdate(self):
    if self.hasLeftChild() is None and self.hasRightChild() is None:
      self.balancefactor = 0
      return
    elif self.hasLeftChild() is None:
      self.balancefactor = - self.rightChild.height1
    elif self.hasRightChild() is None:
      self.balancefactor = self.leftChild.height1
    else:
      self.balancefactor = self.leftChild.height1 - self.rightChild.height1


# ==============  PQ class  =================

class PQ:
  def add(self, val):
    raise NotImplemented

  def peekMin(self):
    raise NotImplemented

  def getMin(self):
    raise NotImplemented

  def __len__(self):
    raise NotImplemented


# ============== LIST CLASS ==================

class ListPQ(PQ):
  def __init__(self):
    self.items = []

  def __len__(self):
    return len(self.items)

  def add(self, val):
    self.items.append(val)

  def peekMin(self):
    return self.getMin(False)

  def getMin(self, toRemove=True):
    if (self.items == []):
      return None
    minIdx = 0
    sz = len(self.items)
    for idx in range(sz):
      if priority(self.items[idx]) < priority(self.items[minIdx]):
        minIdx = idx
    minItem = self.items[minIdx]
    if toRemove:
      del self.items[minIdx]
    return minItem

  def draw(self):
    print(self.items)


# ============== BST CLASS ==================

class BST(PQ):

  def __init__(self):
    self.root = None
    self.size = 0
    self.newNode = None

  def __len__(self):
    return self.size

  ## Part 2
  def add(self, val):
    def _add(root, val, rootparent):
      if root == None:
        x = TreeNode(val, parent=rootparent)
        self.newNode = x
        return x
      if val < root.val:
        root.leftChild = _add(root.leftChild, val, root)
      else:
        root.rightChild = _add(root.rightChild, val, root)
      return root

    self.root = _add(self.root, val, None)
    self.size += 1
    return self.newNode

  def peekMin(self):
    return self.getMin(False)

  def getMin(self, toRemove=True):
    curNode = self.root
    if not curNode:
      return None
    while curNode.leftChild != None:
      curNode = curNode.leftChild
    if toRemove:
      self._remove(curNode)  ## TO IMPLEMENT
      self.size -= 1
    return curNode.val

  ## Part 3
  def _remove(self, node):
    print("***********before removing ", node.val)
    if node.parent is not None:
      if node.rightChild:
        node.rightChild.parent = node.parent
        node.parent.leftChild = node.rightChild
        node.parent = None
      else:
        node.parent.leftChild = None
    else:
      if node.rightChild:
        node = node.rightChild
        node.parent = None
        self.root = node
      else:
        self.root = None

    self.size -= 1
    self.draw()

  def draw(self):
    drawTree(self.root, 0, True)


# ================ class BalancedBST ===============
class Queue:
  def __init__(self):
    self.items = []

  def isEmpty(self):
    return self.items == []

  def enqueue(self, item):
    self.items.insert(0, item)

  def dequeue(self):
    return self.items.pop()

  def size(self):
    return len(self.items)

  def peek(self):
    return self.items[0]


class BalancedBST(BST):

  ## Part 4
  def add(self, val):  ## TO IMPLEMENT
    newNode = BST.add(self, val)
    BalancedBST.traversalHeight(self, self.root)
    BalancedBST.traversalBalance(self, newNode)
    self.size += 1
    return newNode

  def rotateLeft(self, rotRoot):
    newRoot = rotRoot.rightChild
    rotRoot.rightChild = newRoot.leftChild
    if newRoot.leftChild != None:
      newRoot.leftChild.parent = rotRoot
    newRoot.parent = rotRoot.parent
    if rotRoot.isRoot():
      self.root = newRoot
    else:
      if rotRoot.isLeftChild():
        rotRoot.parent.leftChild = newRoot
      else:
        rotRoot.parent.rightChild = newRoot
    newRoot.leftChild = rotRoot
    rotRoot.parent = newRoot
    BalancedBST.traversalHeight(self, self.root)
    BalancedBST.traversalBalanceRoot(self, self.root)

  def rotateRight(self, rotRoot):
    newRoot = rotRoot.leftChild
    rotRoot.leftChild = newRoot.rightChild
    if newRoot.rightChild != None:
      newRoot.rightChild.parent = rotRoot
    newRoot.parent = rotRoot.parent
    if rotRoot.isRoot():
      self.root = newRoot
    else:
      if rotRoot.isRightChild():
        rotRoot.parent.rightChild = newRoot
      else:
        rotRoot.parent.leftChild = newRoot
    newRoot.rightChild = rotRoot
    rotRoot.parent = newRoot
    BalancedBST.traversalHeight(self, self.root)
    BalancedBST.traversalBalanceRoot(self, self.root)

  def draw(self):
    drawTree(self.root, 0, True)

  def traversalHeight(self, node):
    if node is not None:
      node.height1 = node.treeheight()
      BalancedBST.traversalHeight(self, node.leftChild)
      BalancedBST.traversalHeight(self, node.rightChild)
    else:
      return

  def traversalBalance(self, node):
    if node:
      node.balanceupdate()
      if abs(node.balancefactor) > 1:
        BalancedBST.rebalance(self, node)
      BalancedBST.traversalBalance(self, node.parent)
    else:
      return

  def traversalBalanceRoot(self, root):
    if root:
      root.balanceupdate()
      BalancedBST.traversalBalanceRoot(self, root.leftChild)
      BalancedBST.traversalBalanceRoot(self, root.rightChild)
    else:
      return

  def rebalance(self, node):
    if node.balancefactor < 0:
      if node.rightChild.balancefactor > 0:
        self.rotateRight(node.rightChild)
        self.rotateLeft(node)
      else:
        self.rotateLeft(node)
    elif node.balancefactor > 0:
      if node.leftChild.balancefactor < 0:
        self.rotateLeft(node.leftChild)
        self.rotateRight(node)
      else:
        self.rotateRight(node)
# ============== simulator ======================

class Simulator:

  def __init__ (self, newPQ, isLoud=True):
    self.pq = newPQ
    self.limit = -1
    self.clock = 0
    self.log = None
    self.addTime = 0
    self.getTime = 0
    self.isLoud = isLoud

  def setLimit(self, num):
    self.limit = num

  def useLog(self, log):
    self.log = log

  def _getNextEvent(self):
    self.clock += 1  # timestamps start at 1 and go up
    if self.log:
      idx = self.clock - 1
      if idx >= len(self.log):
        return None
      line = self.log[self.clock -1 ]
      #print ("found line", line)
      if line[0] == 'g':
        return ()
      else:
        nums = line[2:-1].split(',')
        return (int(nums[0]), int(nums[1]))
    else:  # either generate a new task or get existing task to process
      num = random.randint(1,22)
      isNew = (num % 7 < 4)  # 4/7 of the time we have new task
      if isNew:
        return (num, self.clock)
      else:
        return ()

  def run(self):
    if self.isLoud:
        print("Simulation starting, PQ is ", type(self.pq), ", using log:", bool(self.log), ", limit is", self.limit)
    log = []
    while (self.limit == -1 or self.clock < self.limit):
      val = self._getNextEvent()
      if val == None:
        break
      elif len(val) > 0: # a new task has been generated for processing
        if self.isLoud:
          print("New task", val, "has been generated")
        startTime = time.time()
        self.pq.add(val)
        endTime = time.time()
        log.append("n" + str(val))
        self.addTime += endTime - startTime
      else:
        startTime = time.time()
        val = self.pq.getMin() # system is ready to process next task
        endTime = time.time()
        if self.isLoud:
          print(val, "is being processed next")
        log.append("g" + str(val))
        self.getTime += endTime - startTime
    if self.isLoud:
      self.pq.draw()
    print("Simulation finished,", type(self.pq), "has size", len(self.pq))
    return log

# ============== additional methods ==================

## Part 1
def priority(val):
  return val

def drawTree(node, indent=0, showHeight=False):
  if node == None:
    return
  drawTree(node.rightChild, indent+1, showHeight)
  if node.rightChild:
    print("     " * indent, "  / ")
  if showHeight:
    print("     " * indent, node.val, ", height", node.height1)
  else:
    print("     " * indent, node.val)
  if node.leftChild:
    print("     " * indent, "  \ ")
  drawTree(node.leftChild, indent+1, showHeight)