Faire correspondre des intervalles

s1 = ]-infini,1]
s2 = [1,3]
s3 = [1,7]
s4 = [3,4]
s5 = [4,5]
s6 = [3,6]

memset(&x,0,sizeof(x));

x = 0;

x |= 2 << i; // x = x | (2 << i)

z = x & y;

z = x | y;

#include <stdio.h>

int main(){
  const char* filename = "mon_fichier.txt";
  FILE *fp = fopen(filename,"r");
  if(!fp){
    fprintf(stderr,"%s: can't read %s\n",argv[0],filename);
    return 1; // quitte le programme avec le code d'erreur 1
  }

  // Lire le contenu de fp
  //...

  fclose(fp);
  return 0; // quitte le programme avec le code d'exécution 0 (tout va bien)
}

segment[0] = [c,e]
segment[1] = [a,b]
segment[2] = [b,d]
segment[3] = [f,h]
segment[4] = [e,f]
segment[5] = [h,i]
  | 0 1 2 3 4 5 |
a | 0 1 0 0 0 0 |
b | 0 1 1 0 0 0 |
c | 1 0 1 0 0 0 |
d | 1 0 1 0 0 0 |
e | 1 0 0 0 1 0 |
f | 0 0 0 1 1 0 |
g | 0 0 0 1 0 0 |
h | 0 0 0 1 0 1 |
i | 0 0 0 0 0 1 |
a belongs to segment [a,b]
b belongs to segment [b,d]
c belongs to segment [c,e]
d belongs to segment [c,e]
e belongs to segment [e,f]
f belongs to segment [f,h]
g belongs to segment [f,h]
h belongs to segment [h,i]
i belongs to segment [h,i]

#include <stdio.h>
#include <stdlib.h>


//========================================================================
// Implémentation du segment tree
// Voir https://en.wikipedia.org/wiki/Segment_tree
//
// - Un segment tree est un arbre binaire équilibré dont chaque feuille
// décrit une borne (unique) étant donné un jeu d'intervalles (segment).
//
// - Chaque noeud décrit un intervalle canonique (tous les intervalles étant
// décrit par une union d'intervalles canoniques). Chaque noeud maintient
// un masque indiquant quels intervalles incluent leur intervalle canonique.
//
//========================================================================

typedef char bound_t;       /**< Le type des bornes décrivant un segment */
typedef long bit_field_t;   /**< Le type du masque maintenu dans un noeud */

#define BOUND_MIN 0        /**< - infini */
#define BOUND_MAX 255      /**< + infini */

/**
 * \class segment_t Décrit un intervalle
 */
typedef struct segment_t{
   bound_t lb;                    /**< La borne inférieure de l'intervalle */
   bound_t ub;                    /**< La borne supérieure de l'intervalle */
} segment_t;

/**
 * \class node_t Noeud de l'arbre canonique
 */
typedef struct node_t{
   unsigned          index;       /**< L'index du noeud dans l'arbre  */
   struct node_t *   l;           /**< Fils gauche */
   struct node_t *   r;           /**< Fils droit */
   struct segment_t  segment;     /**< L'intervalle canonique couvert par le noeud */
   bit_field_t       intervals;   /**< Le bit 1 << i vaut 1 ssi 'segment' décrit un intervalle canonique maximal inclu dans l'intervalle i */
} node_t;

/**
 * \class tree_t Le segment tree
 */
typedef struct tree_t{
   struct node_t    * nodes;       /**< Les noeuds stockés dans l'arbre. &nodes[0] correspond au noeud racine */
   struct segment_t * segments;    /**< Les segments stockés dans l'arbre. segments[i] décrit l'intervalle correspondant au bit 'i' dans le masque intervals d'un noeud. */
   unsigned           nb_segments; /**< Le nombre de segment installés */
} tree_t;


// Usage interne au segment tree
static tree_t prepare_tree(unsigned,const bound_t *,unsigned);
static int    install_segment(tree_t *,const segment_t *);
static void   init_tree_rec(tree_t *,node_t *,unsigned *,unsigned,unsigned *,const bound_t *,unsigned);
static void   install_interval_rec(tree_t *,node_t *,unsigned,const segment_t *);
static void   get_intervals_rec(tree_t *,node_t *,bound_t,bit_field_t *);
static void   get_interval_rec (tree_t *,node_t *,bound_t,bit_field_t *);
static int    sort_growing(const void *x,const void *y);

// Utilisation du segment tree
tree_t      make_tree(const segment_t *segments,unsigned nb_segments,unsigned *nb_bounds);
void        release_tree(tree_t *);
int         bit_field2index(bit_field_t *);
bit_field_t get_intervals(tree_t *,bound_t);
segment_t * get_interval(tree_t *,bound_t);


