====== Introduction ======

Le but est de gérer un ensemble d'intervalles pour l'ensemble des entiers (suivant type/implémentation, signé ou non) semi-ouverts ([X;Y[ avec X < Y) par une liste. Toutefois, il est aisé de passer d'un intervalle ouvert à semi-ouvert, en ajoutant un à la borne supérieure.

Dans le cas d'un recouvrement, une fusion doit être opérée lors de l'insertion pour ne conserver que l'intervalle résultant (le plus grand).
Exemple: si l'on possède [1;4[ et que l'on veut insérer [2;7[, on doit aboutir à [1;7[.

Contraintes :
  * les intervalles seront ordonnés sur leur borne inférieure, de manière croissante

Effets :
  * étant donné que les intervalles sont triés de manière croissante selon leur borne inférieure, la liste d'intervalles sera toujours parcourue en fonction de cet ordre (le sens inverse pourrait être permis par une liste doublement chaînée)
  * étant donné que les recouvrements sont gérés à l'insertion :
    * la liste ne contiendra jamais d'intervalles se chevauchant
    * chaque entier ne peut être présent qu'au plus une fois

Exemples d'application :
  * coloration des correspondances de la sortie de grep sur systèmes Unixoïdes (à cause des séquence d'échappement ANSI à insérer). La recherche des motifs "él" et "lè" dans "élève" serait incorrecte
  * cut dont le comportement attendu, selon la norme, est :<code>L'entrée sélectionnée est écrite dans le même ordre qu'elle est lue (3,1 aboutit en 1,3), et est écrite exactement une fois (3,1-5 aboutit en 1-5)</code>

====== Algorithme général ======

Détails des cas (+ illustrations)

<code>Intervalle: <borneInférieure: entier, borneSupérieure: entier></code>

Prototype de la fonction à implémenter :
<code>fonction insérerIntervalle(listeIntervalles: liste[Intervalle], borneInférieure: entier, borneSupérieure: entier)</code>

===== Liste vide =====

Si la liste d'intervalles est vide, ajouter (peu importe que ce soit en tête ou en queue) l'intervalle [borneInférieure;borneSupérieure[ :
<code>fonction insérerIntervalle(listeIntervalles: liste[Intervalle], borneInférieure: entier, borneSupérieure: entier)
    si estVide(listeIntervalles) alors
        ajouterEnQueue(listeIntervalles, créerIntervalle(borneInférieure, borneSupérieure)
    sinon
        // partie complétée par la suite
    fsi
fin</code>

===== Position de la borne inférieure =====

Il existe deux cas différents : cette borne est, ou non (en dehors), située dans un intervalle existant.
<code>borneInférieure dedans :
       X1---
borneInférieure dehors (deux sous-cas) :
 X2---
             X3---
Intervalles de comparaison (L1 = courant, L2 = prochain) :
   L1 ---- U1     L2 ---- U2</code>

Cas :
  - X1 est située dans l'intervalle courant
    * (X1_1) si la borne supérieure de l'intervalle à ajouter est également située dans ce même intervalle, nous n'avons rien à faire
    * (X1_2) sinon il y a au moins une fusion à opérer: fin de la boucle, nous avons trouvé notre point d'origine
  - X2 est située à gauche de l'intervalle courant
    * (X2_1) si la borne supérieure de l'intervalle à ajouter est également située à gauche de ce même intervalle, nous devons ajouter notre nouvel intervalle avant (ajouter avant = ajouter après son prédécesseur pour ceux qui voudraient utiliser une liste simplement chaînée) celui où on se trouve et mettre fin à la fonction
    * (X2_2) sinon il y a au moins une fusion à opérer: fin de la boucle, nous avons trouvé notre point d'origine
  - X3 est gérée par la prochaine itération. Toutefois, si on atteignait la fin de la liste, nous ajoutons le nouvel intervalle en queue et mettons fin à la fonction

Ne perdons pas de vue que la liste est triée selon la borne inférieure. Par conséquent, si celle-ci est inférieure à celle de l'intervalle courant lors de notre parcours de la liste, il n'est pas utile d'aller plus loin.

<code>
ElementDeListe from <- tête(listeIntervalles)
tant que non finListe(listeIntervalles, from) faire
    Intervalle i <- valeur(listeIntervalles, from)
    si borneInférieure < i.borneInférieure alors // cas X2
        si borneSupérieure < i.borneInférieure alors // cas X2_1
            ajouterAvant(listeIntervalles, from, créerIntervalle(borneInférieure, borneSupérieure)
            retourner
        sinon // cas X2_2
            fin de la boucle
        fsi
    sinon // borneInférieure >= i.borneInférieure
        si borneInférieure <= i.borneSupérieure // cas X1
            si borneSupérieure <= i.borneSupérieure // cas X1_1
                retourner // [borneInférieure;borneSupérieure[ compris dans i: fin de la fonction, rien à faire
            sinon // cas X1_2
                fin de la boucle
            fsi
        fsi
    fsi
    from <- successeur(listeIntervalles, from)
ftant</code>

Il ne s'agit là que d'un premier repérage : nous n'avons pas, pour le moment, considéré les intervalles environnants pour déterminer si nous devons procéder à une(des) fusion(s).

Toutefois, on remarquera un nouveau cas particulier à l'issue de cette itération : si from marque la fin de la liste alors l'intervalle est nouveau et disjoint des autres (= pas de chevauchement) : on peut l'ajouter en fin de liste et mettre fin à la fonction.
<code>si finListe(listeIntervalles, from) alors
    ajouterEnQueue(listeIntervalles, créerIntervalle(borneInférieure, borneSupérieure)
    retourner // inutile de poursuivre
fsi</code>

===== Position de la borne supérieure =====

<code>borneInférieure dedans :
     ---Y1
borneInférieure dehors (deux sous-cas) :
---Y2
           ---Y3
Intervalle de comparaison :
     L ---- U</code>

Ayant déjà assuré, lors du repérage du placement de la borne inférieure, que l'intervalle que nous cherchons à ajouter est contenu dans un autre, l'intervalle représenté sur la figure par [L;U[ ne peut être que différent de celui désigné par from (représenté par [L1;U1[ dans la figure de la partie précédente).

Cas :
  - Y1 est située dans l'intervalle courant : fin de l'itération
  - Y2 est située à gauche de l'intervalle courant : fin de l'itération, étant allé trop loin, nous prenons l'intervalle précédent comme base (cet intervalle précédent pouvant ne pas exister, cas de figure qui est testé par la suite)
  - Y3 est située à droite de l'intervalle courant : ça relève de l'itération suivante (s'il y en a un) sinon (fin de liste atteinte)

<code>ElementDeListe prev <- from
ElementDeListe to <- successeur(listeIntervalles, from)
tant que non finListe(listeIntervalles, to) faire
    Intervalle i <- valeur(listeIntervalles, to)
    si i.borneInférieure >= borneSupérieure // cas Y2
        to <- prev
        fin de la boucle
    fsi
    si i.borneSupérieure >= borneSupérieure // cas Y1 (le si ci-dessus implique i.borneInférieure < borneSupérieure)
        fin de la boucle
    fsi
    prev <- to
    to <- successeur(listeIntervalles, to)
ftant</code>

Si à l'issue de l'itération, la fin de la liste est atteinte, nous réassignons à to la queue de la liste (prev) :
<code>si finListe(listeIntervalles, to) alors
    to <- prev
fsi</code>

===== Fusion =====

<code>
        X1 ----------------------- Y1
 X2 ------------------ Y2
 X3 ---------- Y3
               X4 ----------------- Y4
                       X5 ------------------------------------ Y5

    L1 ---- U1    L2 ---- U2    L3 ---- U3    L4 ---- U4</code>
Etapes :
  * si les éléments de la liste désignés par from et to sont différents, supprimer les éléments de from à to sauf un que nous mettrons à jour (je réutilise from)
  * mettre à jour celui que nous choisissons de conserver de sorte que :
    * borneInférieure = minimum(i.borneInférieure, borneInférieure)
    * borneSupérieure = maximum(i.borneSupérieure, borneSupérieure)

<code>
ElementDeListe el <- successeur(listeIntervalles, from)
tant que el != successeur(listeIntervalles, to) faire // jusqu'à to compris
    el <- supprimerElement(listeIntervalles, el)
ftant
Intervalle i <- valeur(listeIntervalles, from)
i.borneInférieure = minimum(i.borneInférieure, borneInférieure)
i.borneSupérieure = maximum(i.borneSupérieure, borneSupérieure)
</code>

===== Algorithme final =====

<code>fonction insérerIntervalle(listeIntervalles: liste[Intervalle], borneInférieure: entier, borneSupérieure: entier)
    si estVide(listeIntervalles) alors
        ajouterEnQueue(listeIntervalles, créerIntervalle(borneInférieure, borneSupérieure)
    sinon
        ElementDeListe from <- tête(listeIntervalles)
        tant que non finListe(listeIntervalles, from) faire
            Intervalle i <- valeur(listeIntervalles, from)
            si borneInférieure < i.borneInférieure alors // cas X2
                si borneSupérieure < i.borneInférieure alors // cas X2_1
                    ajouterAvant(listeIntervalles, from, créerIntervalle(borneInférieure, borneSupérieure)
                    retourner
                sinon // cas X2_2
                    fin de la boucle
                fsi
            sinon // borneInférieure >= i.borneInférieure
                si borneInférieure <= i.borneSupérieure // cas X1
                    si borneSupérieure <= i.borneSupérieure // cas X1_1
                        retourner // [borneInférieure;borneSupérieure[ compris dans i: fin de la fonction, rien à faire
                    sinon // cas X1_2
                        fin de la boucle
                    fsi
                fsi
            fsi
            from <- successeur(listeIntervalles, from)
        ftant
        si finListe(listeIntervalles, from) alors
            ajouterEnQueue(listeIntervalles, créerIntervalle(borneInférieure, borneSupérieure)
            retourner // inutile de poursuivre
        sinon
            // partie fusion
            ElementDeListe prev <- from
            ElementDeListe to <- successeur(listeIntervalles, from)
            tant que non finListe(listeIntervalles, to) faire
                Intervalle i <- valeur(listeIntervalles, to)
                si i.borneInférieure >= borneSupérieure // cas Y2
                    to <- prev
                    fin de la boucle
                fsi
                si i.borneSupérieure >= borneSupérieure // cas Y1 (le si ci-dessus implique i.borneInférieure < borneSupérieure)
                    fin de la boucle
                fsi
                prev <- to
                to <- successeur(listeIntervalles, to)
            ftant
            si finListe(listeIntervalles, to) alors
                to <- prev
            fsi
            ElementDeListe el <- successeur(listeIntervalles, from)
            tant que el != successeur(listeIntervalles, to) faire // jusqu'à to compris
                el <- supprimerElement(listeIntervalles, el)
            ftant
            Intervalle i <- valeur(listeIntervalles, from)
            i.borneInférieure = minimum(i.borneInférieure, borneInférieure)
            i.borneSupérieure = maximum(i.borneSupérieure, borneSupérieure)
        fsi
    fsi
fin</code>

====== Implémentation ======

J'ai opté pour une variante de liste doublement chaînée où cette liste est en fait accédée par un objet intermédiaire de plus haut niveau. Ce, pour plusieurs raisons :
  * conserver un pointeur sur la fin de la liste, afin de permettre des adjonctions en queue en temps constant O(1) et non O(n) en fonction de la longueur n de celle-ci
  * associer d'autres données à la liste, notamment un destructeur (fonction de rappel pour libérer la mémoire des objets contenus dans la liste) car j'aime que les structures de données possèdent une certaine autonomie, transparence et propreté (aucun risque d'oublier de libérer la mémoire ainsi en en laissant la charge au développeur)
  * pour les suppressions, au lieu de libérer la mémoire maillon par maillon, je conserve le ou les éléments en interne dans une pile (LIFO) pour les "recycler"

[[https://github.com/julp/ugrep/blob/master/struct/intervals.c|Source C intégrée à mon projet ugrep (avec parsing des intervalles)]]