# An AVL tree, python
import random


class TreeNode:
    def __init__(self, key, val, left=None, right=None, parent=None, bal=0):
        self.key = key
        self.payload = val
        self.leftChild = left
        self.rightChild = right
        self.parent = parent
        self.balanceFactor = bal

    def update_val(self, new_val):  # added
        self.payload = new_val

    def hasLeftChild(self):
        return self.leftChild

    def hasRightChild(self):
        return self.rightChild

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

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

    def isRoot(self):
        return not self.parent

    def isLeaf(self):
        return not (self.rightChild or self.leftChild)

    def hasAnyChildren(self):
        return self.rightChild or self.leftChild

    def hasBothChildren(self):
        return self.rightChild and self.leftChild

    def replaceNodeData(self, key, value, lc, rc):
        self.key = key
        self.payload = value
        self.leftChild = lc
        self.rightChild = rc
        if self.hasLeftChild():
            self.leftChild.parent = self
        if self.hasRightChild():
            self.rightChild.parent = self

    def findSuccessor(self):
        succ = None
        if self.hasRightChild():
            succ = self.rightChild.findMin()
        else:
            if self.parent:
                if self.isLeftChild():
                    succ = self.parent
                else:
                    self.parent.rightChild = None
                    succ = self.parent.findSuccessor()
                    self.parent.rightChild = self
        return succ

    def findMin(self):
        current = self
        while current.hasLeftChild():
            current = current.leftChild
        return current

    def spliceOut(self):
        if self.isLeaf():
            if self.isLeftChild():
                self.parent.leftChild = None
            else:
                self.parent.rightChild = None
        elif self.hasAnyChildren():
            if self.hasLeftChild():
                if self.isLeftChild():
                    self.parent.leftChild = self.leftChild
                else:
                    self.parent.rightChild = self.leftChild
                self.leftChild.parent = self.parent
            else:
                if self.isLeftChild():
                    self.parent.leftChild = self.rightChild
                else:
                    self.parent.rightChild = self.rightChild
                self.rightChild.parent = self.parent


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

    def length(self):
        return self.size

    def __len__(self):
        return self.size

    def __getitem__(self, key):
        return self.get(key)

    def __setitem__(self, k, v):
        self.put(k, v)

    def put(self, key, val):
        if self.root:
            self._put(key, val, self.root)
        else:
            self.root = TreeNode(key, val)
        self.size = self.size + 1

    # start of overwritten section and balancing methods
    def _put(self, key, val, currentNode):
        # pdb.set_trace()
        if key == currentNode.key:
            currentNode.update_val(val)
            return
        if key < currentNode.key:
            if currentNode.hasLeftChild():
                self._put(key, val, currentNode.leftChild)
            else:
                currentNode.leftChild = TreeNode(key, val, parent=currentNode)
                self.updateBalance(currentNode.leftChild)
        else:
            if currentNode.hasRightChild():
                self._put(key, val, currentNode.rightChild)
            else:
                currentNode.rightChild = TreeNode(key, val, parent=currentNode)
                self.updateBalance(currentNode.rightChild)

    def rotateLeft(self, rotRoot):
        # pdb.set_trace()
        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
        rotRoot.balanceFactor = rotRoot.balanceFactor + 1 - min(newRoot.balanceFactor, 0)
        newRoot.balanceFactor = newRoot.balanceFactor + 1 + max(rotRoot.balanceFactor, 0)

    def rotateRight(self, rotRoot):
        # pdb.set_trace()
        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.isLeftChild():
                rotRoot.parent.leftChild = newRoot
            else:
                rotRoot.parent.rightChild = newRoot
        newRoot.rightChild = rotRoot
        rotRoot.parent = newRoot
        rotRoot.balanceFactor = rotRoot.balanceFactor - 1 - max(newRoot.balanceFactor, 0)
        newRoot.balanceFactor = newRoot.balanceFactor - 1 + min(0, rotRoot.balanceFactor)

    def updateBalance(self, node):
        # pdb.set_trace()
        if node.balanceFactor > 1 or node.balanceFactor < -1:
            self.rebalance(node)
            return
        if node.parent != None:
            if node.isLeftChild():
                node.parent.balanceFactor += 1
            elif node.isRightChild():
                node.parent.balanceFactor -= 1

            if node.parent.balanceFactor != 0:
                self.updateBalance(node.parent)

    def rebalance(self, node):
        # pdb.set_trace()
        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)

    # end of overwritten and balancing methods

    def get(self, key):
        if self.root:
            res = self._get(key, self.root)
            if res:
                return res.payload
            else:
                return None
        else:
            return None

    def _get(self, key, currentNode):
        if not currentNode:
            return None
        elif currentNode.key == key:
            return currentNode
        elif key < currentNode.key:
            return self._get(key, currentNode.leftChild)
        else:
            return self._get(key, currentNode.rightChild)

    def __delitem__(self, key):
        self.delete(key)

    def delete(self, key):
        if self.size > 1:
            nodeToRemove = self._get(key, self.root)
            if nodeToRemove:
                self.remove(nodeToRemove)
                self.size = self.size - 1
            else:
                raise KeyError('Error, key not in tree')
        elif self.size == 1 and self.root.key == key:
            self.root = None
            self.size = self.size - 1
        else:
            raise KeyError('Error, key not in tree')

    def remove(self, currentNode):
        if currentNode.isLeaf():  # this is leaf
            if currentNode == currentNode.parent.leftChild:
                currentNode.parent.leftChild = None
                currentNode.parent.balanceFactor -= 1
                if currentNode.parent.balanceFactor < -1:
                    self.updateBalance(currentNode.parent)
            else:
                currentNode.parent.rightChild = None
                currentNode.parent.balanceFactor += 1
                if currentNode.parent.balanceFactor > 1:
                    self.updateBalance(currentNode.parent)
        elif currentNode.hasBothChildren():  # this is interior node
            succ = currentNode.findSuccessor()
            succ.spliceOut()
            if succ.isLeftChild():
                succ.parent.balanceFactor -= 1
                self.updateBalance(succ.parent)
            elif succ.isRightChild():
                succ.parent.balanceFactor += 1
                self.updateBalance(succ.parent)
            currentNode.key = succ.key
            currentNode.payload = succ.payload

        else:  # this node has one child
            if currentNode.hasLeftChild():
                if currentNode.isLeftChild():
                    currentNode.leftChild.parent = currentNode.parent
                    currentNode.parent.leftChild = currentNode.leftChild
                    currentNode.parent.balanceFactor -= 1
                    self.updateBalance(currentNode.parent)
                elif currentNode.isRightChild():
                    currentNode.leftChild.parent = currentNode.parent
                    currentNode.parent.rightChild = currentNode.leftChild
                    currentNode.parent.balanceFactor += 1
                    self.updateBalance(currentNode.parent)
                else:
                    currentNode.replaceNodeData(currentNode.leftChild.key,
                                                currentNode.leftChild.payload,
                                                currentNode.leftChild.leftChild,
                                                currentNode.leftChild.rightChild)
            else:
                if currentNode.isLeftChild():
                    currentNode.rightChild.parent = currentNode.parent
                    currentNode.parent.leftChild = currentNode.rightChild
                    currentNode.parent.balanceFactor -= 1
                    self.updateBalance(currentNode.parent)
                elif currentNode.isRightChild():
                    currentNode.rightChild.parent = currentNode.parent
                    currentNode.parent.rightChild = currentNode.rightChild
                    currentNode.parent.balanceFactor += 1
                    self.updateBalance(currentNode.parent)
                else:
                    currentNode.replaceNodeData(currentNode.rightChild.key,
                                                currentNode.rightChild.payload,
                                                currentNode.rightChild.leftChild,
                                                currentNode.rightChild.rightChild)


