# -*- coding: utf-8 -*-

"""
B树的Python实现
"""


class Node(object):
    def __init__(self, key):
        self.key1 = key
        self.key2 = None
        self.left = None
        self.middle = None
        self.right = None

    def isLeaf(self):
        return self.left is None and self.middle is None and self.right is None

    def isFull(self):
        return self.key2 is not None

    def hasKey(self, key):
        if (self.key1 == key) or (self.key2 is not None and self.key2 == key):
            return True
        else:
            return False

    def getChild(self, key):
        if key < self.key1:
            return self.left
        elif self.key2 is None:
            return self.middle
        elif key < self.key2:
            return self.middle
        else:
            return self.right


class Tree(object):
    def __init__(self):
        self.root = None

    def get(self, key):
        if self.root is None:
            return None
        else:
            return self._get(self.root, key)

    def _get(self, node, key):
        if node is None:
            return None
        elif node.hasKey(key):
            return node
        else:
            child = node.getChild(key)
            return self._get(child, key)

    def put(self, key):
        if self.root is None:
            self.root = Node(key)
        else:
            pKey, pRef = self._put(self.root, key)
            if pKey is not None:
                newnode = Node(pKey)
                newnode.left = self.root
                newnode.middle = pRef
                self.root = newnode

    def _put(self, node, key):
        if node.hasKey(key):
            return None, None
        elif node.isLeaf():
            return self._addtoNode(node, key, None)
        else:
            child = node.getChild(key)
            pKey, pRef = self._put(child, key)
            if pKey is None:
                return None, None
            else:
                return self._addtoNode(node, pKey, pRef)

    def _addtoNode(self, node, key, pRef):
        if node.isFull():
            return self._splitNode(node, key, pRef)
        else:
            if key < node.key1:
                node.key2 = node.key1
                node.key1 = key
                if pRef is not None:
                    node.right = node.middle
                    node.middle = pRef
            else:
                node.key2 = key
                if pRef is not None:
                    node.right = pRef
            return None, None

    def _splitNode(self, node, key, pRef):
        newnode = Node(None)
        if key < node.key1:
            pKey = node.key1
            node.key1 = key
            newnode.key1 = node.key2
            if pRef is not None:
                newnode.left = node.middle
                newnode.middle = node.right
                node.middle = pRef
        elif key < node.key2:
            pKey = key
            newnode.key1 = node.key2
            if pRef is not None:
                newnode.left = pRef
                newnode.middle = node.right
        else:
            pKey = node.key2
            newnode.key1 = key
            if pRef is not None:
                newnode.left = node.right
                newnode.middle = pRef
        node.key2 = None
        return pKey, newnode
