/*
Copyright 2012-2014 Samuel Gesche

This file is part of the Greek Reuse Toolkit.

The Greek Reuse Toolkit is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

The Greek Reuse Toolkit is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with the Greek Reuse Toolkit.  If not, see <http://www.gnu.org/licenses/>.
*/

package fr.cnrs.liris.drim.grt.proc.recherche;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import fr.cnrs.liris.drim.grt.modele.Citation;
import fr.cnrs.liris.drim.grt.modele.Coordonnee;
import fr.cnrs.liris.drim.grt.modele.Lemme;
import fr.cnrs.liris.drim.grt.modele.OrdreStrict;
import fr.cnrs.liris.drim.grt.modele.Passage;
import fr.cnrs.liris.drim.grt.modele.Terme;
import fr.cnrs.liris.drim.grt.modele.exceptions.ListeStatistiqueNonInitialiseeException;
import fr.cnrs.liris.drim.grt.modele.listes.ExpressionsEntropiques;
import fr.cnrs.liris.drim.grt.modele.listes.LemmesEntropiques;
import fr.cnrs.liris.drim.grt.modele.listes.LemmesStatistiquementVides;
import fr.cnrs.liris.drim.grt.proc.Processus;
import fr.cnrs.liris.drim.grt.proc.parsers.PassageType;
import fr.cnrs.liris.drim.grt.proc.parsers.Temps;
import fr.cnrs.liris.drim.grt.proc.similarite.AnalyseurSSpace;
import fr.cnrs.liris.drim.grt.proc.similarite.AnalyseurSpectral;
import fr.cnrs.liris.drim.grt.proc.similarite.DistanceStatisticoSemantique;

/**
 *
 * @author Sam
 */
public class RechercheNLexes implements Processus, Recherche {
    
    private double avancement;
    private String statut = "";
    private String logExecution = "";
    private long momentDebut = 0;
    private long momentFin = 0;
    
    private PassageType source;
    private PassageType citeur;
    private boolean intradocumentaire;
    
    private int ordreCompte;
    private int traitementTermes;
    private int tolerance;
    private double seuil = 0.0;
    private int motsVides;
    private int expressionsVides;
    private int seuilFusion = 0;
    private int nbMotsMaxCitation;
    
    private AnalyseurSpectral analyseurSpectral;
    private AnalyseurSSpace analyseurSSpace;
    
    private int mesureSimilarite;
    private int parametreSimilarite = 0;
    private double seuilEgalite = 1.0;
    
    private int seuilDegrossissage = 100000;
    
    private int tailleFenetre;
    
    private OrdreStrict granulariteSource = OrdreStrict.getInstance(OrdreStrict.MOTS);
    private OrdreStrict granulariteCiteur = OrdreStrict.getInstance(OrdreStrict.MOTS);
    
    /**
     * Initialise une recherche par n-lexes.
     * @param source le texte cité
     * @param citeur le texte qui a cité (ou pas)
     * @param granulariteSource le niveau de structure auquel s'arrêter dans le texte source
     * @param granulariteCiteur le niveau de structure auquel s'arrêter dans le texte citeur 
     */
    public RechercheNLexes(PassageType source, PassageType citeur, OrdreStrict granulariteSource, OrdreStrict granulariteCiteur) {
        if(source.getType() != PassageType.PASSAGE_BIBLIQUE && 
                source.getType() != PassageType.PASSAGE_PATRISTIQUE && 
                source.getType() != PassageType.PASSAGE_PHILON) {
            throw new IllegalArgumentException("Type de passage source non reconnu : " + source.getType());
        }
        if(citeur.getType() != PassageType.PASSAGE_BIBLIQUE && 
                citeur.getType() != PassageType.PASSAGE_PATRISTIQUE && 
                citeur.getType() != PassageType.PASSAGE_PHILON) {
            throw new IllegalArgumentException("Type de passage citant non reconnu : " + citeur.getType());
        }
        this.source = source;
        this.citeur = citeur;
        this.granulariteSource = granulariteSource;
        this.granulariteCiteur = granulariteCiteur;
        
        intradocumentaire = false;
        
        ordreCompte = Recherche.L_ORDRE_DES_MOTS_COMPTE;
        traitementTermes = Recherche.TERMES_BRUTS;
        tolerance = Recherche.CORRESPONDANCE_STRICTE;
        motsVides = Recherche.TEXTE_AVEC_MOTS_VIDES;
        mesureSimilarite = Recherche.SIMILARITE_EXACTE;
        nbMotsMaxCitation = Integer.MAX_VALUE;
        
        analyseurSpectral = new AnalyseurSpectral();
        analyseurSSpace = new AnalyseurSSpace();
        
        avancement = 0.0;
    }
    
    @Override
    public void setSourceEtCiteurIdentiques(boolean identiques) {
        intradocumentaire = identiques;
    }

    @Override
    public void setTraitementTermes(int TERMES_QQCH) {
        traitementTermes = TERMES_QQCH;
    }

    @Override
    public void setImportanceOrdreMots(int L_ORDRE_DES_MOTS_QQCH) {
        ordreCompte = L_ORDRE_DES_MOTS_QQCH;
    }

    @Override
    public void setToleranceCorrespondance(int CORRESPONDANCE_QQCH, double seuil) {
        tolerance = CORRESPONDANCE_QQCH;
        this.seuil = seuil;
    }

    @Override
    public void setFiltrageMotsVides(int TEXTE_QQCH) {
        motsVides = TEXTE_QQCH;
    }

    @Override
    public void setFiltrageExpressionsVides(int FILTRAGE_QQCH) {
        expressionsVides = FILTRAGE_QQCH;
    }

    @Override
    public void setMultiCitation(int CITATIONS_QQCH) {
        throw new UnsupportedOperationException("Not supported yet.");
    }

    @Override
    public void setSeuilFusion(int nbMotsDifferents) {
        this.seuilFusion = nbMotsDifferents;
    }
    
    @Override
    public void setSimilarite(int SIMILARITE_QQCH, int parametre, double seuilEgalite) {
        this.mesureSimilarite = SIMILARITE_QQCH;
        this.parametreSimilarite = parametre;
        this.seuilEgalite = seuilEgalite;
    }
    
    public void setAnalyseur(AnalyseurSpectral analyseur) {
        this.analyseurSpectral = analyseur;
    }
    
    public void setAnalyseurSSpace(AnalyseurSSpace analyseurSSpace) {
        this.analyseurSSpace = analyseurSSpace;
    }
    
    public void setNbMotsMaxParCitation(int max) {
        this.nbMotsMaxCitation = max;
    }
    
    public void setTailleFenetre(int tailleFenetre) {
        this.tailleFenetre = tailleFenetre;
    }
    
