SDSL: Succinct Data Structure Library
A C++ template library for succinct data structures
|
00001 /* sdsl - succinct data structures library 00002 Copyright (C) 2008 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 SDSL_CODER 00022 #define SDSL_CODER 00023 00024 #include "int_vector.hpp" 00025 #include "fibonacci_coder.hpp" 00026 #include "elias_delta_coder.hpp" 00027 #include "ternary_coder.hpp" 00028 00029 namespace sdsl 00030 { 00031 00033 namespace coder 00034 { 00035 00036 template<class Coder> 00037 class run_length 00038 { 00039 public: 00040 typedef uint64_t size_type; 00041 static void encode(uint64_t x, uint64_t*& z, uint8_t offset); 00042 static uint64_t encoding_length(const uint64_t* s, uint8_t s_offset, size_type bit_length); 00043 }; 00044 00045 template<class Coder> 00046 typename run_length<Coder>::size_type run_length<Coder>::encoding_length(const uint64_t* s, uint8_t s_offset, size_type bit_length) 00047 { 00048 assert(s_offset < 64); 00049 size_type i=0; 00050 uint64_t w = (*s >> s_offset); 00051 uint8_t last_bit = w&1; 00052 size_type result = 0; 00053 while (i < bit_length) { 00054 size_type len = 0; 00055 while (last_bit == (w&1) and i < bit_length) { 00056 // std::cout<<w<<" "<<i<<std::endl; 00057 ++len; ++i; ++s_offset; 00058 w >>= 1; 00059 if (s_offset == 64) { 00060 s_offset = 0; 00061 w = *(++s); 00062 } 00063 } 00064 // std::cout<<"len="<<Coder::encoding_length(len)<<std::endl; 00065 last_bit = (w&1); 00066 result += Coder::encoding_length(len); 00067 } 00068 return result; 00069 } 00070 00071 00072 } // end namespace coder 00073 00074 } // end namespace sdsl 00075 00076 #endif