from Rivisitazione.LinkedMwTree import LinkedMwTree
from Rivisitazione.Tdp_collections.map.map_base import MapBase
from Rivisitazione.sorted_table_map import SortedTableMap

class TwoDTreeMap(LinkedMwTree,MapBase):

    # --------------- nonpublic utilities -------------------------------
    def __init__(self,d=4):

        super().__init__()
        if d >3 and d<9:
          self._d=d
        else:
            raise Exception("Errore non compreso tra 2 e 9 esclusi")


    def _subtree_search(self , p , k):
        """Return Position of p's subtree having key k, or last node searched."""

        self._validate(p)

        if p.element().getEffective(k) is not None:
            return p

        if not self.is_leaf(p):

            child = p.element().find_gt(k)

            if(child == None): #ultimo
                return self._subtree_search(self._make_position(p.get_last()),k)
            else:
                return self._subtree_search(self._make_position(child[1]),k)
        else:
            return p


    def _subtree_first_position(self, p):

        self._validate(p)
        walk = p

        while not self.is_leaf(walk):
            walk = self._make_position(walk.element().find_min()[1])
        return walk

    def _subtree_last_position(self, p):

        self._validate(p)
        walk = p

        while not self.is_leaf(walk):
            walk = self._make_position(walk._node._last)
        return walk


    # --------------------- public methods providing "positional" support ---------------------

    def first(self):
        return self._subtree_first_position(self.root()) if len(self) > 0 else None

    def last(self):
        return self._subtree_last_position(self.root()) if len(self) > 0 else None

    def sibling(self, p):

        self._validate(p)
        s = self.left_brother(p) if self.left_brother(p) != None else self.right_brother(p) if self.right_brother(
            p) != None else None

    def before(self , p):
        pass

    def after(self , p):
        pass

    def find_position(self,k):

        if self.is_empty():
            return None
        else:
            p= self._subtree_search(self.root(),k)
            return p

    def delete(self, p):
        pass

    # --------------------- public methods for (standard) map interface ---------------------

    def __getitem__(self, k):

        if self.is_empty():
            raise KeyError('Errore chiave non trovata poichè albero vuoto : ' + repr(k))
        else:
            p = self._subtree_search(self.root(),k)


            if p.element().getEffective(k) is not None:
                return p.element().getEffective(k)
            else:
                raise KeyError('Key Error: ' + repr(k))

    def __setitem__(self, key, value):

        if self.is_empty():
            element = SortedTableMap()
            element[key]=None
            element.setEffective(key,value)
            self._add_root(element)

        else:
            p = self._subtree_search(self.root(), key)
            if(p.element().get(key)!=None):
                p.element().setEffective(key,value)
            else:
                overflow = self._check_overflow(p)
                if overflow == True:
                    p = self._subtree_search(self.root(), key)
                p.element()[key]=None
                p.element().setEffective(key, value)
            p._node._size_elem += 1
            self._size += 1

    def __delitem__(self, key):
        if self.is_empty():
            raise KeyError('Errore chiave non trovata poichè albero vuoto : ' + repr(key))
        else:
            p = self._subtree_search(self.root(), key)

        print("p : "+str(p))

        if(not self.is_leaf(p)): #se non sono foglia
            p = self._swap_with_pre(p,key)

        if self._check_underflow(p):
            pass

        del p._node._elements[key]


    #--------------------- private method for __setitem__ --------------------------------------

    def _check_overflow(self, p):

        if p.get_size() == self._d - 1:
            if p._node == self._root:
                self._make_new_root()
                return True
            else:
                self._check_overflow(self.parent(p))
                self._split(p)
            return True
        else:
            return False

    def _make_new_root(self):

        p = self.root()
        leaf = self.is_leaf(p)
        pivot = round((p.get_size() - 0.1) / 2)
        item_promote = p.element().get_by_index(pivot)
        n1_elem=p.element().subElement(0,pivot)
        n2_elem=p.element().subElement(pivot+1,len(p.element()))
        n1_last = item_promote._value
        n2_last = p.get_last()

        n1_node = self._Node(n1_elem,None,n1_last)
        n2_node = self._Node(n2_elem,None,n2_last)


        elem_promote = SortedTableMap()
        elem_promote[item_promote._key] = n1_node  # qui va n1
        elem_promote.setEffective(item_promote._key,item_promote.effective())

        self._root._elements = elem_promote
        self._root._last = n2_node
        self._root._size_elem = 1

        #settiamo i parent
        n1_node._parent = self._root
        n2_node._parent = self._root

        if not leaf:
            for c in n1_node._elements.value():
                c._parent = n1_node
            n1_node._last._parent = n1_node

            for c in n2_node._elements.value():
                c._parent = n2_node
            n2_node._last._parent = n2_node

    def _split(self,p):

        leaf = self.is_leaf(p)
        pivot = round((p.get_size() - 0.1) / 2)

        item_promote = p.element().get_by_index(pivot)
        n1_elem = p.element().subElement(0, pivot)
        n2_elem = p.element().subElement(pivot + 1, len(p.element()))
        parent = self.parent(p)
        n1_node = self._Node(n1_elem, parent._node, item_promote._value)

        parent.element()[item_promote._key] = n1_node
        parent.element().setEffective(item_promote._key, item_promote._effective)

        p._node._elements = n2_elem
        p._node._size_elem = len(n2_elem)

        if not leaf:
            for c in p._node.element().value():
                c._parent = p._node

        if not leaf:
            for c in n1_node._elements.value():
                c._parent = n1_node
            n1_node._last._parent = n1_node

        parent._node._size_elem += 1

    # --------------------- private method for __delitem__ --------------------------------------

    def _swap_with_pre(self , p , k):

        self._validate(p)
        son = self._make_position(p.element().get(k))
        pre=self._subtree_last_position(son)
        kC = pre.element().find_max()[0]

        p._node._elements.changeKey(k,kC,pre._node._elements.getEffective(kC))
        pre._node._elements.changeKey(kC,k,p._node._elements.getEffective(k))

        return pre

    def _check_underflow(self, p):
        if p.get_size() != 1:
            return False
        else:
            True


    def _move_elem(self):
        pass #da implementare forse dopo

    def _delete_pos(self, p):

        pass

    def _swap_elem(self, ind1, p1, ind2, p2):

        pass