#We simulate the parallel algorithm with priority
import random
import math

#The principal variables are defined here
max_load = 2
#rap is the constant between the number of balls and the number of bins, nBalls = rap*nBills
rap = 10
n = 1000000
#Balls[i]=j means that the ball i is in the bin j (if j is -1 then i hasn't commited)
Balls = range(int(rap*n))
#Bins[i] is the load of the bin i
Bins = range(n)
#Bins_round[i] is the list of the balls that have sent a message to bin i during the round simulated
bins_round = range(n)
#Balls_round[i] is the list of bins that have answered to the ball i during the round simulated
balls_round = range(int(rap*n))
#An useful list
l = range(n)


#It puts k in all the cases of the list l
def place(k,l):
        for i in range(len(l)):
                l[i] = k

#It allows to begin a new simulation
def remise_zero():              
        place(-1,Balls)
        place(0,Bins)

#It begins a simulation by defining the different lists according to the number of balls
def change_n(k):
        global n
        global Balls
        global Bins
        global bins_round
        global balls_round
        global l
        n = k
        l = range(n)
        Balls = range(int(rap*n))
        Bins = range(n)
        bins_round = range(n)
        balls_round = range(int(rap*n))
        l = range(n)

#This function simulates a round of the algorithm with priority
#nb_balls is the number of balls left
#Current_ball lists the balls that are still here : we have nb_balls = len(current_balls)
#nb_c is the number of messages sent per round
def round(nb_balls,current_balls,nb_c):
        #Answers[b] counts the bumber of answers that b has done during this round
        answers = range(n)
        place(0,answers)
        for p in range(nb_c):
                #Here we simulate what happens to the messages of priority p
                #For this priority, the choices hasn't been made so far
                place([],balls_round)
                place([],bins_round)
                #Each ball chooses one bin for its message of priority p
                for i in range(nb_balls):
                        choice_i = random.choice(l)
                        #We add the ball i to bins_round[choice_i]
                        bins_round[choice_i] = bins_round[choice_i] + [current_balls[i]]
                #Each bin answers to a certain number of messages
                for i in range(n):
                        #max_i is the number of answer to messages of priority p that the ball i can do
                        max_i = min(max_load-Bins[i]-answers[i],len(bins_round[i]))
                        #Balls_i lists the balls that the bin i answered to
                        balls_i = random.sample(bins_round[i],max_i)
                        for j in balls_i:
                                #We add the bin i to the list of the ball that j can commit into
                                balls_round[j] = balls_round[j] + [i]
                #Each ball commits if it can
                for i in range(int(rap*n)):
                        #If it can commit and it hasn't commited so far then it does
                        if len(balls_round[i]) !=  0 and Balls[i] == -1:
                                choice_commit = random.choice(balls_round[i])
                                Balls[i] = choice_commit
                                Bins[choice_commit] = Bins[choice_commit] + 1
                        else:
                                #The number of answer that the bin b can do has to be decreased either by incrementing Bins[b] or by increasing answer[b]
                                for b in (balls_round[i]):
                                        answers[b] = answers[b]+1

#It sumulates one time the algorithm
def simulation():
        global max_load
        current_balls = range(int(rap*n))
        remise_zero()
        nb_balls = int(n*rap)
        nb_rounds = 0
        #Here we choose the first parameter : the number of messages during the first round
        nb_c = 1
        #Here is the second : the max_load during the first round
        max_load = 8
        while nb_rounds < 3:
                print(nb_rounds)
                round(nb_balls,current_balls,nb_c)
                #Current_balls are the non-commited balls
                current_balls = [b for b in range(int(rap*n)) if Balls[b] == -1]
                nb_balls = len(current_balls)
                nb_rounds = nb_rounds+1
                #Parameters for the second round
                if nb_rounds == 1:
                        max_load = 10
                        nb_c = 3
                #Parameter for the third round
                if nb_rounds == 2:
                        max_load = 13
                        nb_c = 5
                print(nb_balls)
        return(nb_balls)

#Allow to repeat simulations and get an average number of what returns simulations.
#Simulation can easily be changed to return the number of bins with a certain load, the number of remaining balls after 1,2 or three rounds.
def nb_moy(essais):
        nb_balls_moy = 0.
        for i in range(essais):
                remise_zero()
                nb_balls_moy = nb_balls_moy + (float(simulation()))/(float(essais))     
        print(nb_balls_moy)


nb_moy(10)

#Si 2 rounds, L1=10, L2=15,nb_c1 = 1, nb_c2 = 2, 35.1 balles sur les 10^7 en moyenne.
#Si 2 rounds, L1=15, L2=15,nb_c1 = 1, nb_c2 = 2, 813.4 balles sur les 10^7 en moyenne.
#Si 3 rounds, L=13, nb_c1 = 1, nb_c2 = 2, nb_c3 = 5, 18.5 balles