# end of tree code


# functions on tree:
def inorder_traversal(tree):
    cur = tree.root

    def helper(current):
        if current:
            helper(current.leftChild)
            print(current.key, current.payload)
            helper(current.rightChild)
        return helper(cur)


def height_node(tree_node):
    if not tree_node:
        return 0
    else:
        return 1 + max(height_node(tree_node.leftChild), height_node(tree_node.rightChild))


def is_balanced(tree_node):
    return abs(height_node(tree_node.leftChild) - height_node(tree_node.rightChild)) <= 1


def list_print(tree_node):
    def top_height(tree_node):
        if not tree_node:
            return 0
        else:
            return 1 + top_height(tree_node.parent)

    if not tree_node:
        return []
    else:
        size = height_node(tree_node.root)
        l1 = [[] for x in range(size)]

        def travel_list(current):
            if current:
                travel_list(current.leftChild)
                l1[top_height(current) - 1].append(current.key)
                travel_list(current.rightChild)
            return l1

        l = travel_list(tree_node.root)
        for x in range(len(l)):
            print(l[x])


# tests in a loop:
for f in range(100):
    mytree1 = BinarySearchTree()
    for x in range(1000):
        mytree1.put(random.randint(-10000, 10000), "a")
    for i in range(100):
        if mytree1.get(i):
            mytree1.delete(i)
        if not is_balanced(mytree1.root):
            print("not good")
            h = height_node(mytree1.root)
            print("height: ", h)
            list_print(mytree1)
            break
    del (mytree1)

