swcsa/intIndex/icsa.c

   1 /* icsa.c
   2  * Copyright (C) 2011, Antonio Fariña and Eduardo Rodriguez, all rights reserved.
   3  *
   4  * icsa.c: Implementation of the interface "../intIndex/interfaceIntIndex.h"
   5  *   that permits to represent a sequence of uint32 integers with an iCSA:
   6  *   An integer-oriented Compressed Suffix Array.
   7  *   Such representation will be handled as a "ticsa" data structure, that
   8  *   the WCSA self-index will use (as an opaque type) to
   9  *   create/save/load/search/recover/getSize of the representation of the
  10  *   original sequence.
  11  *   Suffix sorting is done via Larson/Sadakane suffix sort algorithm
  12  *   from the char-based csa.
  13  *
  14  *   Ref: Larsson, N. J. and Sadakane, K. 2007. Faster suffix sorting. Theoretical
  15  *        Computer Science 387, 3, 258–272.
  16  *
  17  *
  18  * See more details in:
  19  * Antonio Fariña, Nieves Brisaboa, Gonzalo Navarro, Francisco Claude, Ángeles Places,
  20  * and Eduardo Rodríguez. Word-based Self-Indexes for Natural Language Text. ACM
  21  * Transactions on Information Systems (TOIS), 2012.
  22  * http://vios.dc.fi.udc.es/indexing/wsi/publications.html
  23  * http://www.dcc.uchile.cl/~gnavarro/ps/tois11.pdf
  24  *
  25  * This library is free software; you can redistribute it and/or
  26  * modify it under the terms of the GNU Lesser General Public
  27  * License as published by the Free Software Foundation; either
  28  * version 2.1 of the License, or (at your option) any later version.
  29  *
  30  * This library is distributed in the hope that it will be useful,
  31  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  32  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  33  * Lesser General Public License for more details.
  34  *
  35  * You should have received a copy of the GNU Lesser General Public
  36  * License along with this library; if not, write to the Free Software
  37  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  38  *
  39  */
  40
  41 #include <limits.h>
  42 #include "icsa.h"
  43
  44 #define KEY(p)          (V[*(p)+(h)])
  45 #define SWAP(p, q)      (tmp=*(p), *(p)=*(q), *(q)=tmp)
  46 #define MED3(a, b, c)   (KEY(a)<KEY(b) ?                        \
  47         (KEY(b)<KEY(c) ? (b) : KEY(a)<KEY(c) ? (c) : (a))       \
  48         : (KEY(b)>KEY(c) ? (b) : KEY(a)>KEY(c) ? (c) : (a)))
  49
  50 static int *I,                  /* group array, ultimately suffix array.*/
  51    *V,                          /* inverse array, ultimately inverse of I.*/
  52    r,                           /* number of symbols aggregated by transform.*/
  53    h;                           /* length of already-sorted prefixes.*/
  54
  55 /* Subroutine for select_sort_split and sort_split. Sets group numbers for a
  56    group whose lowest position in I is pl and highest position is pm.*/
  57
  58 static void update_group(int *pl, int *pm)
  59 {
  60    int g;
  61
  62    g=pm-I;                      /* group number.*/
  63    V[*pl]=g;                    /* update group number of first position.*/
  64    if (pl==pm)
  65       *pl=-1;                   /* one element, sorted group.*/
  66    else
  67       do                        /* more than one element, unsorted group.*/
  68          V[*++pl]=g;            /* update group numbers.*/
  69       while (pl<pm);
  70 }
  71
  72 /* Quadratic sorting method to use for small subarrays. To be able to update
  73    group numbers consistently, a variant of selection sorting is used.*/
  74
  75 static void select_sort_split(int *p, int n) {
  76    int *pa, *pb, *pi, *pn;
  77    int f, v, tmp;
  78
  79    pa=p;                        /* pa is start of group being picked out.*/
  80    pn=p+n-1;                    /* pn is last position of subarray.*/
  81    while (pa<pn) {
  82       for (pi=pb=pa+1, f=KEY(pa); pi<=pn; ++pi)
  83          if ((v=KEY(pi))<f) {
  84             f=v;                /* f is smallest key found.*/
  85             SWAP(pi, pa);       /* place smallest element at beginning.*/
  86             pb=pa+1;            /* pb is position for elements equal to f.*/
  87          } else if (v==f) {     /* if equal to smallest key.*/
  88             SWAP(pi, pb);       /* place next to other smallest elements.*/
  89             ++pb;
  90          }
  91       update_group(pa, pb-1);   /* update group values for new group.*/
  92       pa=pb;                    /* continue sorting rest of the subarray.*/
  93    }
  94    if (pa==pn) {                /* check if last part is single element.*/
  95       V[*pa]=pa-I;
  96       *pa=-1;                   /* sorted group.*/
  97    }
  98 }
  99
 100 /* Subroutine for sort_split, algorithm by Bentley & McIlroy.*/
 101
 102 static int choose_pivot(int *p, int n) {
 103    int *pl, *pm, *pn;
 104    int s;
 105
 106    pm=p+(n>>1);                 /* small arrays, middle element.*/
 107    if (n>7) {
 108       pl=p;
 109       pn=p+n-1;
 110       if (n>40) {               /* big arrays, pseudomedian of 9.*/
 111          s=n>>3;
 112          pl=MED3(pl, pl+s, pl+s+s);
 113          pm=MED3(pm-s, pm, pm+s);
 114          pn=MED3(pn-s-s, pn-s, pn);
 115       }
 116       pm=MED3(pl, pm, pn);      /* midsize arrays, median of 3.*/
 117    }
 118    return KEY(pm);
 119 }
 120
 121 /* Sorting routine called for each unsorted group. Sorts the array of integers
 122    (suffix numbers) of length n starting at p. The algorithm is a ternary-split
 123    quicksort taken from Bentley & McIlroy, "Engineering a Sort Function",
 124    Software -- Practice and Experience 23(11), 1249-1265 (November 1993). This
 125    function is based on Program 7.*/
 126
 127 static void sort_split(int *p, int n)
 128 {
 129    int *pa, *pb, *pc, *pd, *pl, *pm, *pn;
 130    int f, v, s, t, tmp;
 131
 132    if (n<7) {                   /* multi-selection sort smallest arrays.*/
 133       select_sort_split(p, n);
 134       return;
 135    }
 136
 137    v=choose_pivot(p, n);
 138    pa=pb=p;
 139    pc=pd=p+n-1;
 140    while (1) {                  /* split-end partition.*/
 141       while (pb<=pc && (f=KEY(pb))<=v) {
 142          if (f==v) {
 143             SWAP(pa, pb);
 144             ++pa;
 145          }
 146          ++pb;
 147       }
 148       while (pc>=pb && (f=KEY(pc))>=v) {
 149          if (f==v) {
 150             SWAP(pc, pd);
 151             --pd;
 152          }
 153          --pc;
 154       }
 155       if (pb>pc)
 156          break;
 157       SWAP(pb, pc);
 158       ++pb;
 159       --pc;
 160    }
 161    pn=p+n;
 162    if ((s=pa-p)>(t=pb-pa))
 163       s=t;
 164    for (pl=p, pm=pb-s; s; --s, ++pl, ++pm)
 165       SWAP(pl, pm);
 166    if ((s=pd-pc)>(t=pn-pd-1))
 167       s=t;
 168    for (pl=pb, pm=pn-s; s; --s, ++pl, ++pm)
 169       SWAP(pl, pm);
 170
 171    s=pb-pa;
 172    t=pd-pc;
 173    if (s>0)
 174       sort_split(p, s);
 175    update_group(p+s, p+n-t-1);
 176    if (t>0)
 177       sort_split(p+n-t, t);
 178 }
 179
 180 /* Bucketsort for first iteration.
 181
 182    Input: x[0...n-1] holds integers in the range 1...k-1, all of which appear
 183    at least once. x[n] is 0. (This is the corresponding output of transform.) k
 184    must be at most n+1. p is array of size n+1 whose contents are disregarded.
 185
 186    Output: x is V and p is I after the initial sorting stage of the refined
 187    suffix sorting algorithm.*/
 188
 189 static void bucketsort(int *x, int *p, int n, int k)
 190 {
 191    int *pi, i, c, d, g;
 192
 193    for (pi=p; pi<p+k; ++pi)
 194       *pi=-1;                   /* mark linked lists empty.*/
 195    for (i=0; i<=n; ++i) {
 196       x[i]=p[c=x[i]];           /* insert in linked list.*/
 197       p[c]=i;
 198    }
 199    for (pi=p+k-1, i=n; pi>=p; --pi) {
 200       d=x[c=*pi];               /* c is position, d is next in list.*/
 201       x[c]=g=i;                 /* last position equals group number.*/
 202       if (d>=0) {               /* if more than one element in group.*/
 203          p[i--]=c;              /* p is permutation for the sorted x.*/
 204          do {
 205             d=x[c=d];           /* next in linked list.*/
 206             x[c]=g;             /* group number in x.*/
 207             p[i--]=c;           /* permutation in p.*/
 208          } while (d>=0);
 209       } else
 210          p[i--]=-1;             /* one element, sorted group.*/
 211    }
 212 }
 213
 214 /* Transforms the alphabet of x by attempting to aggregate several symbols into
 215    one, while preserving the suffix order of x. The alphabet may also be
 216    compacted, so that x on output comprises all integers of the new alphabet
 217    with no skipped numbers.
 218
 219    Input: x is an array of size n+1 whose first n elements are positive
 220    integers in the range l...k-1. p is array of size n+1, used for temporary
 221    storage. q controls aggregation and compaction by defining the maximum value
 222    for any symbol during transformation: q must be at least k-l; if q<=n,
 223    compaction is guaranteed; if k-l>n, compaction is never done; if q is
 224    INT_MAX, the maximum number of symbols are aggregated into one.
 225
 226    Output: Returns an integer j in the range 1...q representing the size of the
 227    new alphabet. If j<=n+1, the alphabet is compacted. The global variable r is
 228    set to the number of old symbols grouped into one. Only x[n] is 0.*/
 229
 230 static int transform(int *x, int *p, int n, int k, int l, int q)
 231 {
 232    int b, c, d, e, i, j, m, s;
 233    int *pi, *pj;
 234
 235    for (s=0, i=k-l; i; i>>=1)
 236       ++s;                      /* s is number of bits in old symbol.*/
 237    e=INT_MAX>>s;                /* e is for overflow checking.*/
 238    for (b=d=r=0; r<n && d<=e && (c=d<<s|(k-l))<=q; ++r) {
 239       b=b<<s|(x[r]-l+1);        /* b is start of x in chunk alphabet.*/
 240       d=c;                      /* d is max symbol in chunk alphabet.*/
 241    }
 242    m=(1<<(r-1)*s)-1;            /* m masks off top old symbol from chunk.*/
 243    x[n]=l-1;                    /* emulate zero terminator.*/
 244    if (d<=n) {                  /* if bucketing possible, compact alphabet.*/
 245       for (pi=p; pi<=p+d; ++pi)
 246          *pi=0;                 /* zero transformation table.*/
 247       for (pi=x+r, c=b; pi<=x+n; ++pi) {
 248          p[c]=1;                /* mark used chunk symbol.*/
 249          c=(c&m)<<s|(*pi-l+1);  /* shift in next old symbol in chunk.*/
 250       }
 251       for (i=1; i<r; ++i) {     /* handle last r-1 positions.*/
 252          p[c]=1;                /* mark used chunk symbol.*/
 253          c=(c&m)<<s;            /* shift in next old symbol in chunk.*/
 254       }
 255       for (pi=p, j=1; pi<=p+d; ++pi)
 256          if (*pi)
 257             *pi=j++;            /* j is new alphabet size.*/
 258       for (pi=x, pj=x+r, c=b; pj<=x+n; ++pi, ++pj) {
 259          *pi=p[c];              /* transform to new alphabet.*/
 260          c=(c&m)<<s|(*pj-l+1);  /* shift in next old symbol in chunk.*/
 261       }
 262       while (pi<x+n) {          /* handle last r-1 positions.*/
 263          *pi++=p[c];            /* transform to new alphabet.*/
 264          c=(c&m)<<s;            /* shift right-end zero in chunk.*/
 265       }
 266    } else {                     /* bucketing not possible, don't compact.*/
 267       for (pi=x, pj=x+r, c=b; pj<=x+n; ++pi, ++pj) {
 268          *pi=c;                 /* transform to new alphabet.*/
 269          c=(c&m)<<s|(*pj-l+1);  /* shift in next old symbol in chunk.*/
 270       }
 271       while (pi<x+n) {          /* handle last r-1 positions.*/
 272          *pi++=c;               /* transform to new alphabet.*/
 273          c=(c&m)<<s;            /* shift right-end zero in chunk.*/
 274       }
 275       j=d+1;                    /* new alphabet size.*/
 276    }
 277    x[n]=0;                      /* end-of-string symbol is zero.*/
 278    return j;                    /* return new alphabet size.*/
 279 }
 280
 281 /* Makes suffix array p of x. x becomes inverse of p. p and x are both of size
 282    n+1. Contents of x[0...n-1] are integers in the range l...k-1. Original
 283    contents of x[n] is disregarded, the n-th symbol being regarded as
 284    end-of-string smaller than all other symbols.*/
 285
 286 void suffixsort(int *x, int *p, int n, int k, int l)
 287 {
 288    int *pi, *pk;
 289    int i, j, s, sl;
 290
 291    V=x;                         /* set global values.*/
 292    I=p;
 293
 294    if (n>=k-l) {                /* if bucketing possible,*/
 295       j=transform(V, I, n, k, l, n);
 296       bucketsort(V, I, n, j);   /* bucketsort on first r positions.*/
 297    } else {
 298       transform(V, I, n, k, l, INT_MAX);
 299       for (i=0; i<=n; ++i)
 300          I[i]=i;                /* initialize I with suffix numbers.*/
 301       h=0;
 302       sort_split(I, n+1);       /* quicksort on first r positions.*/
 303    }
 304    h=r;                         /* number of symbols aggregated by transform.*/
 305
 306    while (*I>=-n) {
 307       pi=I;                     /* pi is first position of group.*/
 308       sl=0;                     /* sl is negated length of sorted groups.*/
 309       do {
 310          if ((s=*pi)<0) {
 311             pi-=s;              /* skip over sorted group.*/
 312             sl+=s;              /* add negated length to sl.*/
 313          } else {
 314             if (sl) {
 315                *(pi+sl)=sl;     /* combine sorted groups before pi.*/
 316                sl=0;
 317             }
 318             pk=I+V[s]+1;        /* pk-1 is last position of unsorted group.*/
 319             sort_split(pi, pk-pi);
 320             pi=pk;              /* next group.*/
 321          }
 322       } while (pi<=I+n);
 323       if (sl)                   /* if the array ends with a sorted group.*/
 324          *(pi+sl)=sl;           /* combine sorted groups at end of I.*/
 325       h=2*h;                    /* double sorted-depth.*/
 326    }
 327
 328    for (i=0; i<=n; ++i)         /* reconstruct suffix array from inverse.*/
 329       I[V[i]]=i;
 330 }
 331
 332
 333 //ticsa *createIntegerCSA(uint **intVector, uint textSize, char *build_options) {
 334 int buildIntIndex (uint *intVector, uint n, char *build_options, void **index ){
 335         uint textSize=n;
 336         ticsa *myicsa;
 337         myicsa = (ticsa *) malloc (sizeof (ticsa));
 338         uint *Psi, *SAI, *C, vocSize;
 339         register uint i, j;
 340         uint nsHUFF;
 341
 342         parametersCSA(myicsa, build_options);
 343
 344         nsHUFF=myicsa->tempNSHUFF;
 345
 346         // Almacenamos o valor dalguns parametros
 347
 348         myicsa->suffixArraySize = textSize;
 349         myicsa->D = (uint*) malloc (sizeof(uint) * ((textSize+31)/32));
 350
 351         myicsa->samplesASize = (textSize + myicsa->T_A - 1) / myicsa->T_A + 1; //--> última pos siempre sampleada!
 352 //      myicsa->samplesASize = (textSize + myicsa->T_A - 1) / myicsa->T_A ;//+ 1;
 353         myicsa->samplesA = (uint *)malloc(sizeof(uint) * myicsa->samplesASize);
 354         myicsa->samplesA[myicsa->samplesASize-1] = 0000;
 355         myicsa->BA = (uint*) malloc (sizeof(uint) * ((textSize+31)/32));
 356         myicsa->samplesAInvSize = (textSize + myicsa->T_AInv - 1) / myicsa->T_AInv;
 357         myicsa->samplesAInv = (uint *)malloc(sizeof(int) * myicsa->samplesAInvSize);
 358
 359         // CONSTRUIMOS A FUNCION C
 360         vocSize = 0;
 361         for(i=0;i<textSize;i++) if(intVector[i]>vocSize) vocSize = intVector[i];
 362         C = (uint *) malloc(sizeof(uint) * (vocSize + 1));      // Para contar o 0 terminador
 363         for(i=0;i<vocSize;i++) C[i] = 0;
 364         for(i=0;i<textSize;i++) C[intVector[i]]++;
 365         for (i=0,j=0;i<=vocSize;i++) {
 366                 j = j + C[i];
 367                 C[i] = j;
 368         }
 369         for(i=vocSize;i>0;i--) C[i] = C[i-1];
 370         C[0] = 0;
 371
 372         // Reservamos espacio para os array de sufijos
 373         Psi = (uint *) malloc (sizeof(uint) * (textSize+1));
 374         printf("\n\t *BUILDING THE SUFFIX ARRAY over %d integers... (with larsson-sadakane)", textSize);fflush(stdout);
 375
 376 /* Makes suffix array p of x. x becomes inverse of p. p and x are both of size
 377    n+1. Contents of x[0...n-1] are integers in the range l...k-1. Original
 378    contents of x[n] is disregarded, the n-th symbol being regarded as
 379    end-of-string smaller than all other symbols.*/
 380    //void suffixsort(int *x, int *p, int n, int k, int l)
 381
 382         //suffixsort((int *)intVector, (int *)Psi, n, vocSize+1, 1);
 383         suffixsort((int *)intVector, (int *)Psi, n-1, vocSize+1, 1);
 384         //*Psi = *Psi++;        // Con esto temos o array de sufixos desde a primeira posición (sen o terminador)
 385         printf("\n\t ...... ended.");
 386
 387
 388
 389         // CONSTRUIMOS A INVERSA DO ARRAY DE SUFIXOS
 390         //SAI = (uint *) malloc (sizeof(uint) * (textSize + 1));        // +1 para repetir na ultima posición. Evitamos un if
 391         //for(i=0;i<textSize;i++) SAI[Psi[i]] = i;
 392         //SAI[textSize] = SAI[0];
 393
 394         //SAI = intVector;
 395
 396         SAI = (uint *) malloc (sizeof(uint) * (textSize + 1));  // +1 para repetir na ultima posición. Evitamos un if
 397         for(i=0;i<textSize;i++) SAI[i] = intVector[i];
 398         SAI[textSize] = SAI[0];
 399
 400         //SAI[textSize] = SAI[0];
 401
 402         // ALMACENAMOS AS MOSTRAS DO ARRAY DE SUFIXOS
 403         for(i=0;i<((textSize+31)/32);i++) myicsa->BA[i] = 0;
 404         for(i=0; i<textSize; i+=myicsa->T_A) bitset(myicsa->BA, SAI[i]);
 405         bitset(myicsa->BA, SAI[textSize-1]);                    // A ultima posicion sempre muestreada
 406         //printf("TextSize = %d\n", textSize);
 407         myicsa->bBA = createBitmap(myicsa->BA, textSize);
 408         for(i=0,j=0; i<textSize; i++) if(bitget(myicsa->BA, i)) myicsa->samplesA[j++] = Psi[i];
 409
 410         // ALMACENAMOS AS MOSTRAS DA INVERSA DO ARRAY DE SUFIXOS
 411         for(i=0,j=0;i<textSize;i+=myicsa->T_AInv) myicsa->samplesAInv[j++] = SAI[i];
 412
 413         // CONSTRUIMOS E COMPRIMIMOS PSI
 414         printf("\n\t Creating compressed Psi...");
 415         for(i=0;i<textSize;i++) Psi[i] = SAI[Psi[i]+1];
 416
 417         //FILE *ff = fopen("psi.log","w");
 418         //for (i=0;i<textSize;i++) fprintf(ff,"%d::%u",i,Psi[i]);
 419         //fclose(ff);
 420
 421         free(SAI);
 422
 423
 424         #ifdef PSI_HUFFMANRLE
 425         myicsa->hcPsi = huffmanCompressPsi(Psi,textSize,myicsa->T_Psi,nsHUFF);
 426         #endif
 427         #ifdef PSI_GONZALO
 428         myicsa->gcPsi = gonzaloCompressPsi(Psi,textSize,myicsa->T_Psi,nsHUFF);
 429         #endif
 430         #ifdef PSI_DELTACODES
 431         myicsa->dcPsi = deltaCompressPsi(Psi,textSize,myicsa->T_Psi);
 432         #endif
 433
 434         free(Psi);
 435
 436         // Contruimos D
 437         for(i=0;i<((textSize+31)/32);i++) myicsa->D[i] = 0;
 438         for(i=0;i<=vocSize;i++) bitset(myicsa->D, C[i]);
 439         myicsa->bD = createBitmap(myicsa->D,textSize);
 440         free(C);
 441
 442         // VARIABLE GLOBAL QUE ALMACENA O ESTADO DOS DISPLAYS (IMPORTANTE PARA DISPLAY SECUENCIAL)
 443         // Almacena a última posición do array de sufixos que mostramos con display ou displayNext
 444         // Se nos piden un displayNext, aplicamos PSI sobre esta posición e obtemos a seguinte,
 445         // coa que podemos obter o símbolo pedido, e actualizamos displayState
 446         myicsa->displayCSAState = 0;
 447         myicsa->displayCSAPrevPosition = -2;  //needed by DisplayCSA(position)
 448
 449         //aintVector = intVector;
 450         // Liberamos o espacio non necesario
 451
 452         *index = myicsa;
 453         //return (myicsa);
 454         return 0;
 455 }
 456
 457
 458 //Returns number of elements in the indexed sequence of integers
 459 int sourceLenIntIndex(void *index, uint *numInts){
 460         ticsa *myicsa = (ticsa *) index;
 461         *numInts= myicsa->suffixArraySize;
 462         return 0; //no error;
 463 }
 464
 465 int saveIntIndex(void *index, char *pathname) {
 466 //void storeStructsCSA(ticsa *myicsa, char *basename) {
 467
 468         ticsa *myicsa = (ticsa *) index;
 469         char *basename=pathname;
 470
 471         char *filename;
 472         int file;
 473
 474         // Reservamos espacio para o nome do ficheiro
 475         filename = (char *)malloc(sizeof(char)*MAX_FILENAME_LENGTH);
 476
 477         // Ficheiro co n�mero de elementos indexados (enteiros do texto orixinal)
 478         strcpy(filename, basename);
 479         strcat(filename, ".");
 480         strcat(filename, NUMBER_OF_ELEMENTS_FILE_EXT);
 481         unlink(filename);
 482         if( (file = open(filename, O_WRONLY|O_CREAT,S_IRWXG | S_IRWXU)) < 0) {
 483                 printf("Cannot open file %s\n", filename);
 484                 exit(0);
 485         }
 486         write(file, &(myicsa->suffixArraySize), sizeof(int));
 487         close(file);
 488
 489         strcpy(filename, basename);
 490         strcat(filename, ".");
 491         strcat(filename, PSI_COMPRESSED_FILE_EXT);
 492
 493         #ifdef PSI_HUFFMANRLE
 494                 storeHuffmanCompressedPsi(&(myicsa->hcPsi), filename);
 495         #endif
 496         #ifdef PSI_GONZALO
 497                 storeGonzaloCompressedPsi(&(myicsa->gcPsi), filename);
 498         #endif
 499         #ifdef PSI_DELTACODES
 500                 storeDeltaCompressedPsi(&(myicsa->dcPsi), filename);
 501         #endif
 502
 503         // Ficheiro co vector de bits D
 504         strcpy(filename, basename);
 505         strcat(filename, ".");
 506         strcat(filename, D_FILE_EXT);
 507         unlink(filename);
 508         if( (file = open(filename, O_WRONLY|O_CREAT,S_IRWXG | S_IRWXU)) < 0) {
 509                 printf("Cannot open file %s\n", filename);
 510                 exit(0);
 511         }
 512         write(file, myicsa->D, sizeof(int)*((myicsa->suffixArraySize+31)/32));
 513         close(file);
 514
 515         // Directorio de rank para D
 516         // Almacenamos o n�mero de superbloques seguido dos superbloques
 517         // E logo o n�mero de bloques seguido dos bloques
 518         strcpy(filename, basename);
 519         strcat(filename, ".");
 520         strcat(filename, D_RANK_DIRECTORY_FILE_EXT);
 521         saveBitmap(filename,myicsa->bD);
 522
 523         // Ficheiro coas mostras de A
 524         strcpy(filename, basename);
 525         strcat(filename, ".");
 526         strcat(filename, SAMPLES_A_FILE_EXT);
 527         unlink(filename);
 528         if( (file = open(filename, O_WRONLY|O_CREAT,S_IRWXG | S_IRWXU)) < 0) {
 529                 printf("Cannot open file %s\n", filename);
 530                 exit(0);
 531         }
 532         write(file, myicsa->samplesA, sizeof(int) * (myicsa->samplesASize));
 533         close(file);
 534
 535         // Ficheiro co vector BA (marca as posicions de A muestreadas)
 536         strcpy(filename, basename);
 537         strcat(filename, ".");
 538         strcat(filename, BA_FILE_EXT);
 539         unlink(filename);
 540         if( (file = open(filename, O_WRONLY|O_CREAT,S_IRWXG | S_IRWXU)) < 0) {
 541                 printf("Cannot open file %s\n", filename);
 542                 exit(0);
 543         }
 544         write(file, myicsa->BA, sizeof(int)*((myicsa->suffixArraySize+31)/32));
 545         close(file);
 546
 547         // Directorio de rank para BA
 548         strcpy(filename, basename);
 549         strcat(filename, ".");
 550         strcat(filename, BA_RANK_DIRECTORY_FILE_EXT);
 551         saveBitmap(filename, myicsa->bBA);
 552
 553         // Ficheiro coas mostras de A inversa
 554         strcpy(filename, basename);
 555         strcat(filename, ".");
 556         strcat(filename, SAMPLES_A_INV_FILE_EXT);
 557         unlink(filename);
 558         if( (file = open(filename, O_WRONLY|O_CREAT,S_IRWXG | S_IRWXU)) < 0) {
 559                 printf("Cannot open file %s\n", filename);
 560                 exit(0);
 561         }
 562         write(file, myicsa->samplesAInv, sizeof(int) * (myicsa->samplesAInvSize));
 563         close(file);
 564
 565         // Ficheiro co periodo de muestreo de A e A inversa
 566         strcpy(filename, basename);
 567         strcat(filename, ".");
 568         strcat(filename, SAMPLING_PERIOD_A_FILE_EXT);
 569         unlink(filename);
 570         if( (file = open(filename, O_WRONLY|O_CREAT,S_IRWXG | S_IRWXU)) < 0) {
 571                 printf("Cannot open file %s\n", filename);
 572                 exit(0);
 573         }
 574         write(file, &(myicsa->T_A), sizeof(int));
 575         write(file, &(myicsa->T_AInv), sizeof(int));
 576
 577         write(file, &(myicsa->psiSearchFactorJump), sizeof(uint));
 578
 579         close(file);
 580         free(filename);
 581         return 0; //no error.
 582 }
 583
 584 //Returns the size (in bytes) of the index over the sequence of integers.
 585 //uint CSA_size(ticsa *myicsa) {
 586 int sizeIntIndex(void *index, uint *numBytes) {
 587         ticsa *myicsa = (ticsa *) index;
 588         uint size = 0;
 589         size +=(sizeof (ticsa) * 1);
 590         size += sizeof(uint)*((myicsa->suffixArraySize+31)/32) ;  //D vector
 591         size += myicsa->bD->mem_usage;
 592         size += sizeof(uint) * myicsa->samplesASize ;  // samples A
 593         size += sizeof(uint) * myicsa->samplesAInvSize ;  // samples A^{-1}
 594         size += sizeof(uint)*((myicsa->suffixArraySize+31)/32) ;  //BA vector
 595         size += myicsa->bBA->mem_usage;
 596         #ifdef PSI_HUFFMANRLE
 597                 size +=myicsa->hcPsi.totalMem;
 598         #endif
 599         #ifdef PSI_GONZALO
 600                 size +=myicsa->gcPsi.totalMem;
 601         #endif
 602         #ifdef PSI_DELTACODES
 603                 size +=myicsa->dcPsi.totalMem;
 604         #endif
 605         *numBytes = size;
 606         return 0; //no error.
 607 }
 608
 609
 610 //ticsa *loadCSA(char *basename) {
 611 int loadIntIndex(char *pathname, void **index){
 612
 613         char *basename=pathname;
 614         char *filename;
 615         int file;
 616         uint length;
 617         char c;
 618         char *word;
 619         struct stat f_stat;
 620         uint suffixArraySize;
 621
 622         ticsa *myicsa;
 623         myicsa = (ticsa *) malloc (sizeof (ticsa) * 1);
 624
 625
 626         // VARIABLE GLOBAL QUE ALMACENA O ESTADO DOS DISPLAYS (IMPORTANTE PARA DISPLAY SECUENCIAL)
 627         // Almacena a �ltima posici�n do array de sufixos que mostramos con display ou displayNext
 628         // Se nos piden un displayNext, aplicamos PSI sobre esta posici�n e obtemos a seguinte,
 629         // coa que podemos obter o s�mbolo pedido, e actualizamos displayState
 630         myicsa->displayCSAState = 0;
 631         myicsa->displayCSAPrevPosition = -2;  //needed by DisplayCSA(position)
 632
 633         // Reservamos espacio para o nome do ficheiro
 634         filename = (char *)malloc(sizeof(char)*MAX_FILENAME_LENGTH);
 635
 636         // LEEMOS OS DATOS DO FICHEIRO QUE ALMACENA O NUMERO DE ELEMENTOS INDEXADOS
 637         strcpy(filename, basename);
 638         strcat(filename, ".");
 639         strcat(filename, NUMBER_OF_ELEMENTS_FILE_EXT);
 640         if( (file = open(filename, O_RDONLY)) < 0) {
 641                 printf("Cannot read file %s\n", filename);exit(0);
 642         }
 643         read(file, &suffixArraySize, sizeof(uint));
 644         myicsa->suffixArraySize = suffixArraySize;
 645         printf("Number of indexed elements (suffix array size) = %d\n", suffixArraySize);
 646
 647         // LEEMOS OS DATOS DO FICHEIRO QUE ALMACENA PSI COMPRIMIDA
 648         strcpy(filename, basename);
 649         strcat(filename, ".");
 650         strcat(filename, PSI_COMPRESSED_FILE_EXT);
 651         #ifdef PSI_HUFFMANRLE
 652                 myicsa->hcPsi = loadHuffmanCompressedPsi(filename);
 653         #endif
 654         #ifdef PSI_GONZALO
 655                 myicsa->gcPsi = loadGonzaloCompressedPsi(filename);
 656         #endif
 657         #ifdef PSI_DELTACODES
 658                 myicsa->dcPsi = loadDeltaCompressedPsi(filename);
 659         #endif
 660
 661         // LEEMOS OS DATOS DO FICHEIRO QUE ALMACENA D
 662         strcpy(filename, basename);
 663         strcat(filename, ".");
 664         strcat(filename, D_FILE_EXT);
 665         if( (file = open(filename, O_RDONLY)) < 0) {
 666                 printf("Cannot read file %s\n", filename); exit(0);
 667         }
 668         myicsa->D = (uint *) malloc (sizeof(uint)*((suffixArraySize+31)/32));
 669         read(file, myicsa->D, sizeof(uint)*((suffixArraySize+31)/32));
 670         printf("Bit vector D loaded (%d bits)\n", suffixArraySize);
 671
 672         // LEEMOS OS DATOS DO FICHEIRO QUE ALMACENA O DIRECTORIO DE RANK1 PARA D
 673         strcpy(filename, basename);
 674         strcat(filename, ".");
 675         strcat(filename, D_RANK_DIRECTORY_FILE_EXT);
 676         myicsa->bD = loadBitmap(filename,myicsa->D,suffixArraySize);
 677         {       uint ns, nb;
 678                 ns = myicsa->bD->sSize;
 679                 nb = myicsa->bD->bSize;
 680                 myicsa->bD->data = myicsa->D;
 681                 printf("Rank1 Directory for D loaded (%d superblocks, %d blocks)\n", ns, nb);
 682         }
 683
 684         // LEEMOS OS DATOS DO FICHEIRO QUE ALMACENA SAMPLES A
 685         strcpy(filename, basename);
 686         strcat(filename, ".");
 687         strcat(filename, SAMPLES_A_FILE_EXT);
 688         if( (file = open(filename, O_RDONLY)) < 0) {
 689                 printf("Cannot read file %s\n", filename); exit(0);
 690         }
 691         if( fstat(file, &f_stat) < 0) {
 692                 printf("Cannot read information from file %s\n", filename);     exit(0);
 693         }
 694         myicsa->samplesASize = (f_stat.st_size)/sizeof(uint);
 695         myicsa->samplesA = (uint *)malloc(sizeof(uint) * myicsa->samplesASize);
 696         read(file, myicsa->samplesA, sizeof(uint) * myicsa->samplesASize);
 697         printf("Suffix array samples loaded (%d samples)\n", myicsa->samplesASize);
 698
 699         // LEEMOS OS DATOS DO FICHEIRO QUE ALMACENA BA
 700         strcpy(filename, basename);
 701         strcat(filename, ".");
 702         strcat(filename, BA_FILE_EXT);
 703         if( (file = open(filename, O_RDONLY)) < 0) {
 704                 printf("Cannot read file %s\n", filename); exit(0);
 705         }
 706         myicsa->BA = (uint *) malloc (sizeof(uint)*((suffixArraySize+31)/32));
 707         read(file, myicsa->BA, sizeof(uint)*((suffixArraySize+31)/32));
 708         printf("Bit vector BA loaded (%d bits)\n", suffixArraySize);
 709
 710         // LEEMOS OS DATOS DO FICHEIRO QUE ALMACENA O DIRECTORIO DE RANK1 PARA BA
 711         strcpy(filename, basename);
 712         strcat(filename, ".");
 713         strcat(filename, BA_RANK_DIRECTORY_FILE_EXT);
 714         myicsa->bBA = loadBitmap(filename,myicsa->BA,suffixArraySize);
 715         {       uint ns, nb;
 716                 ns = myicsa->bBA->sSize;
 717                 nb = myicsa->bBA->bSize;
 718                 myicsa->bBA->data = myicsa->BA;
 719                 printf("Rank1 Directory for BA loaded (%d superblocks, %d blocks)\n", ns, nb);
 720         }
 721
 722         // LEEMOS OS DATOS DO FICHEIRO QUE ALMACENA SAMPLES A INVERSA
 723         strcpy(filename, basename);
 724         strcat(filename, ".");
 725         strcat(filename, SAMPLES_A_INV_FILE_EXT);
 726         if( (file = open(filename, O_RDONLY)) < 0) {
 727                 printf("Cannot read file %s\n", filename); exit(0);
 728         }
 729         if( fstat(file, &f_stat) < 0) {
 730                 printf("Cannot read information from file %s\n", filename);     exit(0);
 731         }
 732         myicsa->samplesAInvSize = (f_stat.st_size)/(sizeof(uint));
 733         myicsa->samplesAInv = (uint *)malloc(sizeof(uint) * myicsa->samplesAInvSize);
 734         read(file, myicsa->samplesAInv, sizeof(uint) * myicsa->samplesAInvSize);
 735         printf("Suffix array inverse samples loaded (%d samples)\n", myicsa->samplesAInvSize);
 736
 737         // LEEMOS OS DATOS DO FICHEIRO QUE ALMACENA O PERIODO DE MUESTREO DO ARRAY DE SUFIXOS E DA INVERSA
 738         strcpy(filename, basename);
 739         strcat(filename, ".");
 740         strcat(filename, SAMPLING_PERIOD_A_FILE_EXT);
 741         if( (file = open(filename, O_RDONLY)) < 0) {
 742                 printf("Cannot read file %s\n", filename); exit(0);
 743         }
 744         read(file, &(myicsa->T_A), sizeof(uint));
 745         read(file, &(myicsa->T_AInv), sizeof(uint));
 746         printf("Sampling A Period T = %d, Sampling A inv Period TInv = %d\n", myicsa->T_A, myicsa->T_AInv);
 747
 748         read(file, &(myicsa->psiSearchFactorJump), sizeof(uint));
 749         printf("Psi Bin Search Factor-Jump is = %d\n", myicsa->psiSearchFactorJump);
 750
 751         close(file);
 752         free(filename);
 753
 754         //return myicsa;
 755         *index = myicsa;
 756         return 0;
 757 }
 758
 759
 760 //uint destroyStructsCSA(ticsa *myicsa) {
 761 int freeIntIndex(void *index) {
 762         ticsa *myicsa = (ticsa *) index;
 763                 // Liberamos o espacio reservado
 764
 765         if (!myicsa) return 0;
 766
 767         size_t total=0, totaltmp=0;
 768
 769         uint nbytes;sizeIntIndex(index, &nbytes);
 770
 771         total +=(sizeof (ticsa) * 1);;
 772
 773         #ifdef PSI_HUFFMANRLE
 774                 total+= totaltmp = myicsa->hcPsi.totalMem;
 775                 destroyHuffmanCompressedPsi(&(myicsa->hcPsi));
 776         #endif
 777         #ifdef PSI_GONZALO
 778                 total+= totaltmp = myicsa->gcPsi.totalMem;
 779                 destroyGonzaloCompressedPsi(&(myicsa->gcPsi));
 780         #endif
 781         #ifdef PSI_DELTACODES
 782                 total+= totaltmp = myicsa->dcPsi.totalMem;
 783                 destroyDeltaCodesCompressedPsi(&(myicsa->dcPsi));
 784         #endif
 785         printf("\n\t[destroying  SA: compressed PSI structure] ...Freed %zu bytes... RAM", totaltmp);
 786
 787         free(myicsa->D);                        total+= totaltmp =  (sizeof(uint)*((myicsa->suffixArraySize+31)/32));
 788                                                         printf("\n\t[destroying  SA: D vector] ...Freed %zu bytes... RAM",totaltmp);
 789         free(myicsa->samplesA);         total+= totaltmp = (sizeof(uint) * myicsa->samplesASize);
 790                                                         printf("\n\t[destroying  Samples A: A   ] ...Freed %zu bytes... RAM",totaltmp);
 791         free(myicsa->samplesAInv);      total+= totaltmp =  (sizeof(uint) * myicsa->samplesAInvSize);
 792                                                         printf("\n\t[destroying  Samples AInv: A   ] ...Freed %zubytes... RAM",totaltmp);
 793                                                 printf("\n\t[destroying  rank bit D   ] ...Freed %zu bytes... RAM", (size_t)myicsa->bD->mem_usage);
 794         free(myicsa->BA);                       total+= totaltmp =  (sizeof(uint)*((myicsa->suffixArraySize+31)/32));
 795                                                         printf("\n\t[destroying  SA: BA vector] ...Freed %zu bytes... RAM",totaltmp);
 796
 797                                                                 total += myicsa->bD->mem_usage;
 798         destroyBitmap(myicsa->bD);
 799                                                                 total += myicsa->bBA->mem_usage;
 800         destroyBitmap(myicsa->bBA);
 801
 802         printf("\n\t**** [the whole iCSA ocuppied ... %zu bytes... RAM",total);
 803         printf("\n\t**** iCSA size = %zu bytes ", (size_t) nbytes);
 804         printf("\n");
 805
 806         free(myicsa);
 807
 808         return 0; //no error.
 809 }
 810
 811         // Shows detailed summary info of the self-index (memory usage of each structure)
 812 int printInfoIntIndex(void *index, const char tab[]) {
 813         ticsa *myicsa = (ticsa *) index;
 814         if (!myicsa) return 0;
 815
 816         uint structure, totalpsi, totalD, totalBD, totalSA,totalSAinv, totalBA,totalBBA;
 817
 818         structure=sizeof(ticsa);
 819
 820         #ifdef PSI_HUFFMANRLE
 821                 totalpsi = myicsa->hcPsi.totalMem;
 822         #endif
 823         #ifdef PSI_GONZALO
 824                 totalpsi = myicsa->gcPsi.totalMem;
 825         #endif
 826         #ifdef PSI_DELTACODES
 827                 totalpsi = myicsa->dcPsi.totalMem;
 828         #endif
 829
 830         totalD   = (sizeof(uint)*((myicsa->suffixArraySize+31)/32));
 831         totalBD  = myicsa->bD->mem_usage;
 832         totalSA  = (sizeof(uint) * myicsa->samplesASize);
 833         totalSAinv = (sizeof(uint) * myicsa->samplesAInvSize);
 834         totalBA  = (sizeof(uint)*((myicsa->suffixArraySize+31)/32));
 835         totalBBA = myicsa->bBA->mem_usage;
 836
 837         uint nbytes; sizeIntIndex(index, &nbytes); //whole self-index
 838
 839         printf("\n ===================================================:");
 840         printf("\n%sSummary Self-index on integers (icsa) layer:",tab);
 841         printf("\n%s   icsa structure = %d bytes",tab, structure);
 842         printf("\n%s   psi         = %8d bytes",tab, totalpsi);
 843         printf("\n%s   D (bitmap)  = %8d bytes",tab, totalD);
 844         printf("\n%s   rank for D  = %8d bytes",tab, totalBD);
 845         printf("\n%s   SA(sampled) = %8d bytes",tab, totalSA);
 846         printf("\n%s   SAinv(samp) = %8d bytes",tab, totalSAinv);
 847         printf("\n%s   BA (bitmap) = %8d bytes",tab, totalBA);
 848         printf("\n%s   rank for BA = %8d bytes",tab, totalBBA);
 849         printf("\n%sTotal = ** %9d bytes (in RAM) ** ",tab, nbytes);
 850         printf("\n");
 851
 852         return 0; //no error.
 853 }
 854
 855
 856 // OPERACIONS DO CSA
 857
 858 // BUSCA BINARIA SOBRE MOSTRAS + 2 BUSCAS EXPONENCIAIS + 2 BUSCAS BINARIAS
 859 // 1º Busca binaria sobre o array de sufixos, elexindo como pivote un múltiplo de bin_search_psi_skip_interval (que orixinalmente foi pensado para igualar co valor de Psi).
 860 // 2º Esta busca pode deterse por:
 861 //      a) O pivote repítese entre dúas iteracións -> As ocorrencias están entre o pivote e a seguinte mostra (pivote + bin_search_psi_skip_interval) -> facemos dúas buscas binarias
 862 //      b) O pivote é unha ocorrencia do patrón -> Faise unha busca exponencial sobre mostras hacia a esquerda e outra hacia a dereita, ata atopar a unha mostra á esquerda e outra
 863 //      á dereita do intervalo de ocorrencias. Entre cada unha destas e a inmediatamente anterior da busca exponencial, faise unha busca binaria para atopar os extremos do intervalo.
 864
 865 int countIntIndex(void *index, uint *pattern, uint length, ulong *numocc, ulong *left, ulong *right){
 866         //unsigned int countCSA(ticsa *myicsa, uint *pattern, uint patternSize, uint *left, uint *right) {
 867
 868         uint patternSize = length;
 869         ticsa *myicsa = (ticsa *) index;
 870
 871         register unsigned long l, r, i;
 872         register long comp, p, previousP;
 873         //register unsigned int l, r, i;
 874         //register int comp, p, previousP;
 875         register uint bin_search_psi_skip_interval = myicsa->psiSearchFactorJump;
 876
 877         //fprintf(stderr,"\n psiSearchFactor = %d",myicsa->psiSearchFactorJump);
 878
 879         l = 0;
 880         r = (myicsa->suffixArraySize+bin_search_psi_skip_interval-2)/bin_search_psi_skip_interval*bin_search_psi_skip_interval;
 881         p = ((l+r)/2)/bin_search_psi_skip_interval * bin_search_psi_skip_interval;
 882         previousP = 0;
 883
 884         // BUSCA BINARIA SOBRE MOSTRAS
 885         while( (p != previousP) && (comp = SadCSACompare(myicsa, pattern, patternSize, p)) ) {
 886                 if(comp > 0) l = p;
 887                 else r = p;
 888                 previousP = p;
 889                 p = ((l+r)/2)/bin_search_psi_skip_interval*bin_search_psi_skip_interval;
 890         }
 891
 892         if(p==previousP) {
 893
 894                 // BUSCA BINARIA ENTRE O PIVOTE E A SEGUINTE MOSTRA
 895                 l = previousP;
 896                 r = previousP+bin_search_psi_skip_interval;
 897                 if(r > myicsa->suffixArraySize) r = myicsa->suffixArraySize - 1;
 898                 while(l < r) {
 899                         p = (l+r)/2;
 900                         if(SadCSACompare(myicsa, pattern, patternSize, p) <= 0) r = p;
 901                         else l = p+1;
 902                 }
 903
 904                 if(SadCSACompare(myicsa, pattern, patternSize, r)) {
 905                         *left = l;
 906                         *right = r;
 907                         //return 0;
 908                         *numocc = 0;
 909                         return 0; //no error.
 910                 }
 911                 *left = r;
 912
 913                 l = previousP;
 914                 r = previousP+bin_search_psi_skip_interval;
 915                 if(r > myicsa->suffixArraySize) r = myicsa->suffixArraySize - 1;
 916                 while(l < r) {
 917                         p = (l+r+1)/2;
 918                         if(SadCSACompare(myicsa, pattern, patternSize, p) >= 0) l = p;
 919                         else r = p-1;
 920                 }
 921                 *right = l;
 922
 923         } else {
 924
 925                 previousP = p;  // En previousP poñemos o p atopado na busca sobre as mostras
 926
 927                 // BUSCA EXPONENCIAL HACIA ATRÁS
 928                 i = 1;
 929                 p -= bin_search_psi_skip_interval;
 930                 while(p>0 && !SadCSACompare(myicsa, pattern, patternSize, p)) {
 931                         i<<=1;
 932                         p = previousP-(i*bin_search_psi_skip_interval);
 933                 }
 934                 // Busca binaria entre as duas ultimas mostras da exponencial
 935                 if(previousP > i*bin_search_psi_skip_interval) l = previousP-(i*bin_search_psi_skip_interval);
 936                 else l=0;
 937                 i>>=1;
 938                 r = previousP-(i*bin_search_psi_skip_interval);
 939                 while(l < r) {
 940                         p = (l+r)/2;
 941                         if(SadCSACompare(myicsa, pattern, patternSize, p) <= 0) r = p;
 942                         else l = p+1;
 943                 }
 944                 *left = r;
 945
 946                 // BUSCA EXPONENCIAL HACIA ADIANTE
 947                 i = 1;
 948                 p = previousP+bin_search_psi_skip_interval;
 949                 while(p<myicsa->suffixArraySize && !SadCSACompare(myicsa, pattern, patternSize, p)) {
 950                         i<<=1;
 951                         p = previousP+(i*bin_search_psi_skip_interval);
 952                 }
 953                 // Busca binaria entre as duas ultimas mostras da exponencial
 954                 if(p < myicsa->suffixArraySize) r = previousP+(i*bin_search_psi_skip_interval);
 955                 else r = myicsa->suffixArraySize-1;
 956                 i>>=1;
 957                 l = previousP+(i*bin_search_psi_skip_interval);
 958                 while(l < r) {
 959                         p = (l+r+1)/2;
 960                         if(SadCSACompare(myicsa, pattern, patternSize, p) >= 0) l = p;
 961                         else r = p-1;
 962                 }
 963                 *right = l;
 964         }
 965
 966         //return *right-*left+1;
 967         *numocc = (uint) *right-*left+1;
 968         return 0; //no error
 969 }
 970
 971 // Version inicial de busca binaria
 972 unsigned int countCSABin(ticsa *myicsa, uint *pattern, uint patternSize, uint *left, uint *right) {
 973         register ulong l, r, p;
 974
 975         l = 0;
 976         r = myicsa->suffixArraySize-1;
 977
 978         while(l < r) {
 979                 p = (l+r)/2;
 980                 if(SadCSACompare(myicsa, pattern, patternSize, p) <= 0) r = p;
 981                 else l = p+1;
 982         }
 983
 984         // SE SON DISTINTOS O PATRON NON APARECE NO TEXTO E DEVOLVEMOS 0
 985         if(SadCSACompare(myicsa, pattern, patternSize, r)) {
 986                 *left = l;
 987                 *right = r;
 988                 return 0;
 989         }
 990
 991         // Almacenamos o limite esquerdo
 992         *left = r;
 993
 994         // SE SON IGUALES (O PATRON APARECE NO TEXTO), BUSCAMOS AGORA O LIMITE DEREITO, QUE ALMACENAREMOS EN right
 995         // NOTA: INICIAMOS A BUSQUEDA A PARTIR DO ESQUERDO...
 996         l = r;
 997         r = myicsa->suffixArraySize-1;
 998
 999         while(l < r) {
1000                 p = (l+r+1)/2;
1001                 if(SadCSACompare(myicsa, pattern, patternSize, p) >= 0) l = p;
1002                 else r = p-1;
1003         }
1004
1005         // Gardamos o limite dereito
1006         *right = l;
1007
1008         return (uint) *right-*left+1;
1009 }
1010
1011 int locateIntIndex(void *index, uint *pattern, uint length, ulong **occ, ulong *numocc) {
1012         //unsigned int *locateCSA(ticsa *myicsa, uint *pattern, uint patternSize, uint *occ) {
1013
1014         ticsa *myicsa = (ticsa *) index;
1015         uint patternSize = length;
1016         ulong *positions;
1017         ulong occurrences;
1018         register ulong left, right;
1019
1020                 //occurrences = countCSA(myicsa, pattern, patternSize, &left, &right);
1021         int err;
1022         err = countIntIndex((void *) myicsa, pattern, patternSize, &occurrences, &left, &right);
1023         *numocc = occurrences;
1024
1025         if (occurrences) {
1026                 register ulong idx = 0;
1027                 positions = (ulong*) malloc(sizeof(ulong) * occurrences);
1028                 while(left<=right) positions[idx++] = A(myicsa,left++);
1029
1030                 *occ = positions;
1031                 return 0;
1032                 //return positions;
1033         }
1034
1035         (*occ)=NULL;
1036         return 0; //no error, but no occurrences.
1037
1038         //return NULL;
1039 }
1040
1041 // Devolve o enteiro do texto que ocupa a posicion dada,
1042 // e fixa o estado para poder seguir obtendo os seguintes enteiros con displayNext();
1043
1044 int displayIntIndex(void *index, ulong position, uint *value){
1045         //uint displayCSA(ticsa *myicsa, uint position) {
1046         ticsa *myicsa = (ticsa *) index;
1047         if (position == (myicsa->displayCSAPrevPosition +1)) {
1048                 myicsa->displayCSAPrevPosition = position;
1049                 //return displayCSANext(myicsa);
1050                 *value = displayCSANext(myicsa);
1051         }
1052         else {
1053                 myicsa->displayCSAPrevPosition = position;
1054                 //return displayCSAFirst(myicsa, position);
1055                 *value = displayCSAFirst(myicsa, position);
1056         }
1057         return 0; //no error
1058 }
1059
1060
1061 /**********************************************************************/
1062
1063 // Devolve o enteiro do texto que ocupa a posicion dada, e fixa o estado
1064 // para poder seguir obtendo os seguintes enteiros con displayNext();
1065 uint displayCSAFirst(ticsa *myicsa, uint position) {
1066
1067         register uint positionAux, index;
1068         register uint T_AInv = myicsa->T_AInv;
1069
1070         positionAux = myicsa->samplesAInv[position / T_AInv];
1071         for(index = 0; index < position%T_AInv; index++) {
1072                 #ifdef PSI_HUFFMANRLE
1073                         positionAux=getHuffmanPsiValue(&(myicsa->hcPsi),positionAux);
1074                 #endif
1075                 #ifdef PSI_GONZALO
1076                         positionAux=getGonzaloPsiValue(&(myicsa->gcPsi),positionAux);
1077                 #endif
1078                 #ifdef PSI_DELTACODES
1079                         positionAux=getDeltaPsiValue(&(myicsa->dcPsi),positionAux);
1080                 #endif
1081         }
1082
1083         // Fijamos a variable global para a chamada a displayNext
1084         myicsa->displayCSAState = positionAux;
1085
1086         //      return rank1(D, Dir, positionAux) - 1;
1087         return rank(myicsa->bD, positionAux) - 1;
1088 }
1089
1090
1091 // Devolve o seguinte enteiro do texto (a partir do estado)
1092 unsigned int displayCSANext(ticsa *myicsa) {
1093         #ifdef PSI_HUFFMANRLE
1094                 myicsa->displayCSAState=getHuffmanPsiValue(&(myicsa->hcPsi),myicsa->displayCSAState);
1095         #endif
1096         #ifdef PSI_GONZALO
1097                 myicsa->displayCSAState = getGonzaloPsiValue(&(myicsa->gcPsi),myicsa->displayCSAState);
1098         #endif
1099         #ifdef PSI_DELTACODES
1100                 myicsa->displayCSAState = getDeltaPsiValue(&(myicsa->dcPsi),myicsa->displayCSAState);
1101         #endif
1102         return rank(myicsa->bD, myicsa->displayCSAState) - 1;
1103 }
1104
1105
1106 // Mostra as estructuras creadas
1107 void showStructsCSA(ticsa *myicsa) {
1108
1109         unsigned int index;
1110
1111         // ESTRUCTURAS PARA CSA
1112         printf("Basic CSA structures:\n\n");
1113
1114         // VALORES DA FUNCI�N PSI (decodificando)
1115         printf("\tPSI: (Sampling period = %d)\n", myicsa->T_Psi);
1116         for(index=0; index < myicsa->suffixArraySize; index++)
1117                 #ifdef PSI_HUFFMANRLE
1118                         printf("\tPsi[%d] = %d\n", index, getHuffmanPsiValue(&(myicsa->hcPsi),index));
1119                 #endif
1120                 #ifdef PSI_GONZALO
1121                         printf("\tPsi[%d] = %d\n", index, getGonzaloPsiValue(&(myicsa->gcPsi),index));
1122                 #endif
1123                 #ifdef PSI_DELTACODES
1124                         printf("\tPsi[%d] = %d\n", index, getDeltaPsiValue(&(myicsa->dcPsi),index));
1125                 #endif
1126         printf("\n");
1127
1128         // VECTOR D DE SADAKANE CO DIRECTORIO DE RANK ASOCIADO
1129         printf("\tD = ");
1130         showBitVector(myicsa->D, myicsa->suffixArraySize);
1131         printf("\n\nSuperbloques de D:\n");
1132         {       uint ns;
1133                 uint nb;
1134                 ns = myicsa->bD->sSize;
1135                 nb= myicsa->bD->bSize;
1136                 for(index=0; index<ns; index++) {
1137                         //printf("\tDs[%d] = %d\n", index, Dir.Ds[index]);
1138                         printf("\tDs[%d] = %d\n", index, myicsa->bD->sdata[index]);
1139                 }
1140                 printf("\nBloques de D:\n");
1141
1142                 for(index=0; index<nb; index++) {
1143                         //printf("\tDb[%d] = %d\n", index, Dir.Db[index]);
1144                         printf("\tDb[%d] = %d\n", index, myicsa->bD->bdata[index]);
1145                 }
1146                 printf("\n\n");
1147         }
1148         // ESTRUCTURAS PARA ACCEDER O ARRAY DE SUFIXOS E A SUA INVERSA
1149         printf("Suffix Array Sampling Structures: (Sampling period = %d)\n", myicsa->T_A);
1150         printf("\tSuffix Array Samples:\n");
1151         for(index=0; index < myicsa->samplesASize; index++)
1152                 printf("\tSamplesA[%d] = %d\n", index, myicsa->samplesA[index]);
1153         printf("\n");
1154         printf("\tInverse Suffix Array Samples:\n");
1155         for(index=0; index < myicsa->samplesASize; index++)
1156                 printf("\tSamplesAInv[%d] = %d\n", index, myicsa->samplesAInv[index]);
1157         printf("\n");
1158
1159 }
1160
1161
1162 // Comparacion de Sadakane entre un patron (pattern) y el sufijo en la posicion p del array de sufijos
1163 // IMPORTANTE EVITAR ULTIMA CHAMADA A PSI
1164 int SadCSACompare(ticsa *myicsa, uint *pattern, uint patternSize, uint p) {
1165
1166         register unsigned int j, i, currentInteger, diff;
1167
1168         i = p;
1169         j = 0;
1170
1171         while(1) {
1172                 currentInteger = rank(myicsa->bD, i) - 1;
1173                 diff = pattern[j++] - currentInteger;
1174                 if(diff) return diff;
1175                 if(j == patternSize) return 0;
1176                 else
1177                         #ifdef PSI_HUFFMANRLE
1178                                 i=getHuffmanPsiValue(&(myicsa->hcPsi),i);
1179                         #endif
1180                         #ifdef PSI_GONZALO
1181                                 i=getGonzaloPsiValue(&(myicsa->gcPsi),i);
1182                         #endif
1183                         #ifdef PSI_DELTACODES
1184                                 i=getDeltaPsiValue(&(myicsa->dcPsi),i);
1185                         #endif
1186         }
1187
1188 }
1189
1190
1191 // Acceso a array de sufixos A
1192 inline uint A(ticsa *myicsa, uint position) {
1193
1194         register uint timesPsi, sampleValue;
1195         register uint T_A = myicsa->T_A;
1196
1197         uint proba = position;
1198
1199         timesPsi = 0;
1200         while(!bitget(myicsa->BA, position)) {
1201
1202                 #ifdef PSI_HUFFMANRLE
1203                         position=getHuffmanPsiValue(&(myicsa->hcPsi),position);
1204                 #endif
1205                 #ifdef PSI_GONZALO
1206                         position=getGonzaloPsiValue(&(myicsa->gcPsi),position);
1207                 #endif
1208                 #ifdef PSI_DELTACODES
1209                         position=getDeltaPsiValue(&(myicsa->dcPsi),position);
1210                 #endif
1211                 timesPsi++;
1212
1213         }
1214         sampleValue = myicsa->samplesA[rank(myicsa->bBA, position)-1];
1215
1216         return sampleValue - timesPsi;
1217
1218 }
1219
1220
1221 // Acceso 'a inversa do array de sufixos
1222 inline uint inverseA(ticsa *myicsa, uint offset) {
1223
1224         register uint index, inverseValue;
1225         register uint T_AInv = myicsa->T_AInv;
1226
1227         inverseValue = myicsa->samplesAInv[offset/T_AInv];
1228         for(index=0; index<(offset%T_AInv); index++)
1229                 #ifdef PSI_HUFFMANRLE
1230                         inverseValue=getHuffmanPsiValue(&(myicsa->hcPsi),inverseValue);
1231                 #endif
1232                 #ifdef PSI_GONZALO
1233                    inverseValue = getGonzaloPsiValue(&(myicsa->gcPsi),inverseValue);
1234                 #endif
1235                 #ifdef PSI_DELTACODES
1236                         inverseValue = getDeltaPsiValue(&(myicsa->dcPsi),inverseValue);
1237                 #endif
1238         return inverseValue;
1239
1240 }
1241
1242 // Initializes the parameters of the index.
1243 uint parametersCSA(ticsa *myicsa, char *build_options){
1244         char delimiters[] = " =;";
1245         int j,num_parameters;
1246         char ** parameters;
1247         int ssA,ssAinv,ssPsi,nsHuff,psiSearchFactor;
1248
1249         ssA    = DEFAULT_A_SAMPLING_PERIOD;
1250         ssAinv = DEFAULT_A_INV_SAMPLING_PERIOD;
1251         ssPsi  = DEFAULT_PSI_SAMPLING_PERIOD;
1252         nsHuff = DEFAULT_nsHUFF;
1253         psiSearchFactor = DEFAULT_PSI_BINARY_SEARCH_FACTOR;
1254
1255         if (build_options != NULL) {
1256         parse_parameters(build_options,&num_parameters, &parameters, delimiters);
1257         for (j=0; j<num_parameters;j++) {
1258
1259                 if ((strcmp(parameters[j], "sA") == 0 ) && (j < num_parameters-1) ) {
1260                         ssA=atoi(parameters[j+1]);
1261                 }
1262                 if ((strcmp(parameters[j], "sAinv") == 0 ) && (j < num_parameters-1) ) {
1263                         ssAinv=atoi(parameters[j+1]);
1264                 }
1265                 if ((strcmp(parameters[j], "sPsi") == 0 ) && (j < num_parameters-1) ) {
1266                         ssPsi=atoi(parameters[j+1]);
1267                 }
1268                 if ((strcmp(parameters[j], "nsHuff") == 0 ) && (j < num_parameters-1) ) {
1269                         nsHuff=atoi(parameters[j+1]);
1270                         nsHuff *=1024;
1271                 }
1272                 if ((strcmp(parameters[j], "psiSF") == 0 ) && (j < num_parameters-1) ) {
1273                         psiSearchFactor=atoi(parameters[j+1]);
1274                 }
1275                 j++;
1276         }
1277         free_parameters(num_parameters, &parameters);
1278         }
1279
1280         myicsa->T_A = ssA;
1281         myicsa->T_AInv = ssAinv;
1282         myicsa->T_Psi = ssPsi;
1283         myicsa->tempNSHUFF = nsHuff;
1284         myicsa->psiSearchFactorJump = psiSearchFactor * ssPsi;
1285
1286         printf("\n\t parameters for iCSA: sampleA=%d, sampleAinv=%d, samplePsi=%d",ssA,ssAinv,ssPsi);
1287         printf("\n\t              : nsHuff=%d, psiSearchFactor = %d --> jump = %d", nsHuff,psiSearchFactor, myicsa->psiSearchFactorJump);
1288 }