|
SDSL: Succinct Data Structure Library
A C++ template library for succinct data structures
|
|
SDSL: Succinct Data Structure Library
A C++ template library for succinct data structures
|
00001 /* sdsl - succinct data structures library 00002 Copyright (C) 2009 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 */ 00021 #ifndef INCLUDED_SDSL_ALGORITHMS_FOR_BALANCED_PARENTHESES 00022 #define INCLUDED_SDSL_ALGORITHMS_FOR_BALANCED_PARENTHESES 00023 00024 #include "int_vector.hpp" // for bit_vector 00025 #include <stack> // for calculate_pioneers_bitmap method 00026 #include <map> // for calculate_pioneers_bitmap method 00027 #include "sorted_stack_support.hpp" 00028 00029 00030 namespace sdsl 00031 { 00032 00033 namespace algorithm 00034 { 00035 00037 00045 inline void calculate_pioneers_bitmap(const bit_vector& bp, bit_vector::size_type block_size, bit_vector& pioneer_bitmap) 00046 { 00047 typedef bit_vector::size_type size_type; 00048 pioneer_bitmap.resize(bp.size()); // resize pioneers bitmap 00049 util::set_zero_bits(pioneer_bitmap); // initialize bitmap with zeros 00050 00051 std::stack<size_type> opening_parenthesis; 00052 size_type blocks = (bp.size()+block_size-1)/block_size; 00053 // calculate positions of findclose and findopen pioneers 00054 for (size_type block_nr = 0; block_nr < blocks; ++block_nr) { 00055 std::map<size_type, size_type> block_and_position; // for find_open and find_close 00056 std::map<size_type, size_type> matching_position; // for find_open and find_close 00057 for (size_type i=0, j=block_nr*block_size; i < block_size and j < bp.size(); ++i, ++j) { 00058 if (bp[j]) {//opening parenthesis 00059 opening_parenthesis.push(j); 00060 } else { // closing parenthesis 00061 size_type position = opening_parenthesis.top(); 00062 size_type blockpos = position/block_size; 00063 opening_parenthesis.pop(); 00064 block_and_position[blockpos] = position; 00065 matching_position[blockpos] = j; // greatest j is pioneer 00066 } 00067 } 00068 for (std::map<size_type, size_type>::const_iterator it = block_and_position.begin(), 00069 end = block_and_position.end(), 00070 mit = matching_position.begin(); it != end and it->first != block_nr; ++it, ++mit) { 00071 // opening and closing pioneers are symmetric 00072 pioneer_bitmap[it->second] = 1; 00073 pioneer_bitmap[mit->second] = 1; 00074 } 00075 } 00076 // assert that the sequence is balanced 00077 assert(opening_parenthesis.empty()); 00078 } 00079 00081 00090 template<class size_type> 00091 void calculate_pioneers_bitmap_succinct(const bit_vector& bp, size_type block_size, bit_vector& pioneer_bitmap) 00092 { 00093 pioneer_bitmap.resize(bp.size()); // resize pioneers bitmap to the resulting size 00094 util::set_zero_bits(pioneer_bitmap); // initialize bitmap with zeros 00095 00096 sorted_stack_support opening_parenthesis(bp.size()); 00097 bit_vector::size_type cur_pioneer_block = 0, last_start = 0, last_j = 0, cur_block=0, first_index_in_block=0; 00098 // calculate positions of findclose and findopen pioneers 00099 for (bit_vector::size_type j=0, new_block=block_size; j < bp.size(); ++j, --new_block) { 00100 if (!(new_block)) { 00101 cur_pioneer_block = j/block_size; 00102 ++cur_block; 00103 first_index_in_block = j; 00104 new_block = block_size; 00105 } 00106 00107 if (bp[j]) { // opening parenthesis 00108 if (/*j < bp.size() is not neccecssary as the last parenthesis is always a closing one*/ 00109 new_block>1 and !bp[j+1]) { 00110 ++j; --new_block; 00111 continue; 00112 } 00113 opening_parenthesis.push(j); 00114 } else { 00115 assert(!opening_parenthesis.empty()); 00116 size_type start = opening_parenthesis.top(); 00117 opening_parenthesis.pop(); 00118 if (start < first_index_in_block) { 00119 if ((start/block_size)==cur_pioneer_block) { 00120 pioneer_bitmap[last_start] = pioneer_bitmap[last_j] = 0; // override false pioneer 00121 } 00122 pioneer_bitmap[start] = pioneer_bitmap[j] = 1; 00123 cur_pioneer_block = start/block_size; 00124 last_start = start; 00125 last_j = j; 00126 } 00127 } 00128 } 00129 // assert that the sequence is balanced 00130 assert(opening_parenthesis.empty()); 00131 } 00132 00133 00134 template<class size_type> 00135 void calculate_pioneers_bitmap_succinct2(const bit_vector& bp, size_type block_size, bit_vector& pioneer_bitmap) 00136 { 00137 pioneer_bitmap.resize(bp.size()); // resize pioneers bitmap to the resulting size 00138 util::set_zero_bits(pioneer_bitmap); // initialize bitmap with zeros 00139 const uint64_t* data = bp.data(); 00140 bit_vector::size_type cnt=0; 00141 for (bit_vector::size_type i=0; i < bp.size() ; i+=64, ++data) { 00142 cnt += bit_magic::b1Cnt(*data); 00143 } 00144 } 00145 00146 00148 00156 template<class int_vector> 00157 void calculate_matches(const bit_vector& bp, int_vector& matches) 00158 { 00159 typedef bit_vector::size_type size_type; 00160 matches = int_vector(bp.size(), 0, bit_magic::l1BP(bp.size())+1); 00161 std::stack<size_type> opening_parenthesis; 00162 for (size_type i=0; i < bp.size(); ++i) { 00163 if (bp[i]) {// opening parenthesis 00164 opening_parenthesis.push(i); 00165 } else { // closing parenthesis 00166 assert(!opening_parenthesis.empty()); 00167 size_type position = opening_parenthesis.top(); 00168 opening_parenthesis.pop(); 00169 matches[i] = position; 00170 assert(matches[i]==position); 00171 matches[position] = i; 00172 assert(matches[position]==i); 00173 } 00174 } 00175 // assert that the sequence is balanced 00176 assert(opening_parenthesis.empty()); 00177 } 00178 00179 template<class int_vector> 00180 void calculate_matches_for_pioneers(const bit_vector& bp, const bit_vector& pioneer_bitmap, int_vector& matches) 00181 { 00182 assert(pioneer_bitmap.size()==bp.size()); 00183 typedef bit_vector::size_type size_type; 00184 matches = int_vector(pioneer_bitmap.size(), 0, bit_magic::l1BP(bp.size())+1); 00185 std::stack<size_type> opening_parenthesis; 00186 for (size_type i=0; i < bp.size(); ++i) { 00187 if (pioneer_bitmap[i]) { 00188 if (bp[i]) {// opening parenthesis 00189 opening_parenthesis.push(i); 00190 } else { // closing parenthesis 00191 assert(!opening_parenthesis.empty()); 00192 size_type position = opening_parenthesis.top(); 00193 opening_parenthesis.pop(); 00194 matches[i] = position; 00195 assert(matches[i]==position); 00196 matches[position] = i; 00197 assert(matches[position]==i); 00198 } 00199 } 00200 } 00201 // assert that the sequence is balanced 00202 assert(opening_parenthesis.empty()); 00203 } 00204 00205 00207 00215 template<class int_vector> 00216 void calculate_enclose(const bit_vector& bp, int_vector& enclose) 00217 { 00218 typedef bit_vector::size_type size_type; 00219 enclose = int_vector(bp.size(), 0, bit_magic::l1BP(bp.size())+1); 00220 std::stack<size_type> opening_parenthesis; 00221 for (size_type i=0; i < bp.size(); ++i) { 00222 if (bp[i]) {// opening parenthesis 00223 if (!opening_parenthesis.empty()) { 00224 size_type position = opening_parenthesis.top(); 00225 enclose[i] = position; 00226 assert(enclose[i]==position); 00227 } else 00228 enclose[i] = bp.size(); 00229 opening_parenthesis.push(i); 00230 } else { // closing parenthesis 00231 size_type position = opening_parenthesis.top(); 00232 enclose[i] = position; // find open answer if i is a closing parenthesis 00233 opening_parenthesis.pop(); 00234 } 00235 } 00236 // assert that the sequence is balanced 00237 assert(opening_parenthesis.empty()); 00238 } 00239 00240 template<class bp_support> 00241 bool check_bp_support(const bit_vector& bp, bp_support bp_s) 00242 { 00243 typedef bit_vector::size_type size_type; 00244 // check access and select 00245 for (size_type i = 0, excess=0, ones=0; i < bp.size(); ++i) { 00246 if (bp[i]) { 00247 ++excess; 00248 ++ones; 00249 size_type sel = bp_s.select(ones); 00250 if (sel != i) { 00251 std::cerr<<"select operation: i="<<ones<<" value="<<sel<<" expected="<<i<<std::endl; 00252 return false; 00253 } 00254 } else 00255 --excess; 00256 00257 if (bp_s.excess(i) != excess) { 00258 std::cerr<<"excess operation: i="<<i<<" value="<<bp_s.excess(i)<<" expected="<< excess<<std::endl; 00259 return false; 00260 } 00261 } 00262 // check find_open and find_close 00263 std::stack<size_type> opening_parenthesis; 00264 for (size_type i=0; i < bp.size(); ++i) { 00265 // std::cerr<<bp[i]<<" i="<<i<<std::endl; 00266 if (bp[i]) {// opening parenthesis 00267 opening_parenthesis.push(i); 00268 } else { // closing parenthesis 00269 assert(!opening_parenthesis.empty()); 00270 size_type position = opening_parenthesis.top(); 00271 size_type fc = bp_s.find_close(position); 00272 if (fc != i) { 00273 std::cerr<<"find_close operation: i="<<position<<" value="<<fc<<" expected="<< i << std::endl; 00274 return false; 00275 } 00276 size_type fo = bp_s.find_open(i); 00277 if (fo != position) { 00278 std::cerr<<"find_open operation: i="<<i<<" value="<<fo<<" expected="<< position << std::endl; 00279 return false; 00280 } 00281 opening_parenthesis.pop(); 00282 } 00283 } 00284 if (!opening_parenthesis.empty()) { 00285 std::cerr<<"balanced parenthese sequence is NOT balanced!" <<std::endl; 00286 return false; 00287 } 00288 // check enclose 00289 for (size_type i=0; i < bp.size(); ++i) { 00290 if (bp[i]) {// opening parenthesis 00291 size_type ec = bp_s.enclose(i); 00292 size_type position = bp.size(); 00293 if (!opening_parenthesis.empty()) { 00294 position = opening_parenthesis.top(); 00295 } 00296 opening_parenthesis.push(i); 00297 if (ec != position) { 00298 std::cerr<<"encolse operation i="<<i<<" value="<<ec<<" expected=" << position << std::endl; 00299 } 00300 } else { // closing parenthesis 00301 opening_parenthesis.pop(); 00302 } 00303 } 00304 return true; 00305 } 00306 00308 00315 // TODO: implement a fast version using lookup-tables of size 8 00316 inline bit_vector::size_type near_find_close_naive(const bit_vector& bp, bit_vector::size_type i, const bit_vector::size_type block_size) 00317 { 00318 typedef bit_vector::size_type size_type; 00319 size_type opening_parentheses = 1; 00320 for (size_type j=i+1; j < (i/block_size+1)*block_size; ++j) { 00321 if (bp[j]) 00322 ++opening_parentheses; 00323 else { 00324 --opening_parentheses; 00325 if (opening_parentheses == 0) { 00326 return j; 00327 } 00328 } 00329 } 00330 return i; 00331 } 00332 00333 const uint32_t near_find_close_8bits_lookup[256]= { 00334 1985229328U,2574668850U,2574668848U,2576971348U,2574668816U,2576971348U,2576971344U,2576980342U, 00335 2574668304U,2576971346U,2576971344U,2576980342U,2576971280U,2576980342U,2576980336U,2576980377U, 00336 2574660112U,2576971314U,2576971312U,2576980342U,2576971280U,2576980342U,2576980336U,2576980377U, 00337 2576970256U,2576980338U,2576980336U,2576980377U,2576980240U,2576980377U,2576980368U,2576980377U, 00338 2574529040U,2576970802U,2576970800U,2576980340U,2576970768U,2576980340U,2576980336U,2576980377U, 00339 2576970256U,2576980338U,2576980336U,2576980377U,2576980240U,2576980377U,2576980368U,2576980377U, 00340 2576953872U,2576980274U,2576980272U,2576980377U,2576980240U,2576980377U,2576980368U,2576980377U, 00341 2576978448U,2576980370U,2576980368U,2576980377U,2576980240U,2576980377U,2576980368U,2576980377U, 00342 2572431888U,2576962610U,2576962608U,2576980308U,2576962576U,2576980308U,2576980304U,2576980377U, 00343 2576962064U,2576980306U,2576980304U,2576980377U,2576980240U,2576980377U,2576980368U,2576980377U, 00344 2576953872U,2576980274U,2576980272U,2576980377U,2576980240U,2576980377U,2576980368U,2576980377U, 00345 2576978448U,2576980370U,2576980368U,2576980377U,2576980240U,2576980377U,2576980368U,2576980377U, 00346 2576626192U,2576978994U,2576978992U,2576980372U,2576978960U,2576980372U,2576980368U,2576980377U, 00347 2576978448U,2576980370U,2576980368U,2576980377U,2576980240U,2576980377U,2576980368U,2576980377U, 00348 2576953872U,2576980274U,2576980272U,2576980377U,2576980240U,2576980377U,2576980368U,2576980377U, 00349 2576978448U,2576980370U,2576980368U,2576980377U,2576980240U,2576980377U,2576980368U,2576980377U, 00350 2522100240U,2576766002U,2576766000U,2576979540U,2576765968U,2576979540U,2576979536U,2576980374U, 00351 2576765456U,2576979538U,2576979536U,2576980374U,2576979472U,2576980374U,2576980368U,2576980377U, 00352 2576757264U,2576979506U,2576979504U,2576980374U,2576979472U,2576980374U,2576980368U,2576980377U, 00353 2576978448U,2576980370U,2576980368U,2576980377U,2576980240U,2576980377U,2576980368U,2576980377U, 00354 2576626192U,2576978994U,2576978992U,2576980372U,2576978960U,2576980372U,2576980368U,2576980377U, 00355 2576978448U,2576980370U,2576980368U,2576980377U,2576980240U,2576980377U,2576980368U,2576980377U, 00356 2576953872U,2576980274U,2576980272U,2576980377U,2576980240U,2576980377U,2576980368U,2576980377U, 00357 2576978448U,2576980370U,2576980368U,2576980377U,2576980240U,2576980377U,2576980368U,2576980377U, 00358 2572431888U,2576962610U,2576962608U,2576980308U,2576962576U,2576980308U,2576980304U,2576980377U, 00359 2576962064U,2576980306U,2576980304U,2576980377U,2576980240U,2576980377U,2576980368U,2576980377U, 00360 2576953872U,2576980274U,2576980272U,2576980377U,2576980240U,2576980377U,2576980368U,2576980377U, 00361 2576978448U,2576980370U,2576980368U,2576980377U,2576980240U,2576980377U,2576980368U,2576980377U, 00362 2576626192U,2576978994U,2576978992U,2576980372U,2576978960U,2576980372U,2576980368U,2576980377U, 00363 2576978448U,2576980370U,2576980368U,2576980377U,2576980240U,2576980377U,2576980368U,2576980377U, 00364 2576953872U,2576980274U,2576980272U,2576980377U,2576980240U,2576980377U,2576980368U,2576980377U, 00365 2576978448U,2576980370U,2576980368U,2576980377U,2576980240U,2576980377U,2576980368U,2576980377U 00366 }; 00367 00368 const uint32_t near_find_open_8bits_lookup[256]= { 00369 2576980377U,2576980377U,2576980377U,2576980377U,2576980377U,2576980377U,2576980377U,2576980377U, 00370 2576980377U,2576980377U,2576980377U,2576980377U,2576980377U,2576980377U,2576980377U,2576980377U, 00371 2576980377U,2576980377U,2576980377U,2576980377U,2576980377U,2576980377U,2576980377U,2576980377U, 00372 2576980377U,2576980377U,2576980377U,2576980377U,2576980377U,2576980377U,2576980369U,2576980225U, 00373 2576980377U,2576980377U,2576980377U,2576980377U,2576980377U,2576980377U,2576980377U,2576980377U, 00374 2576980377U,2576980377U,2576980377U,2576980377U,2576980377U,2576980377U,2576980369U,2576980225U, 00375 2576980377U,2576980377U,2576980377U,2576980377U,2576980377U,2576980377U,2576980369U,2576980225U, 00376 2576980371U,2576980371U,2576980371U,2576980227U,2576980259U,2576980259U,2576978211U,2576941347U, 00377 2576980377U,2576980377U,2576980377U,2576980377U,2576980377U,2576980377U,2576980377U,2576980377U, 00378 2576980377U,2576980377U,2576980377U,2576980377U,2576980377U,2576980377U,2576980369U,2576980225U, 00379 2576980377U,2576980377U,2576980377U,2576980377U,2576980377U,2576980377U,2576980369U,2576980225U, 00380 2576980371U,2576980371U,2576980371U,2576980227U,2576980259U,2576980259U,2576978211U,2576941347U, 00381 2576980373U,2576980373U,2576980373U,2576980373U,2576980373U,2576980373U,2576980373U,2576980229U, 00382 2576980373U,2576980373U,2576980373U,2576980229U,2576980261U,2576980261U,2576978213U,2576941349U, 00383 2576980293U,2576980293U,2576980293U,2576980293U,2576980293U,2576980293U,2576978245U,2576941381U, 00384 2576978757U,2576978757U,2576978757U,2576941893U,2576950085U,2576950085U,2576425797U,2566988613U, 00385 2576980375U,2576980375U,2576980375U,2576980375U,2576980375U,2576980375U,2576980375U,2576980375U, 00386 2576980375U,2576980375U,2576980375U,2576980375U,2576980375U,2576980375U,2576980375U,2576980231U, 00387 2576980375U,2576980375U,2576980375U,2576980375U,2576980375U,2576980375U,2576980375U,2576980231U, 00388 2576980375U,2576980375U,2576980375U,2576980231U,2576980263U,2576980263U,2576978215U,2576941351U, 00389 2576980375U,2576980375U,2576980375U,2576980375U,2576980375U,2576980375U,2576980375U,2576980231U, 00390 2576980375U,2576980375U,2576980375U,2576980231U,2576980263U,2576980263U,2576978215U,2576941351U, 00391 2576980295U,2576980295U,2576980295U,2576980295U,2576980295U,2576980295U,2576978247U,2576941383U, 00392 2576978759U,2576978759U,2576978759U,2576941895U,2576950087U,2576950087U,2576425799U,2566988615U, 00393 2576980327U,2576980327U,2576980327U,2576980327U,2576980327U,2576980327U,2576980327U,2576980327U, 00394 2576980327U,2576980327U,2576980327U,2576980327U,2576980327U,2576980327U,2576978279U,2576941415U, 00395 2576980327U,2576980327U,2576980327U,2576980327U,2576980327U,2576980327U,2576978279U,2576941415U, 00396 2576978791U,2576978791U,2576978791U,2576941927U,2576950119U,2576950119U,2576425831U,2566988647U, 00397 2576979303U,2576979303U,2576979303U,2576979303U,2576979303U,2576979303U,2576979303U,2576942439U, 00398 2576979303U,2576979303U,2576979303U,2576942439U,2576950631U,2576950631U,2576426343U,2566989159U, 00399 2576958823U,2576958823U,2576958823U,2576958823U,2576958823U,2576958823U,2576434535U,2566997351U, 00400 2576565607U,2576565607U,2576565607U,2567128423U,2569225575U,2569225575U,2435007847U,19088743U 00401 }; 00402 00403 const int8_t excess_8bits_lookup[256]= { 00404 -8,-6,-6,-4,-6,-4,-4,-2,-6,-4,-4,-2,-4,-2,-2,0, 00405 -6,-4,-4,-2,-4,-2,-2,0,-4,-2,-2,0,-2,0,0,2, 00406 -6,-4,-4,-2,-4,-2,-2,0,-4,-2,-2,0,-2,0,0,2, 00407 -4,-2,-2,0,-2,0,0,2,-2,0,0,2,0,2,2,4, 00408 -6,-4,-4,-2,-4,-2,-2,0,-4,-2,-2,0,-2,0,0,2, 00409 -4,-2,-2,0,-2,0,0,2,-2,0,0,2,0,2,2,4, 00410 -4,-2,-2,0,-2,0,0,2,-2,0,0,2,0,2,2,4, 00411 -2,0,0,2,0,2,2,4,0,2,2,4,2,4,4,6, 00412 -6,-4,-4,-2,-4,-2,-2,0,-4,-2,-2,0,-2,0,0,2, 00413 -4,-2,-2,0,-2,0,0,2,-2,0,0,2,0,2,2,4, 00414 -4,-2,-2,0,-2,0,0,2,-2,0,0,2,0,2,2,4, 00415 -2,0,0,2,0,2,2,4,0,2,2,4,2,4,4,6, 00416 -4,-2,-2,0,-2,0,0,2,-2,0,0,2,0,2,2,4, 00417 -2,0,0,2,0,2,2,4,0,2,2,4,2,4,4,6, 00418 -2,0,0,2,0,2,2,4,0,2,2,4,2,4,4,6, 00419 0,2,2,4,2,4,4,6,2,4,4,6,4,6,6,8 00420 }; 00421 00422 inline bit_vector::size_type near_find_close(const bit_vector& bp, const bit_vector::size_type i, const bit_vector::size_type block_size) 00423 { 00424 typedef bit_vector::size_type size_type; 00425 typedef bit_vector::difference_type difference_type; 00426 difference_type excess=1; 00427 00428 const size_type end = ((i+1)/block_size+1)*block_size; 00429 const size_type l = (((i+1)+7)/8)*8; 00430 const size_type r = (end/8)*8; 00431 for (size_type j=i+1; j < std::min(end,l); ++j) { 00432 if (bp[j]) 00433 ++excess; 00434 else { 00435 --excess; 00436 if (excess == 0) { 00437 return j; 00438 } 00439 } 00440 } 00441 const uint64_t* b = bp.data(); 00442 for (size_type j=l; j<r; j+=8) { 00443 if (excess <= 8) { 00444 assert(excess>0); 00445 uint32_t x = near_find_close_8bits_lookup[((*(b+(j>>6)))>>(j&0x3F))&0xFF ]; 00446 uint8_t p = (x >> ((excess-1)<<2))&0xF; 00447 if (p < 9) { 00448 return j+p; 00449 } 00450 } 00451 excess += excess_8bits_lookup[((*(b+(j>>6)))>>(j&0x3F))&0xFF ]; 00452 } 00453 for (size_type j=std::max(l,r); j < end; ++j) { 00454 if (bp[j]) 00455 ++excess; 00456 else { 00457 --excess; 00458 if (excess == 0) { 00459 return j; 00460 } 00461 } 00462 } 00463 return i; 00464 } 00465 00466 // TODO: umbenennen der method in near_find_first_closing_with_excess_diff 00467 inline bit_vector::size_type near_find_closing(const bit_vector& bp, bit_vector::size_type i, bit_vector::size_type closings, const bit_vector::size_type block_size) 00468 { 00469 typedef bit_vector::size_type size_type; 00470 typedef bit_vector::difference_type difference_type; 00471 difference_type excess=0; 00472 difference_type succ_excess=-closings; 00473 00474 const size_type end = (i/block_size+1)*block_size; 00475 const size_type l = (((i)+7)/8)*8; 00476 const size_type r = (end/8)*8; 00477 for (size_type j=i; j < std::min(end,l); ++j) { 00478 if (bp[j]) 00479 ++excess; 00480 else { 00481 --excess; 00482 if (excess == succ_excess) { 00483 return j; 00484 } 00485 } 00486 } 00487 const uint64_t* b = bp.data(); 00488 for (size_type j=l; j<r; j+=8) { 00489 if (excess-succ_excess <= 8) { 00490 // assert(excess>0); 00491 uint32_t x = near_find_close_8bits_lookup[((*(b+(j>>6)))>>(j&0x3F))&0xFF ]; 00492 uint8_t p = (x >> (((excess-succ_excess)-1)<<2))&0xF; 00493 if (p < 9) { 00494 return j+p; 00495 } 00496 } 00497 excess += excess_8bits_lookup[((*(b+(j>>6)))>>(j&0x3F))&0xFF ]; 00498 } 00499 for (size_type j=std::max(l,r); j < end; ++j) { 00500 if (bp[j]) 00501 ++excess; 00502 else { 00503 --excess; 00504 if (excess == succ_excess) { 00505 return j; 00506 } 00507 } 00508 } 00509 return i-1; 00510 } 00511 00512 const unsigned char near_fwd_excess_8bits_lookup[4352]= { 00513 7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00514 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00515 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00516 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00517 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00518 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00519 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00520 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00521 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00522 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00523 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00524 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00525 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00526 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00527 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00528 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00529 00530 6,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00531 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00532 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00533 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00534 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00535 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00536 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00537 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00538 6,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00539 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00540 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00541 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00542 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00543 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00544 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00545 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00546 00547 5,7,7,8,7,8,8,8,7,8,8,8,8,8,8,8, 00548 7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00549 7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00550 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00551 5,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00552 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00553 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00554 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00555 5,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00556 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00557 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00558 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00559 5,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00560 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00561 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00562 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00563 00564 4,6,6,8,6,8,8,8,6,8,8,8,8,8,8,8, 00565 6,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00566 4,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00567 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00568 4,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00569 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00570 4,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00571 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00572 4,6,6,8,6,8,8,8,6,8,8,8,8,8,8,8, 00573 6,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00574 4,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00575 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00576 4,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00577 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00578 4,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00579 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00580 00581 3,5,5,7,5,7,7,8,5,7,7,8,7,8,8,8, 00582 3,7,7,8,7,8,8,8,7,8,8,8,8,8,8,8, 00583 3,7,7,8,7,8,8,8,7,8,8,8,8,8,8,8, 00584 3,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00585 3,5,5,8,5,8,8,8,5,8,8,8,8,8,8,8, 00586 3,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00587 3,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00588 3,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00589 3,5,5,8,5,8,8,8,5,8,8,8,8,8,8,8, 00590 3,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00591 3,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00592 3,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00593 3,5,5,8,5,8,8,8,5,8,8,8,8,8,8,8, 00594 3,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00595 3,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00596 3,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00597 00598 2,4,4,6,4,6,6,8,2,6,6,8,6,8,8,8, 00599 2,6,6,8,6,8,8,8,2,8,8,8,8,8,8,8, 00600 2,4,4,8,4,8,8,8,2,8,8,8,8,8,8,8, 00601 2,8,8,8,8,8,8,8,2,8,8,8,8,8,8,8, 00602 2,4,4,8,4,8,8,8,2,8,8,8,8,8,8,8, 00603 2,8,8,8,8,8,8,8,2,8,8,8,8,8,8,8, 00604 2,4,4,8,4,8,8,8,2,8,8,8,8,8,8,8, 00605 2,8,8,8,8,8,8,8,2,8,8,8,8,8,8,8, 00606 2,4,4,6,4,6,6,8,2,6,6,8,6,8,8,8, 00607 2,6,6,8,6,8,8,8,2,8,8,8,8,8,8,8, 00608 2,4,4,8,4,8,8,8,2,8,8,8,8,8,8,8, 00609 2,8,8,8,8,8,8,8,2,8,8,8,8,8,8,8, 00610 2,4,4,8,4,8,8,8,2,8,8,8,8,8,8,8, 00611 2,8,8,8,8,8,8,8,2,8,8,8,8,8,8,8, 00612 2,4,4,8,4,8,8,8,2,8,8,8,8,8,8,8, 00613 2,8,8,8,8,8,8,8,2,8,8,8,8,8,8,8, 00614 00615 1,3,3,5,1,5,5,7,1,5,5,7,1,7,7,8, 00616 1,3,3,7,1,7,7,8,1,7,7,8,1,8,8,8, 00617 1,3,3,7,1,7,7,8,1,7,7,8,1,8,8,8, 00618 1,3,3,8,1,8,8,8,1,8,8,8,1,8,8,8, 00619 1,3,3,5,1,5,5,8,1,5,5,8,1,8,8,8, 00620 1,3,3,8,1,8,8,8,1,8,8,8,1,8,8,8, 00621 1,3,3,8,1,8,8,8,1,8,8,8,1,8,8,8, 00622 1,3,3,8,1,8,8,8,1,8,8,8,1,8,8,8, 00623 1,3,3,5,1,5,5,8,1,5,5,8,1,8,8,8, 00624 1,3,3,8,1,8,8,8,1,8,8,8,1,8,8,8, 00625 1,3,3,8,1,8,8,8,1,8,8,8,1,8,8,8, 00626 1,3,3,8,1,8,8,8,1,8,8,8,1,8,8,8, 00627 1,3,3,5,1,5,5,8,1,5,5,8,1,8,8,8, 00628 1,3,3,8,1,8,8,8,1,8,8,8,1,8,8,8, 00629 1,3,3,8,1,8,8,8,1,8,8,8,1,8,8,8, 00630 1,3,3,8,1,8,8,8,1,8,8,8,1,8,8,8, 00631 00632 0,2,0,4,0,4,0,6,0,2,0,6,0,6,0,8, 00633 0,2,0,6,0,6,0,8,0,2,0,8,0,8,0,8, 00634 0,2,0,4,0,4,0,8,0,2,0,8,0,8,0,8, 00635 0,2,0,8,0,8,0,8,0,2,0,8,0,8,0,8, 00636 0,2,0,4,0,4,0,8,0,2,0,8,0,8,0,8, 00637 0,2,0,8,0,8,0,8,0,2,0,8,0,8,0,8, 00638 0,2,0,4,0,4,0,8,0,2,0,8,0,8,0,8, 00639 0,2,0,8,0,8,0,8,0,2,0,8,0,8,0,8, 00640 0,2,0,4,0,4,0,6,0,2,0,6,0,6,0,8, 00641 0,2,0,6,0,6,0,8,0,2,0,8,0,8,0,8, 00642 0,2,0,4,0,4,0,8,0,2,0,8,0,8,0,8, 00643 0,2,0,8,0,8,0,8,0,2,0,8,0,8,0,8, 00644 0,2,0,4,0,4,0,8,0,2,0,8,0,8,0,8, 00645 0,2,0,8,0,8,0,8,0,2,0,8,0,8,0,8, 00646 0,2,0,4,0,4,0,8,0,2,0,8,0,8,0,8, 00647 0,2,0,8,0,8,0,8,0,2,0,8,0,8,0,8, 00648 00649 8,1,1,3,8,1,1,5,8,1,1,5,3,1,1,7, 00650 8,1,1,3,8,1,1,7,8,1,1,7,3,1,1,8, 00651 8,1,1,3,8,1,1,7,8,1,1,7,3,1,1,8, 00652 8,1,1,3,5,1,1,8,5,1,1,8,3,1,1,8, 00653 8,1,1,3,8,1,1,5,8,1,1,5,3,1,1,8, 00654 8,1,1,3,8,1,1,8,8,1,1,8,3,1,1,8, 00655 8,1,1,3,8,1,1,8,8,1,1,8,3,1,1,8, 00656 8,1,1,3,5,1,1,8,5,1,1,8,3,1,1,8, 00657 8,1,1,3,8,1,1,5,8,1,1,5,3,1,1,8, 00658 8,1,1,3,8,1,1,8,8,1,1,8,3,1,1,8, 00659 8,1,1,3,8,1,1,8,8,1,1,8,3,1,1,8, 00660 8,1,1,3,5,1,1,8,5,1,1,8,3,1,1,8, 00661 8,1,1,3,8,1,1,5,8,1,1,5,3,1,1,8, 00662 8,1,1,3,7,1,1,8,7,1,1,8,3,1,1,8, 00663 8,1,1,3,7,1,1,8,7,1,1,8,3,1,1,8, 00664 7,1,1,3,5,1,1,8,5,1,1,8,3,1,1,8, 00665 00666 8,0,8,0,8,0,2,0,8,0,8,0,8,0,2,0, 00667 8,0,8,0,8,0,2,0,8,0,4,0,4,0,2,0, 00668 8,0,8,0,8,0,2,0,8,0,8,0,8,0,2,0, 00669 8,0,8,0,8,0,2,0,8,0,4,0,4,0,2,0, 00670 8,0,8,0,8,0,2,0,8,0,8,0,8,0,2,0, 00671 8,0,8,0,8,0,2,0,8,0,4,0,4,0,2,0, 00672 8,0,8,0,8,0,2,0,8,0,6,0,6,0,2,0, 00673 8,0,6,0,6,0,2,0,6,0,4,0,4,0,2,0, 00674 8,0,8,0,8,0,2,0,8,0,8,0,8,0,2,0, 00675 8,0,8,0,8,0,2,0,8,0,4,0,4,0,2,0, 00676 8,0,8,0,8,0,2,0,8,0,8,0,8,0,2,0, 00677 8,0,8,0,8,0,2,0,8,0,4,0,4,0,2,0, 00678 8,0,8,0,8,0,2,0,8,0,8,0,8,0,2,0, 00679 8,0,8,0,8,0,2,0,8,0,4,0,4,0,2,0, 00680 8,0,8,0,8,0,2,0,8,0,6,0,6,0,2,0, 00681 8,0,6,0,6,0,2,0,6,0,4,0,4,0,2,0, 00682 00683 8,8,8,1,8,8,8,1,8,8,8,1,8,3,3,1, 00684 8,8,8,1,8,8,8,1,8,8,8,1,8,3,3,1, 00685 8,8,8,1,8,8,8,1,8,8,8,1,8,3,3,1, 00686 8,8,8,1,8,5,5,1,8,5,5,1,5,3,3,1, 00687 8,8,8,1,8,8,8,1,8,8,8,1,8,3,3,1, 00688 8,8,8,1,8,8,8,1,8,8,8,1,8,3,3,1, 00689 8,8,8,1,8,8,8,1,8,8,8,1,8,3,3,1, 00690 8,8,8,1,8,5,5,1,8,5,5,1,5,3,3,1, 00691 8,8,8,1,8,8,8,1,8,8,8,1,8,3,3,1, 00692 8,8,8,1,8,8,8,1,8,8,8,1,8,3,3,1, 00693 8,8,8,1,8,8,8,1,8,8,8,1,8,3,3,1, 00694 8,8,8,1,8,5,5,1,8,5,5,1,5,3,3,1, 00695 8,8,8,1,8,8,8,1,8,8,8,1,8,3,3,1, 00696 8,8,8,1,8,7,7,1,8,7,7,1,7,3,3,1, 00697 8,8,8,1,8,7,7,1,8,7,7,1,7,3,3,1, 00698 8,7,7,1,7,5,5,1,7,5,5,1,5,3,3,1, 00699 00700 8,8,8,8,8,8,8,2,8,8,8,8,8,8,8,2, 00701 8,8,8,8,8,8,8,2,8,8,8,4,8,4,4,2, 00702 8,8,8,8,8,8,8,2,8,8,8,8,8,8,8,2, 00703 8,8,8,8,8,8,8,2,8,8,8,4,8,4,4,2, 00704 8,8,8,8,8,8,8,2,8,8,8,8,8,8,8,2, 00705 8,8,8,8,8,8,8,2,8,8,8,4,8,4,4,2, 00706 8,8,8,8,8,8,8,2,8,8,8,6,8,6,6,2, 00707 8,8,8,6,8,6,6,2,8,6,6,4,6,4,4,2, 00708 8,8,8,8,8,8,8,2,8,8,8,8,8,8,8,2, 00709 8,8,8,8,8,8,8,2,8,8,8,4,8,4,4,2, 00710 8,8,8,8,8,8,8,2,8,8,8,8,8,8,8,2, 00711 8,8,8,8,8,8,8,2,8,8,8,4,8,4,4,2, 00712 8,8,8,8,8,8,8,2,8,8,8,8,8,8,8,2, 00713 8,8,8,8,8,8,8,2,8,8,8,4,8,4,4,2, 00714 8,8,8,8,8,8,8,2,8,8,8,6,8,6,6,2, 00715 8,8,8,6,8,6,6,2,8,6,6,4,6,4,4,2, 00716 00717 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,3, 00718 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,3, 00719 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,3, 00720 8,8,8,8,8,8,8,5,8,8,8,5,8,5,5,3, 00721 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,3, 00722 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,3, 00723 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,3, 00724 8,8,8,8,8,8,8,5,8,8,8,5,8,5,5,3, 00725 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,3, 00726 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,3, 00727 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,3, 00728 8,8,8,8,8,8,8,5,8,8,8,5,8,5,5,3, 00729 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,3, 00730 8,8,8,8,8,8,8,7,8,8,8,7,8,7,7,3, 00731 8,8,8,8,8,8,8,7,8,8,8,7,8,7,7,3, 00732 8,8,8,7,8,7,7,5,8,7,7,5,7,5,5,3, 00733 00734 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00735 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,4, 00736 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00737 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,4, 00738 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00739 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,4, 00740 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,6, 00741 8,8,8,8,8,8,8,6,8,8,8,6,8,6,6,4, 00742 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00743 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,4, 00744 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00745 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,4, 00746 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00747 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,4, 00748 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,6, 00749 8,8,8,8,8,8,8,6,8,8,8,6,8,6,6,4, 00750 00751 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00752 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00753 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00754 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,5, 00755 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00756 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00757 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00758 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,5, 00759 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00760 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00761 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00762 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,5, 00763 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00764 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,7, 00765 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,7, 00766 8,8,8,8,8,8,8,7,8,8,8,7,8,7,7,5, 00767 00768 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00769 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00770 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00771 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00772 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00773 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00774 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00775 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,6, 00776 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00777 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00778 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00779 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00780 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00781 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00782 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00783 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,6, 00784 00785 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00786 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00787 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00788 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00789 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00790 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00791 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00792 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00793 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00794 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00795 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00796 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00797 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00798 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00799 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00800 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,7 00801 }; 00802 00804 00806 inline bit_vector::size_type near_fwd_excess(const bit_vector& bp, bit_vector::size_type i, bit_vector::difference_type rel, const bit_vector::size_type block_size) 00807 { 00808 typedef bit_vector::size_type size_type; 00809 typedef bit_vector::difference_type difference_type; 00810 difference_type excess = rel; 00811 // std::cout<<"excess = "<<excess<<std::endl; 00812 00813 const size_type end = (i/block_size+1)*block_size; 00814 const size_type l = (((i)+7)/8)*8; 00815 const size_type r = (end/8)*8; 00816 for (size_type j=i; j < std::min(end,l); ++j) { 00817 if (bp[j]) 00818 --excess; 00819 else { 00820 ++excess; 00821 } 00822 if (!excess) { 00823 return j; 00824 } 00825 } 00826 excess += 8; 00827 const uint64_t* b = bp.data(); 00828 for (size_type j=l; j < r; j+=8) { 00829 if (excess >= 0 and excess <= 16) { 00830 uint32_t x = near_fwd_excess_8bits_lookup[(excess<<8) + (((*(b+(j>>6)))>>(j&0x3F))&0xFF) ]; 00831 if (x < 8) { 00832 return j+x; 00833 } 00834 } 00835 excess -= excess_8bits_lookup[((*(b+(j>>6)))>>(j&0x3F))&0xFF ]; 00836 } 00837 excess -= 8; 00838 for (size_type j=std::max(l,r); j < end; ++j) { 00839 if (bp[j]) 00840 --excess; 00841 else { 00842 ++excess; 00843 } 00844 if (!excess) { 00845 return j; 00846 } 00847 } 00848 return i-1; 00849 } 00850 00851 const int8_t near_rmq_8bits_val_lookup[256]= { 00852 -8,-6,-6,-4,-6,-4,-4,-2,-6,-4,-4,-2,-4,-2,-2,0, 00853 -6,-4,-4,-2,-4,-2,-2,0,-4,-2,-2,0,-2,0,-1,1, 00854 -6,-4,-4,-2,-4,-2,-2,0,-4,-2,-2,0,-2,0,-1,1, 00855 -4,-2,-2,0,-2,0,-1,1,-3,-1,-1,1,-2,0,-1,1, 00856 -6,-4,-4,-2,-4,-2,-2,0,-4,-2,-2,0,-2,0,-1,1, 00857 -4,-2,-2,0,-2,0,-1,1,-3,-1,-1,1,-2,0,-1,1, 00858 -5,-3,-3,-1,-3,-1,-1,1,-3,-1,-1,1,-2,0,-1,1, 00859 -4,-2,-2,0,-2,0,-1,1,-3,-1,-1,1,-2,0,-1,1, 00860 -7,-5,-5,-3,-5,-3,-3,-1,-5,-3,-3,-1,-3,-1,-1,1, 00861 -5,-3,-3,-1,-3,-1,-1,1,-3,-1,-1,1,-2,0,-1,1, 00862 -5,-3,-3,-1,-3,-1,-1,1,-3,-1,-1,1,-2,0,-1,1, 00863 -4,-2,-2,0,-2,0,-1,1,-3,-1,-1,1,-2,0,-1,1, 00864 -6,-4,-4,-2,-4,-2,-2,0,-4,-2,-2,0,-2,0,-1,1, 00865 -4,-2,-2,0,-2,0,-1,1,-3,-1,-1,1,-2,0,-1,1, 00866 -5,-3,-3,-1,-3,-1,-1,1,-3,-1,-1,1,-2,0,-1,1, 00867 -4,-2,-2,0,-2,0,-1,1,-3,-1,-1,1,-2,0,-1,1 00868 }; 00869 00870 const int8_t near_rightmost_rmq_8bits_pos_lookup[256]= { 00871 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 00872 7,7,7,7,7,7,7,7,7,7,7,7,7,7,0,0, 00873 7,7,7,7,7,7,7,7,7,7,7,7,7,7,0,0, 00874 7,7,7,7,7,7,0,0,2,2,2,2,1,1,0,0, 00875 7,7,7,7,7,7,7,7,7,7,7,7,7,7,0,0, 00876 7,7,7,7,7,7,0,0,2,2,2,2,1,1,0,0, 00877 4,4,4,4,4,4,4,4,4,4,4,4,1,1,0,0, 00878 3,3,3,3,3,3,0,0,2,2,2,2,1,1,0,0, 00879 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, 00880 6,6,6,6,6,6,6,6,6,6,6,6,1,1,0,0, 00881 6,6,6,6,6,6,6,6,6,6,6,6,1,1,0,0, 00882 3,3,3,3,3,3,0,0,2,2,2,2,1,1,0,0, 00883 5,5,5,5,5,5,5,5,5,5,5,5,5,5,0,0, 00884 5,5,5,5,5,5,0,0,2,2,2,2,1,1,0,0, 00885 4,4,4,4,4,4,4,4,4,4,4,4,1,1,0,0, 00886 3,3,3,3,3,3,0,0,2,2,2,2,1,1,0,0 00887 }; 00888 00890 00895 inline bit_vector::size_type near_rmq(const bit_vector& bp, bit_vector::size_type l, bit_vector::size_type r, bit_vector::difference_type& min_rel_ex) 00896 { 00897 typedef bit_vector::size_type size_type; 00898 typedef bit_vector::difference_type difference_type; 00899 const size_type l8 = (((l+1)+7)/8)*8; 00900 const size_type r8 = (r/8)*8; 00901 difference_type excess = 0; 00902 difference_type min_pos=l; 00903 min_rel_ex = 0; 00904 for (size_type j=l+1; j < std::min(l8,r+1); ++j) { 00905 if (bp[j]) 00906 ++excess; 00907 else { 00908 --excess; 00909 if (excess <= min_rel_ex) { 00910 min_rel_ex = excess; 00911 min_pos = j; 00912 } 00913 } 00914 } 00915 00916 const uint64_t* b = bp.data(); 00917 for (size_type j=l8; j < r8; j+=8) { 00918 // if( excess-8 <= min_rel_ex ){ 00919 int8_t x = near_rmq_8bits_val_lookup[(((*(b+(j>>6)))>>(j&0x3F))&0xFF) ]; 00920 if ((excess+x) <= min_rel_ex) { 00921 min_rel_ex = excess+x; 00922 min_pos = j + near_rightmost_rmq_8bits_pos_lookup[(((*(b+(j>>6)))>>(j&0x3F))&0xFF) ]; 00923 } 00924 // } 00925 excess += excess_8bits_lookup[((*(b+(j>>6)))>>(j&0x3F))&0xFF ]; 00926 } 00927 for (size_type j=std::max(l8,r8); j<r+1; ++j) { 00928 if (bp[j]) 00929 ++excess; 00930 else { 00931 --excess; 00932 if (excess <= min_rel_ex) { 00933 min_rel_ex = excess; 00934 min_pos = j; 00935 } 00936 } 00937 } 00938 return min_pos; 00939 } 00940 00941 const unsigned char near_bwd_excess_8bits_lookup[4352]= { 00942 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00943 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00944 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00945 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00946 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00947 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00948 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00949 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00950 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00951 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00952 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00953 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00954 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00955 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00956 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00957 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,0, 00958 00959 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00960 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00961 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00962 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00963 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00964 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00965 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00966 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00967 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00968 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00969 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00970 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00971 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00972 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00973 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00974 8,8,8,8,8,8,8,8,8,8,8,8,8,8,1,1, 00975 00976 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00977 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00978 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00979 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00980 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00981 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00982 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00983 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,0, 00984 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00985 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00986 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00987 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,0, 00988 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00989 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,0, 00990 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,0, 00991 8,8,8,8,8,8,8,0,8,8,8,0,2,2,2,2, 00992 00993 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00994 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00995 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00996 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00997 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00998 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 00999 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01000 8,8,8,8,8,8,8,8,8,8,8,8,8,8,1,1, 01001 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01002 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01003 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01004 8,8,8,8,8,8,8,8,8,8,8,8,8,8,1,1, 01005 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01006 8,8,8,8,8,8,8,8,8,8,8,8,8,8,1,1, 01007 8,8,8,8,8,8,8,8,8,8,8,8,8,8,1,1, 01008 8,8,8,8,8,8,1,1,3,3,3,3,3,3,3,3, 01009 01010 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01011 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01012 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01013 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,0, 01014 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01015 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,0, 01016 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,0, 01017 8,8,8,8,8,8,8,0,8,8,8,0,2,2,2,2, 01018 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01019 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,0, 01020 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,0, 01021 8,8,8,8,8,8,8,0,8,8,8,0,2,2,2,2, 01022 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,0, 01023 8,8,8,8,8,8,8,0,8,8,8,0,2,2,2,2, 01024 8,8,8,8,8,8,8,0,8,8,8,0,2,2,2,2, 01025 4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4, 01026 01027 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01028 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01029 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01030 8,8,8,8,8,8,8,8,8,8,8,8,8,8,1,1, 01031 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01032 8,8,8,8,8,8,8,8,8,8,8,8,8,8,1,1, 01033 8,8,8,8,8,8,8,8,8,8,8,8,8,8,1,1, 01034 8,8,8,8,8,8,1,1,3,3,3,3,3,3,3,3, 01035 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01036 8,8,8,8,8,8,8,8,8,8,8,8,8,8,1,1, 01037 8,8,8,8,8,8,8,8,8,8,8,8,8,8,1,1, 01038 8,8,8,8,8,8,1,1,3,3,3,3,3,3,3,3, 01039 8,8,8,8,8,8,8,8,8,8,8,8,8,8,1,1, 01040 8,8,8,8,8,8,1,1,3,3,3,3,3,3,3,3, 01041 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5, 01042 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5, 01043 01044 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01045 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,0, 01046 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,0, 01047 8,8,8,8,8,8,8,0,8,8,8,0,2,2,2,2, 01048 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,0, 01049 8,8,8,8,8,8,8,0,8,8,8,0,2,2,2,2, 01050 8,8,8,8,8,8,8,0,8,8,8,0,2,2,2,2, 01051 4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4, 01052 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,0, 01053 8,8,8,8,8,8,8,0,8,8,8,0,2,2,2,2, 01054 8,8,8,8,8,8,8,0,8,8,8,0,2,2,2,2, 01055 4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4, 01056 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, 01057 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, 01058 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, 01059 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, 01060 01061 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01062 8,8,8,8,8,8,8,8,8,8,8,8,8,8,1,1, 01063 8,8,8,8,8,8,8,8,8,8,8,8,8,8,1,1, 01064 8,8,8,8,8,8,1,1,3,3,3,3,3,3,3,3, 01065 8,8,8,8,8,8,8,8,8,8,8,8,8,8,1,1, 01066 8,8,8,8,8,8,1,1,3,3,3,3,3,3,3,3, 01067 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5, 01068 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5, 01069 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 01070 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 01071 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 01072 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 01073 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 01074 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 01075 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 01076 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 01077 01078 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,0, 01079 8,8,8,8,8,8,8,0,8,8,8,0,2,2,2,2, 01080 8,8,8,8,8,8,8,0,8,8,8,0,2,2,2,2, 01081 4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4, 01082 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, 01083 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, 01084 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, 01085 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, 01086 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, 01087 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, 01088 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, 01089 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, 01090 4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4, 01091 2,2,2,2,0,8,8,8,0,8,8,8,8,8,8,8, 01092 2,2,2,2,0,8,8,8,0,8,8,8,8,8,8,8, 01093 0,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01094 01095 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 01096 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 01097 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 01098 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 01099 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 01100 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 01101 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 01102 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 01103 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5, 01104 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5, 01105 3,3,3,3,3,3,3,3,1,1,8,8,8,8,8,8, 01106 1,1,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01107 3,3,3,3,3,3,3,3,1,1,8,8,8,8,8,8, 01108 1,1,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01109 1,1,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01110 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01111 01112 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, 01113 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, 01114 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, 01115 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, 01116 4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4, 01117 2,2,2,2,0,8,8,8,0,8,8,8,8,8,8,8, 01118 2,2,2,2,0,8,8,8,0,8,8,8,8,8,8,8, 01119 0,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01120 4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4, 01121 2,2,2,2,0,8,8,8,0,8,8,8,8,8,8,8, 01122 2,2,2,2,0,8,8,8,0,8,8,8,8,8,8,8, 01123 0,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01124 2,2,2,2,0,8,8,8,0,8,8,8,8,8,8,8, 01125 0,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01126 0,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01127 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01128 01129 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5, 01130 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5, 01131 3,3,3,3,3,3,3,3,1,1,8,8,8,8,8,8, 01132 1,1,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01133 3,3,3,3,3,3,3,3,1,1,8,8,8,8,8,8, 01134 1,1,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01135 1,1,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01136 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01137 3,3,3,3,3,3,3,3,1,1,8,8,8,8,8,8, 01138 1,1,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01139 1,1,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01140 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01141 1,1,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01142 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01143 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01144 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01145 01146 4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4, 01147 2,2,2,2,0,8,8,8,0,8,8,8,8,8,8,8, 01148 2,2,2,2,0,8,8,8,0,8,8,8,8,8,8,8, 01149 0,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01150 2,2,2,2,0,8,8,8,0,8,8,8,8,8,8,8, 01151 0,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01152 0,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01153 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01154 2,2,2,2,0,8,8,8,0,8,8,8,8,8,8,8, 01155 0,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01156 0,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01157 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01158 0,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01159 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01160 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01161 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01162 01163 3,3,3,3,3,3,3,3,1,1,8,8,8,8,8,8, 01164 1,1,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01165 1,1,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01166 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01167 1,1,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01168 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01169 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01170 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01171 1,1,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01172 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01173 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01174 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01175 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01176 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01177 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01178 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01179 01180 2,2,2,2,0,8,8,8,0,8,8,8,8,8,8,8, 01181 0,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01182 0,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01183 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01184 0,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01185 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01186 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01187 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01188 0,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01189 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01190 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01191 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01192 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01193 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01194 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01195 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01196 01197 1,1,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01198 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01199 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01200 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01201 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01202 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01203 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01204 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01205 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01206 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01207 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01208 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01209 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01210 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01211 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01212 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01213 01214 0,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01215 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01216 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01217 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01218 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01219 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01220 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01221 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01222 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01223 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01224 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01225 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01226 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01227 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01228 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 01229 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8 01230 01231 }; 01233 01235 inline bit_vector::size_type near_bwd_excess(const bit_vector& bp, bit_vector::size_type i, bit_vector::difference_type rel, const bit_vector::size_type block_size) 01236 { 01237 typedef bit_vector::size_type size_type; 01238 typedef bit_vector::difference_type difference_type; 01239 difference_type excess = rel; 01240 const difference_type begin = ((difference_type)(i)/block_size)*block_size; 01241 const difference_type r = ((difference_type)(i)/8)*8; 01242 const difference_type l = ((difference_type)((begin+7)/8))*8; 01243 for (difference_type j=i+1; j >= /*begin*/std::max(r,begin); --j) { 01244 if (bp[j]) 01245 ++excess; 01246 else 01247 --excess; 01248 if (!excess) return j-1; 01249 } 01250 01251 excess += 8; 01252 const uint64_t* b = bp.data(); 01253 for (difference_type j=r-8; j >= l; j-=8) { 01254 if (excess >= 0 and excess <= 16) { 01255 uint32_t x = near_bwd_excess_8bits_lookup[(excess<<8) + (((*(b+(j>>6)))>>(j&0x3F))&0xFF) ]; 01256 // std::cerr<<"i = "<<i<<" j="<<j<<" x = "<<x<<" excess = "<< excess-8 << " "<< (((*(b+(j>>6)))>>(j&0x3F))&0xFF) << " " << (excess<<8) << " begin = " << begin << " r = " << r <<" l="<<l<< std::endl; 01257 if (x < 8) { 01258 return j+x-1; 01259 } 01260 } 01261 excess += excess_8bits_lookup[((*(b+(j>>6)))>>(j&0x3F))&0xFF ]; 01262 } 01263 excess -= 8; 01264 for (difference_type j=std::min(l, r); j > begin; --j) { 01265 if (bp[j]) 01266 ++excess; 01267 else 01268 --excess; 01269 if (!excess) return j-1; 01270 } 01271 if (0==begin and -1==rel) { 01272 return -1; 01273 } 01274 return i+1; 01275 } 01276 01277 01278 01279 01281 01288 inline bit_vector::size_type near_find_open_naive(const bit_vector& bp, bit_vector::size_type i, const bit_vector::size_type block_size) 01289 { 01290 typedef bit_vector::size_type size_type; 01291 size_type closing_parentheses = 1; 01292 for (size_type j=i; j+block_size-1 > i and j>0; --j) { 01293 if (bp[j-1]) { 01294 --closing_parentheses; 01295 if (closing_parentheses == 0) { 01296 return j-1; 01297 } 01298 } else 01299 ++closing_parentheses; 01300 } 01301 return i; 01302 } 01303 01304 01305 inline bit_vector::size_type near_find_open(const bit_vector& bp, bit_vector::size_type i, const bit_vector::size_type block_size) 01306 { 01307 typedef bit_vector::size_type size_type; 01308 typedef bit_vector::difference_type difference_type; 01309 difference_type excess = -1; 01310 const difference_type begin = ((difference_type)(i-1)/block_size)*block_size; 01311 const difference_type r = ((difference_type)(i-1)/8)*8; 01312 const difference_type l = ((difference_type)((begin+7)/8))*8; 01313 for (difference_type j=i-1; j >= std::max(r,begin); --j) { 01314 if (bp[j]) { 01315 if (++excess == 0) { 01316 return j; 01317 } 01318 } else 01319 --excess; 01320 } 01321 const uint64_t* b = bp.data(); 01322 for (difference_type j=r-8; j >= l; j-=8) { 01323 if (excess >= -8) { 01324 assert(excess<0); 01325 uint32_t x = near_find_open_8bits_lookup[((*(b+(j>>6)))>>(j&0x3F))&0xFF ]; 01326 uint8_t p = (x >> ((-excess-1)<<2))&0xF; 01327 if (p < 9) { 01328 return j+p; 01329 } 01330 } 01331 excess += excess_8bits_lookup[((*(b+(j>>6)))>>(j&0x3F))&0xFF ]; 01332 } 01333 for (difference_type j=std::min(l, r)-1; j >= begin; --j) { 01334 if (bp[j]) { 01335 if (++excess == 0) { 01336 return j; 01337 } 01338 } else 01339 --excess; 01340 } 01341 return i; 01342 } 01343 01344 01345 inline bit_vector::size_type near_find_opening(const bit_vector& bp, bit_vector::size_type i, const bit_vector::size_type openings,const bit_vector::size_type block_size) 01346 { 01347 typedef bit_vector::size_type size_type; 01348 typedef bit_vector::difference_type difference_type; 01349 difference_type excess = 0; 01350 difference_type succ_excess = openings; 01351 01352 const difference_type begin = ((difference_type)(i)/block_size)*block_size; 01353 const difference_type r = ((difference_type)(i)/8)*8; 01354 const difference_type l = ((difference_type)((begin+7)/8))*8; 01355 //std::cout<<"i="<<i<<" begin="<<begin<<" r="<<r<<" l="<<l<<std::endl; 01356 for (difference_type j=i; j >= std::max(r,begin); --j) { 01357 if (bp[j]) { 01358 if (++excess == succ_excess) { 01359 return j; 01360 } 01361 } else 01362 --excess; 01363 } 01364 const uint64_t* b = bp.data(); 01365 for (difference_type j=r-8; j >= l; j-=8) { 01366 if (succ_excess-excess <= 8) { 01367 // assert(excess<0); 01368 assert(succ_excess-excess>0); 01369 uint32_t x = near_find_open_8bits_lookup[((*(b+(j>>6)))>>(j&0x3F))&0xFF ]; 01370 uint8_t p = (x >> ((succ_excess-excess-1)<<2))&0xF; 01371 if (p < 9) { 01372 return j+p; 01373 } 01374 } 01375 excess += excess_8bits_lookup[((*(b+(j>>6)))>>(j&0x3F))&0xFF ]; 01376 } 01377 for (difference_type j=std::min(l, r)-1; j >= begin; --j) { 01378 if (bp[j]) { 01379 if (++excess == succ_excess) { 01380 return j; 01381 } 01382 } else 01383 --excess; 01384 } 01385 return i+1; 01386 } 01387 01388 01389 01390 01392 01399 // TODO: implement a fast version using lookup-tables of size 8 01400 inline bit_vector::size_type near_enclose(const bit_vector& bp, bit_vector::size_type i, const bit_vector::size_type block_size) 01401 { 01402 typedef bit_vector::size_type size_type; 01403 size_type opening_parentheses = 1; 01404 for (size_type j=i; j+block_size-1 > i and j>0; --j) { 01405 if (bp[j-1]) { 01406 ++opening_parentheses; 01407 if (opening_parentheses == 2) { 01408 return j-1; 01409 } 01410 } else 01411 --opening_parentheses; 01412 } 01413 return i; 01414 } 01415 01416 01417 const uint16_t min_excess_info_8bits_lookup[256]= { 01418 17,4105,4360,8201,4615,8713,8456,12297,4870,8968,8968,12297,8711,12809,12552,16393, 01419 5125,9223,9223,13321,9223,13321,12552,16393,8966,13064,13064,16393,12807,16905,16648,20489, 01420 5380,9478,9478,13576,9478,13576,13576,16393,9478,13576,13576,16393,12807,16905,16648,20489, 01421 9221,13319,13319,17417,13319,17417,16648,20489,13062,17160,17160,20489,16903,21001,20744,24585, 01422 5635,9733,9733,13831,9733,13831,13831,17929,9733,13831,13831,17929,13831,17929,16648,20489, 01423 9733,13831,13831,17929,13831,17929,16648,20489,13062,17160,17160,20489,16903,21001,20744,24585, 01424 9476,13574,13574,17672,13574,17672,17672,20489,13574,17672,17672,20489,16903,21001,20744,24585, 01425 13317,17415,17415,21513,17415,21513,20744,24585,17158,21256,21256,24585,20999,25097,24840,28681, 01426 5890,9988,9988,14086,9988,14086,14086,18184,9988,14086,14086,18184,14086,18184,18184,20489, 01427 9988,14086,14086,18184,14086,18184,18184,20489,14086,18184,18184,20489,16903,21001,20744,24585, 01428 9988,14086,14086,18184,14086,18184,18184,20489,14086,18184,18184,20489,16903,21001,20744,24585, 01429 13317,17415,17415,21513,17415,21513,20744,24585,17158,21256,21256,24585,20999,25097,24840,28681, 01430 9731,13829,13829,17927,13829,17927,17927,22025,13829,17927,17927,22025,17927,22025,20744,24585, 01431 13829,17927,17927,22025,17927,22025,20744,24585,17158,21256,21256,24585,20999,25097,24840,28681, 01432 13572,17670,17670,21768,17670,21768,21768,24585,17670,21768,21768,24585,20999,25097,24840,28681, 01433 17413,21511,21511,25609,21511,25609,24840,28681,21254,25352,25352,28681,25095,29193,28936,32777 01434 }; 01435 01436 inline bit_vector::size_type near_rmq_open(const bit_vector& bp, const bit_vector::size_type begin, const bit_vector::size_type end) 01437 { 01438 typedef bit_vector::size_type size_type; 01439 typedef bit_vector::difference_type difference_type; 01440 difference_type min_excess = end-begin+1, ex = 0; 01441 size_type result = end; 01442 01443 const size_type l = ((begin+7)/8)*8; 01444 const size_type r = (end/8)*8; 01445 01446 for (size_type k=begin; k < std::min(end,l); ++k) { 01447 if (bp[k]) { 01448 ++ex; 01449 if (ex <= min_excess) { 01450 result = k; 01451 min_excess = ex; 01452 } 01453 } else { 01454 --ex; 01455 } 01456 } 01457 const uint64_t* b = bp.data();// + (l>>6); 01458 for (size_type k = l; k < r; k+=8) { 01459 uint16_t x = min_excess_info_8bits_lookup[((*(b+(k>>6)))>>(k&0x3F))&0xFF ]; 01460 int8_t ones = (x>>12); 01461 if (ones) { 01462 int8_t min_ex = (x&0xFF)-8; 01463 if (ex+min_ex <= min_excess) { 01464 result = k + ((x>>8)&0xF); 01465 min_excess = ex+min_ex; 01466 } 01467 } 01468 ex += ((ones<<1)-8); 01469 } 01470 for (size_type k=std::max(r,l); k < end; ++k) { 01471 if (bp[k]) { 01472 ++ex; 01473 if (ex <= min_excess) { 01474 result = k; 01475 min_excess = ex; 01476 } 01477 } else { 01478 --ex; 01479 } 01480 } 01481 if (min_excess <= ex) 01482 return result; 01483 return end; 01484 } 01485 01486 inline bit_vector::size_type near_rmq_open_naive(const bit_vector& bp, const bit_vector::size_type begin, const bit_vector::size_type end) 01487 { 01488 typedef bit_vector::size_type size_type; 01489 typedef bit_vector::difference_type difference_type; 01490 difference_type min_excess = end-begin+1, ex = 0; 01491 size_type result = end; 01492 for (size_type k=begin; k<end; ++k) { 01493 if (bp[k]) { 01494 ++ex; 01495 if (ex <= min_excess) { 01496 result = k; 01497 min_excess = ex; 01498 } 01499 } else { 01500 --ex; 01501 } 01502 } 01503 if (min_excess <= ex) 01504 return result; 01505 return end; 01506 } 01507 01508 01509 }// end namespace algorithm 01510 01511 }// end namespace sdsl 01512 01513 #endif 01514 01515
1.8.0
