#!/usr/bin/env python
#-*- coding:UTF-8-*-
import sys

class Item:
    def __init__(self, key, value):
        self.key=key
        self.value=value


class Node:
    def __init__(self, parent=None, nextNode=None):
        self.parent   = parent
        self.children = []
        self.keys     = []
        self.values   = []
        self.nextNode = nextNode


    def add(self,item):
        if (not self.children): #leaf
            if (len(self.keys)<3): #if leaf has place
                return(self.insertinsparseleaf(item)) #insert in leaf
            else:
                self.splitLeaf(item)
        else:
            for child in self.children:
                print self.keys
                if item.key<self.keys[self.children.index(child)]:
                    child.add(item)
                    return("inserted")
                else:
                    self.children[-1].add(item)
                    return("inserted")


    def splitLeaf(self,item):
        if (not self.parent):
            if (not self.children):
                self.firstSplit(item) # special case
                return("split complete")
            else:
                self.rootSplit()
        else:

            newNode=Node()
            self.nextNode=newNode
            if self.keys[-1]<item.key:
                popped=self.keys.pop()
                newNode.keys.append(popped)
                newNode.values.append(self.values.pop())
                newNode.keys.append(item.key)
                newNode.values.append(item.value)
            else:
                newNode.keys.append(item.key)
                newNode.values.append(item.value)
                newNode.keys.append(self.keys.pop())
                newNode.values.append(self.values.pop())
            t.root.children.append(newNode)
            t.root.keys.append(newNode.keys[0])
            newNode.parent=self.parent


            if len(self.parent.children)>4:# internal split requiered
                self.internalSplit(item)

        return("leaf splitted")

    def firstSplit(self,item):
        newRoot=Node()
        t.root=newRoot
        newNode=Node()
        self.nextNode=newNode
        self.parent=newRoot
        newNode.parent=newRoot
        if self.keys[-1]<item.key:
            popped=self.keys.pop()
            newNode.keys.append(popped)
            newNode.values.append(self.values.pop())
            newNode.keys.append(item.key)
            newNode.values.append(item.value)
            newRoot.keys.append(popped)
            newRoot.children.append(self)
            newRoot.children.append(newNode)
        else:
            newNode.keys.append(item.key)
            newNode.values.append(item.value)
            newNode.keys.append(self.keys.pop())
            newNode.values.append(self.values.pop())
            newRoot.keys.append(item.key)
            newRoot.children.append(newNode)
            newRoot.chilldren.apprnd(self)

        return


    def internalSplit(self, item):
        if (not self.parent.parent):
            self.rootSplit(item)
        else:
            pass

    def rootSplit(self,item):
        newRoot=Node()
        newNode=Node()
        newRoot.children.append(self.parent)
        newRoot.children.append(newNode)
        newNode.children.append(self.parent.children.pop(-2))
        newNode.children.append(self.parent.children.pop())
        self.parent.keys.pop(-2)
        newNode.keys.append(self.parent.keys.pop())
        for child in newNode.children:
            child.parent=newNode
        newRoot.keys.append(newNode.children[0].keys[0])
        t.root=newRoot





    def insertinsparseleaf(self,item):
        self.keys.append(item.key)
        self.keys.sort()
        self.values.insert(self.keys.index(item.key),item.value)
        return "inserted"


    def search(self,key):
        if (not self.children): #leaf node
            for x in self.keys:
                if (key==x):
                    return self.values[self.keys.index(x)]
        else: #not leaf nodes
            for x in self.keys:
                if (key<x):
                    return self.children[self.keys.index(x)].search(key) #terminal recursivity
                return self.children[len(self.keys)].search(key)

    def addchildrentoprint(self,children):
        toprint=""
        if (not self.children):
            return toprint
        else:
            for childkey in children.children:
                toprint += "\t\t "+str(childkey.keys)+"\n"
            return toprint

    def printnode(self):
        toprint=""
        if (not self.children): #leaf
            pass
        else:
            for children in self.children:
                toprint += "\n\t A child with keys :"+str(children.keys)+"\n"
                toprint += str(self.addchildrentoprint(children))

        return "Root has the key(s) : "+str(t.root.keys)+toprint

class Tree:
    def __init__(self):
        self.root = None # We init the tree with an empty node
        print "Empty tree created"

    def insert(self, item):
        if (not self.root): # First node inserted in tree
            self.root=Node()
            self.root.add(item)
            print "Added root node to tree"
        else:
            self.root.add(item)

    def search(self,key):
        if (not self.root):
            print "You need to add an item first."
            return -1
        else:
            return "Item with key "+str(key)+" has the values : "+str(self.root.search(key))

    def printree(self):
        print "\n \nCalling print tree method "
        print(self.root.printnode())



print("\n\n")
t=Tree()
i=Item(1,(1,2))
i2=Item(2,(3,4))
i3=Item(3,(5,6))
i4=Item(4,(7,8))
i5=Item(5,(9,10))
i6=Item(6,(11,12))
i7=Item(7,(13,14))
i8=Item(8,(15,16))
i9=Item(9,(17,18))
i10=Item(10,(19,20))
i11=Item(11,(21,22))

t.insert(i)

t.insert(i2)

t.insert(i3)

t.insert(i4)

t.insert(i5)

t.insert(i6)

t.insert(i7)

t.insert(i8)

t.insert(i9)

t.insert(i10)
t.insert(i11)
t.printree()




print t.search(1)
print t.search(8)
print t.search(10)

print "\nProgram ending.\n"