sdsl/include/sdsl/enc_vector_prac2.hpp

Go to the documentation of this file.

/* sdsl - succinct data structures library
    Copyright (C) 20011 Simon Gog

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see http://www.gnu.org/licenses/ .
*/
#include "int_vector.hpp"
#include "elias_delta_coder.hpp"
#include "iterators.hpp"

#ifndef SDSL_ENC_VECTOR_PRAC2
#define SDSL_ENC_VECTOR_PRAC2

namespace sdsl
{

template<uint8_t fixedIntWidth>
struct enc_vector_prac2_trait {
    typedef int_vector<0> int_vector_type;
};

template<>
struct enc_vector_prac2_trait<32> {
    typedef int_vector<32> int_vector_type;
};


template<class Coder=coder::elias_delta,
         uint32_t SampleDens = 8, uint8_t fixedIntWidth=0>
class enc_vector_prac2
{
    public:
        typedef uint64_t                                                        value_type;     // STL Container requirement
        typedef random_access_const_iterator<enc_vector_prac2> iterator;// STL Container requirement
        typedef iterator                                                        const_iterator; // STL Container requirement
        typedef const value_type                                        reference;
        typedef const value_type                                        const_reference;
        typedef const value_type*                                       const_pointer;
        typedef ptrdiff_t                                                       difference_type;// STL Container requirement
        typedef int_vector<>::size_type                         size_type;              // STL Container requirement
        typedef Coder                                                           coder;
        typedef typename enc_vector_prac2_trait<fixedIntWidth>::int_vector_type int_vector_type;
        static  const uint32_t                                          sample_dens     = SampleDens;

        int_vector<0>   m_z;            // compressed bit stream
    private:
        int_vector_type   m_sample_vals_and_pointer;
        size_type               m_elements;    // number of elements
        uint32_t                m_sample_dens;

        // workaround function for the constructor
        void construct() {
            m_elements = 0;
            m_sample_dens = 8;
        }
        void copy(const enc_vector_prac2& v);

        void clear() {
            m_z.resize(0);
            m_elements = 0;
            m_sample_vals_and_pointer.resize(0);
        }

    public:
        enc_vector_prac2() {
            construct();
        };

        enc_vector_prac2(const enc_vector_prac2& v);


        template<class Container>
        enc_vector_prac2(const Container& c) {
            construct();
            init(c);
        };

        /*
            \param v_buf A int_vector_file_buf.
                \pre No two adjacent values should be equal.
        */
        template<uint8_t int_width, class size_type_class>
        enc_vector_prac2(int_vector_file_buffer<int_width, size_type_class>& v_buf) {
            construct();
            init(v_buf);
        }

        template<class Container>
        void init(const Container& c);

        template<uint8_t int_width, class size_type_class>
        void init(int_vector_file_buffer<int_width, size_type_class>& v_buf);

        ~enc_vector_prac2() {
        };


        size_type size()const;


        static size_type max_size();


        bool empty() const;


        void swap(enc_vector_prac2& v);


        const const_iterator begin()const;


        const const_iterator end()const;

        // Iterator that points to the last element of the enc_vector_prac2.
        /*
         *      Required for the Container Concept of the STL.
         *  \sa rend()
         */
//              reverse_iterator rbegin()const;

        // Iterator that points to the position before the first element of the enc_vector_prac2.
        /*
         *      Required for the Container Concept of the STL
         *  \sa rbegin()
         */
//              reverse_iterator rend()const;


        value_type operator[](size_type i)const;


        enc_vector_prac2& operator=(const enc_vector_prac2& v);


        bool operator==(const enc_vector_prac2& v)const;


        bool operator!=(const enc_vector_prac2& v)const;


        size_type serialize(std::ostream& out) const;

        void load(std::istream& in);


        value_type sample(const size_type i) const;