print("OK")

# python double linked list

class DoubleLinkedlist:
    class Node:
        def __init__(self, initdata):
            self.data = initdata
            self.next = None
            self.prev = None

        def getData(self):
            return self.data

        def getNext(self):
            return self.next

        def getPrev(self):
            return self.prev

        def setData(self, newdata):
            self.data = newdata

        def setNext(self, newnext):
            self.next = newnext

        def setPrev(self, newprev):
            self.prev = newprev

    def __init__(self):
        self.head = None
        self.last = None
        self.N = 0

    def is_empty(self):
        return self.head == None

    def push(self, x):
        temp = self.Node(x)
        if self.head == None:
            self.head = temp
            self.last = temp
        else:
            temp2 = self.head
            temp.setNext(self.head)
            self.head = temp
            temp2.setPrev(temp)
        self.N += 1

    def append(self, x):  # add at the end of the list
        temp = self.Node(x)
        if self.head == None:
            self.head = temp
            self.last = temp
        else:
            temp2 = self.last
            temp.setPrev(self.last)
            self.last = temp
            temp2.setNext(temp)
        self.N += 1

    def __len__(self):
        return self.size()

    def size(self):
        return self.N

    def search(self, item):  # returns (don't remove) item from the list
        current = self.head
        found = False
        while current != None and not found:
            if current.getData() == item:
                found = True
            else:
                current = current.getNext()
        return found

    def __getitem__(self, index):
        return self.get(index)

    def __setitem__(self, i, v):
        return self.update(v, i)

    def get(self, i=0):  # returns item with index i
        current = self.head
        found = False
        cnt = 0
        while not cnt > i and not found:
            if cnt == i:
                found = True
            else:
                current = current.getNext()
                cnt += 1
        return current.getData()

    def update(self, new_item, i):  # takes index and new item and update list element
        current = self.head
        cnt = 0
        found = False
        while not found:
            if cnt == i:
                current.setData(new_item)
                found = True
            else:
                current = current.getNext()
                cnt += 1

    def index(self, item):  # return first item index  in  the list
        current = self.head
        found = False
        cnt = 0
        while current != None and not found:
            if current.getData() == item:
                found = True
            else:
                cnt += 1
                current = current.getNext()
        return cnt

    def slice(self, start, stop):  # create a python style slice
        tempList = DoubleLinkedlist()
        current = self.head
        cnt = 0
        while cnt != start:
            cnt += 1
            current = current.getNext()
        while cnt < stop:
            t = current.getData()
            tempList.append(t)
            cnt += 1
            current = current.getNext()
        return tempList

    def remove(self, item):  # delete the first occurence of an item
        current = self.head
        previous = None
        found = False
        while not found:
            if current.getData() == item:
                found = True
            else:
                previous = current
                current = current.getNext()

        if previous == None:
            self.head = current.getNext()
        else:

            current.setPrev(current.getPrev)
            previous.setNext(current.getNext())
        self.N -= 1

    def pop(self, i=0):
        current = self.head
        previous = None
        found = False
        cnt = 0
        while not found:
            if cnt == i:
                found = True
            else:
                previous = current
                current = current.getNext()
            cnt += 1
        if previous == None:
            self.head = current.getNext()
        else:

            current.setPrev(current.getPrev)
            previous.setNext(current.getNext())
        self.N -= 1

    def __str__(self):  # enables print(list)
        if self.head != None:
            current = self.head
            out = '[' + str(current.getData())
            while current.getNext() != None:
                current = current.getNext()
                out += ', ' + str(current.getData())
            return out + ']'
        return '[]'

    def __add__(self, list_item):  # magic method enables concat: l1 + l2
        self.last.setNext(list_item.head)
        list_item.head.setPrev(self.last)
        self.last = list_item.last
        self.N += list_item.size()

    def iterate(self):  # returns iterator over the list
        current = self.head
        while current != None:
            yield current
            current = current.getNext()

    def __eq__(self, other):  # defines equality, enables to use == as a value equality
        if self.size() != other.size():
            return False
        current = self.head
        current2 = other.head
        while current != None:
            if current.getData() != current2.getData():
                return False
            else:
                current = current.getNext()
                current2 = current2.getNext()
        return True


