From 60f0f1a447b2b89ca99589c68333d72bcdeb263d Mon Sep 17 00:00:00 2001 From: kim Date: Tue, 27 Jan 2009 12:29:05 +0000 Subject: [PATCH] Add some more file from libcds HEAD git-svn-id: svn+ssh://idea.nguyen.vg/svn/sxsi/trunk/XMLTree@71 3cdefd35-fc62-479d-8e8d-bae585ffb9ca --- libcds/src/static_permutation/perm.cpp | 260 ++++++++++++++++++ libcds/src/static_permutation/perm.h | 88 ++++++ .../static_permutation/static_permutation.cpp | 33 +++ .../static_permutation/static_permutation.h | 49 ++++ .../static_permutation_builder.h | 40 +++ .../static_permutation_builder_mrrr.cpp | 35 +++ .../static_permutation_builder_mrrr.h | 46 ++++ .../static_permutation_mrrr.cpp | 62 +++++ .../static_permutation_mrrr.h | 51 ++++ 9 files changed, 664 insertions(+) create mode 100755 libcds/src/static_permutation/perm.cpp create mode 100755 libcds/src/static_permutation/perm.h create mode 100644 libcds/src/static_permutation/static_permutation.cpp create mode 100644 libcds/src/static_permutation/static_permutation.h create mode 100644 libcds/src/static_permutation/static_permutation_builder.h create mode 100644 libcds/src/static_permutation/static_permutation_builder_mrrr.cpp create mode 100644 libcds/src/static_permutation/static_permutation_builder_mrrr.h create mode 100644 libcds/src/static_permutation/static_permutation_mrrr.cpp create mode 100644 libcds/src/static_permutation/static_permutation_mrrr.h 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 +#include +#include + +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; ibwdptrs, 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= 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;ibwdptrs[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)); +} diff --git a/libcds/src/static_permutation/perm.h b/libcds/src/static_permutation/perm.h new file mode 100755 index 0000000..20d0bf6 --- /dev/null +++ b/libcds/src/static_permutation/perm.h @@ -0,0 +1,88 @@ +/* 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 +#include +#include + +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 diff --git a/libcds/src/static_permutation/static_permutation.cpp b/libcds/src/static_permutation/static_permutation.cpp new file mode 100644 index 0000000..b47059b --- /dev/null +++ b/libcds/src/static_permutation/static_permutation.cpp @@ -0,0 +1,33 @@ +/* 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 * 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; +} diff --git a/libcds/src/static_permutation/static_permutation.h b/libcds/src/static_permutation/static_permutation.h new file mode 100644 index 0000000..7d8ffef --- /dev/null +++ b/libcds/src/static_permutation/static_permutation.h @@ -0,0 +1,49 @@ +/* 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 + +#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 + +#endif diff --git a/libcds/src/static_permutation/static_permutation_builder.h b/libcds/src/static_permutation/static_permutation_builder.h new file mode 100644 index 0000000..2a860ad --- /dev/null +++ b/libcds/src/static_permutation/static_permutation_builder.h @@ -0,0 +1,40 @@ +/* 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 +#include + +/** 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 + +#endif diff --git a/libcds/src/static_permutation/static_permutation_builder_mrrr.cpp b/libcds/src/static_permutation/static_permutation_builder_mrrr.cpp new file mode 100644 index 0000000..996beb4 --- /dev/null +++ b/libcds/src/static_permutation/static_permutation_builder_mrrr.cpp @@ -0,0 +1,35 @@ +/* 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::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); +} diff --git a/libcds/src/static_permutation/static_permutation_builder_mrrr.h b/libcds/src/static_permutation/static_permutation_builder_mrrr.h new file mode 100644 index 0000000..051d7e2 --- /dev/null +++ b/libcds/src/static_permutation/static_permutation_builder_mrrr.h @@ -0,0 +1,46 @@ +/* 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 +#include +#include + +/** 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 + +#endif diff --git a/libcds/src/static_permutation/static_permutation_mrrr.cpp b/libcds/src/static_permutation/static_permutation_mrrr.cpp new file mode 100644 index 0000000..7bb7a69 --- /dev/null +++ b/libcds/src/static_permutation/static_permutation_mrrr.cpp @@ -0,0 +1,62 @@ +/* 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::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; +} diff --git a/libcds/src/static_permutation/static_permutation_mrrr.h b/libcds/src/static_permutation/static_permutation_mrrr.h new file mode 100644 index 0000000..0f196a5 --- /dev/null +++ b/libcds/src/static_permutation/static_permutation_mrrr.h @@ -0,0 +1,51 @@ +/* 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 +#include +#include + +/** 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 -- 2.17.1