SDSL: Succinct Data Structure Library
A C++ template library for succinct data structures
 All Classes Namespaces Files Functions Variables Typedefs Friends
sdsl/include/sdsl/rrr_vector_15.hpp
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