bitcompressed_vector.hpp

Go to the documentation of this file.

// -----------------------------------------------------------------------------------------------------
// Copyright (c) 2006-2019, Knut Reinert & Freie Universität Berlin
// Copyright (c) 2016-2019, Knut Reinert & MPI für molekulare Genetik
// This file may be used, modified and/or redistributed under the terms of the 3-clause BSD-License
// shipped with this file and also available at: https://github.com/seqan/seqan3/blob/master/LICENSE.md
// -----------------------------------------------------------------------------------------------------

#pragma once

#include <type_traits>

#include <sdsl/int_vector.hpp>

#include <seqan3/alphabet/detail/alphabet_proxy.hpp>
#include <seqan3/core/concept/cereal.hpp>
#include <seqan3/core/type_traits/all.hpp>
#include <seqan3/range/shortcuts.hpp>
#include <seqan3/range/detail/random_access_iterator.hpp>
#include <seqan3/range/view/to_char.hpp>
#include <seqan3/range/view/to_rank.hpp>
#include <seqan3/range/view/convert.hpp>
#include <seqan3/std/concepts>
#include <seqan3/std/iterator>
#include <seqan3/std/ranges>

namespace seqan3
{

// forward
class debug_stream_type;

template <Alphabet alphabet_type>
    requires std::is_same_v<alphabet_type, std::remove_reference_t<alphabet_type>>
class bitcompressed_vector
{
private:
    static constexpr size_t bits_per_letter = std::ceil(std::log2(alphabet_size<alphabet_type>));

    static_assert(bits_per_letter <= 64, "Alphabet must be representable in at most 64bit.");

    using data_type = sdsl::int_vector<bits_per_letter>;

    data_type data;

    class reference_proxy_type : public alphabet_proxy<reference_proxy_type, alphabet_type>
    {
    private:
        using base_t = alphabet_proxy<reference_proxy_type, alphabet_type>;
        friend base_t;

        static uint8_t constexpr safe_bits_per_letter = (bits_per_letter ==  8 ||
                                                         bits_per_letter == 16 ||
                                                         bits_per_letter == 32) ? 64 : bits_per_letter;

        using internal_proxy_type = sdsl::int_vector_reference<sdsl::int_vector<safe_bits_per_letter>>;
        ranges::semiregular_t<internal_proxy_type> internal_proxy;

        constexpr void on_update() noexcept
        {
            internal_proxy.get() = static_cast<base_t &>(*this).to_rank();
        }

    public:
        // Import from base:
        using base_t::operator=;

        constexpr reference_proxy_type()                                         noexcept = default; 
        constexpr reference_proxy_type(reference_proxy_type const &)             noexcept = default; 
        constexpr reference_proxy_type(reference_proxy_type &&)                  noexcept = default; 
        constexpr reference_proxy_type & operator=(reference_proxy_type const &) noexcept = default; 
        constexpr reference_proxy_type & operator=(reference_proxy_type &&)      noexcept = default; 
        ~reference_proxy_type()                                                  noexcept = default; 

        reference_proxy_type(internal_proxy_type const & internal) noexcept :
            internal_proxy{internal}
        {
            static_cast<base_t &>(*this).assign_rank(internal);
        }
    };

    static_assert(WritableAlphabet<reference_proxy_type>);
    //NOTE(h-2): it is entirely unclear to me why we need this
    template <typename t>
        requires std::is_same_v<value_type_t<remove_cvref_t<t>>, alphabet_type>
    static constexpr bool has_same_value_type_v = true;

public:
    using value_type        = alphabet_type;
    using reference         = std::conditional_t<std::is_lvalue_reference_v<reference_t<data_type>>,
                                                 reference_t<data_type>,
                                                 reference_proxy_type>;
    using const_reference   = alphabet_type;
    using iterator          = detail::random_access_iterator<bitcompressed_vector>;
    using const_iterator    = detail::random_access_iterator<bitcompressed_vector const>;
    using difference_type   = difference_type_t<data_type>;
    using size_type         = size_type_t<data_type>;

    // this signals to range-v3 that something is a container :|
    using allocator_type    = void;

