X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=libcds%2Fsrc%2Fstatic_permutation%2Fperm.cpp;fp=libcds%2Fsrc%2Fstatic_permutation%2Fperm.cpp;h=d2a40a18c5e79daa1d413d54f911eb626e1197f6;hb=60f0f1a447b2b89ca99589c68333d72bcdeb263d;hp=0000000000000000000000000000000000000000;hpb=52cb7bbcda67f4676335cdd4eb96d4d87ad1445d;p=SXSI%2FXMLTree.git

diff --git a/libcds/src/static_permutation/perm.cpp b/libcds/src/static_permutation/perm.cpp
new file mode 100755
index 0000000..d2a40a1
--- /dev/null
+++ b/libcds/src/static_permutation/perm.cpp
@@ -0,0 +1,260 @@
+/* perm.cpp
+ * Copyright (C) 2005, Diego Arroyuelo, all rights reserved.
+ *
+ * Permutation
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
+ *
+ */
+
+#include <perm.h>
+#include <cmath>
+#include <cassert>
+
+int compare(const void *p1, const void *p2) {
+  return  ((auxbwd *)p1)->key - ((auxbwd *)p2)->key;
+}
+
+
+perm createPerm(uint *elems, uint nelems, uint t, static_bitsequence_builder * bmb) {
+  perm P;
+  uint *b, *baux, nextelem, i, j, bptr,
+    aux, antbptr,nbwdptrs, elem,nbits, firstelem, cyclesize;
+  auxbwd *auxbwdptr;
+  P = new struct sperm;
+  P->elems  = elems;
+  P->nelems = nelems;
+  P->nbits  = bits(nelems-1);
+  nbits = bits(nelems-1);
+  P->t = t;
+  if (t==1) {
+    P->bwdptrs = new uint[uint_len(nelems,nbits)];
+    assert(P->bwdptrs!=NULL);
+    P->nbwdptrs = nelems;
+    for (i=0; i<nelems; i++) {
+      uint bg = get_field(elems, nbits, i);
+      assert(bg<nelems);
+      set_field(P->bwdptrs, nbits, bg, i);
+    }
+    P->bmap = NULL;
+  }
+  else {
+    auxbwdptr = new auxbwd[(t+((int)ceil((double)nelems/t)))];
+    assert(auxbwdptr!=NULL);
+    b = new uint[uint_len(nelems,1)];
+    for(i=0;i<uint_len(nelems,1);i++)
+      b[i]=0;
+    assert(b!=NULL);    
+    baux = new uint[uint_len(nelems,1)];
+    for(i=0;i<uint_len(nelems,1);i++)
+      baux[i] = 0;
+    assert(baux!=NULL);
+    nbwdptrs = 0;
+    for (i = 0; i < nelems; i++) {
+      if (bitget(baux,i) == 0) {
+        nextelem = j = bptr = antbptr = i;
+        aux = 0;
+        bitset(baux, j);
+        cyclesize = 0;
+        firstelem = j;
+        while ((elem=get_field(elems,nbits,j)) != nextelem) {
+          j = elem;
+          bitset(baux, j);
+          aux++;
+          if (aux >= t) {
+            auxbwdptr[nbwdptrs].key = j;
+            auxbwdptr[nbwdptrs++].pointer = bptr;
+            antbptr = bptr;
+            bptr    = j;
+            aux     = 0;
+            bitset(b, j);
+          }
+          cyclesize++;
+        }
+        if (cyclesize >= t) {
+          auxbwdptr[nbwdptrs].key = nextelem;
+          auxbwdptr[nbwdptrs++].pointer = bptr;
+          bitset(b, nextelem);
+        }
+      }
+    }
+    qsort(auxbwdptr, nbwdptrs, sizeof(auxbwd), &compare);
+    aux = uint_len(nbwdptrs,P->nbits);
+    P->bwdptrs = new uint[aux];
+    assert(P->bwdptrs!=NULL);
+    for(i=0;i<aux;i++) P->bwdptrs[i] = 0;
+    P->nbwdptrs = nbwdptrs;
+    for (i = 0; i < nbwdptrs; i++) {
+      set_field(P->bwdptrs, nbits, i, auxbwdptr[i].pointer);
+      //if(i<5) 
+      //  printf(" %d ",get_field(P->bwdptrs,nbits,i));
+    }
+    //printf("\n");
+    P->bmap = bmb->build(b, nelems);
+    //delete [] P->bmap;
+    delete [] b;
+    delete [] (baux);
+    delete [] (auxbwdptr);
+  }
+  return P;
+}
+
+
+void destroyPerm(perm P) {
+  delete [] P->elems;
+  if (P->bmap) delete P->bmap;
+  delete [] P->bwdptrs;
+  delete P;
+}
+
+
+// Computes P-1[i]
+uint inversePerm(perm P, uint i) {
+  uint j, elem;
+  if (P->t==1) {
+    j = get_field(P->bwdptrs,P->nbits,i); 
+  }
+  else {
+    j = i;
+    while (((elem=get_field(P->elems,P->nbits,j)) != i)&&(!P->bmap->access(j)))
+      j = elem;
+
+    if (elem != i) {
+      // follows the backward pointer
+      j = get_field(P->bwdptrs, P->nbits, P->bmap->rank1(j-1));
+      while ((elem = get_field(P->elems,P->nbits,j))!= i)
+        j = elem;
+    }
+  }
+  return j;
+}
+
+
+// gets the ith element of a perm P
+
+uint getelemPerm(perm P, uint i) {
+  return get_field(P->elems, P->nbits, i);
+}
+
+
+uint savePerm(perm P, FILE *f) {
+  uint aux;
+  uint v;
+
+  if (fwrite(&P->nelems,sizeof(uint),1,f) != 1) {
+    fprintf(stderr,"Error: Cannot write Permutation on file\n");
+    exit(1);
+  }
+
+  aux = uint_len(P->nelems,P->nbits);
+  if (fwrite(P->elems,sizeof(uint),aux,f) != aux) {
+    fprintf(stderr,"Error: Cannot write Permutation on file\n");
+    exit(1);
+  }
+
+  aux = ((P->nelems+W-1)/W);
+
+  if (P->bmap) {
+    v=1;
+    if (fwrite(&v,sizeof(uint),1,f) != 1) {
+      fprintf(stderr,"Error: Cannot write Permutation on file\n");
+      exit(1);
+    }
+    P->bmap->save(f);
+  }
+  else {
+    v=0;
+    if (fwrite(&v,sizeof(uint),1,f) != 1) {
+      fprintf(stderr,"Error: Cannot write Permutation on file\n");
+      exit(1);
+    }
+  }
+
+  if (fwrite(&P->nbwdptrs,sizeof(uint),1,f) != 1) {
+    fprintf(stderr,"Error: Cannot write Permutation on file\n");
+    exit(1);
+  }
+
+  aux = uint_len(P->nbwdptrs,P->nbits);
+  if (fwrite(P->bwdptrs,sizeof(uint),aux,f) != aux) {
+    fprintf(stderr,"Error: Cannot write Permutation on file\n");
+    exit(1);
+  }
+  if (fwrite(&P->t,sizeof(uint),1,f) != 1) {
+    fprintf(stderr,"Error: Cannot write Permutation on file\n");
+    exit(1);
+  }
+  return 0;
+}
+
+
+perm loadPerm(FILE *f) {
+  uint aux;
+  perm P;
+  uint v;
+
+  P = new struct sperm;          //(struct sperm*) malloc(sizeof(struct sperm));
+
+  if (fread(&P->nelems,sizeof(uint),1,f) != 1) {
+    fprintf(stderr,"Error: Cannot read Permutation from file\n");
+    exit(1);
+  }
+  P->nbits = bits(P->nelems-1);
+  aux = uint_len(P->nelems,P->nbits);
+  P->elems = new uint[aux];      //(uint *)malloc(aux*sizeof(uint));
+
+  if (fread(P->elems,sizeof(uint),aux,f) != aux) {
+    fprintf(stderr,"Error: Cannot read Permutation from file\n");
+    exit(1);
+  }
+
+  if (fread(&v,sizeof(uint),1,f) != 1) {
+    fprintf(stderr,"Error: Cannot read Permutation from file\n");
+    exit(1);
+  }
+
+  if (v) {
+    P->bmap = static_bitsequence::load(f);
+  }
+  else P->bmap = NULL;
+
+  if (fread(&P->nbwdptrs,sizeof(uint),1,f) != 1) {
+    fprintf(stderr,"Error: Cannot read Permutation from file\n");
+    exit(1);
+  }
+
+  aux = uint_len(P->nbwdptrs,P->nbits);
+  P->bwdptrs = new uint[aux];    //(uint*) malloc(aux*sizeof(uint));
+
+  if (fread(P->bwdptrs,sizeof(uint),aux,f) != aux) {
+    fprintf(stderr,"Error: Cannot read Permutation from file\n");
+    exit(1);
+  }
+
+  if (fread(&P->t,sizeof(uint),1,f) != 1) {
+    fprintf(stderr,"Error: Cannot read Permutation from file\n");
+    exit(1);
+  }
+
+  return P;
+}
+
+
+uint sizeofPerm(perm P) {
+  return sizeof(struct sperm) +
+    ((uint_len(P->nelems,P->nbits))*sizeof(uint)) +
+    ((P->bmap)?(P->bmap->size()):0) +
+    ((uint_len(P->nbwdptrs,P->nbits))*sizeof(uint));
+}