1 /* static_sequence_gmr_chunk.cpp
2 * Copyright (C) 2008, Francisco Claude, 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
22 #include "static_sequence_gmr_chunk.h"
25 static_sequence_gmr_chunk::static_sequence_gmr_chunk(uint * sequence, uint chunk_length, static_bitsequence_builder *bmb, static_permutation_builder *pmb) {
27 for(uint i=0;i<chunk_length;i++) {
28 sigma = max(sigma,sequence[i]);
30 uint * X_bitmap = new uint[uint_len(1+chunk_length+sigma,1)];
31 assert(X_bitmap!=NULL);
32 for(uint i=0;i<uint_len(1+chunk_length+sigma,1);i++) X_bitmap[i]=0;
33 uint pi_blen = bits(chunk_length-1);
34 uint * pi = new uint[uint_len(pi_blen,chunk_length)];
36 for(uint i=0;i<uint_len(pi_blen,chunk_length);i++) pi[i] = 0;
38 uint * counter = new uint[sigma+2];
39 for(uint c=0;c<=sigma+1;c++) counter[c]=0;
40 for(uint i=0;i<chunk_length;i++) counter[sequence[i]+1]++;
42 for(uint c=0;c<sigma;c++) {
44 for(uint i=0;i<counter[c+1];i++) {
45 bitset(X_bitmap, X_pos);
48 counter[c+1]+=counter[c];
51 for(uint i=0;i<chunk_length;i++) {
52 set_field(pi, pi_blen,counter[sequence[i]], i);
53 counter[sequence[i]]++;
55 //cout << "pi_blen=" << pi_blen << endl;
56 this->X = bmb->build(X_bitmap,X_pos); //new BitRankW32Int(X_bitmap, X_pos, true,20);
59 //cout << "a" << endl; cout.flush();
60 this->permutation = pmb->build(pi,chunk_length); //createPerm(pi, chunk_length, t);
61 //cout << "a" << endl; cout.flush();
62 assert(permutation!=NULL);
64 this->len = chunk_length;
68 static_sequence_gmr_chunk::static_sequence_gmr_chunk() {
71 static_sequence_gmr_chunk::~static_sequence_gmr_chunk() {
77 uint static_sequence_gmr_chunk::access(uint j) {
78 uint invPerm = permutation->rev_pi(j); //inversePerm(permutation, j);
79 //cout << "invPerm=" << invPerm << endl;
80 uint rank_pos = X->select1(invPerm+1);
81 //cout << "rank_pos=" << rank_pos << endl;
82 uint ret = rank_pos - X->rank1(rank_pos);// - 1;
83 //cout << "ret = " << ret << endl;
88 uint static_sequence_gmr_chunk::select(uint i, uint j) {
89 uint pos = X->select0(i+1) + j - i -1;
90 /*cout << "pos=" << pos << endl;
91 cout << "pos'=" << X->rank1(X->select0(i+1)+j) << endl;
92 cout << "perm_pos=" << permutation->pi(pos) << endl;*/
93 return permutation->pi(pos); //getelemPerm(permutation, pos);
97 uint static_sequence_gmr_chunk::rank(uint i, uint j) {
98 uint ini = X->select0(i+1)-i;
100 uint fin = X->select0(i+2);
101 if(fin<i+2) return 0;
103 if(fin<ini) return 0;
104 if(permutation->pi(ini) > j) return 0;
105 if(permutation->pi(ini) == j) return 1;
106 if(ini==fin) return 1;
108 uint med = (ini+fin)/2;
109 uint elem = permutation->pi(med); //getelemPerm(permutation, med);
110 if(elem >= j) fin = med;
113 while(fin>ini_o && permutation->pi(fin)>j) fin--;
118 uint static_sequence_gmr_chunk::size() {
119 return sizeof(static_sequence_gmr_chunk)+permutation->size()+X->size();
122 uint static_sequence_gmr_chunk::save(FILE *fp) {
123 uint wr = GMR_CHUNK_HDR;
124 wr = fwrite(&wr,sizeof(uint),1,fp);
125 wr += fwrite(&len,sizeof(uint),1,fp);
126 wr += fwrite(&sigma,sizeof(uint),1,fp);
128 if(X->save(fp)) return 1;
129 if(permutation->save(fp)) return 1;
133 static_sequence_gmr_chunk * static_sequence_gmr_chunk::load(FILE *fp) {
135 if(fread(&rd,sizeof(uint),1,fp)!=1) return NULL;
136 if(rd!=GMR_CHUNK_HDR) return NULL;
137 static_sequence_gmr_chunk * ret = new static_sequence_gmr_chunk();
138 rd = fread(&ret->len,sizeof(uint),1,fp);
139 rd += fread(&ret->sigma,sizeof(uint),1,fp);
140 ret->X = static_bitsequence::load(fp);
141 ret->permutation = static_permutation::load(fp);
142 if(rd!=2 || ret->X==NULL || ret->permutation==NULL) {
143 /*cout << "rd=" << rd << endl;
144 cout << "X =" << ret->X << endl;
145 cout << "P =" << ret->permutation << endl;*/