from Rivisitazione.Tree import Tree
from Rivisitazione.sorted_table_map import SortedTableMap


class LinkedMwTree(Tree):

    class _Node:

        __slots__ = '_elements' , '_parent' ,  '_size_elem' ,'_last'

        def __init__(self, elements= None , parent=None ,last=None ):

            self._elements= SortedTableMap() if elements is None else elements
            self._parent=parent
            self._last = last
            self._size_elem= 0 if elements is None else len(self._elements)


    class Position(Tree.Position):

        __slots__ = 'index'

        def __init__(self, container, node , index=0):

            self._container = container
            self._node = node
            self._index = index

        def element(self):

            return self._node._elements

        def get_index(self):
            return self._index

        def get_key(self):

            return self.element().get_by_index(self.get_index())[0]

        def get_value(self):

            return self.element().get_by_index(self.get_index())[1]

        def get_item(self):

            return self.element().get_by_index(self.get_index())

        def get_size(self):
            return self._node._size_elem

        def get_last(self): #da inserire nell'alber
            return self._node._last

        def keys(self):
            for k in self.element().keys():
                yield k

        def value(self):
            for v in self.element().value():
                yield v
            yield self.get_last()

        def num_elem(self):

            if self.get_last() == None:
                return 0
            else:
                return len(self.element())


        def __eq__(self, other):

            return type(other) is type(self) and other._node is self._node

        def __str__(self):
            s="[ "
            for e in self.element().keys():
                s+=str(e)+" "
            return s + "]"

            # ------------------------------- utility methods -------------------------------

    def _validate(self, p):
        """Return associated node, if position is valid."""
        if not isinstance(p, self.Position):
            raise TypeError('p must be proper Position type')
        if p._container is not self:
            raise ValueError('p does not belong to this container')
        if p._node._parent is p._node:  # convention for deprecated nodes
            raise ValueError('p is no longer valid')
        return p._node


    def _make_position(self, node):
        """Return Position instance for given node (or None if no node)."""
        return self.Position(self, node) if node is not None else None

        # --------------------------  alberi constructor --------------------------

    def __init__(self):
        """Create an initially empty binary alberi."""
        self._root = None
        self._size = 0

        # -------------------------- public accessors --------------------------

    def __len__(self):
        """Return the total number of elements in the alberi."""
        return self._size

    def root(self):
        """Return the root Position of the alberi (or None if alberi is empty)."""
        return self._make_position(self._root)

    def parent(self, p):
        """Return the Position of p's parent (or None if p is root)."""
        node = self._validate(p)
        return self._make_position(node._parent)


    def num_children(self, p):
        """Return the number of children of Position p."""
        node = self._validate(p)

        if node._last is None:
            return 0
        else:
            return len(node._elements) + 1



            # -------------------------- nonpublic mutators --------------------------

    def _add_root(self, e):
        """Place element e at the root of an empty alberi and return new Position.

        Raise ValueError if alberi nonempty.
        """
        if self._root is not None:
            raise ValueError('Root exists')
        self._size = 1
        self._root = self._Node(e)
        return self._make_position(self._root)

    def _delete(self, p , key):
        "del key from position"
        node = self._validate(p)
        del node._elements[key]
        self._size-=1
        node._size_elem-=1

    #fine linked ora dobbiamo fare binary

    def children(self, p):
        """Generate an iteration of Positions representing p's children."""
        node = self._validate(p)

        if self.num_children(p)!=0:
            for c in node._elements.value():
                yield self._make_position(c)

            yield self._make_position(node._last)

    def right_brother(self,p):
        "return the right brother or Null"
        self._validate(p)
        if(p != self.root()):
            parent = self.parent(p)
            last_key = p.element().find_max()[0]
            last_parent_key = parent.element().find_max()[0]

            father_key = parent.element().find_gt(last_key)

            if (father_key == None):
                return None
            elif (father_key[0] == last_parent_key):
                return self._make_position(parent.get_last())
            else:
                return self._make_position(parent.element().find_gt(father_key[0])[1])
        return None


    def left_brother(self,p):
        "return the left brother or Null"
        if (p != self.root()):
            self._validate(p)
            parent = self.parent(p)
            last_key = p.element().find_max()[0]
            first_parent_key = parent.element().find_min()[0]

            father_key = parent.element().find_gt(last_key)

            if (father_key == None):  # sono last
                return self._make_position(parent.element().find_max()[1])
            elif (father_key[0] == first_parent_key):  # sono il primo
                return None
            else:
                return self._make_position(parent.element().find_lt(father_key[0])[1])
        return None