class BinaryTree():
    
    def __init__(self, children = None):
        """
        A binary tree is either a leaf or a node with two subtrees.
        
        INPUT:
            
            - children, either None (for a leaf), or a list of size excatly 2 
            of either two binary trees or 2 objects that can be made into binary trees
        """
        self._isleaf = (children is None)
        if not self._isleaf:
            if len(children) != 2:
                raise ValueError("A binary tree needs exactly two children")
            self._children = tuple(c if isinstance(c,BinaryTree) else BinaryTree(c) for c in children)
        self._size = None
        
    def __repr__(self):
        if self.is_leaf():
            return "leaf"
        return str(self._children)
    
    def __eq__(self, other):
        """
        Return true if other represents the same binary tree as self
        """
        if not isinstance(other, BinaryTree):
            return False
        if self.is_leaf():
            return other.is_leaf()
        return self.left() == other.left() and self.right() == other.right()
    
    
    def left(self):
        """
        Return the left subtree of self
        """
        return self._children[0]
    
    def right(self):
        """
        Return the right subtree of self
        """
        return self._children[1]
    
    def is_leaf(self):
        """
        Return true is self is a leaf
        """
        return self._isleaf
    
    def _compute_size(self):
        """
        Recursively computes the size of self
        """
        if self.is_leaf():
            self._size = 0
        else:
            self._size = self.left().size() + self.right().size() +1 
    
    def size(self):
        """
        Return the number of nodes (non leaves) in the binary tree
        """
        if self._size is None:
            self._compute_size()
        return self._size
    
    
leaf = BinaryTree()
        

t = BinaryTree()
t

t.size()

t = BinaryTree([[leaf,leaf], leaf]) # a tree of size 2
t

t.size()

t = BinaryTree([leaf, [leaf,leaf]]) # a different tree of size 2
t

t.size()

t = BinaryTree([[leaf, leaf], [leaf, leaf]]) # a tree of size 3
t

t.size()

"""
Explanation: Arbres binaires
Le but de ce TP est d'implanter les fonctions usuelles telles que la génération exhaustive (fabriquer tous les éléments de l'ensemble), rank et unrank sur l'ensemble des arbres binaires.  
Pour représenter les arbres binaires en python, on utilisera la structure suivante.
Exécutez les cellules suivantes et observez les exemples.
End of explanation
"""


# t1 = BinaryTree(...)


# t2 = BinaryTree(...)


# t3 = BinaryTree(...)


# t4 = BinaryTree(...)


"""
Explanation: Il y a 5 arbres binaires de taille 3. L'un deux est celui que nous venons de construire. 
Construisez explicitement les 4 autres
End of explanation
"""


import math
import random
class BinaryTrees():
    
    def __init__(self, size):
        """
        The combinatorial set of binary trees of size `size`
        
        INPUT:
        
            - size a non negative integers
        """
        self._size = size
        
    def size(self):
        """
        Return the size of the binary trees of the set
        """
        return self._size
    
    def __repr__(self):
        """
        Default string repr of ``self``
        """
        return "Binary Trees of size " + str(self._size)
    
    def cardinality(self):
        """
        Return the cardinality of the set
        """
        # This is given to you
        n = self._size
        f = math.factorial(n)
        return math.factorial(2*n)//(f*f*(n+1))
    
    def __iter__(self):
        """
        Iterator on the elements of the set
        """
        # écrire le code ici
                    
    def first(self):
        """
        Return the first element of the set 
        """
        for t in self:
            return t
                    
    def rank(self,t):
        """
        Return the rank of the binary tree t in the generation order of the set (starting at 0)
        
        INPUT:
        
            - t, a binary tree
        """
        # écrire le code ici
    
    def unrank(self,i):
        """
        Return the binary tree corresponding to the rank ``i`` 
        
        INPUT:
        
            - i, a integer between 0 and the cardinality minus 1
        """
        # écrire le code ici
        
    def next(self,t):
        """
        Return the next element following t in self
        
        INPUT :
        
            - t a binary tree
            
        OUPUT :
        
        The next binary tree or None if t is the last permutation of self
        """
        # écrire le code ici
        
    
    def random_element(self):
        """
        Return a random element of ``self`` with uniform probability
        """
        # écrire le code ici


