2 * Copyright (C) 2005, Diego Arroyuelo, all rights reserved.
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.
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.
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
26 int compare(const void *p1, const void *p2) {
27 return ((auxbwd *)p1)->key - ((auxbwd *)p2)->key;
31 perm createPerm(uint *elems, uint nelems, uint t, static_bitsequence_builder * bmb) {
33 uint *b, *baux, nextelem, i, j, bptr,
34 aux, antbptr,nbwdptrs, elem,nbits, firstelem, cyclesize;
39 P->nbits = bits(nelems-1);
40 nbits = bits(nelems-1);
43 P->bwdptrs = new uint[uint_len(nelems,nbits)];
44 assert(P->bwdptrs!=NULL);
46 for (i=0; i<nelems; i++) {
47 uint bg = get_field(elems, nbits, i);
49 set_field(P->bwdptrs, nbits, bg, i);
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++)
60 baux = new uint[uint_len(nelems,1)];
61 for(i=0;i<uint_len(nelems,1);i++)
65 for (i = 0; i < nelems; i++) {
66 if (bitget(baux,i) == 0) {
67 nextelem = j = bptr = antbptr = i;
72 while ((elem=get_field(elems,nbits,j)) != nextelem) {
77 auxbwdptr[nbwdptrs].key = j;
78 auxbwdptr[nbwdptrs++].pointer = bptr;
87 auxbwdptr[nbwdptrs].key = nextelem;
88 auxbwdptr[nbwdptrs++].pointer = bptr;
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);
102 // printf(" %d ",get_field(P->bwdptrs,nbits,i));
105 P->bmap = bmb->build(b, nelems);
109 delete [] (auxbwdptr);
115 void destroyPerm(perm P) {
117 if (P->bmap) delete P->bmap;
118 delete [] P->bwdptrs;
124 uint inversePerm(perm P, uint i) {
127 j = get_field(P->bwdptrs,P->nbits,i);
131 while (((elem=get_field(P->elems,P->nbits,j)) != i)&&(!P->bmap->access(j)))
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)
145 // gets the ith element of a perm P
147 uint getelemPerm(perm P, uint i) {
148 return get_field(P->elems, P->nbits, i);
152 uint savePerm(perm P, FILE *f) {
156 if (fwrite(&P->nelems,sizeof(uint),1,f) != 1) {
157 fprintf(stderr,"Error: Cannot write Permutation on file\n");
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");
167 aux = ((P->nelems+W-1)/W);
171 if (fwrite(&v,sizeof(uint),1,f) != 1) {
172 fprintf(stderr,"Error: Cannot write Permutation on file\n");
179 if (fwrite(&v,sizeof(uint),1,f) != 1) {
180 fprintf(stderr,"Error: Cannot write Permutation on file\n");
185 if (fwrite(&P->nbwdptrs,sizeof(uint),1,f) != 1) {
186 fprintf(stderr,"Error: Cannot write Permutation on file\n");
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");
195 if (fwrite(&P->t,sizeof(uint),1,f) != 1) {
196 fprintf(stderr,"Error: Cannot write Permutation on file\n");
203 perm loadPerm(FILE *f) {
208 P = new struct sperm; //(struct sperm*) malloc(sizeof(struct sperm));
210 if (fread(&P->nelems,sizeof(uint),1,f) != 1) {
211 fprintf(stderr,"Error: Cannot read Permutation from file\n");
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));
218 if (fread(P->elems,sizeof(uint),aux,f) != aux) {
219 fprintf(stderr,"Error: Cannot read Permutation from file\n");
223 if (fread(&v,sizeof(uint),1,f) != 1) {
224 fprintf(stderr,"Error: Cannot read Permutation from file\n");
229 P->bmap = static_bitsequence::load(f);
233 if (fread(&P->nbwdptrs,sizeof(uint),1,f) != 1) {
234 fprintf(stderr,"Error: Cannot read Permutation from file\n");
238 aux = uint_len(P->nbwdptrs,P->nbits);
239 P->bwdptrs = new uint[aux]; //(uint*) malloc(aux*sizeof(uint));
241 if (fread(P->bwdptrs,sizeof(uint),aux,f) != aux) {
242 fprintf(stderr,"Error: Cannot read Permutation from file\n");
246 if (fread(&P->t,sizeof(uint),1,f) != 1) {
247 fprintf(stderr,"Error: Cannot read Permutation from file\n");
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));