# Ce fichier contient (au moins) cinq erreurs.
# Instructions:
#  - tester jusqu'à atteindre 100% de couverture;
#  - corriger les bugs;"
#  - envoyer le diff ou le dépôt git par email."""
import hypothesis
from hypothesis import given, settings
from hypothesis.strategies import  integers, lists

class BinHeap:
    #structure de tas binaires d'entiers
    def __init__(self):
        #initialise un tas binaire d'entiers avec un element 0
        self.heapList = [0]
        self.currentSize = 1#taille de la liste heapList (invariant)

    def percUp(self,i):
        #upward percolation until 0 reached or father is bigger
        while i // 2 > 0 and self.heapList[i] < self.heapList[i // 2]:
             tmp = self.heapList[i // 2]
             self.heapList[i // 2] = self.heapList[i]
             self.heapList[i] = tmp
             i //= 2

    def insert(self,k):
        #inserting a new value into the heap
        self.heapList.append(k)
        self.percUp(self.currentSize)
        self.currentSize = self.currentSize + 1

    def percDown(self,i):
        while (i * 2) < self.currentSize:#while I have a child
            mc = self.minChild(i)#mc is the index of the smallest
            if self.heapList[i] > self.heapList[mc]:
                tmp = self.heapList[i]
                self.heapList[i] = self.heapList[mc]
                self.heapList[mc] = tmp
            i = mc

    def minChild(self,i):
        if i * 2 >= self.currentSize or i == 0:
            print("No Child. None is returned.")
            return 
        if i * 2 + 1 >= self.currentSize:
            return i * 2
        else:
            if self.heapList[i*2] < self.heapList[i*2+1]:
                return i * 2
            else:
                return i * 2 + 1

    def delMin(self):
        try:
            rval = self.heapList[1]
        except IndexError:
            print("Empty heap. Nothing is changed. None is returned.")
            return
        
        self.currentSize = self.currentSize - 1
        self.heapList[1] = self.heapList[self.currentSize]
        self.heapList.pop()
        self.percDown(1)
        return rval

    def buildHeap(self,alist):
        #creates a whole heap from a list, by percolating all its elements
        i = 1
        self.currentSize = len(alist) + 1# + 1
        self.heapList = [0] + alist # enlever le [:]
        while (i < self.currentSize):
            self.percUp(i)
            i += 1


def assert_isheaplist(x,val,lon,HL):
    assert ((x * 2 + 1 > lon) or (x * 2 + 1 == lon and HL[2*x] >= val) or (HL[2*x] >= val and HL[2*x+1] >= val))

def assert_goodheap(tau,lon):
    for x in range(1,lon):
        assert_isheaplist(x,tau.heapList[x],tau.currentSize,tau.heapList)
    
def test_init():
    tau = BinHeap()
    assert tau.heapList == [0]
    assert tau.currentSize == 1

@given(integers())
@settings(max_examples=100)
def test_percup(integer):
    gamma = [0,1,3,2,9,99,2,3,10,9,103,102,3,2,3,3]
    tau = BinHeap()
    tau.currentsize = 16
    tau.heapList = gamma[:]
    tau.percUp(15)
    assert tau.heapList == gamma[:]
    tau.heapList[15] = 2
    tau.percUp(15)
    print(tau.heapList)
    assert tau.heapList == [0,1,3,2,9,99,2,2,10,9,103,102,3,2,3,3] 
    assert tau.currentsize == 16
    tau.heapList.append(8)
    tau.currentsize = 17
    tau.percUp(16)
    assert tau.heapList == [0,1,3,2,8,99,2,2,9,9,103,102,3,2,3,3,10]
    
    tau.heapList.append(integer)
    tau.currentsize = 18
    tau.percUp(17)
    assert tau.heapList[17] >= tau.heapList[8]
    assert tau.heapList[8] >= tau.heapList[4]
    
@given(lists(elements=integers()))
@settings(max_examples=1000)
def test_build(L):
    tau = BinHeap()
    tau.buildHeap(L)
    assert tau.currentSize == len(L) + 1
    assert sorted(tau.heapList) == sorted(L+[0])
    assert_goodheap(tau,len(L)+1)
    #for x in range(1,len(L) + 1):
    #    assert_isheaplist(x,tau.heapList[x],tau.currentSize,tau.heapList)
    
@given(lists(elements=integers()),integers())
@settings(max_examples=1000)
def test_insert(L,i):
    tau = BinHeap()
    tau.buildHeap(L)
    tau.insert(i)
    assert_goodheap(tau,len(L)+1)
    
@given(lists(elements=integers()),integers())
@settings(max_examples=100)
def test_percDown(L,i):
    tau = BinHeap()
    L += [10]
    tau.buildHeap(L)
    tau.heapList[1] = i
    tau.percDown(1)
    for x in range(1,len(L) + 1):
        for _ in range(len(L)):
            tau.percDown(x)
    #then we test that we got a well-ordered heap
    assert_goodheap(tau,len(L)+1)

    
@given(lists(elements=integers()))
@settings(max_examples=400,deadline=None)
def test_delmin(L):
    L += [10]
    tau = BinHeap()
    assert tau.delMin() is None
    tau.buildHeap(L)
    #print(L)
    #print("sorted",sorted(L),"\n")
    #print("TAU ", tau.heapList,"\n")
    assert tau.delMin() == min(L)
    
@given(lists(elements=integers()),integers())
@settings(max_examples=400)
def test_minChild(L,i):
    tau = BinHeap()
    assert tau.minChild(abs(i)) is None
    tau.buildHeap(2*L+[0,1])
    assert tau.minChild(len(L)+1) is not None

@given(lists(elements=integers()),lists(elements=integers()))
@settings(max_examples=400,deadline=None)
def test_general(L,K):
    tau = BinHeap()
    tau.buildHeap(L)#tas construit avec L
    for k in K:tau.insert(k)#on rajoute les elements de K
    assert_goodheap(tau,tau.currentSize)
    
    x = []
    while tau.currentSize > 1:x.append(tau.delMin())#on retire tous les elements
    assert x == sorted(L + K)#verifie qu'on a bien le minimum avec delmin
    assert tau.delMin() is None
    
    x = []
    tau.buildHeap(K)
    for l in L:#teste si 1 suite d'insertion/ suppression maintient la structure
        tau.delMin()
        tau.insert(l)
    assert_goodheap(tau,tau.currentSize)
[((88, 1, 88, 27), 'hypothesis.settings', 'settings', (), '', False, 'from hypothesis import given, settings\n'), ((113, 1, 113, 28), 'hypothesis.settings', 'settings', (), '', False, 'from hypothesis import given, settings\n'), ((124, 1, 124, 28), 'hypothesis.settings', 'settings', (), '', False, 'from hypothesis import given, settings\n'), ((132, 1, 132, 27), 'hypothesis.settings', 'settings', (), '', False, 'from hypothesis import given, settings\n'), ((147, 1, 147, 41), 'hypothesis.settings', 'settings', (), '', False, 'from hypothesis import given, settings\n'), ((159, 1, 159, 27), 'hypothesis.settings', 'settings', (), '', False, 'from hypothesis import given, settings\n'), ((167, 1, 167, 41), 'hypothesis.settings', 'settings', (), '', False, 'from hypothesis import given, settings\n'), ((87, 7, 87, 17), 'hypothesis.strategies.integers', 'integers', ({}, {}), '()', False, 'from hypothesis.strategies import integers, lists\n'), ((123, 34, 123, 44), 'hypothesis.strategies.integers', 'integers', ({}, {}), '()', False, 'from hypothesis.strategies import integers, lists\n'), ((131, 34, 131, 44), 'hypothesis.strategies.integers', 'integers', ({}, {}), '()', False, 'from hypothesis.strategies import integers, lists\n'), ((158, 34, 158, 44), 'hypothesis.strategies.integers', 'integers', ({}, {}), '()', False, 'from hypothesis.strategies import integers, lists\n'), ((112, 22, 112, 32), 'hypothesis.strategies.integers', 'integers', ({}, {}), '()', False, 'from hypothesis.strategies import integers, lists\n'), ((123, 22, 123, 32), 'hypothesis.strategies.integers', 'integers', ({}, {}), '()', False, 'from hypothesis.strategies import integers, lists\n'), ((131, 22, 131, 32), 'hypothesis.strategies.integers', 'integers', ({}, {}), '()', False, 'from hypothesis.strategies import integers, lists\n'), ((146, 22, 146, 32), 'hypothesis.strategies.integers', 'integers', ({}, {}), '()', False, 'from hypothesis.strategies import integers, lists\n'), ((158, 22, 158, 32), 'hypothesis.strategies.integers', 'integers', ({}, {}), '()', False, 'from hypothesis.strategies import integers, lists\n'), ((166, 22, 166, 32), 'hypothesis.strategies.integers', 'integers', ({}, {}), '()', False, 'from hypothesis.strategies import integers, lists\n'), ((166, 49, 166, 59), 'hypothesis.strategies.integers', 'integers', ({}, {}), '()', False, 'from hypothesis.strategies import integers, lists\n')]