    bitcompressed_vector()                                                   = default; 
    constexpr bitcompressed_vector(bitcompressed_vector const &)             = default; 
    constexpr bitcompressed_vector(bitcompressed_vector &&)                  = default; 
    constexpr bitcompressed_vector & operator=(bitcompressed_vector const &) = default; 
    constexpr bitcompressed_vector & operator=(bitcompressed_vector &&)      = default; 
    ~bitcompressed_vector()                                                  = default; 

    template <std::ranges::InputRange other_range_t>
        requires has_same_value_type_v<other_range_t>
    explicit bitcompressed_vector(other_range_t && range) :
        bitcompressed_vector{seqan3::begin(range), seqan3::end(range)}
    {}

    bitcompressed_vector(size_type const count, value_type const value) :
        data(count, to_rank(value))
    {}

    template <std::ForwardIterator begin_iterator_type, std::Sentinel<begin_iterator_type> end_iterator_type>
    bitcompressed_vector(begin_iterator_type begin_it, end_iterator_type end_it)
        requires std::CommonReference<value_type_t<begin_iterator_type>, value_type>
    {
        insert(cend(), begin_it, end_it);
    }

    bitcompressed_vector(std::initializer_list<value_type> ilist) :
        bitcompressed_vector(std::begin(ilist), std::end(ilist))
    {}

    bitcompressed_vector & operator=(std::initializer_list<value_type> ilist)
    {
        assign(std::begin(ilist), std::end(ilist));
        return *this;
    }

    template <std::ranges::InputRange other_range_t>
    void assign(other_range_t && range)
        requires std::CommonReference<value_type_t<other_range_t>, value_type>
    {
        bitcompressed_vector rhs{std::forward<other_range_t>(range)};
        swap(rhs);
    }

    void assign(size_type const count, value_type const value)
    {
        bitcompressed_vector rhs{count, value};
        swap(rhs);
    }

    template <std::ForwardIterator begin_iterator_type, std::Sentinel<begin_iterator_type> end_iterator_type>
    void assign(begin_iterator_type begin_it, end_iterator_type end_it)
        requires std::CommonReference<value_type_t<begin_iterator_type>, value_type>
    {
        bitcompressed_vector rhs{begin_it, end_it};
        swap(rhs);
    }

    void assign(std::initializer_list<value_type> ilist)
    {
        assign(std::begin(ilist), std::end(ilist));
    }


    iterator begin() noexcept
    {
        return iterator{*this};
    }

    const_iterator begin() const noexcept
    {
        return const_iterator{*this};
    }

    const_iterator cbegin() const noexcept
    {
        return const_iterator{*this};
    }

    iterator end() noexcept
    {
        return iterator{*this, size()};
    }

    const_iterator end() const noexcept
    {
        return const_iterator{*this, size()};
    }

    const_iterator cend() const noexcept
    {
        return const_iterator{*this, size()};
    }

    reference at(size_type const i)
    {
        if (i >= size()) // [[unlikely]]
        {
            throw std::out_of_range{"Trying to access element behind the last in bitcompressed_vector."};
        }
        return (*this)[i];
    }

    const_reference at(size_type const i) const
    {
        if (i >= size()) // [[unlikely]]
        {
            throw std::out_of_range{"Trying to access element behind the last in bitcompressed_vector."};
        }
        return (*this)[i];
    }

    reference operator[](size_type const i) noexcept
    {
        assert(i < size());
        return data[i];
    }

    const_reference operator[](size_type const i) const noexcept
    {
        assert(i < size());
        return assign_rank_to(data[i], const_reference{});
    }

    reference front() noexcept
    {
        assert(size() > 0);
        return (*this)[0];
    }

    const_reference front() const noexcept
    {
        assert(size() > 0);
        return (*this)[0];
    }

    reference back() noexcept
    {
        assert(size() > 0);
        return (*this)[size()-1];
    }

    const_reference back() const noexcept
    {
        assert(size() > 0);
        return (*this)[size()-1];
    }

    bool empty() const noexcept
    {
        return size() == 0;
    }

    size_type size() const noexcept
    {
        return data.size();
    }

