# 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)
[((2854, 2880), 'hypothesis.settings', 'settings', ([], {'max_examples': '(100)'}), '(max_examples=100)\n', (2862, 2880), False, 'from hypothesis import given, settings\n'), ((3612, 3639), 'hypothesis.settings', 'settings', ([], {'max_examples': '(1000)'}), '(max_examples=1000)\n', (3620, 3639), False, 'from hypothesis import given, settings\n'), ((3986, 4013), 'hypothesis.settings', 'settings', ([], {'max_examples': '(1000)'}), '(max_examples=1000)\n', (3994, 4013), False, 'from hypothesis import given, settings\n'), ((4181, 4207), 'hypothesis.settings', 'settings', ([], {'max_examples': '(100)'}), '(max_examples=100)\n', (4189, 4207), False, 'from hypothesis import given, settings\n'), ((4551, 4592), 'hypothesis.settings', 'settings', ([], {'max_examples': '(400)', 'deadline': 'None'}), '(max_examples=400, deadline=None)\n', (4559, 4592), False, 'from hypothesis import given, settings\n'), ((4873, 4899), 'hypothesis.settings', 'settings', ([], {'max_examples': '(400)'}), '(max_examples=400)\n', (4881, 4899), False, 'from hypothesis import given, settings\n'), ((5123, 5164), 'hypothesis.settings', 'settings', ([], {'max_examples': '(400)', 'deadline': 'None'}), '(max_examples=400, deadline=None)\n', (5131, 5164), False, 'from hypothesis import given, settings\n'), ((2841, 2851), 'hypothesis.strategies.integers', 'integers', ([], {}), '()\n', (2849, 2851), False, 'from hypothesis.strategies import integers, lists\n'), ((3973, 3983), 'hypothesis.strategies.integers', 'integers', ([], {}), '()\n', (3981, 3983), False, 'from hypothesis.strategies import integers, lists\n'), ((4168, 4178), 'hypothesis.strategies.integers', 'integers', ([], {}), '()\n', (4176, 4178), False, 'from hypothesis.strategies import integers, lists\n'), ((4860, 4870), 'hypothesis.strategies.integers', 'integers', ([], {}), '()\n', (4868, 4870), False, 'from hypothesis.strategies import integers, lists\n'), ((3598, 3608), 'hypothesis.strategies.integers', 'integers', ([], {}), '()\n', (3606, 3608), False, 'from hypothesis.strategies import integers, lists\n'), ((3961, 3971), 'hypothesis.strategies.integers', 'integers', ([], {}), '()\n', (3969, 3971), False, 'from hypothesis.strategies import integers, lists\n'), ((4156, 4166), 'hypothesis.strategies.integers', 'integers', ([], {}), '()\n', (4164, 4166), False, 'from hypothesis.strategies import integers, lists\n'), ((4537, 4547), 'hypothesis.strategies.integers', 'integers', ([], {}), '()\n', (4545, 4547), False, 'from hypothesis.strategies import integers, lists\n'), ((4848, 4858), 'hypothesis.strategies.integers', 'integers', ([], {}), '()\n', (4856, 4858), False, 'from hypothesis.strategies import integers, lists\n'), ((5082, 5092), 'hypothesis.strategies.integers', 'integers', ([], {}), '()\n', (5090, 5092), False, 'from hypothesis.strategies import integers, lists\n'), ((5109, 5119), 'hypothesis.strategies.integers', 'integers', ([], {}), '()\n', (5117, 5119), False, 'from hypothesis.strategies import integers, lists\n')]