    /**
     * Cherche des citations par n-lexes dans le texte.
     * La méthode utilisée ici est celle des n-lexes : seront recherchées et renvoyées 
     * des suites de n termes communs aux deux textes.
     * @return la liste des textes communs trouvés
     * @throws fr.cnrs.liris.drim.grt.modele.exceptions.ListeStatistiqueNonInitialiseeException
     */
    public Citation[] chercheCitations() throws ListeStatistiqueNonInitialiseeException {
        ArrayList<Citation> resultat = new ArrayList<>();
        
        // 1. Lister les n-lexes des documents source et citant
        long tps = System.currentTimeMillis();
        momentDebut = tps;
        avancement = 0.00; statut = "1a. lecture du document source";
        Passage[] nLexesSource;
        Passage[] nLexesCiteur;
        if(motsVides == Recherche.TEXTE_AVEC_MOTS_VIDES) {
            nLexesSource = source.getPassage().getNLexes(tailleFenetre);
            avancement = 0.002; statut = "1b. lecture du document citant";
            nLexesCiteur = citeur.getPassage().getNLexes(tailleFenetre);
            avancement = 0.005;
        } else if(motsVides == Recherche.TEXTE_SANS_MOTS_VIDES) {
            nLexesSource = source.getPassage().getNLexesSansMotsVides(tailleFenetre);
            avancement = 0.002; statut = "1b. lecture du document citant";
            nLexesCiteur = citeur.getPassage().getNLexesSansMotsVides(tailleFenetre);
            avancement = 0.005;
        } else {
            nLexesSource = source.getPassage().getNLexesSansMotsStatistiquementVides(tailleFenetre);
            avancement = 0.002; statut = "1b. lecture du document citant";
            nLexesCiteur = citeur.getPassage().getNLexesSansMotsStatistiquementVides(tailleFenetre);
            avancement = 0.005;
        }
        //System.err.println("Etape 1   : " + Temps.getTexte(System.currentTimeMillis() - tps, 15));
        logExecution = logExecution + "Etape 1   : " + Temps.getTexte(System.currentTimeMillis() - tps, 15) + "\n";
        //System.err.println("n-lexes   : " + nLexesCiteur.length);
        logExecution = logExecution + "n-lexes   : " + nLexesCiteur.length + "\n";
        tps = System.currentTimeMillis();
        
        // 2a. Indexer tous les termes source pour retrouver rapidement 
        // dans quel n-lexe se trouve un terme donné
        // o(n) si on considère la taille des n-lexes négligeable 
        // par rapport à celle du texte
        Map<Terme, Set<Passage>> indexMotsSource = new HashMap<>();
        Map<Passage, Set<Passage>> grappesSource = new HashMap<>();
        Map<Terme, Set<Passage>> indexSource = new HashMap<>();
        Set<Passage> indexVidesSource = new HashSet<>();
        for(int a=0; a<nLexesSource.length; a++) {
            avancement = 0.005+0.005*a/nLexesSource.length; statut = "2a. indexation des termes du document source ("+(a+1)+"/"+nLexesSource.length+")";
            Passage courant = nLexesSource[a];
            if(expressionsVides == Recherche.FILTRAGE_SANS_LEMMES_NI_EXPRESSIONS_VIDES) {
                if(ExpressionsEntropiques.contientTexte(courant) || LemmesEntropiques.constitueLaTotaliteDe(courant)) {
                    indexVidesSource.add(courant);
                }
            } else if(expressionsVides == Recherche.FILTRAGE_SANS_LEMMES_STATISTIQUEMENT_VIDES) {
                if(LemmesStatistiquementVides.constitueLaTotaliteDe(courant)) {
                    indexVidesSource.add(courant);
                }
            }
            Passage[] mots = courant.getSousPassages();
            for(Passage mot: mots) {
                Terme terme = mot.getContenu();
                if(traitementTermes == Recherche.TERMES_LEMMATISES) {
                    terme = getLemmeOpti(terme);
                } else if(traitementTermes == Recherche.TERMES_NORMALISES) {
                    terme = getNormOpti(terme);
                }
                if(indexSource.containsKey(terme)) {
                    indexSource.get(terme).add(courant);
                } else {
                    Set<Passage> nlleListe = new HashSet<>();
                    nlleListe.add(courant);
                    indexSource.put(terme, nlleListe);
                }
                if(indexMotsSource.containsKey(terme)) {
                    indexMotsSource.get(terme).add(mot);
                } else {
                    Set<Passage> nlleListe = new HashSet<>();
                    nlleListe.add(mot);
                    indexMotsSource.put(terme, nlleListe);
                }
                if(grappesSource.containsKey(mot)) {
                    grappesSource.get(mot).add(courant);
                } else {
                    Set<Passage> nlleListe = new HashSet<>();
                    nlleListe.add(courant);
                    grappesSource.put(mot, nlleListe);
                }
            }
        }
        
        // 2b. Indexer tous les termes citants pour retrouver rapidement 
        // dans quel n-lexe se trouve un terme donné
        // o(n) si on considère la taille des n-lexes négligeable 
        // par rapport à celle du texte
        Map<Terme, Set<Passage>> indexMotsCiteur = new HashMap<>();
        Map<Passage, Set<Passage>> grappesCiteur = new HashMap<>();
        Map<Terme, Set<Passage>> indexCiteur = new HashMap<>();
        Set<Passage> indexVidesCiteur = new HashSet<>();
        for(int a=0; a<nLexesCiteur.length; a++) {
            avancement = 0.010+0.005*a/nLexesCiteur.length; statut = "2b. indexation des termes du document citant ("+(a+1)+"/"+nLexesCiteur.length+")";
            Passage courant = nLexesCiteur[a];
            if(expressionsVides == Recherche.FILTRAGE_SANS_LEMMES_NI_EXPRESSIONS_VIDES) {
                if(ExpressionsEntropiques.contientTexte(courant)) {
                    indexVidesCiteur.add(courant);
                } else if(LemmesEntropiques.constitueLaTotaliteDe(courant)) {
                    indexVidesCiteur.add(courant);
                }
            } else if(expressionsVides == Recherche.FILTRAGE_SANS_LEMMES_STATISTIQUEMENT_VIDES) {
                if(LemmesStatistiquementVides.constitueLaTotaliteDe(courant)) {
                    indexVidesCiteur.add(courant);
                }
            }
            Passage[] mots = courant.getSousPassages();
            for(Passage mot: mots) {
                Terme terme = mot.getContenu();
                if(traitementTermes == Recherche.TERMES_LEMMATISES) {
                    terme = getLemmeOpti(terme);
                } else if(traitementTermes == Recherche.TERMES_NORMALISES) {
                    terme = getNormOpti(terme);
                }
                if(indexCiteur.containsKey(terme)) {
                    indexCiteur.get(terme).add(courant);
                } else {
                    Set<Passage> nlleListe = new HashSet<>();
                    nlleListe.add(courant);
                    indexCiteur.put(terme, nlleListe);
                }
                if(indexMotsCiteur.containsKey(terme)) {
                    indexMotsCiteur.get(terme).add(mot);
                } else {
                    Set<Passage> nlleListe = new HashSet<>();
                    nlleListe.add(mot);
                    indexMotsCiteur.put(terme, nlleListe);
                }
                if(grappesCiteur.containsKey(mot)) {
                    grappesCiteur.get(mot).add(courant);
                } else {
                    Set<Passage> nlleListe = new HashSet<>();
                    nlleListe.add(courant);
                    grappesCiteur.put(mot, nlleListe);
                }
            }
        }
        avancement = 0.015;
        //System.err.println("Etape 2   : " + Temps.getTexte(System.currentTimeMillis() - tps, 15));
        logExecution = logExecution + "Etape 2   : " + Temps.getTexte(System.currentTimeMillis() - tps, 15) + "\n";
        //System.err.println("Source : " + nLexesSource.length + " - " + indexVidesSource.size());
        //System.err.println("Citant : " + nLexesCiteur.length + " - " + indexVidesCiteur.size());
        tps = System.currentTimeMillis();
        
        // 3a. Si besoin est, préparer la mesure de similarité
        if(mesureSimilarite == Recherche.SIMILARITE_PAR_CO_OCCURRENCES) {
            statut = "3a. calcul de la matrice des similarités";
            analyseurSpectral.calculeDistance(parametreSimilarite, traitementTermes, AnalyseurSpectral.TERMES_TOUS_SAUFS_VIDES);
        } else if(mesureSimilarite == Recherche.SIMILARITE_LSA) {
            statut = "3a. Récupération de l'espace sémantique";
        }
        avancement = 0.015; // 0.10 font partie de l'analyseurSpectral
        
        // 3b. Toujours si besoin est, lister pour chaque terme les termes 'suffisamment similaires'
        // (to do : permettre de faire varier la distance entre euclidienne/Manhattan)
        // Sinon, remplir simplement la liste par des identités
        Map<Terme, Set<Terme>> similarites = new HashMap<>();
        for(Terme t: indexSource.keySet()) {
            Set<Terme> s = new HashSet<>();
            s.add(t);
            similarites.put(t, s);
        }
        for(Terme t: indexCiteur.keySet()) {
            Set<Terme> s = new HashSet<>();
            s.add(t);
            similarites.put(t, s);
        }
        if(mesureSimilarite == Recherche.SIMILARITE_PAR_CO_OCCURRENCES) {
            ArrayList<Terme> liste = new ArrayList<>(similarites.keySet());
            //int max = 0;
            for(int a=0; a<liste.size(); a++) {
                avancement = 0.015+0.085*a/liste.size(); statut = "3b. calcul des similarités ("+(a+1)+"/"+liste.size()+")";
                Terme t = liste.get(a);
                try {
                    similarites.get(t).addAll(Arrays.asList(analyseurSpectral.getDistance().getTermesSimilaires(
                            t, seuilEgalite, DistanceStatisticoSemantique.DISTANCE_EUCLIDIENNE)));
                    /*if(similarites.get(t).size()>max) {
                        max = similarites.get(t).size();
                        //System.err.println(t+" : "+max+" termes similaires");
                    }*/
                } catch(IllegalArgumentException iae) {
                    // Rien de spécial ; juste que le terme n'a pas été répertorié
                }
            }
        } else if(mesureSimilarite == Recherche.SIMILARITE_LSA) {
            ArrayList<Terme> liste = new ArrayList<>(similarites.keySet());
            //int max = 0;
            for(int a=0; a<liste.size(); a++) {
                avancement = 0.015+0.085*a/liste.size(); statut = "3b. calcul des similarités ("+(a+1)+"/"+liste.size()+")";
                Terme t = liste.get(a);
                try {
                    similarites.get(t).addAll(Arrays.asList(analyseurSSpace.getTermesSimilaires(t, seuilEgalite)));
                } catch(IllegalArgumentException iae) {
                    // Rien de spécial ; juste que le terme n'a pas été répertorié
                }
            }
        }
        //System.err.println("Etape 3   : " + Temps.getTexte(System.currentTimeMillis() - tps, 15));
        logExecution = logExecution + "Etape 3   : " + Temps.getTexte(System.currentTimeMillis() - tps, 15) + "\n";
        tps = System.currentTimeMillis();
        
        //System.err.println(nLexesCiteur.length + " n-lexes à tester");
        
        // 4. Pour chaque terme de chaque n-lexe du citeur, lister les 
        // n-lexes source contenant ce terme ou un terme similaire
        // 
        // Optimisation de temps : il faut toujours au moins un terme identique 
        // pour être listé, même avec la mesure de similarité (sinon, risque de 
        // ramener tout l'index)
        // 
        // Conserver ceux qui sont à une distance inférieure au seuil de tolérance
        // Entre o(n) et o(n²) suivant la proportion de n-lexes à vérifier
        for(int a=0; a<nLexesCiteur.length; a++) {
            avancement = 0.100+0.600*a/nLexesCiteur.length; statut = "4. recherche des correspondances ("+(a+1)+"/"+nLexesCiteur.length+" - " + resultat.size() + " trouvées)";
            //System.err.println("Recherche des correspondances ("+(a+1)+"/"+nLexesCiteur.length+")");
            Passage peutEtreCiteur = nLexesCiteur[a];
            if(indexVidesCiteur.contains(peutEtreCiteur)) {
                // Inutile d'évaluer cette expression vide, de toute façon 
                // on la filtrerait plus tard
                continue;
            }
            Passage[] mots = peutEtreCiteur.getSousPassages();
            ArrayList<Passage> suspects0 = new ArrayList<>();
            Set<Passage> suspects;
            if(tolerance == Recherche.CORRESPONDANCE_STRICTE) {
                // grande optimisation dans ce cas-là : on ne retient que les cas
                // où tous les termes sont communs (quelque soit l'ordre)
                Terme terme = mots[0].getContenu();
                if(traitementTermes == Recherche.TERMES_LEMMATISES) {
                    terme = getLemmeOpti(terme);
                } else if(traitementTermes == Recherche.TERMES_NORMALISES) {
                    terme = getNormOpti(terme);
                }
                //System.err.println("   " + similarites.get(terme).size() + " termes similaires trouvés");
                // Prise en compte de la similarité entre termes ; sans cette option, similarites ne doit contenir que le terme lui-même
                /*for(Terme termeSim: similarites.get(terme)) {*/
                if(indexSource.containsKey(terme)) {
                    suspects0.addAll(indexSource.get(terme));
                }
                /*}*/
                //System.err.println("   "+suspects0.size()+" passages correspondants trouvés");
                suspects = new HashSet<>(suspects0);
                for(int i=1; i<mots.length; i++) {
                    ArrayList<Passage> aRetenir0 = new ArrayList<>();
                    terme = mots[i].getContenu();
                    if(traitementTermes == Recherche.TERMES_LEMMATISES) {
                        terme = getLemmeOpti(terme);
                    } else if(traitementTermes == Recherche.TERMES_NORMALISES) {
                        terme = getNormOpti(terme);
                    }
                    for(Terme termeSim: similarites.get(terme)) {
                        if(indexSource.containsKey(termeSim)) {
                            aRetenir0.addAll(indexSource.get(termeSim));
                        }
                    }
                    // optimisation : une seule fois la contrainte d'unicité
                    Set<Passage> aRetenir = new HashSet<>(aRetenir0);
                    suspects.retainAll(aRetenir);
                }
                // Supprimer les passages situés au même endroit dans le cas où on a une recherche de citations intradocumentaire
                if(intradocumentaire) {
                    Set<Passage> suspectsBuffer = new HashSet<>(suspects);
                    for(Passage prospect: suspects) {
                        if(Math.abs(
                                source.getPassage().getIndexMot(prospect.getSousPassages()[0]) - 
                                citeur.getPassage().getIndexMot(peutEtreCiteur.getSousPassages()[0])) <= tailleFenetre) {
                            suspectsBuffer.remove(prospect);
                        }
                    }
                    suspects.clear();
                    suspects.addAll(suspectsBuffer);
                }
            } else {
                for (Passage mot : mots) {
                    Terme terme = mot.getContenu();
                    if(traitementTermes == Recherche.TERMES_LEMMATISES) {
                        terme = getLemmeOpti(terme);
                    } else if(traitementTermes == Recherche.TERMES_NORMALISES) {
                        terme = getNormOpti(terme);
                    }
                    //System.err.println("   " + similarites.get(terme).size() + " termes similaires trouvés");
                    for(Terme termeSim: similarites.get(terme)) {
                        if(indexSource.containsKey(termeSim)) {
                            suspects0.addAll(indexSource.get(termeSim));
                        }
                    }
                }
                suspects = new HashSet<>(suspects0);
            }
            //System.err.println("  " + suspects.size()+" passages restants à tester");
            ArrayList<Citation> citationsPossibles = new ArrayList<>();
            double ecartMinAuSeuil = tailleFenetre;
            for(Passage prospect: suspects) {
                if(indexVidesSource.contains(prospect)) {
                    // Inutile d'évaluer cette expression vide, de toute façon 
                    // on la filtrerait plus tard
                    continue;
                }
                // vérification de la distance
                boolean correspondant;
                int distance;
                double distanceSeuil;
                switch(tolerance) {
                    case Recherche.CORRESPONDANCE_STRICTE:
                        // pas d'optimisation dans ce cas-là (difficile pour pas grand-chose)
                        ecartMinAuSeuil = 0;
                        correspondant = isIdentique(prospect, peutEtreCiteur, similarites);
                        break;
                    case Recherche.CORRESPONDANCE_SEUILLEE_EN_VALEUR:
                        distance = getDistance(prospect, peutEtreCiteur, similarites);
                        distanceSeuil = seuil;
                        if(ecartMinAuSeuil > (distance - distanceSeuil)) {
                            ecartMinAuSeuil = (distance - distanceSeuil);
                        }
                        correspondant = (distance <= distanceSeuil);
                        break;
                    case Recherche.CORRESPONDANCE_SEUILLEE_EN_POURCENTAGE:
                    default:
                        distance = getDistance(prospect, peutEtreCiteur, similarites);
                        distanceSeuil = seuil * Math.max(prospect.getNbSousPassages(), peutEtreCiteur.getNbSousPassages());
                        if(ecartMinAuSeuil > (distance - distanceSeuil)) {
                            ecartMinAuSeuil = (distance - distanceSeuil);
                        }
                        correspondant = (distance <= distanceSeuil);
                }
                if(correspondant) {
                    // clonage des passages pour éviter de les modifier par référence ensuite ; 
                    // par contre, on garde les mots par référence, c'est essentiel
                    Passage src = new Passage("", new Passage[]{}, prospect.getSousPassagesAvecCoordonnees());
                    Passage cit = new Passage("", new Passage[]{}, peutEtreCiteur.getSousPassagesAvecCoordonnees());
                    citationsPossibles.add(new Citation(src, cit, "passage correspondant"));
                }
            }
            //System.err.println(" Restent  "+citationsPossibles.size()+" passages à tester");
            
            // Si l'intersection n'est pas vide, pour chaque membre, vérifier 
            // si l'ordre y est (à supposer que ça ait une importance)
            // o(n) sur un très petit ensemble (normalement)
            for(Citation citationPossible: citationsPossibles) {
                boolean validee = true;
                if(ordreCompte == Recherche.L_ORDRE_DES_MOTS_COMPTE) {
                    for(int i=0; i<citationPossible.getCiteur().getNbSousPassages(); i++) {
                        Terme tCiteur = citationPossible.getCiteur().getSousPassages()[i].getContenu();
                        if(traitementTermes == Recherche.TERMES_LEMMATISES) {
                            tCiteur = getLemmeOpti(tCiteur);
                        } else if(traitementTermes == Recherche.TERMES_NORMALISES) {
                            tCiteur = getNormOpti(tCiteur);
                        }
                        Terme tCite = citationPossible.getCite().getSousPassages()[i].getContenu();
                        if(traitementTermes == Recherche.TERMES_LEMMATISES) {
                            tCite = getLemmeOpti(tCite);
                        } else if(traitementTermes == Recherche.TERMES_NORMALISES) {
                            tCite = getNormOpti(tCite);
                        }
                        try {
                            if(!similarites.get(tCite).contains(tCiteur)) {
                                validee = false;
                                break;
                            }
                        }catch(NullPointerException npe) {
                            // Ne devrait pas arriver
                            Set<Terme> t = new HashSet<>();
                            t.add(tCite);
                            similarites.put(tCite, t);
                            if(!similarites.get(tCite).contains(tCiteur)) {
                                validee = false;
                                break;
                            }
                        }
                    }
                }
                if(validee) {
                    resultat.add(citationPossible);
                    /*//System.err.println("Citation stockée : taille " + 
                            citationPossible.getCite().getNbSousPassages()+"/"+
                            citationPossible.getCiteur().getNbSousPassages());*/
                }
                
            }
            //System.err.println(" Restent  "+resultat.size()+" passages");
                
            // Optimisation : si dans tous les cas étudiés la distance au 
            // seuil est d'au moins N, inutile de vérifier pour les N-1 
            // prochains n-lexes
            if(ecartMinAuSeuil >= 1.0) {
                a += (int)(Math.floor(ecartMinAuSeuil)) - 1;
            }
            
            // Optimisation : étapes 5 et 6 de dégrossissage en cas de grosse quantité de citations trouvées
            if(resultat.size() >= seuilDegrossissage) {
                if(expressionsVides == Recherche.FILTRAGE_SANS_LEMMES_NI_EXPRESSIONS_VIDES || 
                        expressionsVides == Recherche.FILTRAGE_SANS_LEMMES_STATISTIQUEMENT_VIDES) {
                    ArrayList<Citation> resultat2 = new ArrayList<>();
                    for (Citation c : resultat) {
                        if(!indexVidesSource.contains(c.getCite()) && !indexVidesCiteur.contains(c.getCiteur())) {
                            resultat2.add(c);
                        }
                    }
                    resultat.clear();
                    resultat.addAll(resultat2);
                }
            }
            if(resultat.size() >= seuilDegrossissage) {
                int precedentSize = resultat.size();
                int sauts = 10;
                for(int i=0; i<resultat.size(); i++) {
                    avancement = 0.100+0.700*a/nLexesCiteur.length; statut = "4. recherche des correspondances ("+(a+1)+"/"+nLexesCiteur.length+") - dégrossissage (" + (i+1) +"/"+resultat.size() + ")";
                    for(int j=i+1; j<resultat.size(); j++) {
            
                        Citation ci = resultat.get(resultat.size() - i - 1);
                        Citation cj = resultat.get(resultat.size() - j - 1);

                        int d0 = source.getPassage().getDistance(ci.getCite(), cj.getCite());
                        int d1 = citeur.getPassage().getDistance(ci.getCiteur(), cj.getCiteur());

                        if(d0 >= 0 && d0 <= seuilFusion && 
                                d1 >= 0 && d1 <= seuilFusion) {
                            // cj suit ci de près : suppression (on retrouvera cj à l'extension)
                            resultat.remove(cj);
                            j--;
                        }
                    }
                    // Pour éviter de repasser systématiquement les résultats valides quand on a dégrossi le reste
                    if(precedentSize == resultat.size()) {
                        sauts--;
                    } else {
                        sauts = 10;
                    }
                    if(sauts == 0) {
                        break;
                    }
                    precedentSize = resultat.size();
                }
                if(resultat.size() > seuilDegrossissage) {
                    seuilDegrossissage += 10000;
                }
            }
        }
        //System.err.println("Etape 4   : " + Temps.getTexte(System.currentTimeMillis() - tps, 15));
        logExecution = logExecution + "Etape 4   : " + Temps.getTexte(System.currentTimeMillis() - tps, 15) + "\n";
        //System.err.println("Citations : " + resultat.size());
        logExecution = logExecution + "Citations : " + resultat.size() + "\n";
        tps = System.currentTimeMillis();
        
        // 5. Supprimer les citations ne comportant que des expressions vides
        if(expressionsVides == Recherche.FILTRAGE_SANS_LEMMES_NI_EXPRESSIONS_VIDES || 
                expressionsVides == Recherche.FILTRAGE_SANS_LEMMES_STATISTIQUEMENT_VIDES) {
            ArrayList<Citation> resultat2 = new ArrayList<>();
            // Test : afficher si c'est une expression vide
            for(int i=0; i<resultat.size(); i++) {
                avancement = 0.700+0.005*i/resultat.size(); statut = "5. suppression des résultats vides ("+(i+1)+"/"+resultat.size()+")";
                Citation c = resultat.get(i);
                if(!indexVidesSource.contains(c.getCite()) && !indexVidesCiteur.contains(c.getCiteur())) {
                    resultat2.add(c);
                }
                /*
                 * Vieille formulation sans indexation
                //System.err.println("Etude de : "+new Texte(c.getCite()).getTexte());
                if(ExpressionsEntropiques.constitueLaTotaliteDe(c.getCite())) {
                    //System.err.println(" Expression entropique détectée : "+new Texte(c.getCite()).getTexte());
                } else if(ExpressionsEntropiques.constitueLaTotaliteDe(c.getCiteur())) {
                    //System.err.println(" Expression entropique détectée : "+new Texte(c.getCiteur()).getTexte());
                } else if(LemmesEntropiques.constitueLaTotaliteDe(c.getCite())) {
                    //System.err.println(" Lemmes entropique détectés : "+new Texte(c.getCite()).getTexte());
                } else if(LemmesEntropiques.constitueLaTotaliteDe(c.getCiteur())) {
                    //System.err.println(" Lemmes entropique détectés : "+new Texte(c.getCiteur()).getTexte());
                } else {
                    resultat2.add(c);
                }*/
            }
            resultat.clear();
            resultat.addAll(resultat2);
        }
        //System.err.println("Etape 5   : " + Temps.getTexte(System.currentTimeMillis() - tps, 15));
        logExecution = logExecution + "Etape 5   : " + Temps.getTexte(System.currentTimeMillis() - tps, 15) + "\n";
        //System.err.println("Reste     : " + resultat.size());
        logExecution = logExecution + "Reste     : " + resultat.size() + "\n";
        tps = System.currentTimeMillis();
        
        // 6. Filtrer les citations qui se chevauchent
        // Note : supprime les chevauchements, mais non transitif contrairement
        // à la fusion de la partie 8.
        // La fusion est impossible ici parce qu'elle affecte la structure
        // arborescente des passages et qu'on en a besoin en 7.
        /*for(int i=0; i<resultat.size(); i++) {
            avancement = 0.705+0.015*i/resultat.size(); statut = "6. filtrage des citations proches ("+(i+1)+"/"+resultat.size()+")";
            for(int j=i+1; j<resultat.size(); j++) {
                Citation ci = resultat.get(i);
                Citation cj = resultat.get(j);
                
                int d0 = source.getPassage().getDistance(ci.getCite(), cj.getCite());
                int d1 = citeur.getPassage().getDistance(ci.getCiteur(), cj.getCiteur());
                
                if(d0 >= 0 && d0 <= seuilFusion && 
                        d1 >= 0 && d1 <= seuilFusion) {
                    // cj suit ci de près : suppression (on retrouvera cj à l'extension)
                    resultat.remove(j);
                    j--;
                }
            }
        }*/
        //System.err.println("Etape 6   : " + Temps.getTexte(System.currentTimeMillis() - tps, 15));
        logExecution = logExecution + "Etape 6   : " + Temps.getTexte(System.currentTimeMillis() - tps, 15) + "\n";
        //System.err.println("Reste     : " + resultat.size());
        logExecution = logExecution + "Reste     : " + resultat.size() + "\n";
        tps = System.currentTimeMillis();
        
        
        // 7. Rechercher les limites des citations trouvées
        for(int a=0; a<resultat.size(); a++) {
            avancement = 0.720+0.010*a/resultat.size(); statut = "7. extension des citations ("+(a+1)+"/"+resultat.size()+")";
            Citation citation = resultat.get(a);
            Passage src = citation.getCite();
            Passage cit = citation.getCiteur();
            ArrayList<Passage> motsSrc;
            ArrayList<Passage> motsCit;
            //System.err.println("Citation à étudier : taille " + src.getNbSousPassages()+"/"+cit.getNbSousPassages());
            
            int aRajouter = 1;
            /*boolean commence = true;
            int depart = src.getNbSousPassages();
            int depart2 = cit.getNbSousPassages();
            System.err.print("\t");*/
            while(aRajouter>0) {
                /*if(!commence) {
                    if(aRajouter>1) {
                        commence = true;
                        System.err.print("\t(" + depart +"/" + depart2 + ") 1 p+s+ " + "(" + src.getNbSousPassages() + "/" + cit.getNbSousPassages() + ") " + aRajouter + " ");
                    }
                } else {
                    System.err.print("(" + src.getNbSousPassages() + "/" + cit.getNbSousPassages() + ") " + aRajouter + " ");
                }*/
                
                boolean precedentsOK = false;
                boolean suivantsOK = false;
                
                Map<Coordonnee, Passage> listeSrc = new HashMap<>();
                for(Coordonnee c: src.getSousPassagesAvecCoordonnees().keySet()) {
                    listeSrc.put(c, src.getSousPassagesAvecCoordonnees().get(c));
                }
                Map<Coordonnee, Passage> listeCit = new HashMap<>();
                for(Coordonnee c: cit.getSousPassagesAvecCoordonnees().keySet()) {
                    listeCit.put(c, cit.getSousPassagesAvecCoordonnees().get(c));
                }
                Passage testSrc = new Passage("", new Passage[]{}, listeSrc);
                Passage testCit = new Passage("", new Passage[]{}, listeCit);
                
                for(int i=0; i<aRajouter; i++) {
                    //System.err.println("  A présent : taille " + src.getNbSousPassages()+"/"+cit.getNbSousPassages());
                    motsSrc = new ArrayList<>(Arrays.asList(testSrc.getSousPassages()));
                    motsCit = new ArrayList<>(Arrays.asList(testCit.getSousPassages()));
                    Passage motPrecedentSrc;
                    Passage motPrecedentCit;
                    if(motsVides == Recherche.TEXTE_AVEC_MOTS_VIDES) {
                        motPrecedentSrc = source.getPassage().getMotPrecedent(motsSrc.get(0));
                        motPrecedentCit = citeur.getPassage().getMotPrecedent(motsCit.get(0));
                    } else if(motsVides == Recherche.TEXTE_SANS_MOTS_VIDES) {
                        motPrecedentSrc = source.getPassage().getMotNonVidePrecedent(motsSrc.get(0));
                        motPrecedentCit = citeur.getPassage().getMotNonVidePrecedent(motsCit.get(0));
                    } else  { // motsVides == Recherche.TEXTE_SANS_MOTS_STATISTIQUEMENT_VIDES)
                        motPrecedentSrc = source.getPassage().getMotNonStatistiquementVidePrecedent(motsSrc.get(0));
                        motPrecedentCit = citeur.getPassage().getMotNonStatistiquementVidePrecedent(motsCit.get(0));
                    }
                    if(motPrecedentSrc == null || motPrecedentCit == null) {
                        break;
                    }
                    testSrc.addSousPassage(testSrc.getSousCoordonneeMinimale().getPrecedente(), motPrecedentSrc);
                    testCit.addSousPassage(testCit.getSousCoordonneeMinimale().getPrecedente(), motPrecedentCit);
                }

                //System.err.println("  A présent : taille " + src.getNbSousPassages()+"/"+cit.getNbSousPassages());
                boolean correspondant;
                switch(tolerance) {
                    case Recherche.CORRESPONDANCE_STRICTE:
                        correspondant = isIdentique(testSrc, testCit, similarites);
                        break;
                    case Recherche.CORRESPONDANCE_SEUILLEE_EN_VALEUR:
                        correspondant = getDistance(testSrc, testCit, similarites) <= seuil;
                        break;
                    case Recherche.CORRESPONDANCE_SEUILLEE_EN_POURCENTAGE:
                    default:
                        correspondant = getDistance(testSrc, testCit, similarites) <= 
                                seuil * Math.max(testSrc.getNbSousPassages(), testCit.getNbSousPassages());
                }
                //System.err.println("  A présent : taille " + src.getNbSousPassages()+"/"+cit.getNbSousPassages());
                if(correspondant) {
                    for(int i=0; i<aRajouter; i++) {
                        motsSrc = new ArrayList<>(Arrays.asList(src.getSousPassages()));
                        motsCit = new ArrayList<>(Arrays.asList(cit.getSousPassages()));
                        Passage motPrecedentSrc;
                        Passage motPrecedentCit;
                        if(motsVides == Recherche.TEXTE_AVEC_MOTS_VIDES) {
                            motPrecedentSrc = source.getPassage().getMotPrecedent(motsSrc.get(0));
                            motPrecedentCit = citeur.getPassage().getMotPrecedent(motsCit.get(0));
                        } else if(motsVides == Recherche.TEXTE_SANS_MOTS_VIDES) {
                            motPrecedentSrc = source.getPassage().getMotNonVidePrecedent(motsSrc.get(0));
                            motPrecedentCit = citeur.getPassage().getMotNonVidePrecedent(motsCit.get(0));
                        } else { // motsVides == Recherche.TEXTE_SANS_MOTS_STATISTIQUEMENT_VIDES)
                            motPrecedentSrc = source.getPassage().getMotNonStatistiquementVidePrecedent(motsSrc.get(0));
                            motPrecedentCit = citeur.getPassage().getMotNonStatistiquementVidePrecedent(motsCit.get(0));
                        }
                        if(motPrecedentSrc == null || motPrecedentCit == null) {
                            break;
                        }
                        src.addSousPassage(src.getSousCoordonneeMinimale().getPrecedente(), motPrecedentSrc);
                        cit.addSousPassage(cit.getSousCoordonneeMinimale().getPrecedente(), motPrecedentCit);
                        precedentsOK = true;
                    }
                    //System.err.println(" Ajout avant : taille " + src.getNbSousPassages()+"/"+cit.getNbSousPassages());
                }
                /*if(commence && precedentsOK) {
                    System.err.print("p+");
                } else {
                    System.err.print("p-");
                }*/
                //trim(src, cit, tailleFenetre, similarites);
                //System.err.println(" A présent : taille " + src.getNbSousPassages()+"/"+cit.getNbSousPassages());

                listeSrc = new HashMap<>();
                for(Coordonnee c: src.getSousPassagesAvecCoordonnees().keySet()) {
                    listeSrc.put(c, src.getSousPassagesAvecCoordonnees().get(c));
                }
                listeCit = new HashMap<>();
                for(Coordonnee c: cit.getSousPassagesAvecCoordonnees().keySet()) {
                    listeCit.put(c, cit.getSousPassagesAvecCoordonnees().get(c));
                }
                testSrc = new Passage("", new Passage[]{}, listeSrc);
                testCit = new Passage("", new Passage[]{}, listeCit);
                
                for(int i=0; i<aRajouter; i++) {
                    motsSrc = new ArrayList<>(Arrays.asList(testSrc.getSousPassages()));
                    motsCit = new ArrayList<>(Arrays.asList(testCit.getSousPassages()));
                    Passage motSuivantSrc;
                    Passage motSuivantCit;
                    if(motsVides == Recherche.TEXTE_AVEC_MOTS_VIDES) {
                        motSuivantSrc = source.getPassage().getMotSuivant(motsSrc.get(motsSrc.size()-1));
                        motSuivantCit = citeur.getPassage().getMotSuivant(motsCit.get(motsCit.size()-1));
                    } else if(motsVides == Recherche.TEXTE_SANS_MOTS_VIDES) {
                        motSuivantSrc = source.getPassage().getMotNonVideSuivant(motsSrc.get(motsSrc.size()-1));
                        motSuivantCit = citeur.getPassage().getMotNonVideSuivant(motsCit.get(motsCit.size()-1));
                    } else { // motsVides == Recherche.TEXTE_SANS_MOTS_STATISTIQUEMENT_VIDES)
                        motSuivantSrc = source.getPassage().getMotNonStatistiquementVideSuivant(motsSrc.get(motsSrc.size()-1));
                        motSuivantCit = citeur.getPassage().getMotNonStatistiquementVideSuivant(motsCit.get(motsCit.size()-1));
                    }
                    if(motSuivantSrc == null || motSuivantCit == null) {
                        break;
                    }
                    testSrc.addSousPassage(testSrc.getSousCoordonneeMaximale().getSuivante(), motSuivantSrc);
                    testCit.addSousPassage(testCit.getSousCoordonneeMaximale().getSuivante(), motSuivantCit);
                }
                
                correspondant = false;
                switch(tolerance) {
                    case Recherche.CORRESPONDANCE_STRICTE:
                        correspondant = isIdentique(testSrc, testCit, similarites);
                        //System.err.println("["+correspondant+"] "+new Texte(testSrc).getTexte()+" -> "+new Texte(testCit).getTexte());
                        break;
                    case Recherche.CORRESPONDANCE_SEUILLEE_EN_VALEUR:
                        correspondant = getDistance(testSrc, testCit, similarites) <= seuil;
                        break;
                    case Recherche.CORRESPONDANCE_SEUILLEE_EN_POURCENTAGE:
                    default:
                        correspondant = getDistance(testSrc, testCit, similarites) <= 
                                seuil * Math.max(testSrc.getNbSousPassages(), testCit.getNbSousPassages());
                }
                if(correspondant) {
                    for(int i=0; i<aRajouter; i++) {
                        motsSrc = new ArrayList<>(Arrays.asList(src.getSousPassages()));
                        motsCit = new ArrayList<>(Arrays.asList(cit.getSousPassages()));
                        Passage motSuivantSrc;
                        Passage motSuivantCit;
                        if(motsVides == Recherche.TEXTE_AVEC_MOTS_VIDES) {
                            motSuivantSrc = source.getPassage().getMotSuivant(motsSrc.get(motsSrc.size()-1));
                            motSuivantCit = citeur.getPassage().getMotSuivant(motsCit.get(motsCit.size()-1));
                        } else if(motsVides == Recherche.TEXTE_SANS_MOTS_VIDES) {
                            motSuivantSrc = source.getPassage().getMotNonVideSuivant(motsSrc.get(motsSrc.size()-1));
                            motSuivantCit = citeur.getPassage().getMotNonVideSuivant(motsCit.get(motsCit.size()-1));
                        } else { // motsVides == Recherche.TEXTE_SANS_MOTS_STATISTIQUEMENT_VIDES)
                            motSuivantSrc = source.getPassage().getMotNonStatistiquementVideSuivant(motsSrc.get(motsSrc.size()-1));
                            motSuivantCit = citeur.getPassage().getMotNonStatistiquementVideSuivant(motsCit.get(motsCit.size()-1));
                        }
                        if(motSuivantSrc == null || motSuivantCit == null) {
                            break;
                        }
                        src.addSousPassage(src.getSousCoordonneeMaximale().getSuivante(), motSuivantSrc);
                        cit.addSousPassage(cit.getSousCoordonneeMaximale().getSuivante(), motSuivantCit);
                        suivantsOK = true;
                    }
                    //System.err.println(" Ajout après : taille " + src.getNbSousPassages()+"/"+cit.getNbSousPassages());
                }
                /*if(commence && suivantsOK) {
                    System.err.print("s+");
                } else {
                    System.err.print("s-");
                }*/
                //trim(src, cit, tailleFenetre, similarites);
                
                if(precedentsOK || suivantsOK) {
                    // On a réussi à en rajouter autant : essayons avec plus à la fois pour limiter le nombre de comparaisons
                    // Sans exagérer toutefois, la procédure devient vite très longue
                    int nbMotsCitation = src.getNbSousPassages();
                    int nbMotsMax = Math.min(nbMotsMaxCitation, Math.min(source.getPassage().getAllMots().length, citeur.getPassage().getAllMots().length));
                    aRajouter = Math.min(aRajouter * 2, nbMotsMax - nbMotsCitation);
                } else {
                    // On n'a pas réussi à en rajouter autant : essayons avec deux fois moins
                    aRajouter /= 2;
                }
            }
            trim(src, cit, tailleFenetre, similarites);
            //if(commence) System.err.println("(" + src.getNbSousPassages() + "/" + cit.getNbSousPassages() + ")");
            //System.err.println(" A présent : taille " + src.getNbSousPassages()+"/"+cit.getNbSousPassages());
        }
        //System.err.println("Etape 7   : " + Temps.getTexte(System.currentTimeMillis() - tps, 15));
        logExecution = logExecution + "Etape 7   : " + Temps.getTexte(System.currentTimeMillis() - tps, 15) + "\n";
        tps = System.currentTimeMillis();
        
        
        // 8. Fusionner les citations proches
        for(int i=0; i<resultat.size(); i++) {
            avancement = 0.730+0.150*i/resultat.size(); statut = "8. fusion des citations proches ("+(i+1)+"/"+resultat.size()+")";
            int nbFusions = Integer.MAX_VALUE;
            //long tps0 = System.currentTimeMillis(), tps1, no = 0;
            //System.err.println("Fusion des citations proches("+(i+1)+"/"+resultat.size()+")");
            while(nbFusions>0) {
                //no++;
                nbFusions = 0;
                for(int j=i+1; j<resultat.size(); j++) {
                    //tps1 = System.currentTimeMillis();
                    Citation ci = resultat.get(i);
                    Citation cj = resultat.get(j);
                    //System.err.println(" Citations du résultat " + (j+1) + "/" + resultat.size() + " récupérées en "+(System.currentTimeMillis()-tps1)+" ms");
                    //tps1 = System.currentTimeMillis();
                    int d0 = source.getPassage().getDistance(ci.getCite(), cj.getCite());
                    //System.err.println(" Distance 1 du résultat " + (j+1) + "/" + resultat.size() + " récupérée en "+(System.currentTimeMillis()-tps1)+" ms");
                    //tps1 = System.currentTimeMillis();
                    int d1 = citeur.getPassage().getDistance(ci.getCiteur(), cj.getCiteur());
                    //System.err.println(" Distance 2 du résultat " + (j+1) + "/" + resultat.size() + " récupérée en "+(System.currentTimeMillis()-tps1)+" ms");
                    //tps1 = System.currentTimeMillis();
                    if(d0 >= 0 && d0 <= seuilFusion && 
                            d1 >= 0 && d1 <= seuilFusion) {
                        // cj suit ci de près : fusion
                        /*System.err.println("Fusion des citations " + (i+1) + " et (anciennement) " + (j+1));
                        System.err.println(" " + ci.getCite().getNumerosCompletsSousPassages() + " vs " + cj.getCite().getNumerosCompletsSousPassages() + " : distance " + d0);
                        System.err.println(" " + ci.getCiteur().getNumerosCompletsSousPassages() + " vs " + cj.getCiteur().getNumerosCompletsSousPassages() + " : distance " + d1);*/
                        
                        ci.fusionneAvec(cj, "");
                        ci.dedoublonneEtTrie(citeur.getPassage(), source.getPassage());
                        
                        /*System.err.println("  Cité : " + ci.getCite().getAllMots().length + " mots");
                        for(int a=0; a<ci.getCite().getAllMots().length-1; a++) {
                            int dist = source.getPassage().getDistance(ci.getCite().getAllMots()[a], ci.getCite().getAllMots()[a+1]);
                            if(dist<=0) {
                                System.err.println("   /!\\ distance négative ou nulle (" + dist + " entre " + 
                                        ci.getCite().getAllMots()[a].getTexteCompletAvecRefs() + " et " + 
                                        ci.getCite().getAllMots()[a+1].getTexteCompletAvecRefs());
                            }
                        }
                        System.err.println("  Citant : " + ci.getCiteur().getAllMots().length + " mots");
                        for(int a=0; a<ci.getCiteur().getAllMots().length-1; a++) {
                            int dist = citeur.getPassage().getDistance(ci.getCiteur().getAllMots()[a], ci.getCiteur().getAllMots()[a+1]);
                            if(dist<=0) {
                                System.err.println("   /!\\ distance négative ou nulle (" + dist + " entre " + 
                                        ci.getCiteur().getAllMots()[a].getTexteCompletAvecRefs() + " et " + 
                                        ci.getCiteur().getAllMots()[a+1].getTexteCompletAvecRefs());
                            }
                        }*/
                        
                        
                        resultat.remove(cj);
                        nbFusions++;
                        //System.err.println(" Fusion effectuée en "+(System.currentTimeMillis()-tps1)+" ms");
                        break; // pour éviter les problèmes de gestion des indices
                    }
                }
                //System.err.println("=> Cycle " + no + " effectué en "+(System.currentTimeMillis()-tps0)+" ms");
                //tps0 = System.currentTimeMillis();
            }
        }
        //System.err.println("Etape 8   : " + Temps.getTexte(System.currentTimeMillis() - tps, 15));
        logExecution = logExecution + "Etape 8   : " + Temps.getTexte(System.currentTimeMillis() - tps, 15) + "\n";
        //System.err.println("Reste     : " + resultat.size());
        logExecution = logExecution + "Reste     : " + resultat.size() + "\n";
        tps = System.currentTimeMillis();
        
        
        // 9. Prendre les blocs complets
        ArrayList<Citation> citations = new ArrayList<>();
        for(int i=0; i<resultat.size(); i++) {
            avancement = 0.880+0.020*i/resultat.size(); statut = "9. extension aux blocs complets ("+(i+1)+"/"+resultat.size()+")";
            Citation res = resultat.get(i);
            Passage src = res.getCite();
            /*Passage src0 = src.getSousPassages()[0];
            Passage src1 = src.getSousPassages()[src.getNbSousPassages()-1];*/
            Passage srcFinal;
            /*String txtRefSource = References.toReference(
                        src0.getReferenceInitialeDans(source.getPassage()), 
                        src1.getReferenceInitialeDans(source.getPassage()),
                        source.getType());*/
            Passage frag = Passage.etend(src, granulariteSource);
            Map<Coordonnee, Passage> liste = new HashMap<>();
            for(int a=0; a<frag.getAllMots().length; a++) {
                liste.put(new Coordonnee(OrdreStrict.getInstance(OrdreStrict.MOTS), ""+(a+1)), frag.getAllMots()[a]);
            }
            srcFinal = new Passage("", new Passage[]{}, liste);
            //Reference refSource = References.parseReferenceBiblique(txtRefSource);
            //srcFinal = source.rassemblePassage(refSource);
            
            Passage cit = res.getCiteur();
            /*Passage cit0 = cit.getSousPassages()[0];
            Passage cit1 = cit.getSousPassages()[cit.getNbSousPassages()-1];*/
            Passage citFinal;
            /*String txtRefCiteur = References.toReference(
                        cit0.getReferenceInitialeDans(citeur.getPassage()), 
                        cit1.getReferenceInitialeDans(citeur.getPassage()),
                        citeur.getType());*/
            frag = Passage.etend(cit, granulariteCiteur);
            liste = new HashMap<>();
            for(int a=0; a<frag.getAllMots().length; a++) {
                liste.put(new Coordonnee(OrdreStrict.getInstance(OrdreStrict.MOTS), ""+(a+1)), frag.getAllMots()[a]);
            }
            citFinal = new Passage("", new Passage[]{}, liste);
            //Reference refCiteur = References.parseReferencePatristique(txtRefCiteur);
            //citFinal = citeur.rassemblePassage(refCiteur);
            
            
            // Dédoublonner en passant
            Citation citFinale = new Citation(srcFinal, citFinal, res.getArgumentaire());
            citations.add(citFinale);
        }
        avancement = 0.900 ; statut = "terminé";
        momentFin = System.currentTimeMillis();
        //System.err.println("Etape 9   : " + Temps.getTexte(System.currentTimeMillis() - tps, 15));
        logExecution = logExecution + "Etape 9   : " + Temps.getTexte(System.currentTimeMillis() - tps, 15) + "\n";
        //System.err.println("Au final  : " + citations.size() + "\n\n\n");
        logExecution = logExecution + "Au final  : " + citations.size();
        
        // Fini !
        Citation[] rapport = new Citation[citations.size()];
        citations.toArray(rapport);
        return rapport;
    }
    
