IntRepr.hpp

Go to the documentation of this file.

#pragma once

#include <type_traits>

#include <sdsl/bits.hpp>

#include <tudocomp/ds/uint_t.hpp>
#include <tudocomp/ds/dynamic_t.hpp>

namespace tdc {namespace int_vector {
    enum class ElementStorageMode {
        Direct,
        BitPacked
    };

    using DynamicIntValueType = uint64_t;

    struct DynamicWidthMemRw {
        inline static void write_int(uint64_t* word, uint64_t x, uint8_t offset, const uint8_t len) {
            sdsl::bits::write_int(word, x, offset, len);
        }
        inline static uint64_t read_int(const uint64_t* word, uint8_t offset, const uint8_t len) {
            return sdsl::bits::read_int(word, offset, len);
        }
    };
    struct BitWidthMemRw {
        inline static void write_int(uint64_t* word, uint64_t v, uint8_t o, const uint8_t) {
            auto& p = *word;
            const auto mask = uint64_t(1) << o;

            v &= 1;
            p &= (~mask);
            p |= (uint64_t(v) << o);
        }
        inline static uint64_t read_int(const uint64_t* word, uint8_t o, const uint8_t) {
            const auto p = *word;
            const auto mask = uint64_t(1) << o;

            return (p & mask) != 0;
        }
    };
    template<class MB, class MemRw>
    struct RefDispatch {
        typedef MB SelfMaxBit;

        template<class Ref, class V>
        inline static void assign(Ref& self, V v) {
            MemRw::write_int(
                self.m_ptr.m_ptr,
                v,
                self.m_ptr.m_bit_offset,
                self.m_ptr.data_bit_size()
            );
        }

        template<class Ref, class R>
        inline static R cast_for_op(const Ref& self) {
            return MemRw::read_int(
                self.m_ptr.m_ptr,
                self.m_ptr.m_bit_offset,
                self.m_ptr.data_bit_size()
            );
        }
    };
    template<typename const_qual_ptr_t, size_t N>
    class IntPtrFixedWidthRepr {
    public:
        const_qual_ptr_t m_ptr;
        uint8_t m_bit_offset;
    private:
        //const uint8_t m_bit_size;
    public:
        IntPtrFixedWidthRepr(const_qual_ptr_t ptr, uint8_t offset, uint8_t /*size*/):
            m_ptr(ptr), m_bit_offset(offset) /*, m_bit_size(size)*/ {}
        inline uint8_t data_bit_size() const { return N; }
        inline void set_data_bit_size(uint8_t x) { }
        inline IntPtrFixedWidthRepr data_offset_to(const_qual_ptr_t ptr, uint8_t offset) const {
            return IntPtrFixedWidthRepr(ptr, offset, this->data_bit_size());
        }
    };
    template<typename const_qual_ptr_t>
    class IntPtrDynamicWidthRepr {
    public:
        const_qual_ptr_t m_ptr;
        uint8_t m_bit_offset;
    private:
        uint8_t m_bit_size;
    public:
        IntPtrDynamicWidthRepr(const_qual_ptr_t ptr, uint8_t offset, uint8_t size):
            m_ptr(ptr), m_bit_offset(offset), m_bit_size(size) {}
        inline uint8_t data_bit_size() const { return m_bit_size; }
        inline void set_data_bit_size(uint8_t x) { m_bit_size = x; }
        inline IntPtrDynamicWidthRepr data_offset_to(const_qual_ptr_t ptr, uint8_t offset) const {
            return IntPtrDynamicWidthRepr(ptr, offset, this->data_bit_size());
        }
    };
    template<size_t N>
    struct FixedBitPackingVectorRepr {
        using internal_data_type = DynamicIntValueType;

        std::vector<internal_data_type> m_vec;
        uint64_t m_real_size;

