import math
import random
import unittest

from TD_Arbres.Arbre import ABR


def random_dichotomic_list(n: int) -> list:
    random_lst = [random.random() for _ in range(n)]
    random_lst.sort()
    remaining_lst = [random_lst]
    final_lst = []

    while remaining_lst:
        lst = remaining_lst.pop()
        if lst:
            middle = len(lst) // 2
            final_lst += [lst[middle]]
            if middle != 0:
                remaining_lst.append(lst[:middle])
            if len(lst) > middle:
                remaining_lst.append(lst[middle + 1:])

    assert (len(final_lst) == n)
    return final_lst


def random_liste_triee(n: int) -> tuple[list, ABR]:
    random_lst = [random.random() for _ in range(n)]
    arbre = ABR()
    for v in random_lst:
        arbre.insert(v)

    random_lst.sort()
    return random_lst, arbre


def ABR_to_list(arbre: ABR) -> list:
    """
    Convertit un objet de type `ABR` en `list` Python
    :param arbre: la `ABR` à convertir
    :return: la `list`
    """

    lst = []
    if arbre is None:
        return None
    else:
        if arbre._value is None:
            return lst
        else:
            abr_gauche = ABR_to_list(arbre._l)
            if abr_gauche is not None:
                lst = abr_gauche

            lst += [arbre._value]

            abr_droite = ABR_to_list(arbre._r)
            if abr_droite is not None:
                lst += abr_droite

    if lst != sorted(lst):
        print(arbre)
        print(lst)
    return lst


class TestABR(unittest.TestCase):

    @unittest.skipIf(not hasattr(ABR, 'insert'), "Il manque la méthode ABR.insert()")
    def test_ABR_insert(self):
        for _ in range(1000):
            n = random.randint(1, 20)
            random_list = [random.randint(0, 2 * n) for _ in range(n)]
            collection_triee = ABR()

            for i in random_list:
                collection_triee.insert(i)

            liste_finale = ABR_to_list(collection_triee)
            random_list.sort()
            self.assertEqual(liste_finale, random_list, f"La liste n'est pas triée")

    @unittest.skipIf(not hasattr(ABR, 'hauteur'), "Il manque la méthode ABR.hauteur()")
    def test_ABR_hauteur(self):
        collection_triee = ABR()
        self.assertEqual(collection_triee.hauteur(), 0, "La hauteur de l'arbre vide devrait être 0")

        collection_triee.insert(0)
        self.assertEqual(collection_triee.hauteur(), 0, "La hauteur d'une feuille devrait être égal à 0")

        # Test insertion de façon triée
        for _ in range(1000):
            collection_triee = ABR()
            t = [random.random() for _ in range(random.randint(0, 10))]
            t.sort()
            for e in t:
                collection_triee.insert(e)
            self.assertEqual(collection_triee.hauteur(), max(0, len(t) - 1),
                             f'La liste suivante devrait donner un arbre de hauteur {len(t)} : {t}')

        # Test insertion de façon triée inverse
        for _ in range(1000):
            collection_triee = ABR()
            t = [random.random() for _ in range(random.randint(0, 10))]
            t.sort(reverse=True)
            for e in t:
                collection_triee.insert(e)
            self.assertEqual(collection_triee.hauteur(), max(0, len(t) - 1),
                             f'La liste suivante devrait donner un arbre de hauteur {len(t)} : {t}')

        # Test insertion optimale
        for _ in range(1000):
            collection_triee = ABR()
            t = random_dichotomic_list(random.randint(1, 100))
            for e in t:
                collection_triee.insert(e)

            self.assertAlmostEqual(collection_triee.hauteur(), math.log2(len(t)), None,
                                   f'La liste suivante devrait donner un arbre de hauteur {round(math.log2(len(t)), 0)} : {t}',
                                   1)

    @unittest.skipIf(not hasattr(ABR, 'nbNoeuds'), "Il manque la méthode ABR.nbNoeuds()")
    def test_ABR_nbNoeuds(self):
        for _ in range(1000):
            n = random.randint(1, 200)
            random_list = [random.randint(0, 2 * n) for _ in range(n)]
            collection_triee = ABR()

            for i in random_list:
                collection_triee.insert(i)

            self.assertEqual(collection_triee.nbNoeuds(), n,
                             f"Le nombre de noeuds devrait être égal à {n} pour la liste {random_list}")

    @unittest.skipIf(not hasattr(ABR, 'contains'), "Il manque la méthode ABR.contains()")
    def test_ABR_contains(self):
        n = 50
        random_list_in = [random.random() for _ in range(n)]
        random_list_out = [random.random() + 1 for _ in range(n)]
        collection_triee = ABR()

        for i in random_list_in:
            collection_triee.insert(i)

        liste_finale = ABR_to_list(collection_triee)
        random_list = random_list_out + random_list_in
        random.shuffle(random_list)

        for e in random_list:
            self.assertEqual(e in random_list_in, collection_triee.contains(e),
                             f"La vérification de présence de {e} donne une mauvaise réponse pour {random_list_in}")
            liste_temp = ABR_to_list(collection_triee)
            self.assertEqual(liste_temp, liste_finale, f'ListeTriee.contains() ne devrait pas modifier la liste')

    @unittest.skipIf(not hasattr(ABR, 'delete'), "Il manque la méthode ABR.delete()")
    def test_ABR_delete(self):
        for _ in range(100):
            n = random.randint(1, 20)
            t, collection_triee = random_liste_triee(n)
            liste_copie = [i for i in t]
            random.shuffle(liste_copie)

            self.assertRaises(RuntimeError, collection_triee.delete, n)

            liste_reduite = None
            for i in liste_copie:
                collection_triee.delete(i)
                del (t[t.index(i)])
                liste_reduite = ABR_to_list(collection_triee)
                self.assertEqual(t, liste_reduite, f"La liste n'est pas triée ou l'élément {i} n'a pas été supprimé {collection_triee}")

            self.assertEqual(t, [])
            self.assertEqual(liste_reduite, [])
            self.assertRaises(RuntimeError, collection_triee.delete, random.randint(1, 20))


if __name__ == '__main__':
    unittest.main(verbosity=2)