l1 = DoubleLinkedlist()
for i in range(7):
    l1.append(str(i + 9))
print(l1)
l1[0] = "asdf"
l1.pop(6)
print(l1)
print(l1[3])
print(l1.index("11"))
print(len(l1))

'''
output ->
[9, 10, 11, 12, 13, 14, 15]
[asdf, 10, 11, 12, 13, 14]
12
2
6
'''

# binary heap - min heap

class Bin_heap:
    def __init__(self):
        self.heap_list = [0]
        self.__current_size = 0

    def build_heap(self, xs):
        i = len(xs) // 2
        self.__current_size = len(xs)
        self.heap_list = [0] + xs[:]
        while i > 0:
            self.__pop_down(i)
            i = i - 1

    def del_min(self):
        res = self.heap_list[1]
        self.heap_list[1] = self.heap_list[self.__current_size]
        self.__current_size -= 1
        self.heap_list.pop()
        self.__pop_down(1)
        return res

    def insert(self, x):
        self.heap_list.append(x)
        self.__current_size += 1
        self.__pos_item(self.__current_size)

    def find_min(self):
        return self.heap_list[1]

    def size(self):
        return self.__current_size

    def __str__(self):
        return str(print(self.heap_list[1:]))

    def __len__(self):
        return self.size()

    # private methods

    def __pos_item(self, i):
        while i // 2 > 0:
            if self.heap_list[i] < self.heap_list[i // 2]:
                tmp = self.heap_list[i // 2]
                self.heap_list[i // 2] = self.heap_list[i]
                self.heap_list[i] = tmp
            i //= 2

    def __pop_down(self, i):
        while i * 2 <= self.__current_size:
            min_ch = self.__min_child(i)
            if self.heap_list[i] > self.heap_list[min_ch]:
                tmp = self.heap_list[i]
                self.heap_list[i] = self.heap_list[min_ch]
                self.heap_list[min_ch] = tmp
            i = min_ch

    def __min_child(self, i):
        if i * 2 + 1 > self.__current_size:
            return i * 2
        else:
            if self.heap_list[i * 2] < self.heap_list[i * 2 + 1]:
                return i * 2
            else:
                return i * 2 + 1


h1 = Bin_heap()
h1.build_heap([8, 23, 5, 6, 77, 1, -98])
print(h1)
print(h1.find_min())
print(h1)
h1.del_min()
print(h1)
h1.insert(-909)
print(h1)
print(len(h1))
'''
output ->
[-98, 6, 1, 23, 77, 8, 5]
None
-98
[-98, 6, 1, 23, 77, 8, 5]
None
[1, 6, 5, 23, 77, 8]
None
[-909, 6, 1, 23, 77, 8, 5]
None
7
'''