    //private Map<Terme, Set<Terme>> saveSim;
    //private Map<Passage[], Integer> sauvegardesDistances = new HashMap<>();
    /**
     * Donne la distance en nombre de mots différents entre les deux passages 
     * proposés.
     * 
     * Si l'ordre compte, il s'agira de la distance d'édition (nombre de mots à 
     * insérer/supprimer/modifier pour passer de l'un à l'autre ; distance 
     * symétrique, la plus petite étant prise ; algorithme de Wagner-Fisher)
     * Si l'ordre ne compte pas, il s'agira du nombre de mots différents entre 
     * les deux passages
     * 
     * L'identité entre mots est effectuée par terme ou par lemme, et non par 
     * référence
     * 
     * @param p1 un passage
     * @param p2 un autre passage
     * @return la distance en nombre de mots
     */
    private int getDistance(Passage p1, Passage p2, Map<Terme, Set<Terme>> sim) {
        int distance;
        long tps = System.currentTimeMillis();
        /*if(sim == saveSim) {
            if(sauvegardesDistances.containsKey(new Passage[]{p1,p2})) {
                return sauvegardesDistances.get(new Passage[]{p1,p2});
            }
        } else {
            saveSim = sim;
            sauvegardesDistances.clear();
        }*/
        if(ordreCompte == Recherche.L_ORDRE_DES_MOTS_COMPTE) {
            // calculer la distance d'édition - o(n²)
            Passage[] sp1 = p1.getSousPassages();
            Terme[] t1 = new Terme[sp1.length];
            for(int i=0; i<t1.length; i++) {
                if(traitementTermes == Recherche.TERMES_LEMMATISES) {
                    t1[i] = getLemmeOpti(sp1[i].getContenu());
                } else if(traitementTermes == Recherche.TERMES_NORMALISES) {
                    t1[i] = getNormOpti(sp1[i].getContenu());
                } else {
                    t1[i] = sp1[i].getContenu();
                }
            }
            Passage[] sp2 = p2.getSousPassages();
            Terme[] t2 = new Terme[sp2.length];
            for(int i=0; i<t2.length; i++) {
                if(traitementTermes == Recherche.TERMES_LEMMATISES) {
                    t2[i] = getLemmeOpti(sp2[i].getContenu());
                } else if(traitementTermes == Recherche.TERMES_NORMALISES) {
                    t2[i] = getNormOpti(sp2[i].getContenu());
                } else {
                    t2[i] = sp2[i].getContenu();
                }
            }
            int[][] distances = new int[t1.length+1][t2.length+1];
            for(int i=0; i<t1.length+1; i++) {
                distances[i][0] = i;
            }
            for(int j=0; j<t2.length+1; j++) {
                distances[0][j] = j;
            }
            for(int j=1; j<=t2.length; j++) {
                for(int i=1; i<=t1.length; i++) {
                    Set<Terme> s1;
                    if(sim.containsKey(t1[i-1])) {
                        s1 = new HashSet<>(sim.get(t1[i-1]));
                    } else {
                        s1 = new HashSet<>();
                    }
                    Set<Terme> s2;
                    if(sim.containsKey(t2[j-1])) {
                        s2 = new HashSet<>(sim.get(t2[j-1]));
                    } else {
                        s2 = new HashSet<>();
                    }
                    s1.retainAll(s2);
                    //if(t1[i].equals(t2[j])) {
                    if(s1.size()>0) {
                        distances[i][j] = distances[i-1][j-1];
                    } else {
                        distances[i][j] = 1 + Math.min(Math.min(distances[i-1][j], 
                                distances[i][j-1]), distances[i-1][j-1]);
                    }
                }
            }
            distance = distances[t1.length][t2.length];
        } else {
            // Distance = taille max des ensembles - intersection des ensembles
            
            // Construction d'un ensemble de termes
            ArrayList<Terme> liste0 = new ArrayList<>();
            
            // Ajout des termes (ou lemmes) de p1
            for(Passage mot: p1.getSousPassages()) {
                if(traitementTermes == Recherche.TERMES_LEMMATISES) {
                    liste0.addAll(sim.get(getLemmeOpti(mot.getContenu())));
                } else if(traitementTermes == Recherche.TERMES_NORMALISES) {
                    liste0.addAll(sim.get(getNormOpti(mot.getContenu())));
                } else {
                    liste0.addAll(sim.get(mot.getContenu()));
                }
            }
            Set<Terme> liste = new HashSet<>(liste0);
            int taille = liste.size();
            
            // Construction d'un ensemble de termes
            ArrayList<Terme> liste2 = new ArrayList<>();
            
            // Ajout des termes (ou lemmes) de p1
            for(Passage mot: p2.getSousPassages()) {
                if(traitementTermes == Recherche.TERMES_LEMMATISES) {
                    liste2.addAll(sim.get(getLemmeOpti(mot.getContenu())));
                } else if(traitementTermes == Recherche.TERMES_NORMALISES) {
                    liste2.addAll(sim.get(getNormOpti(mot.getContenu())));
                } else {
                    liste2.addAll(sim.get(mot.getContenu()));
                }
            }
            Set<Terme> liste3 = new HashSet<>(liste2);
            int taille2 = liste3.size();
            
            liste.retainAll(liste3);
            
            distance = Math.max(taille, taille2) - liste.size();
        }
        //sauvegardesDistances.put(new Passage[]{p1,p2}, distance);
        //System.err.println("     -> Distance calculée en "+(System.currentTimeMillis()-tps)+" ms");
        return distance;
    }
    
