libcds/src/static_permutation/perm.cpp

   1 /* perm.cpp
   2  * Copyright (C) 2005, Diego Arroyuelo, all rights reserved.
   3  *
   4  * Permutation
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2.1 of the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with this library; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  19  *
  20  */
  21
  22 #include <perm.h>
  23 #include <cmath>
  24 #include <cassert>
  25
  26 int compare(const void *p1, const void *p2) {
  27   return  ((auxbwd *)p1)->key - ((auxbwd *)p2)->key;
  28 }
  29
  30
  31 perm createPerm(uint *elems, uint nelems, uint t, static_bitsequence_builder * bmb) {
  32   perm P;
  33   uint *b, *baux, nextelem, i, j, bptr,
  34     aux, antbptr,nbwdptrs, elem,nbits, firstelem, cyclesize;
  35   auxbwd *auxbwdptr;
  36   P = new struct sperm;
  37   P->elems  = elems;
  38   P->nelems = nelems;
  39   P->nbits  = bits(nelems-1);
  40   nbits = bits(nelems-1);
  41   P->t = t;
  42   if (t==1) {
  43     P->bwdptrs = new uint[uint_len(nelems,nbits)];
  44     assert(P->bwdptrs!=NULL);
  45     P->nbwdptrs = nelems;
  46     for (i=0; i<nelems; i++) {
  47       uint bg = get_field(elems, nbits, i);
  48       assert(bg<nelems);
  49       set_field(P->bwdptrs, nbits, bg, i);
  50     }
  51     P->bmap = NULL;
  52   }
  53   else {
  54     auxbwdptr = new auxbwd[(t+((int)ceil((double)nelems/t)))];
  55     assert(auxbwdptr!=NULL);
  56     b = new uint[uint_len(nelems,1)];
  57     for(i=0;i<uint_len(nelems,1);i++)
  58       b[i]=0;
  59     assert(b!=NULL);
  60     baux = new uint[uint_len(nelems,1)];
  61     for(i=0;i<uint_len(nelems,1);i++)
  62       baux[i] = 0;
  63     assert(baux!=NULL);
  64     nbwdptrs = 0;
  65     for (i = 0; i < nelems; i++) {
  66       if (bitget(baux,i) == 0) {
  67         nextelem = j = bptr = antbptr = i;
  68         aux = 0;
  69         bitset(baux, j);
  70         cyclesize = 0;
  71         firstelem = j;
  72         while ((elem=get_field(elems,nbits,j)) != nextelem) {
  73           j = elem;
  74           bitset(baux, j);
  75           aux++;
  76           if (aux >= t) {
  77             auxbwdptr[nbwdptrs].key = j;
  78             auxbwdptr[nbwdptrs++].pointer = bptr;
  79             antbptr = bptr;
  80             bptr    = j;
  81             aux     = 0;
  82             bitset(b, j);
  83           }
  84           cyclesize++;
  85         }
  86         if (cyclesize >= t) {
  87           auxbwdptr[nbwdptrs].key = nextelem;
  88           auxbwdptr[nbwdptrs++].pointer = bptr;
  89           bitset(b, nextelem);
  90         }
  91       }
  92     }
  93     qsort(auxbwdptr, nbwdptrs, sizeof(auxbwd), &compare);
  94     aux = uint_len(nbwdptrs,P->nbits);
  95     P->bwdptrs = new uint[aux];
  96     assert(P->bwdptrs!=NULL);
  97     for(i=0;i<aux;i++) P->bwdptrs[i] = 0;
  98     P->nbwdptrs = nbwdptrs;
  99     for (i = 0; i < nbwdptrs; i++) {
 100       set_field(P->bwdptrs, nbits, i, auxbwdptr[i].pointer);
 101       //if(i<5)
 102       //  printf(" %d ",get_field(P->bwdptrs,nbits,i));
 103     }
 104     //printf("\n");
 105     P->bmap = bmb->build(b, nelems);
 106     //delete [] P->bmap;
 107     delete [] b;
 108     delete [] (baux);
 109     delete [] (auxbwdptr);
 110   }
 111   return P;
 112 }
 113
 114
 115 void destroyPerm(perm P) {
 116   delete [] P->elems;
 117   if (P->bmap) delete P->bmap;
 118   delete [] P->bwdptrs;
 119   delete P;
 120 }
 121
 122
 123 // Computes P-1[i]
 124 uint inversePerm(perm P, uint i) {
 125   uint j, elem;
 126   if (P->t==1) {
 127     j = get_field(P->bwdptrs,P->nbits,i);
 128   }
 129   else {
 130     j = i;
 131     while (((elem=get_field(P->elems,P->nbits,j)) != i)&&(!P->bmap->access(j)))
 132       j = elem;
 133
 134     if (elem != i) {
 135       // follows the backward pointer
 136       j = get_field(P->bwdptrs, P->nbits, P->bmap->rank1(j-1));
 137       while ((elem = get_field(P->elems,P->nbits,j))!= i)
 138         j = elem;
 139     }
 140   }
 141   return j;
 142 }
 143
 144
 145 // gets the ith element of a perm P
 146
 147 uint getelemPerm(perm P, uint i) {
 148   return get_field(P->elems, P->nbits, i);
 149 }
 150
 151
 152 uint savePerm(perm P, FILE *f) {
 153   uint aux;
 154   uint v;
 155
 156   if (fwrite(&P->nelems,sizeof(uint),1,f) != 1) {
 157     fprintf(stderr,"Error: Cannot write Permutation on file\n");
 158     exit(1);
 159   }
 160
 161   aux = uint_len(P->nelems,P->nbits);
 162   if (fwrite(P->elems,sizeof(uint),aux,f) != aux) {
 163     fprintf(stderr,"Error: Cannot write Permutation on file\n");
 164     exit(1);
 165   }
 166
 167   aux = ((P->nelems+W-1)/W);
 168
 169   if (P->bmap) {
 170     v=1;
 171     if (fwrite(&v,sizeof(uint),1,f) != 1) {
 172       fprintf(stderr,"Error: Cannot write Permutation on file\n");
 173       exit(1);
 174     }
 175     P->bmap->save(f);
 176   }
 177   else {
 178     v=0;
 179     if (fwrite(&v,sizeof(uint),1,f) != 1) {
 180       fprintf(stderr,"Error: Cannot write Permutation on file\n");
 181       exit(1);
 182     }
 183   }
 184
 185   if (fwrite(&P->nbwdptrs,sizeof(uint),1,f) != 1) {
 186     fprintf(stderr,"Error: Cannot write Permutation on file\n");
 187     exit(1);
 188   }
 189
 190   aux = uint_len(P->nbwdptrs,P->nbits);
 191   if (fwrite(P->bwdptrs,sizeof(uint),aux,f) != aux) {
 192     fprintf(stderr,"Error: Cannot write Permutation on file\n");
 193     exit(1);
 194   }
 195   if (fwrite(&P->t,sizeof(uint),1,f) != 1) {
 196     fprintf(stderr,"Error: Cannot write Permutation on file\n");
 197     exit(1);
 198   }
 199   return 0;
 200 }
 201
 202
 203 perm loadPerm(FILE *f) {
 204   uint aux;
 205   perm P;
 206   uint v;
 207
 208   P = new struct sperm;          //(struct sperm*) malloc(sizeof(struct sperm));
 209
 210   if (fread(&P->nelems,sizeof(uint),1,f) != 1) {
 211     fprintf(stderr,"Error: Cannot read Permutation from file\n");
 212     exit(1);
 213   }
 214   P->nbits = bits(P->nelems-1);
 215   aux = uint_len(P->nelems,P->nbits);
 216   P->elems = new uint[aux];      //(uint *)malloc(aux*sizeof(uint));
 217
 218   if (fread(P->elems,sizeof(uint),aux,f) != aux) {
 219     fprintf(stderr,"Error: Cannot read Permutation from file\n");
 220     exit(1);
 221   }
 222
 223   if (fread(&v,sizeof(uint),1,f) != 1) {
 224     fprintf(stderr,"Error: Cannot read Permutation from file\n");
 225     exit(1);
 226   }
 227
 228   if (v) {
 229     P->bmap = static_bitsequence::load(f);
 230   }
 231   else P->bmap = NULL;
 232
 233   if (fread(&P->nbwdptrs,sizeof(uint),1,f) != 1) {
 234     fprintf(stderr,"Error: Cannot read Permutation from file\n");
 235     exit(1);
 236   }
 237
 238   aux = uint_len(P->nbwdptrs,P->nbits);
 239   P->bwdptrs = new uint[aux];    //(uint*) malloc(aux*sizeof(uint));
 240
 241   if (fread(P->bwdptrs,sizeof(uint),aux,f) != aux) {
 242     fprintf(stderr,"Error: Cannot read Permutation from file\n");
 243     exit(1);
 244   }
 245
 246   if (fread(&P->t,sizeof(uint),1,f) != 1) {
 247     fprintf(stderr,"Error: Cannot read Permutation from file\n");
 248     exit(1);
 249   }
 250
 251   return P;
 252 }
 253
 254
 255 uint sizeofPerm(perm P) {
 256   return sizeof(struct sperm) +
 257     ((uint_len(P->nelems,P->nbits))*sizeof(uint)) +
 258     ((P->bmap)?(P->bmap->size()):0) +
 259     ((uint_len(P->nbwdptrs,P->nbits))*sizeof(uint));
 260 }