1 /* static_sequence_gmr.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.h>
24 static_sequence_gmr::static_sequence_gmr(uint * sequence, uint n, uint chunk_length, static_bitsequence_builder * bmb, static_sequence_builder * ssb) {
26 if(len%chunk_length) len+=chunk_length-len%chunk_length;
27 uint * new_seq = new uint[len];
29 for(uint i=0;i<n;i++){
30 new_seq[i] = sequence[i];
31 sigma = max(sigma,new_seq[i]);
34 for(uint i=n;i<len;i++)
37 this->chunk_length = chunk_length;
38 build(new_seq,bmb,ssb);
42 static_sequence_gmr::static_sequence_gmr() {
45 static_sequence_gmr::~static_sequence_gmr() {
47 for (uint i=0;i<len/chunk_length;i++)
53 void static_sequence_gmr::build(uint * sequence, static_bitsequence_builder * bmb, static_sequence_builder * ssb) {
54 uint num_chunks = len/chunk_length;
55 chunk = new static_sequence*[num_chunks];
57 for (uint i=0;i<num_chunks;i++) {
58 chunk[i] = ssb->build(sequence+i*chunk_length, chunk_length);
59 //cout << "1." << i << endl; cout.flush();
60 assert(chunk[i]!=NULL);
62 uint * ones = get_ones(sequence);
63 uint *B_bitmap = new uint[(2+len+(unsigned long long)num_chunks*sigma)/W+1];
64 assert(B_bitmap!=NULL);
65 for (uint i=0;i<(2+len+(unsigned long long)num_chunks*sigma)/W+1;i++)
68 for (unsigned long long i=0;i<(unsigned long long)num_chunks*sigma;i++) {
69 for (uint j=0;j<ones[i];j++) {
70 bitset(B_bitmap, pos);
76 //cout << "5 pos=" << pos << endl; cout.flush();
77 B = bmb->build(B_bitmap, pos);
78 //cout << "6" << endl; cout.flush();
84 uint * static_sequence_gmr::get_ones(uint * sequence) {
85 uint * ones = new uint[(unsigned long long)(len/chunk_length)*sigma];
87 for (uint i=0;i<(unsigned long long)(len/chunk_length)*sigma;i++) ones[i] = 0;
88 for (uint i=0;i<len;i++) {
89 uint whichChunk = (uint)(((unsigned long long)sequence[i]*len+i)/chunk_length);
96 uint static_sequence_gmr::rank(uint c, uint j) {
98 uint i = j/chunk_length;
99 uint bp = (c)*(len/chunk_length);
100 uint rank_pos = B->select0(bp);
101 uint prev = rank_pos-bp+1;
102 uint sum = B->rank1(B->select0(bp+i)) - prev;
103 uint cr = chunk[i]->rank(c,j-i*chunk_length);
108 uint static_sequence_gmr::select(uint c, uint j) {
110 uint rank_pos = B->select0(c*(len/chunk_length));
111 uint prev = B->rank1(rank_pos);
113 uint block = (B->select1(sel));
114 uint i = block-sel+1;
115 uint desp = B->rank1(B->select0((i)))-prev;
116 if (desp+1==0) desp=0;
117 uint rchunk = i%(len/chunk_length);
118 return (rchunk*chunk_length)+chunk[rchunk]->select(c, j-desp);
122 uint static_sequence_gmr::access(uint j) {
123 return chunk[j/chunk_length]->access(j%chunk_length);
127 uint static_sequence_gmr::size() {
129 for (uint i=0;i<len/chunk_length;i++)
130 s += sizeof(void*)+chunk[i]->size();
131 return s+B->size()+sizeof(static_sequence_gmr);
134 uint static_sequence_gmr::save(FILE *fp) {
136 wr = fwrite(&wr,sizeof(uint),1,fp);
137 wr += fwrite(&len,sizeof(uint),1,fp);
138 wr += fwrite(&sigma,sizeof(uint),1,fp);
139 wr += fwrite(&chunk_length,sizeof(uint),1,fp);
141 if(B->save(fp)) return 1;
142 for(uint i=0;i<len/chunk_length;i++)
143 if(chunk[i]->save(fp)) return 1;
147 static_sequence_gmr * static_sequence_gmr::load(FILE *fp) {
149 if(fread(&rd,sizeof(uint),1,fp)!=1) return NULL;
150 if(rd!=GMR_HDR) return NULL;
151 static_sequence_gmr * ret = new static_sequence_gmr();
152 rd = fread(&ret->len,sizeof(uint),1,fp);
153 rd += fread(&ret->sigma,sizeof(uint),1,fp);
154 rd += fread(&ret->chunk_length,sizeof(uint),1,fp);
159 ret->B = static_bitsequence::load(fp);
164 ret->chunk = new static_sequence*[ret->len/ret->chunk_length];
165 for(uint i=0;i<ret->len/ret->chunk_length;i++) {
166 ret->chunk[i] = static_sequence::load(fp);
167 if(ret->chunk[i]==NULL) {