    /**
     * Détermine si la distance est nulle entre les deux Passages proposés. 
     * Plus efficace que getDistance() == 0 dans le cas où l'ordre compte.
     * @param p1 un passage
     * @param p2 un autre passage
     * @return oui ou non
     */
    private boolean isIdentique(Passage p1, Passage p2, Map<Terme, Set<Terme>> sim) {
        return getDistance(p1, p2, sim) == 0;
/*        boolean resultat = true;
        //long tps = System.currentTimeMillis();
        if(p1.getNbSousPassages() != p2.getNbSousPassages()) { // ne devrait pas arriver
            resultat = false;
        } else {
            if(ordreCompte == Recherche.L_ORDRE_DES_MOTS_COMPTE) {
                Passage[] lp1 = p1.getSousPassages();
                Passage[] lp2 = p2.getSousPassages();
                for(int i=0; i<p1.getNbSousPassages(); i++) {
                    Terme t1 = lp1[i].getContenu();
                    Terme t2 = lp2[i].getContenu();
                    if(traitementTermes == Recherche.TERMES_LEMMATISES) {
                        t1 = getLemmeOpti(t1);
                    } else if(traitementTermes == Recherche.TERMES_NORMALISES) {
                        t1 = getNormOpti(t1);
                    }
                    if(traitementTermes == Recherche.TERMES_LEMMATISES) {
                        t2 = getLemmeOpti(t2);
                    } else if(traitementTermes == Recherche.TERMES_NORMALISES) {
                        t2 = getNormOpti(t2);
                    }
                    Set<Terme> s1 = new HashSet<>(sim.get(t1));
                    Set<Terme> s2 = new HashSet<>(sim.get(t2));
                    s1.retainAll(s2);
                    //if(!t1.equals(t2)) {
                    if(s1.isEmpty()) {
                        resultat = false;
                        break;
                    }
                }
            } else {
                return getDistance(p1, p2, sim) == 0;
            }
        }
        //System.err.println("     -> Identité calculée en "+(System.currentTimeMillis()-tps)+" ms");
        return resultat;*/
    }
    
