class File:
    def __init__(self):
        self.elements = []
    
    def enfiler(self, element):
        self.elements.append(element)
    
    def defiler(self):
        if not self.est_vide():
            return self.elements.pop(0)
        else:
            raise IndexError("La file est vide.")
    
    def est_vide(self):
        return len(self.elements) == 0

class Reseau:
    def __init__(self, adresse, masque):
        self.adresse = adresse
        self.masque = masque
        self.machines = {}
        self.file = File()
        
    def connexion(self, file):
        adresse = self.generer_adresse()
        self.machines[adresse] = file
        return adresse
    
    def generer_adresse(self):
        ip = [0, 0, 0, 0]
        range_ip = [0, 0, 0, 0]
        for i in range(4):
            ip[i] = self.adresse[i] & self.masque[i]
            if self.masque[i] != 255:
                range_ip[i] = 255 - self.masque[i]
        ip = self.incrementer(ip)
        while tuple(ip) in self.machines:
            ip = self.incrementer(ip)
        return tuple(ip)
    
    @staticmethod
    def incrementer(ip):
        for i in range(3, -1, -1):
            ip[i] += 1
            if ip[i] <= 255:
                return ip
            else:
                ip[i] = 0
    
    def diffuser(self):
        while not self.file.est_vide():
            paquet = self.file.defiler()
            orig, donnees = paquet
            for m in self.machines:
                if m != orig:
                    self.machines[m].enfiler(paquet)

class Interface:
    def __init__(self, reseau):
        self.sortie = reseau.file
        self.file = File()
        self.adresse = reseau.connexion(self.file)
        self.masque = reseau.masque

class Routeur:
    def __init__(self, nom):
        self.nom = nom
        self.interfaces = []
        self.table = {}

    def branchement(self, reseau):
        k = len(self.interfaces)
        self.table[reseau.adresse] = (k, None, 0)
        self.interfaces.append(Interface(reseau))
        
    def m_a_j(self, passerelle, i_interf, vecteurs):
        a_ete_modif = False
        for adresse, d in vecteurs:
            if adresse not in self.table or d+1 < self.table[adresse][2]:
                self.table[adresse] = (i_interf,
                passerelle, d+1)
                a_ete_modif = True
        if a_ete_modif:
            self.envoyer_vecteurs(i_interf)
        
    def vecteurs(self, i):
        res = []
        for adresse in self.table:
            i_interf, passerelle, dist = self.table[adresse]
            if i_interf != i:
                res.append((adresse, dist))
        return res
    
    def envoyer_vecteurs(self, i_interf):
        for i in range(len(self.interfaces)):
            if i != i_interf:
                adresse = self.interfaces[i].adresse
                v = self.vecteurs(i)
                paquet = (adresse, v)
                self.interfaces[i].sortie.enfiler(paquet)

    def traitement(self):
        for i in range(len(self.interfaces)):
            file = self.interfaces[i].file
            while not file.est_vide():
                orig, donnees = file.defiler()
                self.m_a_j(orig, i, donnees)


def meme_reseau(adresse1, adresse2, masque):
    for i in range(4):
        octet1 = adresse1[i] & masque[i]
        octet2 = adresse2[i] & masque[i]
        if octet1 != octet2:
            return False
    return True

routeur_m = Routeur("M")
routeur_m.table = {(172, 64, 0, 0): (1, None, 0), (172, 60, 0, 0): (0, (172, 58, 0, 2), 1), (192, 168, 47, 0): (0, (172, 58, 0, 2), 2), (172, 62, 0, 0): (0, (172, 58, 0, 2), 2)}

vecteurs = [((192, 168, 72, 0), 0), ((172, 62, 0, 0), 0), ((172, 64, 0, 0), 0), ((172, 60, 0, 0), 1), ((192, 168, 47, 0), 1)]

routeur_m.m_a_j((172, 64, 0, 2), 1, vecteurs)
print(routeur_m.table)


# Exemple de la figure 1

routeurR1 = Routeur("R1")
routeurR2 = Routeur("R2")
routeurR3 = Routeur("R3")

reseauPC1 = Reseau((192, 168, 20, 0), (255, 255, 255, 0))
reseauR1R2 = Reseau((172, 24, 0, 0), (255, 255, 255, 252))
reseauR2R3 = Reseau((172, 24, 1, 0), (255, 255, 255, 252))
reseauPC2 = Reseau((192, 168, 40, 0), (255, 255, 255, 0))

routeurR1.branchement(reseauPC1)
routeurR1.branchement(reseauR1R2)
routeurR2.branchement(reseauR1R2)
routeurR3.branchement(reseauR2R3)
routeurR2.branchement(reseauR2R3)
routeurR3.branchement(reseauPC2)

routeurs = [routeurR1, routeurR2, routeurR3]
reseaux = [reseauPC1, reseauR1R2, reseauR2R3, reseauPC2]

for routeur in routeurs:
    routeur.envoyer_vecteurs(-1)

continuer = True
while continuer:
    continuer = False
    for reseau in reseaux:
        reseau.diffuser()
    for routeur in routeurs:
        routeur.traitement()
    for reseau in reseaux:
        if not reseau.file.est_vide():
            continuer = True
    print("tour")

for routeur in routeurs:
    print(f"{routeur.nom}: {routeur.table}")