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