/**
 * \brief Construit l'arbre, initialise tous les champs de chaque noeuds
 * \param tree Le segment tree
 * \param node Le noeud courant. Pour un appel récursif de partant de la racine, passer &tree->nodes[0]
 * \param cur_index L'index du noeud dans le vecteur
 * \param floor L'étage du noeud courant (0 pour les feuilles, ..., E(log2(nb_leaves)) pour la racine, avec nb_leaves = nb_bounds)
 * \param premaining_bounds Pointe sur le nobre de borne qu'il faut encore installer
 * \param bounds Les bornes ordonnées des intervalles stockés dans l'arbre
 * \param nb_bounds Le nombre de bornes
 */
void init_tree_rec(
   tree_t        * tree,
   node_t        * node,
   unsigned      * cur_index,
   unsigned        floor,
   unsigned      * premaining_bounds,
   const bound_t * bounds,
   unsigned        nb_bounds
){
   node->index = (*cur_index)++;
   node->intervals = 0;
   if(floor){
       // Construire le fils gauche
       if(*premaining_bounds){
           node->l = &tree->nodes[*cur_index];
          init_tree_rec(tree,node->l,cur_index,floor-1,premaining_bounds,bounds,nb_bounds);
          if(floor == 1){
               node->l->segment.lb = node->l->segment.ub = bounds[nb_bounds - *premaining_bounds];
               node->l->l = node->l->r = NULL;
               --*premaining_bounds;
          }
       }else node->l = NULL;

       // Construire le fils droit
       if(*premaining_bounds){
           node->r = &tree->nodes[*cur_index];
          init_tree_rec(tree,node->r,cur_index,floor-1,premaining_bounds,bounds,nb_bounds);
          if(floor == 1){
               node->r->segment.lb = bounds[nb_bounds - *premaining_bounds - 1];
               node->r->segment.ub = bounds[nb_bounds - *premaining_bounds];
               node->r->l = node->r->r = NULL;
          }
       }else node->r = NULL;

       // Installer les bornes
       node->segment.lb = node->l->segment.lb;
       node->segment.ub = node->r ? node->r->segment.ub : node->l->segment.ub;
   }
}

/**
 * \brief Construit l'arbre binaire équilibré
 * \param bounds Les bornes à installer dans l'arbre
 * \param nb_bounds Le nombre de borne
 * \return L'arbre créé
 */
tree_t prepare_tree(unsigned nb_segments,const bound_t *bounds,unsigned nb_bounds){
   tree_t   tree;
   unsigned highest_floor, remaining_bounds, index ;

   // Vérifier que le masque des noeuds est suffisamment grand par rapport au nombre d'intervalles à stocker
   if(nb_segments > 8*sizeof(bit_field_t)){
       printf("prepare_tree: too many segments (%d) (max = %d). last segments will be ignored\n",nb_segments,8*sizeof(bit_field_t));
       nb_segments = 8*sizeof(bit_field_t);
   }

   // Le nombre de noeuds dans un arbre est borné par 2 fois le nombre de feuilles (nb feuilles = 2 fois le nombre de bornes + 1)
   tree.nodes    = (node_t *)    malloc(2*(2 * nb_bounds + 1)*sizeof(node_t));
   tree.segments = (segment_t *) malloc(nb_segments*sizeof(segment_t));
   tree.nb_segments = 0;

   // Les étages sont indexés (de 0 pour les feuilles à highest_floor = E(log2(nb_leaves) pour la racine)
   for(highest_floor = 0;(unsigned) (1 << highest_floor) < (2 * nb_bounds + 1); ++highest_floor);

   // Construire le maillage, installer les index et remettre à zéro intervals
   index = 0;
   remaining_bounds = nb_bounds;
   init_tree_rec(&tree,&tree.nodes[0],&index,highest_floor,&remaining_bounds,bounds,nb_bounds);
   return tree;
}


/**
 * \brief Désalloue l'arbre
 * \param tree L'arbre à désallouer
 */
void release_tree(tree_t *tree){
   if(tree->nodes)    { free(tree->nodes);    tree->nodes    = NULL; }
   if(tree->segments) { free(tree->segments); tree->segments = NULL; }
   tree->nb_segments = 0;
}

/**
 * \brief Installe un intervalle
 * \param tree Le segment tree
 * \param node Le noeud courant. Pour un appel récursif de partant de la racine, passer &tree->nodes[0]
 * \param idx_interval La position du bit qui identifie l'intervalle seg dans chaque noeud de l'arbre
 * \param seg Pointeur sur l'intervalle à installer
 */
