1 /* static_sequence_wvtree_noptrs.cpp
2 * Copyright (C) 2008, Francisco Claude, all rights reserved.
4 * static_sequence_wvtree_noptrs definition
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_wvtree_noptrs.h>
24 static_sequence_wvtree_noptrs::static_sequence_wvtree_noptrs(uint * symbols, uint n, static_bitsequence_builder * bmb, alphabet_mapper * am, bool deleteSymbols) {
29 symbols[i] = am->map(symbols[i]);
30 max_v=max_value(symbols,n);
32 uint *occurrences=new uint[max_v+1];
33 for(uint i=0;i<=max_v;i++) occurrences[i]=0;
35 occurrences[symbols[i]]++;
37 for(uint i=0;i<max_v;i++)
38 if(occurrences[i]==0) to_add++;
39 uint * new_symb = new uint[n+to_add];
41 new_symb[i] = symbols[i];
50 for(uint i=0;i<max_v;i++)
51 if(occurrences[i]==0) {
56 uint new_n = n+to_add;
57 for(uint i=1;i<=max_v;i++)
58 occurrences[i] += occurrences[i-1];
59 uint *oc = new uint[(new_n+1)/W+1];
60 for(uint i=0;i<(new_n+1)/W+1;i++)
62 for(uint i=0;i<=max_v;i++)
63 bitset(oc,occurrences[i]-1);
65 occ = bmb->build(oc,new_n+1);
66 delete [] occurrences;
68 uint ** _bm=new uint*[height];
69 for(uint i=0;i<height;i++) {
70 _bm[i] = new uint[new_n/W+1];
71 for(uint j=0;j<new_n/W+1;j++)
74 build_level(_bm,new_symb,0,new_n,0);
75 bitstring = new static_bitsequence*[height];
76 for(uint i=0;i<height;i++) {
77 bitstring[i] = bmb->build(_bm[i],new_n);
84 symbols[i] = am->unmap(symbols[i]);
86 // delete [] new_symb; // already deleted in build_level()!
90 static_sequence_wvtree_noptrs::static_sequence_wvtree_noptrs() {
93 static_sequence_wvtree_noptrs::~static_sequence_wvtree_noptrs() {
94 for(uint i=0;i<height;i++)
101 uint static_sequence_wvtree_noptrs::save(FILE *fp) {
102 uint wr = WVTREE_NOPTRS_HDR;
103 wr = fwrite(&wr,sizeof(uint),1,fp);
104 wr += fwrite(&n,sizeof(uint),1,fp);
105 wr += fwrite(&max_v,sizeof(uint),1,fp);
106 wr += fwrite(&height,sizeof(uint),1,fp);
108 if(am->save(fp)) return 1;
109 for(uint i=0;i<height;i++)
110 if(bitstring[i]->save(fp)) return 1;
111 if(occ->save(fp)) return 1;
115 static_sequence_wvtree_noptrs * static_sequence_wvtree_noptrs::load(FILE *fp) {
117 if(fread(&rd,sizeof(uint),1,fp)!=1) return NULL;
118 if(rd!=WVTREE_NOPTRS_HDR) return NULL;
119 static_sequence_wvtree_noptrs * ret = new static_sequence_wvtree_noptrs();
120 rd = fread(&ret->n,sizeof(uint),1,fp);
121 rd += fread(&ret->max_v,sizeof(uint),1,fp);
122 rd += fread(&ret->height,sizeof(uint),1,fp);
127 ret->am = alphabet_mapper::load(fp);
133 ret->bitstring = new static_bitsequence*[ret->height];
134 for(uint i=0;i<ret->height;i++) {
135 ret->bitstring[i] = static_bitsequence::load(fp);
136 if(ret->bitstring[i]==NULL){
141 ret->occ = static_bitsequence::load(fp);
149 uint static_sequence_wvtree_noptrs::access(uint pos) {
154 while(level<height) {
155 assert(pos>=start && pos<=end);
156 if(bitstring[level]->access(pos)) {
158 pos=bitstring[level]->rank1(pos-1)-bitstring[level]->rank1(start-1);
159 start=(bitstring[level]->rank1(end)-bitstring[level]->rank1(start-1));
164 pos=pos-start-(bitstring[level]->rank1(pos)-bitstring[level]->rank1(start-1));
165 end=end-start-(bitstring[level]->rank1(end)-bitstring[level]->rank1(start-1));
171 return am->unmap(ret);
174 uint static_sequence_wvtree_noptrs::rank(uint symbol, uint pos) {
175 symbol = am->map(symbol);
180 while(level<height) {
181 if(is_set(symbol,level)) {
182 pos=bitstring[level]->rank1(pos)-bitstring[level]->rank1(start-1)-1;
184 start=(bitstring[level]->rank1(end)-bitstring[level]->rank1(start-1));
189 pos=pos-start+bitstring[level]->rank1(start-1)-bitstring[level]->rank1(pos);
191 end=end-start-(bitstring[level]->rank1(end)-bitstring[level]->rank1(start-1));
196 if(count==0) return 0;
201 vector<int> static_sequence_wvtree_noptrs::access(uint i, uint j, uint min, uint max)
203 vector<int> resultSet;
204 // cout << "height = " << height << endl;
205 access(resultSet, i, j, am->map(min), am->map(max), 0, 0, 0, n-1);
209 void static_sequence_wvtree_noptrs::access(vector<int> &result, uint i, uint j, uint min, uint max, uint l, uint pivot, uint start, uint end)
211 uint symbol = pivot | (1 << (height-l-1));
212 //std::cout << "At l = " << l << ", [" << i << ", " << j << "], [" << min << ", " << max << "], [" << start << ", " << end << "], symbol = " << symbol << std::endl;
216 if (i <= j && pivot >= min && pivot <= max && start <= end)
217 result.push_back(am->unmap((int)pivot));
221 if (j < i || max < min || end < start)
227 uint newi = i + bitstring[l]->rank1(start-1) - bitstring[l]->rank1(i-1);
228 uint newend = end - (bitstring[l]->rank1(end) - bitstring[l]->rank1(start-1));
229 uint newj = j + bitstring[l]->rank1(start-1) - bitstring[l]->rank1(j) + 1;
231 uint newmax = max < symbol - 1 ? max : symbol - 1;
233 access(result, newi, newj-1, min, newmax, l+1, pivot, start, newend);
239 uint newstart = (bitstring[l]->rank1(end)-bitstring[l]->rank1(start-1));
240 newstart = end - newstart + 1;
241 uint newi = bitstring[l]->rank1(i-1)-bitstring[l]->rank1(start-1) + newstart;
242 uint newj = bitstring[l]->rank1(j)-bitstring[l]->rank1(start-1) + newstart;
244 uint newmin = min > symbol ? min : symbol;
246 access(result, newi, newj-1, newmin, max, l+1, symbol, newstart, end);
251 vector<int> static_sequence_wvtree_noptrs::accessAll(uint i, uint j)
253 vector<int> resultSet;
257 resultSet.reserve(j-i+1);
258 accessAll(resultSet, i, j, 0, 0, 0, n-1);
262 void static_sequence_wvtree_noptrs::accessAll(vector<int> &result, uint i, uint j, uint l, uint pivot, uint start, uint end)
264 uint symbol = pivot | (1 << (height-l-1));
265 // std::cout << "At l = " << l << ", [" << i << ", " << j << "], [" << start << ", " << end << "], symbol = " << symbol << std::endl;
269 if (i <= j && start <= end)
270 result.push_back(am->unmap((int)pivot));
274 if (j < i || end < start)
279 uint newi = i + bitstring[l]->rank1(start-1) - bitstring[l]->rank1(i-1);
280 uint newend = end - (bitstring[l]->rank1(end) - bitstring[l]->rank1(start-1));
281 uint newj = j + bitstring[l]->rank1(start-1) - bitstring[l]->rank1(j) + 1;
284 accessAll(result, newi, newj-1, l+1, pivot, start, newend);
289 uint newstart = (bitstring[l]->rank1(end)-bitstring[l]->rank1(start-1));
290 newstart = end - newstart + 1;
291 uint newi = bitstring[l]->rank1(i-1)-bitstring[l]->rank1(start-1) + newstart;
292 uint newj = bitstring[l]->rank1(j)-bitstring[l]->rank1(start-1) + newstart;
295 accessAll(result, newi, newj-1, l+1, symbol, newstart, end);
300 uint static_sequence_wvtree_noptrs::count(uint i, uint j, uint min, uint max)
302 return count(i, j, am->map(min), am->map(max), 0, 0, 0, n-1);
305 uint static_sequence_wvtree_noptrs::count(uint i, uint j, uint min, uint max, uint l, uint pivot, uint start, uint end)
307 uint symbol = pivot | (1 << (height-l-1));
308 //std::cout << "At l = " << l << ", [" << i << ", " << j << "], [" << min << ", " << max << "], [" << start << ", " << end << "], symbol = " << symbol << std::endl;
312 if (i <= j && pivot >= min && pivot <= max && start <= end)
317 if (j < i || max < min || end < start)
324 uint newi = i + bitstring[l]->rank1(start-1) - bitstring[l]->rank1(i-1);
325 uint newend = end - (bitstring[l]->rank1(end) - bitstring[l]->rank1(start-1));
326 uint newj = j + bitstring[l]->rank1(start-1) - bitstring[l]->rank1(j) + 1;
328 uint newmax = max < symbol - 1 ? max : symbol - 1;
330 result += count(newi, newj-1, min, newmax, l+1, pivot, start, newend);
336 uint newstart = (bitstring[l]->rank1(end)-bitstring[l]->rank1(start-1));
337 newstart = end - newstart + 1;
338 uint newi = bitstring[l]->rank1(i-1)-bitstring[l]->rank1(start-1) + newstart;
339 uint newj = bitstring[l]->rank1(j)-bitstring[l]->rank1(start-1) + newstart;
341 uint newmin = min > symbol ? min : symbol;
343 result += count(newi, newj-1, newmin, max, l+1, symbol, newstart, end);
350 inline uint get_start(uint symbol, uint mask) {
354 inline uint get_end(uint symbol, uint mask) {
355 return get_start(symbol,mask)+!mask+1;
358 uint static_sequence_wvtree_noptrs::select(uint symbol, uint j) {
359 symbol = am->map(symbol);
360 uint mask = (1<<height)-2;
362 uint level = height-1;
365 uint start = get_start(symbol,mask);
366 uint end = min(max_v+1,start+sum);
367 start = (start==0)?0:(occ->select1(start)+1);
368 end = occ->select1(end+1)-1;
369 if(is_set(symbol,level)) {
370 uint ones_start = bitstring[level]->rank1(start-1);
371 pos = bitstring[level]->select1(ones_start+pos)-start+1;
374 uint ones_start = bitstring[level]->rank1(start-1);
375 pos = bitstring[level]->select0(start-ones_start+pos)-start+1;
385 uint static_sequence_wvtree_noptrs::size() {
386 uint ptrs = sizeof(static_sequence_wvtree_noptrs)+height*sizeof(static_sequence*);
387 uint bytesBitstrings = 0;
388 for(uint i=0;i<height;i++)
389 bytesBitstrings += bitstring[i]->size();
390 return bytesBitstrings+occ->size()+ptrs;
393 void static_sequence_wvtree_noptrs::build_level(uint **bm, uint *symbols, uint level, uint length, uint offset) {
400 for(uint i=0;i<length;i++)
401 if(!is_set(symbols[i],level))
403 uint cright=length-cleft;
404 uint *left=new uint[cleft], *right=new uint[cright];
406 for(uint i=0;i<length;i++)
407 if(!is_set(symbols[i],level)) {
408 left[cleft++]=symbols[i];
409 bitclean(bm[level],offset+i);
412 right[cright++]=symbols[i];
413 bitset(bm[level],offset+i);
419 build_level(bm,left,level+1,cleft,offset);
420 left = 0; // Gets deleted in recursion.
421 build_level(bm,right,level+1,cright,offset+cleft);
422 right = 0; // Gets deleted in recursion.
427 uint static_sequence_wvtree_noptrs::max_value(uint *symbols, uint n) {
429 for(uint i=0;i<n;i++)
430 max_v = max(symbols[i],max_v);
434 uint static_sequence_wvtree_noptrs::bits(uint val) {
443 bool static_sequence_wvtree_noptrs::is_set(uint val, uint ind) {
445 return (val & (1<<(height-ind-1)))!=0;
449 uint static_sequence_wvtree_noptrs::set(uint val, uint ind) {
451 return val | (1<<(height-ind-1));