BinaryTrees(0)

list(BinaryTrees(0))

BinaryTrees(1)

list(BinaryTrees(1))

BinaryTrees(2)

list(BinaryTrees(2))

BT3 = BinaryTrees(3)
BT3

list(BT3)

t = BinaryTree(((leaf, leaf), (leaf, leaf)))

BT3.rank(t)

BT3.unrank(2)

BT3.next(t)

BT3.random_element()

"""
Explanation: Le but de ce TP est d'implanter les fonctions de la classe BinaryTrees ci-dessous (avec un "s" à la fin) qui représente l'ensemble des arbres binaires d'une taille donnée. La structure de la classe vous est donnée ainsi que les méthodes de base.
Complétez les méthodes manquantes puis exécutez les exemples ci-dessous.
End of explanation
"""


def test_cardinality_iter(S):
    assert len(list(S)) == S.cardinality()

def test_rank(S):
    assert [S.rank(p) for p in S] == list(range(S.cardinality()))
    
def test_unrank(S):
    assert list(S) == [S.unrank(i) for i in range(S.cardinality())]
    
def test_next(S):
    L = [S.first()]
    while True:
        p = S.next(L[-1])
        if p == None:
            break
        L.append(p)
    assert L == list(S)
            
    
def all_tests(S):
    tests = {"Cardinality / iter": test_cardinality_iter, "Rank": test_rank, "Unrank": test_unrank, "Next": test_next}
    for k in tests:
        print ("Testsing: "+ k)
        try:
            tests[k](S)
            print ("Passed")
        except AssertionError:
            print ("Not passed")

all_tests(BinaryTrees(3))

all_tests(BinaryTrees(4))

all_tests(BinaryTrees(5))

all_tests(BinaryTrees(6))

"""
Explanation: La suite de tests que nous avions définies sur les permutations peut aussi s'appliquer sur les arbres binaires. 
Exécutez la cellule suivante puis vérifiez que les tests passent sur les exemples.
End of explanation
"""


import random
def random_grow(t):
    """
    Randomly grows a binary tree 
    
    INPUT:
    
        - t, a binary tree of size n
        
    OUTPUT: a binary tree of size n+1
    """
    if t.is_leaf():
        return BinaryTree([leaf,leaf])
    c = [t.left(),t.right()]
    i = random.randint(0,1)
    c[i] = random_grow(c[i])
    return BinaryTree(c)

def random_binary_tree(n):
    """
    Return a random binary tree of size n
    """
    t = leaf
    for i in range(n):
        t = random_grow(t)
    return t

random_binary_tree(10)

"""
Explanation: Voici une fonction qui calcule un arbre binaire aléatoire. On se demande si chaque arbre est obenu avec une probabilité uniforme.
Exécutez les cellules ci-dessous puis déterminez expérimentalment si la distribution de probabilité est uniforme.
End of explanation
"""


assert BinaryTree([[leaf,leaf], leaf]).height() == 2
assert BinaryTree([leaf,[leaf, leaf]]).height() == 2
assert BinaryTree([[leaf,leaf], [leaf,leaf]]).height() == 2
assert BinaryTree([[leaf,[leaf,leaf]], [leaf,leaf]]).height() == 3

"""
Explanation: La hauteur d'un arbre se calcule récursivement : pour une feuille, la hauteur est 0, sinon c'est le max de la hauteur des fils +1. 
Rajoutez une méthode height à la classe des arbres binaires et vérifiez son fonctionnement avec les tests suivants.
End of explanation
"""


