from math import floor,sqrt

class ObjetSolide:
    def __init__(self,indice):
        self.indice = indice
        self.position = [0,0,0]
        self.min = [-0.5,-0.5,-0.5]
        self.max = [0.5,0.5,0.5]
        self.cellules_coupees = set()
    def set_position(self,p):
        for k in range(3):
            tr = p[k]-self.position[k]
            self.min[k] += tr
            self.max[k] += tr
            self.position[k] = p[k] 
    def set_boite_contenante(self,min,max):
        self.min = min
        self.max = max
    def bornes_cellules(self,delta):
        return [int(floor(self.min[0]/delta[0])),int(floor(self.max[0]/delta[0])),int(floor(self.min[1]/delta[1])),int(floor(self.max[1]/delta[1])),int(floor(self.min[2]/delta[2])),int(floor(self.max[2]/delta[2]))]
    def get_cellules_coupees(self):
        return self.cellules_coupees
    def set_cellules_coupees(self,cellules_coupees):
        self.cellules_coupees = cellules_coupees
    def set_position_collision(self,p,tau):
        self.position_collision = p
        self.instant_collision = tau 
    def valider_position_collision(self):
        self.set_position(self.position_collision)
    def print_cellules_coupees(self):
        for c in self.cellules_coupees:
            print(c)
        
class Cellule:
    def __init__(self,indices):
        self.indices = indices
        self.objets_coupes = set()
    def ajouter_objet(self,indice_objet):
        self.objets_coupes.add(indice_objet)
        return len(self.objets_coupes)
    def enlever_objet(self,indice_objet):
        self.objets_coupes.remove(indice_objet)
        return len(self.objets_coupes)
    def print_objets(self):
        for o in self.objets_coupes:
            print(o)
             
class Pavage:
    def __init__(self,liste_objets,delta,bords,longueurs,periodiques):
        self.liste_objets = liste_objets
        self.delta = delta
        self.bords = bords
        self.periodiques = periodiques
        self.longueurs = longueurs
        self.dict_cellules = {}
            
    def placer_objet_cellule(self,indice_objet,indices_cellule):
        if indices_cellule in self.dict_cellules:
            cellule = self.dict_cellules[indices_cellule]
            cellule.ajouter_objet(indice_objet)
        else:
            cellule = Cellule(indices_cellule)
            self.dict_cellules[indices_cellule] = cellule
            cellule.ajouter_objet(indice_objet)
            
              
    def enlever_objet_cellule(self,indice_objet,indices_cellules):
        if indices_cellules in self.dict_cellules:
            cellule = self.dict_cellules[indices_cellules]
            if cellule.enlever_objet(indice_objet)==0:
                del self.dict_cellules[indices_cellules]
              
    def print_cellules(self):
        for i in self.dict_cellules:
            indices = self.dict_cellules[i].indices
            print("Cellule (%d,%d,%d)"%(indices[0],indices[1],indices[2]))
            self.dict_cellules[i].print_objets()
              
    def deplacer_objet(self,indice_objet,position):
        objet = self.liste_objets[indice_objet]
        anciennes_cellules_coupees = objet.get_cellules_coupees()
        objet.set_position(position)
        cellules_coupees = set()
        bornes = objet.bornes_cellules(self.delta)
        i = [0,0,0]
        pos = position
        for i[0] in range(bornes[0],bornes[1]+1):
            for i[1] in range(bornes[2],bornes[3]+1):
                for i[2] in range(bornes[4],bornes[5]+1):
                    for axe in range(3):
                        if self.bords[axe]:
                            if self.periodiques[axe]:
                                if i[axe] < 0:
                                    i[axe] = self.longueurs[axe]-1
                                    pos[axe] += self.delta*self.longueurs[axe]
                                elif i[axe] > self.longueurs[axe]:
                                    i[axe] = 0
                                    pos[axe] -= self.delta*self.longueurs[axe]
                    cellules_coupees.add((i[0],i[1],i[2]))
        objet.set_position(pos)
        objet.set_cellules_coupees(cellules_coupees)
        nouvelles_cellules = cellules_coupees.difference(anciennes_cellules_coupees)
        for c in nouvelles_cellules:
            self.placer_objet_cellule(indice_objet,c)
        cellules_quittees = anciennes_cellules_coupees.difference(cellules_coupees)
        for c in cellules_quittees:
            self.enlever_objet_cellule(indice_objet,c)
                    
              
    def chercher_collisions(self,detecter_collision,parametres):
        paires_objets = []
        for cellule in self.dict_cellules.values():
            for i1 in cellule.objets_coupes:
                for i2 in cellule.objets_coupes:
                    if i1!=i2:
                        if ((i1,i2) not in paires_objets) and ((i2,i1) not in paires_objets):
                            paires_objets.append((i1,i2))
        collisions = []
        n = 0
        for paire in paires_objets:
            tau = detecter_collision(self.liste_objets[paire[0]],self.liste_objets[paire[1]],parametres)
            if tau >= 0:
                if n==0:
                    collisions.append([paire,tau])
                    n+=1
                else:
                    k1=0
                    k2=n
                    while k1!=k2:
                        k=int((k1+k2)/2)
                        tau0 = collisions[k][1]
                        if tau>tau0:
                            k1 = k
                        else:
                            k2 = k
                    collisions.insert(k2,[paire,tau])
                    n+=1
        liste_collisions = []
        liste_objets_collision = []
        for col in collisions:
            i1 = col[0][0]
            i2 = col[0][1]
            if (not i1 in liste_objets_collision) and (not i2 in liste_objets_collision):
                liste_objets_collision.append(i1)
                liste_objets_collision.append(i2)
                liste_collisions.append(col)
        return [liste_objets_collision,liste_collisions]