SDSL: Succinct Data Structure Library
A C++ template library for succinct data structures
|
00001 /* sdsl - succinct data structures library 00002 Copyright (C) 2011 Simon Gog 00003 00004 This program is free software: you can redistribute it and/or modify 00005 it under the terms of the GNU General Public License as published by 00006 the Free Software Foundation, either version 3 of the License, or 00007 (at your option) any later version. 00008 00009 This program is distributed in the hope that it will be useful, 00010 but WITHOUT ANY WARRANTY; without even the implied warranty of 00011 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00012 GNU General Public License for more details. 00013 00014 You should have received a copy of the GNU General Public License 00015 along with this program. If not, see http://www.gnu.org/licenses/ . 00016 */ 00022 #ifndef INCLUDED_SDSL_RRR_VECTOR_15 00023 #define INCLUDED_SDSL_RRR_VECTOR_15 00024 00025 #include "int_vector.hpp" 00026 #include "bitmagic.hpp" 00027 #include "util.hpp" 00028 #include "rrr_helper.hpp" // for binomial helper class 00029 #include "rrr_vector.hpp" 00030 #include <vector> 00031 #include <algorithm> // for next_permutation 00032 #include <iostream> 00033 00035 namespace sdsl 00036 { 00037 00038 // Helper class 00039 template<uint8_t n> 00040 class binomial 00041 { 00042 public: 00043 typedef uint32_t number_type; 00044 private: 00045 00046 static class impl 00047 { 00048 public: 00049 static const int MAX_SIZE=32; 00050 uint8_t m_space_for_bt[n+1]; 00051 uint8_t m_space_for_bt_pair[256*(n==15)]; 00052 uint64_t m_C[MAX_SIZE]; 00053 int_vector<32> m_nr_to_bin; 00054 int_vector<32> m_bin_to_nr; 00055 00056 impl() { 00057 m_nr_to_bin.resize(1<<n); 00058 m_bin_to_nr.resize(1<<n); 00059 for (int i=0, cnt=0, class_cnt=0; i<=n; ++i) { 00060 m_C[i] = cnt; 00061 class_cnt = 0; 00062 std::vector<bool> b(n,0); 00063 for (int j=0; j<i; ++j) b[n-j-1] = 1; 00064 do { 00065 uint32_t x=0; 00066 for (int k=0; k<n; ++k) 00067 x |= ((uint32_t)b[n-k-1])<<(n-1-k); 00068 m_nr_to_bin[cnt] = x; 00069 m_bin_to_nr[x] = class_cnt; 00070 ++cnt; 00071 ++class_cnt; 00072 } while (next_permutation(b.begin(), b.end())); 00073 if (class_cnt == 1) 00074 m_space_for_bt[i] = 0; 00075 else 00076 m_space_for_bt[i] = bit_magic::l1BP(class_cnt)+1; 00077 // cout << cnt << " " << class_cnt << " " << (int)m_space_for_bt[i] << endl; 00078 } 00079 if (n == 15) { 00080 for (int x=0; x<256; ++x) { 00081 m_space_for_bt_pair[x] = m_space_for_bt[x>>4] + m_space_for_bt[x&0x0F]; 00082 } 00083 } 00084 } 00085 } iii; 00086 00087 public: 00088 00089 static inline uint8_t space_for_bt(uint32_t i) { 00090 return iii.m_space_for_bt[i]; 00091 } 00092 00093 static inline uint32_t nr_to_bin(uint8_t k, uint32_t nr) { 00094 return iii.m_nr_to_bin[iii.m_C[k]+nr]; 00095 } 00096 00097 static inline uint32_t bin_to_nr(uint32_t bin) { 00098 return iii.m_bin_to_nr[bin]; 00099 } 00100 00101 static inline uint8_t space_for_bt_pair(uint8_t x) { 00102 return iii.m_space_for_bt_pair[x]; 00103 } 00104 00105 static inline uint8_t popcount(number_type x) { 00106 return bit_magic::b1Cnt(x); 00107 } 00108 00109 static inline uint8_t select(number_type x, uint32_t i) { 00110 return bit_magic::i1BP(x, i); 00111 } 00112 00113 template<class bit_vector_type> 00114 static inline number_type decode_btnr(const bit_vector_type& bv, 00115 typename bit_vector_type::size_type btnrp, 00116 uint8_t btnrlen) { 00117 return bv.get_int(btnrp, btnrlen); 00118 } 00119 00120 template<class bit_vector_type> 00121 static inline uint8_t get_bt(const bit_vector_type& bv, 00122 typename bit_vector_type::size_type pos, 00123 uint8_t block_size) { 00124 return bit_magic::b1Cnt(bv.get_int(pos, block_size)); 00125 } 00126 00127 template<class bit_vector_type> 00128 static void set_bt(bit_vector_type& bv, 00129 typename bit_vector_type::size_type pos, 00130 number_type bt, 00131 uint8_t space_for_bt) { 00132 bv.set_int(pos, bt, space_for_bt); 00133 } 00134 00135 static inline number_type Li1Mask(uint8_t off) { 00136 return bit_magic::Li1Mask[off]; 00137 } 00138 }; 00139 template<uint8_t n> 00140 typename binomial<n>::impl binomial<n>::iii; 00141 00142 00143 00145 00154 template<class wt_type> 00155 class rrr_vector<15, wt_type> 00156 { 00157 public: 00158 typedef bit_vector::size_type size_type; 00159 typedef bit_vector::value_type value_type; 00160 00161 friend class rrr_rank_support<0, 15, wt_type>; 00162 friend class rrr_rank_support<1, 15, wt_type>; 00163 friend class rrr_select_support<0, 15, wt_type>; 00164 friend class rrr_select_support<1, 15, wt_type>; 00165 00166 typedef rrr_rank_support<1, 15, wt_type> rank_1_type; // typedef for default types for rank and select 00167 typedef rrr_rank_support<0, 15, wt_type> rank_0_type; 00168 typedef rrr_select_support<1, 15, wt_type> select_1_type; 00169 typedef rrr_select_support<0, 15, wt_type> select_0_type; 00170 00171 enum { block_size = 15 }; 00172 typedef binomial<block_size> bi_type; 00173 private: 00174 size_type m_size; // length of the original bit_vector 00175 uint16_t m_sample_rate; 00176 wt_type m_bt; // data structure, which stores the block types (bt). The block type equals the number 00177 // of ones in a block. Another option for this data structure is wt_huff 00178 bit_vector m_btnr; // data structure, which stores the block type numbers of the blocks 00179 int_vector<> m_btnrp; // sample pointers into btnr 00180 int_vector<> m_rank; // sample rank values 00181 00182 void copy(const rrr_vector& rrr) { 00183 m_size = rrr.m_size; 00184 m_sample_rate = rrr.m_sample_rate; 00185 m_bt = rrr.m_bt; 00186 m_btnr = rrr.m_btnr; 00187 m_btnrp = rrr.m_btnrp; 00188 m_rank = rrr.m_rank; 00189 } 00190 public: 00191 const wt_type& bt; 00192 const bit_vector& btnr; 00193 00195 rrr_vector(uint16_t sample_rate=32):m_size(0), m_sample_rate(sample_rate), bt(m_bt), btnr(m_btnr) {}; 00196 00198 rrr_vector(const rrr_vector& rrr): bt(m_bt), btnr(m_btnr) { 00199 copy(rrr); 00200 } 00201 00203 00206 rrr_vector(const bit_vector& bv, uint16_t sample_rate=32): m_sample_rate(sample_rate), bt(m_bt), btnr(m_btnr) { 00207 m_size = bv.size(); 00208 int_vector<> bt_array; 00209 util::assign(bt_array, int_vector<>(m_size/block_size+1, 0, bit_magic::l1BP(block_size)+1)); 00210 // bt_array.set_int_width(bit_magic::l1BP(block_size)+1); 00211 // bt_array.resize((m_size+block_size)/block_size); 00212 00213 // (1) calculate the block types and store them in m_bt 00214 size_type pos = 0, i = 0, x; 00215 size_type btnr_pos = 0; 00216 size_type sum_rank = 0; 00217 while (pos + block_size <= m_size) { // handle all full blocks 00218 bt_array[ i++ ] = x = bit_magic::b1Cnt(bv.get_int(pos, block_size)); 00219 sum_rank += x; 00220 btnr_pos += bi_type::space_for_bt(x); 00221 pos += block_size; 00222 } 00223 if (pos < m_size) { // handle last full block 00224 bt_array[ i++ ] = x = bit_magic::b1Cnt(bv.get_int(pos, m_size - pos)); 00225 sum_rank += x; 00226 btnr_pos += bi_type::space_for_bt(x); 00227 } 00228 // cout << "# bt array initialized "<< endl; 00229 util::assign(m_btnr, bit_vector(std::max(btnr_pos, (size_type)64), 0)); // max necessary for case: block_size == 1 00230 util::assign(m_btnrp, int_vector<>((bt_array.size()+m_sample_rate-1)/m_sample_rate, 0, bit_magic::l1BP(btnr_pos)+1)); 00231 util::assign(m_rank, int_vector<>((bt_array.size()+m_sample_rate-1)/m_sample_rate + 1, 0, bit_magic::l1BP(sum_rank)+1)); 00232 00233 // (2) calculate block type numbers and pointers into btnr and rank samples 00234 pos = 0; i = 0; 00235 btnr_pos= 0, sum_rank = 0; 00236 while (pos + block_size <= m_size) { // handle all full blocks 00237 if ((i % m_sample_rate) == 0) { 00238 m_btnrp[ i/m_sample_rate ] = btnr_pos; 00239 m_rank[ i/m_sample_rate ] = sum_rank; 00240 } 00241 uint16_t space_for_bt = bi_type::space_for_bt(x=bt_array[i++]); 00242 sum_rank += x; 00243 if (space_for_bt) { 00244 m_btnr.set_int(btnr_pos, bi_type::bin_to_nr(bv.get_int(pos, block_size)), space_for_bt); 00245 } 00246 btnr_pos += space_for_bt; 00247 pos += block_size; 00248 } 00249 if (pos < m_size) { // handle last full block 00250 if ((i % m_sample_rate) == 0) { 00251 m_btnrp[ i/m_sample_rate ] = btnr_pos; 00252 m_rank[ i/m_sample_rate ] = sum_rank; 00253 } 00254 uint16_t space_for_bt = bi_type::space_for_bt(x=bt_array[i++]); 00255 sum_rank += x; 00256 if (space_for_bt) { 00257 m_btnr.set_int(btnr_pos, bi_type::bin_to_nr(bv.get_int(pos, m_size - pos)), space_for_bt); 00258 } 00259 btnr_pos += space_for_bt; 00260 } 00261 // for technical reasons add an additional element to m_rank 00262 m_rank[ m_rank.size()-1 ] = sum_rank; // sum_rank contains the total number of set bits in bv 00263 util::assign(m_bt, bt_array); 00264 } 00265 00267 void swap(rrr_vector& rrr) { 00268 if (this != &rrr) { 00269 std::swap(m_size, rrr.m_size); 00270 std::swap(m_sample_rate, rrr.m_sample_rate); 00271 m_bt.swap(rrr.m_bt); 00272 m_btnr.swap(rrr.m_btnr); 00273 m_btnrp.swap(rrr.m_btnrp); 00274 m_rank.swap(rrr.m_rank); 00275 } 00276 } 00277 00279 00282 value_type operator[](size_type i)const { 00283 size_type bt_idx = i/block_size ; 00284 uint8_t* bt = (uint8_t*)(m_bt.data()); 00285 uint8_t i_bt = *(bt + (bt_idx/2)); 00286 if (bt_idx%2 == 1) { 00287 i_bt >>= 4; 00288 } else { 00289 i_bt &= 0x0F; 00290 } 00291 if (i_bt == 0 or i_bt == block_size) { 00292 return i_bt > 0; 00293 } 00294 size_type sample_pos = bt_idx/m_sample_rate; 00295 size_type btnrp = m_btnrp[ sample_pos ]; 00296 size_type j = (sample_pos*m_sample_rate); 00297 bt += j/2; 00298 if (j%2 == 1 and j < bt_idx) { 00299 btnrp += bi_type::space_for_bt((*bt++)>>4); 00300 ++j; 00301 } 00302 while (j+1 < bt_idx) { 00303 btnrp += bi_type::space_for_bt_pair(*(bt++)); // decode two entries at once 00304 j+=2; 00305 } 00306 if (j < bt_idx) { 00307 btnrp += bi_type::space_for_bt((*bt)&0x0F); 00308 } 00309 00310 uint32_t btnr = m_btnr.get_int(btnrp, bi_type::space_for_bt(i_bt)); 00311 00312 uint8_t off = i % block_size; //i - bt_idx*block_size; 00313 return (bi_type::nr_to_bin(i_bt, btnr) >> off) & (uint32_t)1; 00314 } 00315 00317 rrr_vector& operator=(const rrr_vector& rrr) { 00318 if (this != &rrr) { 00319 copy(rrr); 00320 } 00321 return *this; 00322 } 00323 00325 size_type size()const { 00326 return m_size; 00327 } 00328 00330 size_type serialize(std::ostream& out, structure_tree_node* v=NULL, std::string name="")const { 00331 size_type written_bytes = 0; 00332 structure_tree_node* child = structure_tree::add_child(v, name, util::class_name(*this)); 00333 written_bytes += util::write_member(m_size, out, child, "size"); 00334 written_bytes += util::write_member(m_sample_rate, out, child, "sample_rate"); 00335 written_bytes += m_bt.serialize(out, child, "bt"); 00336 written_bytes += m_btnr.serialize(out, child, "btnr"); 00337 written_bytes += m_btnrp.serialize(out, child, "btnrp"); 00338 written_bytes += m_rank.serialize(out, child, "rank_samples"); 00339 structure_tree::add_size(child, written_bytes); 00340 return written_bytes; 00341 } 00342 00344 void load(std::istream& in) { 00345 util::read_member(m_size, in); 00346 util::read_member(m_sample_rate, in); 00347 m_bt.load(in); 00348 m_btnr.load(in); 00349 m_btnrp.load(in); 00350 m_rank.load(in); 00351 } 00352 00353 // Print information about the object to stdout. 00354 void print_info()const { 00355 size_type orig_bv_size = m_size; // size of the original bit vector in bits 00356 size_type rrr_size = util::get_size_in_bytes(*this)*8; 00357 size_type bt_size = util::get_size_in_bytes(m_bt)*8; 00358 size_type btnr_size = util::get_size_in_bytes(m_btnr)*8; 00359 size_type btnrp_and_rank_size = util::get_size_in_bytes(m_btnrp)*8 + util::get_size_in_bytes(m_rank)*8; 00360 std::cout << "#block_size\tsample_rate\torig_bv_size\trrr_size\tbt_size\tbtnr_size\tbtnrp_and_rank_size" << std::endl; 00361 std::cout << (int)block_size << "\t" << m_sample_rate << "\t"; 00362 std::cout << orig_bv_size << "\t" << rrr_size << "\t" << bt_size << "\t" << btnr_size << "\t" 00363 << btnrp_and_rank_size << std::endl; 00364 } 00365 }; 00366 00367 00369 00371 template<uint8_t b, class wt_type> 00372 class rrr_rank_support<b, 15, wt_type> 00373 { 00374 public: 00375 typedef rrr_vector<15, wt_type> bit_vector_type; 00376 typedef typename bit_vector_type::size_type size_type; 00377 typedef typename bit_vector_type::bi_type bi_type; 00378 00379 00380 private: 00381 const bit_vector_type* m_v; 00382 uint16_t m_sample_rate; 00383 // TODO cache for sequential ranks 00384 // mutable size_type m_last_bt; 00385 // mutable size_type m_last_w; // store the last decoded word 00386 // uint16_t m_space_for_bt[256]; 00387 public: 00389 00391 explicit rrr_rank_support(const bit_vector_type* v=NULL) { 00392 init(v); 00393 } 00394 00396 void init(const bit_vector_type* v=NULL) { 00397 set_vector(v); 00398 } 00399 00401 00406 const size_type rank(size_type i)const { 00407 size_type bt_idx = i/bit_vector_type::block_size; 00408 size_type sample_pos = bt_idx/m_sample_rate; 00409 size_type btnrp = m_v->m_btnrp[ sample_pos ]; 00410 size_type rank = m_v->m_rank[ sample_pos ]; 00411 size_type diff_rank = m_v->m_rank[ sample_pos+1 ] - rank; 00412 if (diff_rank == 0) { 00413 return rrr_rank_support_trait<b>::adjust_rank(rank, i); 00414 } else if (diff_rank == (size_type)bit_vector_type::block_size*m_sample_rate) { 00415 return rrr_rank_support_trait<b>::adjust_rank( 00416 rank + i - sample_pos*m_sample_rate*bit_vector_type::block_size, i); 00417 } 00418 uint8_t* bt = (uint8_t*)(m_v->m_bt.data()); 00419 00420 uint8_t last_bt = *(bt + (bt_idx/2)); 00421 if (bt_idx%2 == 1) { 00422 last_bt >>= 4; 00423 } else { 00424 last_bt &= 0x0F; 00425 } 00426 // if the final block type consists only of ones or zeros, we don't have to 00427 // calculate the position pointer and can sum up rank in 64 bit chunks 00428 if (last_bt == 0 or last_bt == 15) { 00429 if (last_bt == 15) 00430 rank += i % bit_vector_type::block_size; 00431 size_type j = (sample_pos*m_sample_rate) << 2; 00432 bt_idx = bt_idx << 2; 00433 if (bt_idx == j) 00434 return rrr_rank_support_trait<b>::adjust_rank(rank, i); 00435 // now j < bt_idx 00436 const uint64_t* bt64 = m_v->m_bt.data() + (j >> 6); // get the word of the start 00437 uint8_t bt64_off = j & 0x3F; // get the offset in the word of the start 00438 const uint64_t* bt64_end = m_v->m_bt.data() + (bt_idx >> 6); 00439 uint8_t bt64_end_off = bt_idx & 0x3F; 00440 // Case (1) 00441 if (bt64 == bt64_end) { 00442 uint64_t w = ((*bt64) >> bt64_off) & bit_magic::Li1Mask[bt64_end_off-bt64_off]; 00443 w = (w & 0x0f0f0f0f0f0f0f0full) + ((w >> 4) & 0x0f0f0f0f0f0f0f0full); 00444 rank += ((0x0101010101010101ull*w) >> 56); 00445 } else { // Case (2) 00446 uint64_t w = ((*bt64) >> bt64_off); 00447 w = (w & 0x0f0f0f0f0f0f0f0full) + ((w >> 4) & 0x0f0f0f0f0f0f0f0full); 00448 rank += ((0x0101010101010101ull*w) >> 56); 00449 while ((++bt64) != bt64_end) { 00450 w = *bt64; 00451 w = (w & 0x0f0f0f0f0f0f0f0full) + ((w >> 4) & 0x0f0f0f0f0f0f0f0full); 00452 rank += ((0x0101010101010101ull*w) >> 56); 00453 } 00454 // now bt64 == bt64_end 00455 if (bt64_end_off > 0) { 00456 w = *bt64 << (64 - bt64_end_off); 00457 w = (w & 0x0f0f0f0f0f0f0f0full) + ((w >> 4) & 0x0f0f0f0f0f0f0f0full); 00458 rank += ((0x0101010101010101ull*w) >> 56); 00459 } 00460 } 00461 return rrr_rank_support_trait<b>::adjust_rank(rank, i); // necessary 00462 } 00463 size_type j = sample_pos*m_sample_rate; 00464 bt += j/2; 00465 if (j%2 == 1 and j < bt_idx) { 00466 const uint8_t r = (*bt++)>>4; 00467 rank += r; 00468 btnrp += bi_type::space_for_bt(r); 00469 ++j; 00470 } 00471 while (j+1 < bt_idx) { 00472 const uint8_t r = *(bt++); 00473 rank += (r>>4)+(r&0x0F); 00474 btnrp += bi_type::space_for_bt_pair(r); // decode two entries at once 00475 j+=2; 00476 } 00477 if (j < bt_idx) { 00478 const uint8_t r = (*bt); 00479 rank += r&0x0F; 00480 btnrp += bi_type::space_for_bt(r&0x0F); 00481 ++j; 00482 } 00483 uint8_t off = i % bit_vector_type::block_size; //i - bt_idx*bit_vector_type::block_size; 00484 if (!off) { // needed for special case: if i=size() is a multiple of block_size 00485 // the access to m_bt would cause a invalid memory access 00486 return rrr_rank_support_trait<b>::adjust_rank(rank, i); 00487 } 00488 uint32_t btnr = m_v->m_btnr.get_int(btnrp, bi_type::space_for_bt(last_bt)); 00489 return rrr_rank_support_trait<b>::adjust_rank(rank + 00490 bit_magic::b1Cnt(((uint64_t)(bi_type::nr_to_bin(last_bt, btnr))) & bit_magic::Li1Mask[off]), i); 00491 } 00492 00494 const size_type operator()(size_type i)const { 00495 return rank(i); 00496 } 00497 00499 const size_type size()const { 00500 return m_v->size(); 00501 } 00502 00504 void set_vector(const bit_vector_type* v=NULL) { 00505 m_v = v; 00506 if (v != NULL) { 00507 m_sample_rate = m_v->m_sample_rate; 00508 } else { 00509 m_sample_rate = 0; 00510 } 00511 } 00512 00513 rrr_rank_support& operator=(const rrr_rank_support& rs) { 00514 if (this != &rs) { 00515 set_vector(rs.m_v); 00516 m_sample_rate = rs.m_sample_rate; 00517 } 00518 return *this; 00519 } 00520 00521 void swap(rrr_rank_support& rs) { 00522 if (this != &rs) { 00523 std::swap(m_sample_rate, rs.m_sample_rate); 00524 } 00525 } 00526 00527 bool operator==(const rrr_rank_support& rs)const { 00528 if (this == &rs) 00529 return true; 00530 return m_sample_rate == rs.m_sample_rate; 00531 } 00532 00533 bool operator!=(const rrr_rank_support& rs)const { 00534 return !(*this == rs); 00535 } 00536 00538 void load(std::istream& in, const bit_vector_type* v=NULL) { 00539 util::read_member(m_sample_rate, in); 00540 set_vector(v); 00541 } 00542 00544 size_type serialize(std::ostream& out, structure_tree_node* v=NULL, std::string name="")const { 00545 structure_tree_node* child = structure_tree::add_child(v, name, util::class_name(*this)); 00546 size_type written_bytes = 0; 00547 written_bytes += util::write_member(m_sample_rate, out, child, "sample_rate"); 00548 structure_tree::add_size(child, written_bytes); 00549 return written_bytes; 00550 } 00551 }; 00552 00553 00555 template<uint8_t b,class wt_type> 00556 class rrr_select_support<b, 15, wt_type> 00557 { 00558 public: 00559 typedef rrr_vector<15, wt_type> bit_vector_type; 00560 typedef typename bit_vector_type::size_type size_type; 00561 typedef typename bit_vector_type::bi_type bi_type; 00562 00563 private: 00564 const bit_vector_type* m_v; 00565 uint16_t m_sample_rate; 00566 00567 // TODO: hinted binary search 00568 size_type select1(size_type i)const { 00569 if (m_v->m_rank[m_v->m_rank.size()-1] < i) 00570 return size(); 00571 // (1) binary search for the answer in the rank_samples 00572 size_type begin=0, end=m_v->m_rank.size()-1; // min included, max excluded 00573 size_type idx, rank; 00574 // invariant: m_rank[end] >= i 00575 // m_rank[begin] < i 00576 while (end-begin > 1) { 00577 idx = (begin+end) >> 1; // idx in [0..m_rank.size()-1] 00578 rank = m_v->m_rank[idx]; 00579 if (rank >= i) 00580 end = idx; 00581 else { // rank < i 00582 begin = idx; 00583 } 00584 } 00585 // (2) linear search between the samples 00586 rank = m_v->m_rank[begin]; // now i>rank 00587 idx = begin * m_sample_rate; // initialize idx for select result 00588 size_type diff_rank = m_v->m_rank[end] - rank; 00589 if (diff_rank == (size_type)bit_vector_type::block_size*m_sample_rate) {// optimisation for select<1> 00590 return idx*bit_vector_type::block_size + i-rank -1; 00591 } 00592 size_type btnrp = m_v->m_btnrp[ begin ]; 00593 uint8_t bt = 0, s = 0; // temp variables for block_type and space for block type 00594 while (i > rank) { 00595 bt = m_v->m_bt[idx++]; 00596 rank += bt; 00597 btnrp += (s=bi_type::space_for_bt(bt)); 00598 } 00599 rank -= bt; 00600 uint32_t btnr = m_v->m_btnr.get_int(btnrp-s, s); 00601 return (idx-1) * bit_vector_type::block_size + bit_magic::i1BP(bi_type::nr_to_bin(bt, btnr), i-rank); 00602 } 00603 00604 // TODO: hinted binary search 00605 size_type select0(size_type i)const { 00606 if ((size()-m_v->m_rank[m_v->m_rank.size()-1]) < i) 00607 return size(); 00608 // (1) binary search for the answer in the rank_samples 00609 size_type begin=0, end=m_v->m_rank.size()-1; // min included, max excluded 00610 size_type idx, rank; 00611 // invariant: m_rank[end] >= i 00612 // m_rank[begin] < i 00613 while (end-begin > 1) { 00614 idx = (begin+end) >> 1; // idx in [0..m_rank.size()-1] 00615 rank = idx*bit_vector_type::block_size*m_sample_rate - m_v->m_rank[idx]; 00616 if (rank >= i) 00617 end = idx; 00618 else { // rank < i 00619 begin = idx; 00620 } 00621 } 00622 // (2) linear search between the samples 00623 rank = begin*bit_vector_type::block_size*m_sample_rate - m_v->m_rank[begin]; // now i>rank 00624 idx = begin * m_sample_rate; // initialize idx for select result 00625 if (m_v->m_rank[end] == m_v->m_rank[begin]) { // only for select<0> 00626 return idx*bit_vector_type::block_size + i-rank -1; 00627 } 00628 size_type btnrp = m_v->m_btnrp[ begin ]; 00629 uint8_t bt = 0, s = 0; // temp variables for block_type and space for block type 00630 while (i > rank) { 00631 bt = m_v->m_bt[idx++]; 00632 rank += (bit_vector_type::block_size-bt); 00633 btnrp += (s=bi_type::space_for_bt(bt)); 00634 } 00635 rank -= (bit_vector_type::block_size-bt); 00636 uint32_t btnr = m_v->m_btnr.get_int(btnrp-s, s); 00637 return (idx-1) * bit_vector_type::block_size + bit_magic::i1BP(~((uint64_t)bi_type::nr_to_bin(bt, btnr)), i-rank); 00638 } 00639 00640 00641 00642 public: 00643 rrr_select_support(const bit_vector_type* v=NULL) { 00644 init(v); 00645 } 00646 00647 void init(const bit_vector_type* v=NULL) { 00648 set_vector(v); 00649 } 00650 00652 size_type select(size_type i)const { 00653 return b ? select1(i) : select0(i); 00654 } 00655 00656 00657 const size_type operator()(size_type i)const { 00658 return select(i); 00659 } 00660 00661 const size_type size()const { 00662 return m_v->size(); 00663 } 00664 00665 void set_vector(const bit_vector_type* v=NULL) { 00666 m_v = v; 00667 if (v != NULL) { 00668 m_sample_rate = m_v->m_sample_rate; 00669 } else { 00670 m_sample_rate = 0; 00671 } 00672 } 00673 00674 rrr_select_support& operator=(const rrr_select_support& rs) { 00675 if (this != &rs) { 00676 set_vector(rs.m_v); 00677 m_sample_rate = rs.m_sample_rate; 00678 } 00679 return *this; 00680 } 00681 00682 void swap(rrr_select_support& rs) { 00683 if (this != &rs) { 00684 std::swap(m_sample_rate, rs.m_sample_rate); 00685 } 00686 } 00687 00688 bool operator==(const rrr_select_support& rs)const { 00689 if (this == &rs) 00690 return true; 00691 return m_sample_rate == rs.m_sample_rate; 00692 } 00693 00694 bool operator!=(const rrr_select_support& rs)const { 00695 return !(*this == rs); 00696 } 00697 00698 00699 void load(std::istream& in, const bit_vector_type* v=NULL) { 00700 util::read_member(m_sample_rate, in); 00701 set_vector(v); 00702 } 00703 00704 size_type serialize(std::ostream& out, structure_tree_node* v=NULL, std::string name="")const { 00705 structure_tree_node* child = structure_tree::add_child(v, name, util::class_name(*this)); 00706 size_type written_bytes = 0; 00707 written_bytes += util::write_member(m_sample_rate, out, child, "sample_rate"); 00708 structure_tree::add_size(child, written_bytes); 00709 return written_bytes; 00710 } 00711 }; 00712 00713 }// end namespace sdsl 00714 00715 #endif