        uint32_t get_sample_dens() const;
        void set_sample_dens(const uint32_t sample_dens);

//              template<class Iterator>
        void get_inter_sampled_values(const size_type i, uint64_t*& it)const {
            *(it++) = 0;
            if (i*SampleDens + SampleDens - 1 < size()) {
                Coder::template decode<true, true>(m_z.data(), m_sample_vals_and_pointer[(i<<1)+1], SampleDens - 1, it);
            } else {
                assert(i*SampleDens < size());
                Coder::template decode<true, true>(m_z.data(), m_sample_vals_and_pointer[(i<<1)+1], size()-i*SampleDens - 1, it);
            }
        };
};


template<class Coder, uint32_t SampleDens, uint8_t fixedIntWidth>
inline uint32_t enc_vector_prac2<Coder, SampleDens, fixedIntWidth>::get_sample_dens() const
{
    if (SampleDens == 0)
        return m_sample_dens;
    else
        return SampleDens;
}

template<class Coder, uint32_t SampleDens, uint8_t fixedIntWidth>
inline void enc_vector_prac2<Coder, SampleDens, fixedIntWidth>::set_sample_dens(const uint32_t sample_dens)
{
    m_sample_dens = sample_dens;
}

template<class Coder, uint32_t SampleDens, uint8_t fixedIntWidth>
inline typename enc_vector_prac2<Coder, SampleDens,fixedIntWidth>::value_type enc_vector_prac2<Coder, SampleDens,fixedIntWidth>::operator[](const size_type i)const
{
    assert(i+1 != 0);
#ifdef SDSL_DEBUG
    if (i >= m_elements) {
        throw std::out_of_range("OUT_OF_RANGE_ERROR: enc_vector_prac2::operator[](size_type); i >= size()!");
        return 0;
    }
#endif
    size_type idx = i/get_sample_dens();
    return m_sample_vals_and_pointer[idx<<1] + Coder::decode_prefix_sum(m_z.data(), m_sample_vals_and_pointer[(idx<<1)+1], i-SampleDens*idx);
}

template<class Coder, uint32_t SampleDens, uint8_t fixedIntWidth>
inline typename enc_vector_prac2<Coder, SampleDens,fixedIntWidth>::value_type enc_vector_prac2<Coder, SampleDens,fixedIntWidth>::sample(const size_type i)const
{
    assert(i*get_sample_dens()+1 != 0);
#ifdef SDSL_DEBUG
    if (i*get_sample_dens() >= m_elements) {
        throw std::out_of_range("OUT_OF_RANGE_ERROR: enc_vector_prac2::sample(size_type); i*get_sample_dens() >= size()!");
        return 0;
    }
#endif
    return m_sample_vals_and_pointer[i<<1];
}

template<class Coder, uint32_t SampleDens, uint8_t fixedIntWidth>
inline enc_vector_prac2<>::size_type enc_vector_prac2<Coder, SampleDens,fixedIntWidth>::size()const
{
    return m_elements;
}

template<class Coder, uint32_t SampleDens, uint8_t fixedIntWidth>
inline enc_vector_prac2<>::size_type enc_vector_prac2<Coder, SampleDens,fixedIntWidth>::max_size()
{
    return int_vector<>::max_size()/2; // each element could possible occupy double space with selfdelimiting codes
}

template<class Coder, uint32_t SampleDens, uint8_t fixedIntWidth>
inline bool enc_vector_prac2<Coder, SampleDens,fixedIntWidth>::empty()const
{
    return 0==m_elements;
}


template<class Coder, uint32_t SampleDens, uint8_t fixedIntWidth>
void enc_vector_prac2<Coder, SampleDens,fixedIntWidth>::copy(const enc_vector_prac2<Coder, SampleDens,fixedIntWidth>& v)
{
    m_z                                 = v.m_z;                                // copy compressed bit stream
    m_sample_vals_and_pointer           = v.m_sample_vals_and_pointer;      // copy sample values
    m_elements                  = v.m_elements;                 // copy number of stored elements
}

template<class Coder, uint32_t SampleDens, uint8_t fixedIntWidth>
enc_vector_prac2<Coder, SampleDens,fixedIntWidth>::enc_vector_prac2(const enc_vector_prac2& v)
{
    copy(v);
}

template<class Coder, uint32_t SampleDens, uint8_t fixedIntWidth>
enc_vector_prac2<Coder, SampleDens,fixedIntWidth>& enc_vector_prac2<Coder, SampleDens,fixedIntWidth>::operator=(const enc_vector_prac2<Coder, SampleDens,fixedIntWidth>& v)
{
    if (this != &v) {// if v and _this_ are not the same object
        copy(v);
    }
    return *this;
}

template<class Coder, uint32_t SampleDens, uint8_t fixedIntWidth>
bool enc_vector_prac2<Coder, SampleDens,fixedIntWidth>::operator==(const enc_vector_prac2<Coder, SampleDens,fixedIntWidth>& v)const
{
    if (this == &v)
        return true;
    return              m_elements == v.m_elements
                and     m_z == v.m_z
                and     m_sample_vals_and_pointer == v.m_sample_vals_and_pointer;
}

template<class Coder, uint32_t SampleDens, uint8_t fixedIntWidth>
bool enc_vector_prac2<Coder, SampleDens,fixedIntWidth>::operator!=(const enc_vector_prac2<Coder, SampleDens,fixedIntWidth>& v)const
{
    return !(*this == v);
}

template<class Coder, uint32_t SampleDens, uint8_t fixedIntWidth>
void enc_vector_prac2<Coder, SampleDens,fixedIntWidth>::swap(enc_vector_prac2<Coder, SampleDens,fixedIntWidth>& v)
{
    if (this != &v) { // if v and _this_ are not the same object
        m_z.swap(v.m_z);                                        // swap compressed bit streams
        m_sample_vals_and_pointer.swap(v.m_sample_vals_and_pointer);
        std::swap(m_elements, v.m_elements);// swap the number of elements
    }
}


template<class Coder, uint32_t SampleDens, uint8_t fixedIntWidth>
template<class Container>
void enc_vector_prac2<Coder, SampleDens,fixedIntWidth>::init(const Container& c)
{
    // clear bit_vectors
    clear();

    if (c.empty())  // if c is empty there is nothing to do...
        return;
    typename Container::const_iterator  it                      = c.begin(), end = c.end();
    typename Container::value_type              v1                      = *it, v2, max_value=0, max_sample_value=0, x;
    size_type samples=0;
    size_type z_size = 0;
//  (1) Calculate maximal value of samples and of deltas
    for (size_type i=0, no_sample=0; it != end; ++it,++i, --no_sample) {
        v2 = *it;
        if (!no_sample) { // add a sample
            no_sample = get_sample_dens();
            if (max_sample_value < v2) max_sample_value = v2;
            ++samples;
        } else {
            if (max_value < v2-v1) max_value = v2 - v1;
            z_size += Coder::encoding_length(v2-v1);
        }
        v1=v2;
    }
//      (2) Write sample values and deltas
    {
        if (max_sample_value > z_size+1)
            m_sample_vals_and_pointer.set_int_width(bit_magic::l1BP(max_sample_value) + 1);
        else
            m_sample_vals_and_pointer.set_int_width(bit_magic::l1BP(z_size+1) + 1);
        m_sample_vals_and_pointer.resize(2*samples+2); // add 2 for last entry
        typename int_vector_type::iterator sv_it = m_sample_vals_and_pointer.begin();
        z_size = 0;
        size_type no_sample=0;
        for (it = c.begin(); it != end; ++it, --no_sample) {
            v2 = *it;
            if (!no_sample) { // add a sample
                no_sample = get_sample_dens();
                *sv_it = v2; ++sv_it;
                *sv_it = z_size; ++sv_it;
            } else {
                x = v2-v1;
                if (v2 == v1) {
                    throw std::logic_error("enc_vector_prac2 cannot decode adjacent equal values!");
                }
                z_size += Coder::encoding_length(x);
            }
            v1=v2;
        }
        *sv_it = 0; ++sv_it;        // initialize
        *sv_it = z_size+1; ++sv_it; // last entry

        m_z.bit_resize(z_size);
        uint64_t* z_data = Coder::raw_data(m_z);
        uint8_t offset = 0;
        no_sample = 0;
        for (it = c.begin(); it != end; ++it, --no_sample) {
            v2 = *it;
            if (!no_sample) { // add a sample
                no_sample = get_sample_dens();
            } else {
                Coder::encode(v2-v1, z_data, offset);
            }
            v1=v2;
        }
//              Coder::encode(delta_c, m_z); // encode delta_c to m_z
    }
//      delta_c.resize(0);
//std::cerr<<"Finished "<<std::endl;,
    m_elements = c.size();
}


template<class Coder, uint32_t SampleDens, uint8_t fixedIntWidth>
template<uint8_t int_width, class size_type_class>
void enc_vector_prac2<Coder, SampleDens,fixedIntWidth>::init(int_vector_file_buffer<int_width, size_type_class>& v_buf)
{
    // clear bit_vectors
    clear();
    size_type n = v_buf.int_vector_size;
    if (n == 0)  // if c is empty there is nothing to do...
        return;
    v_buf.reset();
    value_type  v1=0, v2=0, max_sample_value=0;
    size_type samples=0, z_size=0;
    const size_type sd = get_sample_dens();
    size_type z_size2 = 0, big_val_cnt=0, old_z_size=0, old_i=0;
    size_type big_val[sd+1], big_val_pos[sd+1];
    uint8_t log_sd=bit_magic::l1BP(sd)+1;
    size_type saved_bits=0;
//  (1) Calculate maximal value of samples and of deltas
    for (size_type i=0, r_sum=0, r = v_buf.load_next_block(), no_sample = 0; r_sum < n;) {
        for (; i < r_sum+r; ++i, --no_sample) {
            v2 = v_buf[i-r_sum];
            if (!no_sample) { // is sample
                no_sample = sd;
                if (max_sample_value < v2) max_sample_value = v2;
                ++samples;

                size_type bits=0;
                bits += log_sd; // bits for big_val_cnt
                for (size_type j=0; j<big_val_cnt; ++j) {
                    bits += Coder::encoding_length(big_val[j]);
                    if (j == 0)
                        bits += Coder::encoding_length(big_val_pos[j]+1);
                    else
                        bits += Coder::encoding_length(big_val_pos[j]-big_val_pos[j-1]);
                }
                big_val_cnt = 0;
                if (z_size - old_z_size > bits) {
                    z_size2 += bits;
                } else {
                    z_size2 += (z_size-old_z_size);
                }
                old_z_size = z_size;
                old_i = i;
            } else {
                if (v2 == v1) {
                    throw std::logic_error("enc_vector_prac2 cannot decode adjacent equal values!");
                }
                z_size += Coder::encoding_length(v2-v1);
                if (v2-v1 > 1) {
                    big_val[big_val_cnt] = v2-v1;
                    big_val_pos[big_val_cnt] = i-old_i;
                    ++big_val_cnt;
                }
            }
            v1 = v2;
        }
        r_sum += r; r = v_buf.load_next_block();
    }
    std::cerr<<"z in MB = " << z_size/(8.0*1024.0*1024.0) << std::endl;
    std::cerr<<"z2 in MB = " << z_size2/(8.0*1024.0*1024.0) << std::endl;
    std::cerr<<"saving in MB = " << (z_size-z_size2)/(8.0*1024.0*1024.0) << std::endl;

//      (2) Write sample values and deltas
//     (a) Initialize array for sample values and pointers
    if (max_sample_value > z_size+1)
        m_sample_vals_and_pointer.set_int_width(bit_magic::l1BP(max_sample_value) + 1);
    else
        m_sample_vals_and_pointer.set_int_width(bit_magic::l1BP(z_size+1) + 1);
    m_sample_vals_and_pointer.resize(2*samples+2); // add 2 for last entry

//     (b) Initilize bit_vector for encoded data
    m_z.bit_resize(z_size);
    uint64_t* z_data = Coder::raw_data(m_z);
    uint8_t offset = 0;

//     (c) Write sample values and deltas
    v_buf.reset();
    z_size = 0;
    for (size_type i=0, j=0, r_sum=0, r = v_buf.load_next_block(), no_sample = 0; r_sum < n;) {
        for (; i < r_sum+r; ++i, --no_sample) {
            v2 = v_buf[i-r_sum];
            if (!no_sample) { // is sample
                no_sample = sd;
                m_sample_vals_and_pointer[j++] = v2;    // write samples
                m_sample_vals_and_pointer[j++] = z_size;// write pointers
            } else {
                z_size += Coder::encoding_length(v2-v1);
                Coder::encode(v2-v1, z_data, offset);   // write encoded values
            }
            v1 = v2;
        }
        r_sum += r; r = v_buf.load_next_block();
    }
    m_elements = n;
}


template<class Coder, uint32_t SampleDens, uint8_t fixedIntWidth>
enc_vector_prac2<>::size_type enc_vector_prac2<Coder, SampleDens,fixedIntWidth>::serialize(std::ostream& out) const
{
    size_type written_bytes = 0;
    out.write((char*) &m_elements, sizeof(m_elements));
    written_bytes += sizeof(m_elements);
    written_bytes += m_z.serialize(out);
    written_bytes += m_sample_vals_and_pointer.serialize(out);
    return written_bytes;
}

template<class Coder, uint32_t SampleDens, uint8_t fixedIntWidth>
void enc_vector_prac2<Coder, SampleDens,fixedIntWidth>::load(std::istream& in)
{
    in.read((char*) &m_elements, sizeof(m_elements));
    m_z.load(in);
    m_sample_vals_and_pointer.load(in);
}

template<class Coder, uint32_t SampleDens, uint8_t fixedIntWidth>
const typename enc_vector_prac2<Coder,SampleDens,fixedIntWidth>::const_iterator enc_vector_prac2<Coder, SampleDens,fixedIntWidth>::begin()const
{
    return const_iterator(this, 0);
}

template<class Coder, uint32_t SampleDens, uint8_t fixedIntWidth>
const typename enc_vector_prac2<Coder,SampleDens,fixedIntWidth>::const_iterator enc_vector_prac2<Coder, SampleDens,fixedIntWidth>::end()const
{
    return const_iterator(this, this->m_elements);
}


} // end namespace sdsl

#endif