        inline FixedBitPackingVectorRepr():
            m_vec(), m_real_size(0) {}
        inline FixedBitPackingVectorRepr(const FixedBitPackingVectorRepr& other):
            m_vec(other.m_vec), m_real_size(other.m_real_size) {}
        inline FixedBitPackingVectorRepr(FixedBitPackingVectorRepr&& other):
            m_vec(std::move(other.m_vec)), m_real_size(other.m_real_size) {}

        inline uint8_t raw_width() const { return N; }
        inline void set_width_raw(uint8_t) { }
    };
    struct DynamicBitPackingVectorRepr {
        using internal_data_type = DynamicIntValueType;

        std::vector<internal_data_type> m_vec;
        uint64_t m_real_size;
        uint8_t m_width;

        inline DynamicBitPackingVectorRepr():
            m_vec(), m_real_size(0), m_width(64) {}
        inline DynamicBitPackingVectorRepr(const DynamicBitPackingVectorRepr& other):
            m_vec(other.m_vec), m_real_size(other.m_real_size), m_width(other.m_width) {}
        inline DynamicBitPackingVectorRepr(DynamicBitPackingVectorRepr&& other):
            m_vec(std::move(other.m_vec)), m_real_size(other.m_real_size), m_width(other.m_width) {}

        inline uint8_t raw_width() const { return m_width; }
        inline void set_width_raw(uint8_t width) { m_width = width; }
    };

    template<typename T, typename X = void>
    struct IntRepr {};

    template<size_t N>
    struct IntRepr<uint_impl_t<N>, typename std::enable_if_t<(N > 1) && (N <= 32)>> {
        using value_type = uint_impl_t<N>;
        using mem_rw = DynamicWidthMemRw;
        using IntOpDispatch = RefDispatch<uint32_t, mem_rw>;

        using ConstIntPtrBase = IntPtrFixedWidthRepr<DynamicIntValueType const*, N>;
        using IntPtrBase = IntPtrFixedWidthRepr<DynamicIntValueType*, N>;

        using BitPackingVectorRepr = FixedBitPackingVectorRepr<N>;
    };

    template<size_t N>
    struct IntRepr<uint_impl_t<N>, typename std::enable_if_t<(N > 32) && (N <= 64)>> {
        using value_type = uint_impl_t<N>;
        using mem_rw = DynamicWidthMemRw;
        using IntOpDispatch = RefDispatch<uint64_t, mem_rw>;

        using ConstIntPtrBase = IntPtrFixedWidthRepr<DynamicIntValueType const*, N>;
        using IntPtrBase = IntPtrFixedWidthRepr<DynamicIntValueType*, N>;

        using BitPackingVectorRepr = FixedBitPackingVectorRepr<N>;
    };

    template<>
    struct IntRepr<bool> {
        using value_type = bool;
        using mem_rw = BitWidthMemRw;
        using IntOpDispatch = RefDispatch<uint32_t, mem_rw>;

        using ConstIntPtrBase = IntPtrFixedWidthRepr<DynamicIntValueType const*, 1>;
        using IntPtrBase = IntPtrFixedWidthRepr<DynamicIntValueType*, 1>;

        using BitPackingVectorRepr = FixedBitPackingVectorRepr<1>;
    };

    template<>
    struct IntRepr<dynamic_t> {
        using value_type = uint64_t;
        using mem_rw = DynamicWidthMemRw;
        using IntOpDispatch = RefDispatch<uint64_t, mem_rw>;

        using ConstIntPtrBase = IntPtrDynamicWidthRepr<DynamicIntValueType const*>;
        using IntPtrBase = IntPtrDynamicWidthRepr<DynamicIntValueType*>;

        using BitPackingVectorRepr = DynamicBitPackingVectorRepr;
    };

    template<size_t N>
    struct IntRepr<uint_impl_t<N>, typename std::enable_if_t<(N <= 1)>>; // Unused

    template<size_t N>
    struct IntRepr<uint_impl_t<N>, typename std::enable_if_t<(N > 64)>>; // Invalid

}}