    /**
     * Supprime d'un couple de passages tous les mots dont les termes sont 
     * différents quand ils sont aux extrémités des passages.
     * @param p1 un Passage contenant des mots
     * @param p2 un autre Passage avec le même nombre de mots
     * @param tailleMin la taille au-delà de laquelle il ne faut plus diminuer
     */
    private void trim(Passage p1, Passage p2, int tailleMin, Map<Terme, Set<Terme>> sim) {
        ArrayList<Passage> mots1 = new ArrayList<>(Arrays.asList(p1.getSousPassages()));
        ArrayList<Passage> mots2 = new ArrayList<>(Arrays.asList(p2.getSousPassages()));
        //System.err.println("  Trim : mots " + Arrays.toString(p1.getAllMots())+"/"+Arrays.toString(p2.getAllMots()));
        //System.err.println("  Trim : taille " + mots1.size()+"/"+mots2.size());
        boolean fini = false;
        while(!fini && mots1.size()>tailleMin) {
            Map<Coordonnee, Passage> mots1a = new HashMap<>();
            for(int i=0; i<mots1.size(); i++) {
                mots1a.put(new Coordonnee(OrdreStrict.getInstance(OrdreStrict.MOTS), ""+i), mots1.get(i));
            }
            Map<Coordonnee, Passage> mots2a = new HashMap<>();
            for(int i=0; i<mots2.size(); i++) {
                mots2a.put(new Coordonnee(OrdreStrict.getInstance(OrdreStrict.MOTS), ""+i), mots2.get(i));
            }
            Map<Coordonnee, Passage> mots1b = new HashMap<>();
            for(int i=1; i<mots1.size(); i++) {
                mots1b.put(new Coordonnee(OrdreStrict.getInstance(OrdreStrict.MOTS), ""+i), mots1.get(i));
            }
            Map<Coordonnee, Passage> mots2b = new HashMap<>();
            for(int i=1; i<mots2.size(); i++) {
                mots2b.put(new Coordonnee(OrdreStrict.getInstance(OrdreStrict.MOTS), ""+i), mots2.get(i));
            }
            Passage p1a = new Passage("", new Passage[]{}, mots1a);
            Passage p2a = new Passage("", new Passage[]{}, mots2a);
            Passage p1b = new Passage("", new Passage[]{}, mots1b);
            Passage p2b = new Passage("", new Passage[]{}, mots2b);
            int dista = getDistance(p1a, p2a, sim);
            int distb = getDistance(p1b, p2b, sim);
            //System.err.println("   distance en coupant le premier mot : "+dista+"->"+distb);
            if(dista <= distb) {
                fini = true;
            } else {
                //System.err.println("   Coupure avant - taille " + mots1.size()+"->"+(mots1.size()-1) + " (distance "+dista+"->"+distb+")");
                mots1.remove(0);
                mots2.remove(0);
            }
        }
        // Suppression des signes de ponctuation au début
        while(mots1.get(0).getContenu().estUneFinDePhrase() && mots2.get(0).getContenu().estUneFinDePhrase()) {
            //System.err.println("Suppression d'un signe de ponctuation initial");
            mots1.remove(0);
            mots2.remove(0);
        }
        fini = false;
        while(!fini && mots1.size()>tailleMin) {
            Map<Coordonnee, Passage> mots1a = new HashMap<>();
            for(int i=0; i<mots1.size(); i++) {
                mots1a.put(new Coordonnee(OrdreStrict.getInstance(OrdreStrict.MOTS), ""+i), mots1.get(i));
            }
            Map<Coordonnee, Passage> mots2a = new HashMap<>();
            for(int i=0; i<mots2.size(); i++) {
                mots2a.put(new Coordonnee(OrdreStrict.getInstance(OrdreStrict.MOTS), ""+i), mots2.get(i));
            }
            Map<Coordonnee, Passage> mots1b = new HashMap<>();
            for(int i=0; i<mots1.size()-1; i++) {
                mots1b.put(new Coordonnee(OrdreStrict.getInstance(OrdreStrict.MOTS), ""+i), mots1.get(i));
            }
            Map<Coordonnee, Passage> mots2b = new HashMap<>();
            for(int i=0; i<mots2.size()-1; i++) {
                mots2b.put(new Coordonnee(OrdreStrict.getInstance(OrdreStrict.MOTS), ""+i), mots2.get(i));
            }
            Passage p1a = new Passage("", new Passage[]{}, mots1a);
            Passage p2a = new Passage("", new Passage[]{}, mots2a);
            Passage p1b = new Passage("", new Passage[]{}, mots1b);
            Passage p2b = new Passage("", new Passage[]{}, mots2b);
            int dista = getDistance(p1a, p2a, sim);
            int distb = getDistance(p1b, p2b, sim);
            //System.err.println("   distance en coupant le dernier mot : "+dista+"->"+distb);
            if(dista <= distb) {
                fini = true;
            } else {
                //System.err.println("   Coupure après - taille " + mots1.size()+"->"+(mots1.size()-1) + " (distance "+dista+"->"+distb+")");
                mots1.remove(mots1.size()-1);
                mots2.remove(mots2.size()-1);
            }
        }
        Map<Coordonnee, Passage> lmots1 = new HashMap<>();
        for(int i=0; i<mots1.size(); i++) {
            lmots1.put(new Coordonnee(OrdreStrict.getInstance(OrdreStrict.MOTS), ""+i), mots1.get(i));
        }
        Map<Coordonnee, Passage> lmots2 = new HashMap<>();
        for(int i=0; i<mots2.size(); i++) {
            lmots2.put(new Coordonnee(OrdreStrict.getInstance(OrdreStrict.MOTS), ""+i), mots2.get(i));
        }
        p1.setSousPassages(lmots1);
        p2.setSousPassages(lmots2);
        //System.err.println("  Résultat : taille " + lmots1.keySet().size()+"/"+lmots2.keySet().size());
        //System.err.println("  Résultat : mots " + Arrays.toString(p1.getAllMots())+"/"+Arrays.toString(p2.getAllMots()));
    }
    