void install_interval_rec(
   tree_t          * tree,
   node_t          * node,
   unsigned          idx_interval,
   const segment_t * seg
){
   if(seg->lb <= node->segment.lb && node->segment.ub <= seg->ub){
       // Si l'intervalle canonique du noeud courant est inclu dans seg
       node->intervals |= (1 << idx_interval);
   }else{
       // Si l'intervalle canonique d'un fils recouvre partiellement seg, plonger dedans
       if(node->l && (node->l->segment.lb <= seg->ub && node->l->segment.ub > seg->lb)){
           install_interval_rec(tree,node->l,idx_interval,seg);
       }
       if(node->r && (node->r->segment.lb <= seg->ub && node->r->segment.ub > seg->lb)){
           install_interval_rec(tree,node->r,idx_interval,seg);
       }
   }
}

/**
 * \brief Installe un intervalle dans l'arbre
 * \param tree Le segment tree
 * \param seg Pointeur sur l'intervalle à installer
 * \return Le nombre de segments insérés avec succès
 */
int install_segment(
   tree_t          * tree,
   const segment_t * seg
){
   // Vérifier que le pool d'intervalles enregistrés n'est pas plein
   if(tree->nb_segments > 8*sizeof(bit_field_t)) return 0;

   // Installer l'intervalle dans les segments enregistrés
   tree->segments[tree->nb_segments].lb = seg->lb;
   tree->segments[tree->nb_segments].ub = seg->ub;

   // Marquer les noeuds
   install_interval_rec(tree,&tree->nodes[0],(tree->nb_segments)++,seg);
   return 1;
}

/**
 * \brief Retrouve le masque constitué des identifiants d'intervalles contenant un point donné
 * \param tree Le segment tree
 * \param node Le noeud courant. Pour un appel récursif de partant de la racine, passer &tree->nodes[0]
 * \param value Le point
 * \param b Un pointeur vers le masque initialisé à 0
 */
void get_intervals_rec(
   tree_t      * tree,
   node_t      * node,
   bound_t       value,
   bit_field_t * b
){
   *b |= node->intervals;
   if(node->l || node->r){
          if(node->l && (value < node->l->segment.ub || (value == node->l->segment.ub && !node->l->r))){
           // Si le point est situé avant la borne supérieure du fils gauche, ou que ce fils gauche
           // est une feuille contenant la valeur value, on cherche dans le fils gauche.
           get_intervals_rec(tree,node->l,value,b);
       }else if(node->r){
           // Sinon le point est dans le sous-arbre droit.
           get_intervals_rec(tree,node->r,value,b);
       }
   }
}

/**
 * \brief Retrouve le masque constitué des identifiants d'intervalles contenant un point donné.
 * Si on sait qu'au plus un segment correspond, utiliser get_interval (plus efficace)
 * \param tree Le segment tree
 * \param value Le point
 * \return Le masque constitué des identifiants d'intervalles contenant un point donné
 */
bit_field_t get_intervals(
   tree_t      * tree,
   bound_t       value
){
   bit_field_t b;
   if(!tree->nodes) return 0; // arbre vide
   b = 0;
   get_intervals_rec(tree,&tree->nodes[0],value,&b);
   return b;
}

/**
 * \brief Retrouve le premier intervalle qui contient un point
 * \param tree Le segment tree
 * \param node Le noeud courant. Pour un appel récursif de partant de la racine, passer &tree->nodes[0]
 * \param pt Le point
 * \param b Un pointeur vers le masque initialisé à 0
 */
void get_interval_rec(
   tree_t      * tree,
   node_t      * node,
   bound_t       value,
   bit_field_t * b
){
   *b |= node->intervals;
   if(!*b &&(node->l || node->r)){
       if(node->l && (value < node->l->segment.ub || (value == node->l->segment.ub && !node->l->r))) get_interval_rec(tree,node->l,value,b);
       else if (node->r) get_interval_rec(tree,node->r,value,b);
   }
}

/**
 * \brief Cherche un intervalle stocké dans l'arbre contenant un point particulier
 * \param tree Le segment tree
 * \param value Le point
 * \return Un pointeur vers le segment correspondant
 */
segment_t * get_interval(
   tree_t  * tree,
   bound_t   value
){
   bit_field_t b;
   if(!tree->nodes) return NULL; // arbre vide
   b = 0;
   get_interval_rec(tree,&tree->nodes[0],value,&b);
   if(!b) return NULL; // 'value' n'est inclu dans aucun segment canonique
   return &tree->segments[bit_field2index(&b)];
}