    size_type max_size() const noexcept
    {
        return data.max_size();
    }

    size_type capacity() const noexcept
    {
        return data.capacity();
    }

    void reserve(size_type const new_cap)
    {
        data.reserve(new_cap);
    }

    void shrink_to_fit()
    {
        data.shrink_to_fit();
    }

    void clear() noexcept
    {
        data.clear();
    }

    iterator insert(const_iterator pos, value_type const value)
    {
        return insert(pos, 1, value);
    }

    iterator insert(const_iterator pos, size_type const count, value_type const value)
    {
        auto const pos_as_num = std::distance(cbegin(), pos); // we want to insert BEFORE this position

        data.insert(data.begin() + pos_as_num, count, to_rank(value));

        return begin() + pos_as_num;
    }

    template <std::ForwardIterator begin_iterator_type, std::Sentinel<begin_iterator_type> end_iterator_type>
    iterator insert(const_iterator pos, begin_iterator_type begin_it, end_iterator_type end_it)
        requires std::CommonReference<value_type_t<begin_iterator_type>, value_type>
    {
        auto const pos_as_num = std::distance(cbegin(), pos);

        auto v = std::ranges::subrange<begin_iterator_type, end_iterator_type>{begin_it, end_it}
               | view::convert<value_type>
               | view::to_rank;
        data.insert(data.begin() + pos_as_num, seqan3::begin(v), seqan3::end(v));

        return begin() + pos_as_num;
    }

    iterator insert(const_iterator pos, std::initializer_list<value_type> const & ilist)
    {
        return insert(pos, ilist.begin(), ilist.end());
    }

    iterator erase(const_iterator begin_it, const_iterator end_it)
    {
        if (begin_it >= end_it) // [[unlikely]]
            return begin() + std::distance(cbegin(), end_it);

        auto const begin_it_pos = std::distance(cbegin(), begin_it);
        auto const end_it_pos = std::distance(cbegin(), end_it);

        data.erase(data.cbegin() + begin_it_pos,
                   data.cbegin() + end_it_pos);

        return begin() + begin_it_pos;
    }

    iterator erase(const_iterator pos)
    {
       return erase(pos, pos + 1);
    }

    void push_back(value_type const value)
    {
        data.push_back(to_rank(value));
    }

    void pop_back()
    {
        assert(size() > 0);
        data.pop_back();
    }

    void resize(size_type const count)
    {
        assert(count < max_size());
        data.resize(count);
    }

    void resize(size_type const count, value_type const value)
    {
        assert(count < max_size());
        data.resize(count, to_rank(value));
    }

    constexpr void swap(bitcompressed_vector & rhs) noexcept
    {
        std::swap(data, rhs.data);
    }

    constexpr void swap(bitcompressed_vector && rhs) noexcept
    {
        std::swap(data, rhs.data);
    }

    friend constexpr void swap(bitcompressed_vector & lhs, bitcompressed_vector & rhs) noexcept
    {
        std::swap(lhs, rhs);
    }

    friend constexpr void swap(bitcompressed_vector && lhs, bitcompressed_vector && rhs) noexcept
    {
        std::swap(lhs, rhs);
    }

    constexpr bool operator==(bitcompressed_vector const & rhs) const noexcept
    {
        return data == rhs.data;
    }

    constexpr bool operator!=(bitcompressed_vector const & rhs) const noexcept
    {
        return data != rhs.data;
    }

    constexpr bool operator<(bitcompressed_vector const & rhs) const noexcept
    {
        return data < rhs.data;
    }

    constexpr bool operator>(bitcompressed_vector const & rhs) const noexcept
    {
        return data > rhs.data;
    }

    constexpr bool operator<=(bitcompressed_vector const & rhs) const noexcept
    {
        return data <= rhs.data;
    }

    constexpr bool operator>=(bitcompressed_vector const & rhs) const noexcept
    {
        return data >= rhs.data;
    }

    template <CerealArchive archive_t>
    void CEREAL_SERIALIZE_FUNCTION_NAME(archive_t & archive)
    {
        archive(data); //TODO: data not yet serialisable
    }
};

} // namespace seqan3