#! -*- coding: utf-8 -*-

from collections import deque

class Tournee:
    
    def __init__(self, client, distances, demandes, capacite_max=12):
        self.id = client  # le client initial sert d'identifiant pour la tournée
        self.dist = distances
        self.demandes = demandes
        self.limite = capacite_max
        self.clients = deque([client])
        self.ptc = demandes[client]
        
    def ajout(self, client, gauche=False):
        """Ajoute le client à la file à double entrée des clients de la tournée
        si gauche vaut True, l'ajout se fait sur l'extrémité gauche, elle se fait
        à droite sinon
        """
        if gauche:
            self.clients.appendleft(client)
        else:
            self.clients.append(client)
        self.ptc += self.demandes[client]
                    
    def distance(self):
        """calcule la distance totale (en km) de la tournée"""
        clients = self.clients
        dist = self.dist
        km = dist[0][clients[0]]
        for i in range(1, len(clients)):
            km += dist[clients[i-1]][clients[i]]
        km += dist[clients[-1]][0]
        return km
    
    def extremite(self, client):
        """renvoie 0 si le client est en tête de la tournée -1 s'il est dernier
        et None sinon
        """
        if self.clients[0] == client:
            return 0
        elif self.clients[-1] == client:
            return -1
    
    def points_4a_4b(self, autre_tournee, deux_clients):
        """Renvoie un couple parmi (0, 0), (0, -1) (-1, 0) (-1, -1)
        si les contraintes 4a et 4b de l'algo de Clarke et Wright sont
        vérifiées, None sinon
        """
        if self.id != autre_tournee.id:
            i, j = deux_clients
            for u, v in ((i, j), (j, i)):
                position_u, position_v = self.extremite(u), autre_tournee.extremite(v)
                if position_u is not None and position_v is not None:
                    return position_u, position_v
    
    def fusionnable(self, autre_tournee, deux_clients):
        """une des méthodes de la question 6 : renvoie un couple ou None"""
        positions = self.points_4a_4b(autre_tournee, deux_clients)
        if positions is not None and self.ptc + autre_tournee.ptc <= self.limite:
            return positions
        
    def fusion(self, autre_tournee, deux_clients):
        """renvoie True et réalise la fuion si elle est possible entre self et 
        autre_tournee via les deux clients ; False sinon
        """
        positions = self.fusionnable(autre_tournee, deux_clients)
        if positions is not None:
            p1, p2 = positions
            if p2 == -1:
                autre_tournee.clients.reverse()
            for c in autre_tournee.clients:
                self.ajout(c, gauche=p1 == 0)
            return True
        return False
    
    def affiche(self):
        tournee = ' '.join(str(c) for c in self.clients)
        print(f'tournée 0 {tournee} 0, chargement {self.ptc}')


# La partie algo de Clarke et Wright

def quelle_tournee(d_tournees, client):
    for tid in d_tournees:
        tournee = d_tournees[tid]
        if client in tournee.clients:
            return tid, tournee
    return None, None

def clarke_wright(dist, demandes, capacite=12):
    nb_clients = len(demandes)
    tournees = {c: Tournee(c, dist, demandes, capacite) for c in range(1, nb_clients)}
    sav = savings(dist)
    sorted_savings = sorted(((sav[i][j], i, j) for i in range(len(sav)) for j in range(i+1, len(sav))), reverse=True)
    fini = False
    while not fini:
        fini = True
        for _, i, j in sorted_savings:
            id_de_i, tournee_de_i = quelle_tournee(tournees, i)
            id_de_j, tournee_de_j = quelle_tournee(tournees, j)
            if tournee_de_i is not None and tournee_de_j is not None\
                and tournee_de_i.fusion(tournee_de_j, (i, j)):
                    del tournees[id_de_j]
                    fini = False
    return tournees