/**
 * \brief Convertit un bitfield
 * \param b Pointeur sur le champ de bit
 * \return La position du plus petit bit à 1 (-1 si b ne contient que des 0)
 */
int bit_field2index(bit_field_t *b){
   unsigned i;
   for(i = 0; i < 8 * sizeof(bit_field_t) ; ++i){
       if (*b & (1 << i)) return i;
   }
   return -1;
}

/**
 * \brief Ordonne deux bornes
 * \param x Pointeur sur la première borne
 * \param y Pointeur sur la seconde borne
 * \return une valeur négative si *x inférieur *y, 0 si *x == *y, une valeur positive sinon
 */
int sort_growing(const void *px,const void *py){
   const bound_t *x = px;
   const bound_t *y = py;
   return *x - *y;
}

/**
 * \brief Construit un segment tree étant donné un jeu d'intervalles
 * \param segments Les intervalles
 * \param nb_segments Le nombre d'intervalles
 * \param nb_bounds Un pointeur vers un entier qui contiendra le nombre de bornes distinctes
 * (feuilles) contenu dans l'arbre retourné
 * \return Le segment tree
 */
tree_t make_tree(const segment_t *segments,unsigned nb_segments,unsigned *nb_bounds){
   unsigned  i,n;
   bound_t * bounds;
   tree_t    _tree;
      if(!nb_segments || !segments){
       // Arbre vide
       *nb_bounds = _tree.nb_segments = 0;
       _tree.nodes = NULL;
       _tree.segments = NULL;
   }else{
       n = 2 * (nb_segments + 1);
       bounds = (bound_t *) malloc(n * sizeof(bound_t));

       // Stocker les bornes des intervalles, -infini et +infini dans bounds
       bounds[0] = BOUND_MIN;
       for(i=0;i<nb_segments;++i){
           bounds[2 * i + 1] = segments[i].lb;
           bounds[2 * i + 2] = segments[i].ub;
       }
       bounds[n - 1] = BOUND_MAX;

       // Trier les bornes et virer les doublons (les *nb_bounds premières cases contiendront les bornes 2 à 2 distincites)
       qsort(bounds,n,sizeof(bound_t),sort_growing);
       *nb_bounds = 1;
       for(i=1;i<n;++i){
           if(bounds[i] != bounds[*nb_bounds-1]){
               bounds[*nb_bounds] = bounds[i];
               ++*nb_bounds;
           }
       }

       // Construire le maillage
       _tree = prepare_tree(nb_segments,bounds,*nb_bounds);

       // Installer des segments
       for(i=0;i<nb_segments;++i) install_segment(&_tree,&segments[i]);
       free(bounds);
   }
   return _tree;
}

int main(){
   const unsigned    nb_segments = 6;
   unsigned          i,nb_bounds;
   tree_t            _tree;
   segment_t         segments[nb_segments];
   segment_t      *  seg;
   tree_t         *  tree = &_tree;
   bit_field_t       mask;
   char              c;

   // Les segments que l'on va stocker dans l'arbre
   segments[0].lb = 'c'; segments[0].ub = 'e'; // [c,e]
   segments[1].lb = 'a'; segments[1].ub = 'b'; // [a,b]
   segments[2].lb = 'b'; segments[2].ub = 'd'; // [b,d]
   segments[3].lb = 'f'; segments[3].ub = 'h'; // [f,h]
   segments[4].lb = 'e'; segments[4].ub = 'f'; // [e,f]
   segments[5].lb = 'h'; segments[5].ub = 'i'; // [h,i]
   _tree = make_tree(segments,nb_segments,&nb_bounds);

   // afficher les intervalles
   for(i = 0;i<nb_segments;++i){
       printf("segment[%d] = [%c,%c]\n",i,tree->segments[i].lb,tree->segments[i].ub);
   }

   // get_intervals
   printf("  | ");
   for(i = 0;i<tree->nb_segments;++i) printf("%i ",i);
   printf("|\n");
   for(c = 'a';c<'j';++c){
       printf("%c | ",c);
       mask = get_intervals(tree,c);
       for(i=0;i<tree->nb_segments;++i){
           printf("%d ",mask & (1 << i) ? 1 : 0);
       }
       printf("|\n");
   }

   // get_interval
   for(c = 'a';c<'j';++c){
       seg = get_interval(tree,c);
       if (seg) printf("%c belongs to segment [%c,%c]\n",c,seg->lb,seg->ub);
       else     printf("%c does not belong to any stored segment\n",c);
   }
   // Libérer l'arbre
   release_tree(tree);
   return 0;
}
//========================================================================