--- /dev/null
+/* 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));
+}
--- /dev/null
+/* perm.h
+ * 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
+ *
+ */
+
+#ifndef PERMINCLUDED
+#define PERMINCLUDED
+
+#include <basics.h>
+#include <static_bitsequence.h>
+#include <static_bitsequence_builder.h>
+
+typedef struct sperm
+{
+ uint *elems; // elements of the permutation
+ uint nelems; // # of elements
+ static_bitsequence * bmap; // bitmap allowing rank() queries in O(1) time
+ uint *bwdptrs; // array of backward pointers
+ uint nbits; // log(nelems)
+ uint nbwdptrs; // # of backward pointers
+ uint t;
+} *perm;
+
+typedef struct
+{
+ uint key;
+ uint pointer;
+} auxbwd;
+
+/** Creates a permutation
+ *
+ * @author Diego Arroyuelo
+ */
+perm createPerm(uint *elems, uint nelems, uint t, static_bitsequence_builder * bmb);
+
+/** Gets the i-th element of the permutation
+ *
+ * @author Diego Arroyuelo
+ */
+uint getelemPerm(perm P, uint i);
+
+/** Destroys a permutation
+ *
+ * @author Diego Arroyuelo
+ */
+void destroyPerm(perm P);
+
+/** Get pi(i)^{-1}
+ *
+ * @author Diego Arroyuelo
+ */
+uint inversePerm(perm P, uint i);
+
+/** Saves a permutation
+ *
+ * @author Diego Arroyuelo
+ */
+uint savePerm(perm P, FILE *f);
+
+/** Loads a permutation
+ *
+ * @author Diego Arroyuelo
+ */
+perm loadPerm(FILE *f);
+
+/** Returns the size of the data structure
+ *
+ * @author Diego Arroyuelo
+ */
+uint sizeofPerm(perm P);
+
+#endif
--- /dev/null
+/* static_permutation.cpp
+ * Copyright (C) 2008, Francisco Claude, 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 <static_permutation.h>
+
+static_permutation * static_permutation::load(FILE *fp) {
+ uint rd;
+ if(fread(&rd,sizeof(uint),1,fp)!=1) return NULL;
+ fseek(fp,-sizeof(uint),SEEK_CUR);
+ switch(rd) {
+ case STATIC_PERMUTATION_MRRR_HDR: return static_permutation_mrrr::load(fp);
+ }
+ return NULL;
+}
--- /dev/null
+/* static_permutation.h
+ * Copyright (C) 2008, Francisco Claude, 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
+ *
+ */
+
+#ifndef _STATIC_PERMUTATION_H
+#define _STATIC_PERMUTATION_H
+
+#include <basics.h>
+
+#define STATIC_PERMUTATION_MRRR_HDR 2
+
+/** Base class for static permutations
+ * @author Francisco Claude
+ */
+class static_permutation {
+ public:
+ virtual ~static_permutation() {}
+ /** Computes the i-th element of the permutation */
+ virtual uint pi(uint i)=0;
+ /** Computes the inverse of i */
+ virtual uint rev_pi(uint i)=0;
+ /** Saves the permutation to fp, returns 0 in case of success */
+ virtual uint save(FILE *fp)=0;
+ /** Returns the size of the permutation */
+ virtual uint size()=0;
+ /** Loads a static_permutation from fp */
+ static static_permutation * load(FILE *fp);
+};
+
+#include <static_permutation_mrrr.h>
+
+#endif
--- /dev/null
+/* static_permutation_builder.h
+ * Copyright (C) 2008, Francisco Claude, all rights reserved.
+ *
+ * Permutation builder
+ *
+ * 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
+ *
+ */
+
+#ifndef _STATIC_PERMUTATION_BUILDER_H
+#define _STATIC_PERMUTATION_BUILDER_H
+
+#include <basics.h>
+#include <static_permutation.h>
+
+/** Base class for static permutation builders
+ * @author Francisco Claude
+ */
+class static_permutation_builder {
+ public:
+ virtual ~static_permutation_builder() {}
+ /** Returns a new permutation build for perm */
+ virtual static_permutation * build(uint * perm, uint len)=0;
+};
+
+#include <static_permutation_builder_mrrr.h>
+
+#endif
--- /dev/null
+/* static_permutation_builder_mrrr.cpp
+ * Copyright (C) 2008, Francisco Claude, all rights reserved.
+ *
+ * Permutation builder
+ *
+ * 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 <static_permutation_builder_mrrr.h>
+
+static_permutation_builder_mrrr::static_permutation_builder_mrrr(uint t, static_bitsequence_builder * bmb) {
+ this->t = t;
+ this->bmb = bmb;
+}
+
+static_permutation_builder_mrrr::~static_permutation_builder_mrrr() {
+ //delete bmb;
+}
+
+static_permutation * static_permutation_builder_mrrr::build(uint * perm, uint len) {
+ return new static_permutation_mrrr(perm,len,t,bmb);
+}
--- /dev/null
+/* static_permutation_builder_mrrr.h
+ * Copyright (C) 2008, Francisco Claude, all rights reserved.
+ *
+ * Permutation builder
+ *
+ * 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
+ *
+ */
+
+#ifndef _STATIC_PERMUTATION_BUILDER_MRRR_H
+#define _STATIC_PERMUTATION_BUILDER_MRRR_H
+
+#include <static_permutation_builder.h>
+#include <static_bitsequence.h>
+#include <static_bitsequence_builder.h>
+
+/** Base class for static permutation builders
+ * @author Francisco Claude
+ */
+class static_permutation_builder_mrrr : public static_permutation_builder {
+ public:
+ static_permutation_builder_mrrr(uint t, static_bitsequence_builder * bmb);
+ virtual ~static_permutation_builder_mrrr();
+ /** Returns a new permutation build for perm */
+ virtual static_permutation * build(uint * perm, uint len);
+
+ protected:
+ uint t;
+ static_bitsequence_builder * bmb;
+};
+
+#include <static_permutation_builder_mrrr.h>
+
+#endif
--- /dev/null
+/* static_permutation_mrrr.cpp
+ * Copyright (C) 2008, Francisco Claude, 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 <static_permutation_mrrr.h>
+
+static_permutation_mrrr::static_permutation_mrrr(uint * elems, uint nelems, uint t, static_bitsequence_builder * bmb) {
+ permutation = createPerm(elems, nelems, t, bmb);
+}
+
+static_permutation_mrrr::static_permutation_mrrr() {
+}
+
+static_permutation_mrrr::~static_permutation_mrrr() {
+ destroyPerm(permutation);
+}
+
+uint static_permutation_mrrr::size() {
+ return sizeof(static_permutation)+sizeofPerm(permutation);
+}
+
+uint static_permutation_mrrr::pi(uint i) {
+ return getelemPerm(permutation,i);
+}
+
+uint static_permutation_mrrr::rev_pi(uint i) {
+ return inversePerm(permutation,i);
+}
+
+uint static_permutation_mrrr::save(FILE *fp) {
+ uint wr = STATIC_PERMUTATION_MRRR_HDR;
+ wr = fwrite(&wr,sizeof(uint),1,fp);
+ if(wr!=1) return 1;
+ return savePerm(permutation,fp);
+}
+
+static_permutation_mrrr * static_permutation_mrrr::load(FILE *fp) {
+ uint rd;
+ if(fread(&rd,sizeof(uint),1,fp)!=1) return NULL;
+ if(rd!=STATIC_PERMUTATION_MRRR_HDR) return NULL;
+ static_permutation_mrrr * ret = new static_permutation_mrrr();
+ ret->permutation = loadPerm(fp);
+ return ret;
+}
--- /dev/null
+/* static_permutation_mrrr.h
+ * Copyright (C) 2008, Francisco Claude, 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
+ *
+ */
+
+#ifndef _STATIC_PERMUTATION_MRRR_H
+#define _STATIC_PERMUTATION_MRRR_H
+
+#include <basics.h>
+#include <static_permutation.h>
+#include <perm.h>
+
+/** Wrapper for Diego Arroyuelo's implementation of Munro et al.'s permutations.
+ * @author Francisco Claude
+ */
+class static_permutation_mrrr : public static_permutation {
+ public:
+ static_permutation_mrrr(uint * elems, uint nelems, uint t, static_bitsequence_builder * bmb);
+ virtual ~static_permutation_mrrr();
+ /** Computes the i-th element of the permutation */
+ virtual uint pi(uint i);
+ /** Computes the inverse of i */
+ virtual uint rev_pi(uint i);
+ /** Saves the permutation to fp, returns 0 in case of success */
+ virtual uint save(FILE *fp);
+ /** Returns the size of the permutation */
+ virtual uint size();
+ /** Loads a static_permutation from fp */
+ static static_permutation_mrrr * load(FILE *fp);
+ protected:
+ perm permutation;
+ static_permutation_mrrr();
+};
+
+#endif
projects / SXSI / XMLTree.git / commitdiff