    Map<Terme, Lemme> lemmes = new HashMap<>();
    private Lemme getLemmeOpti(Terme t) {
        if(!lemmes.containsKey(t)) {
            lemmes.put(t, t.getLemmePrincipal());
        }
        return lemmes.get(t);
    }
    
    Map<Terme, Terme> norm = new HashMap<>();
    private Terme getNormOpti(Terme t) {
        if(!norm.containsKey(t)) {
            norm.put(t, t.getFormeNormale());
        }
        return norm.get(t);
    }
    
    @Override
    public double getAvancement() {
        return avancement + (mesureSimilarite == Recherche.SIMILARITE_PAR_CO_OCCURRENCES?(analyseurSpectral.getAvancement()*0.10):0.10);
    }
    
    @Override
    public String getStatut() {
        return statut;
    }
    
    public String getLogExecution() {
        return logExecution;
    }
    
    @Override
    public long getTempsExecution() {
        if(statut.equals("") || statut.equals("terminé")) {
            return momentFin - momentDebut;
        } else {
            return System.currentTimeMillis() - momentDebut;
        }
    }
    
    @Override
    public String toString() {
        return "Recherche par n-grammes : "+
                (ordreCompte==Recherche.L_ORDRE_DES_MOTS_COMPTE?"avec ordre":"sans ordre") + ", " +
                (motsVides==Recherche.TEXTE_AVEC_MOTS_VIDES?"avec les mots vides":(motsVides==Recherche.TEXTE_SANS_MOTS_VIDES?"sans les mots vides":"sans les mots statistiquement vides")) + ", " +
                (expressionsVides==Recherche.FILTRAGE_AVEC_LEMMES_ET_EXPRESSIONS_VIDES?"avec les expressions vides":(expressionsVides==Recherche.FILTRAGE_SANS_LEMMES_NI_EXPRESSIONS_VIDES?"sans les expressions vides":"sans les expressions statistiquement vides")) + ", " +
                (traitementTermes==Recherche.TERMES_BRUTS?"termes bruts":(traitementTermes==Recherche.TERMES_NORMALISES?"termes normalisés":"termes lemmatisés")) + ", " +
                (mesureSimilarite==Recherche.SIMILARITE_EXACTE?"similarité exacte":("similarité par co-occurrences ("+parametreSimilarite+" termes, seuil "+seuilEgalite + ")")) + ", " +
                (tolerance==Recherche.CORRESPONDANCE_STRICTE?"correspondance stricte":("correspondance tolérante ("+(tolerance==Recherche.CORRESPONDANCE_SEUILLEE_EN_POURCENTAGE?(seuil*100)+"%":seuil)+")")) + ", " +
                seuilFusion +" mots max pour fusion, "+ nbMotsMaxCitation+" mots max par citation, " + tailleFenetre+"-grammes";
    }
}
