bitcompressed_vector.hpp

Go to the documentation of this file.

// -----------------------------------------------------------------------------------------------------
// Copyright (c) 2022 deCODE Genetics
// Copyright (c) 2006-2020, Knut Reinert & Freie Universität Berlin
// Copyright (c) 2016-2020, 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/biocpp/biocpp-core/blob/main/LICENSE.md
// -----------------------------------------------------------------------------------------------------
 
#pragma once
 
#include <climits>
#include <concepts>
#include <iterator>
#include <ranges>
#include <type_traits>
 
#include <bio/alphabet/proxy_base.hpp>
#include <bio/ranges/detail/random_access_iterator.hpp>
#include <bio/ranges/views/convert.hpp>
#include <bio/ranges/views/repeat_n.hpp>
#include <bio/ranges/views/to_char.hpp>
#include <bio/ranges/views/to_rank.hpp>
 
namespace bio::ranges
{
 
template <alphabet::writable_semialphabet alphabet_type>
    requires std::regular<alphabet_type>
class bitcompressed_vector
{
private:
    static constexpr size_t bits_per_letter = std::bit_width(alphabet::size<alphabet_type>);
    static_assert(bits_per_letter <= 64, "alphabet must be representable in at most 64bit.");
 
    using word_type                            = uint64_t;
    static constexpr size_t   word_size        = sizeof(word_type) * CHAR_BIT;
    static constexpr size_t   letters_per_word = word_size / bits_per_letter;
    static constexpr uint64_t mask             = (1ull << bits_per_letter) - 1ull;
 
    using data_type = std::vector<uint64_t>;
 
    size_t size_ = 0;
 
    data_type data;
 
    static uint64_t get_rank(data_type const & vec, size_t const i) noexcept
    {
        assert(i / letters_per_word < vec.size());
        uint64_t const word   = vec[i / letters_per_word];
        size_t const   offset = (i % letters_per_word) * bits_per_letter;
        return (word >> offset) & mask;
    }
 
    static void set_rank(data_type & vec, size_t const i, uint64_t const rank) noexcept
    {
        assert(i / letters_per_word < vec.size());
        uint64_t &   word   = vec[i / letters_per_word];
        size_t const offset = (i % letters_per_word) * bits_per_letter;
        word &= ~(mask << offset);
        word |= rank << offset;
    }
 
    void clear_unused_bits_in_last_word()
    {
        if (data.empty() || (size() % letters_per_word == 0))
            return;
 
        size_t const offset = (size() % letters_per_word) * bits_per_letter;
        data.back() &= ((1ull << offset) - 1ull);
    }
 
    class reference_proxy_type : public alphabet::proxy_base<reference_proxy_type, alphabet_type>
    {
    private:
        using base_t = alphabet::proxy_base<reference_proxy_type, alphabet_type>;
 
        data_type * data_ptr;
        size_t      index;
 
    public:
        reference_proxy_type()                                                = delete;
        constexpr reference_proxy_type(reference_proxy_type const &) noexcept = default; 
        constexpr reference_proxy_type(reference_proxy_type &&) noexcept      = default; 
        ~reference_proxy_type() noexcept                                      = default; 
 
        // Import from base:
        using base_t::operator=;
 
        // NOLINTNEXTLINE(bugprone-unhandled-self-assignment)
        constexpr reference_proxy_type & operator=(reference_proxy_type const & rhs)
        {
            return assign_rank(rhs.to_rank());
        }
 
        // NOLINTNEXTLINE(bugprone-unhandled-self-assignment)
        constexpr reference_proxy_type const & operator=(reference_proxy_type const & rhs) const
        {
            return assign_rank(rhs.to_rank());
        }
 
        reference_proxy_type(data_type * const data_ptr_, size_t const index_) noexcept :
          data_ptr{data_ptr_}, index{index_}
        {}
 
        constexpr alphabet::rank_t<alphabet_type> to_rank() const noexcept { return get_rank(*data_ptr, index); }
 
        constexpr reference_proxy_type & assign_rank(alphabet::rank_t<alphabet_type> const r) noexcept
        {
            set_rank(*data_ptr, index, r);
            return *this;
        }
 
        constexpr reference_proxy_type const & assign_rank(alphabet::rank_t<alphabet_type> const r) const noexcept
        {
            set_rank(*data_ptr, index, r);
            return *this;
        }
    };
 
    static_assert(alphabet::writable_alphabet<reference_proxy_type>);
    //NOTE(h-2): it is entirely unclear to me why we need this
    template <typename t>
        requires std::is_same_v<std::ranges::range_value_t<std::remove_cvref_t<t>>, alphabet_type>
    static constexpr bool has_same_value_type_v = true;
 
public:
    using value_type      = alphabet_type;
    using reference       = 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 = std::ranges::range_difference_t<data_type>;
    using size_type       = std::ranges::range_size_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 &&) noexcept             = default; 
    constexpr bitcompressed_vector & operator=(bitcompressed_vector const &)     = default; 
    constexpr bitcompressed_vector & operator=(bitcompressed_vector &&) noexcept = default; 
    ~bitcompressed_vector() noexcept                                             = default; 
 
    template <meta::different_from<bitcompressed_vector> other_range_t>
        requires(std::ranges::input_range<other_range_t> && has_same_value_type_v<other_range_t>)
    explicit bitcompressed_vector(other_range_t && range) :
      bitcompressed_vector{std::ranges::begin(range), std::ranges::end(range)}
    {}
 
    bitcompressed_vector(size_type const count, value_type const value) { insert(cend(), count, value); }
 
    template <std::forward_iterator begin_iterator_type, typename end_iterator_type>
    bitcompressed_vector(begin_iterator_type begin_it, end_iterator_type end_it)
        requires(std::sentinel_for<end_iterator_type, begin_iterator_type> &&
                 std::common_reference_with<std::iter_value_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::input_range other_range_t>
    void assign(other_range_t && range)
        requires std::common_reference_with<std::ranges::range_value_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::forward_iterator begin_iterator_type, typename end_iterator_type>
    void assign(begin_iterator_type begin_it, end_iterator_type end_it)
        requires(std::sentinel_for<end_iterator_type, begin_iterator_type> &&
                 std::common_reference_with<std::iter_value_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 alphabet::assign_rank_to(get_rank(data, i), alphabet_type{});
    }
 
    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];
    }
 
    constexpr data_type & raw_data() noexcept { return data; }
 
    constexpr data_type const & raw_data() const noexcept { return data; }
 
    bool empty() const noexcept { return size() == 0; }
 
    size_type size() const noexcept { return size_; }
 
    size_type max_size() const noexcept
    {
        // this protects against underflow in the multiplication
        return std::max<size_type>(data.max_size(), data.max_size() * letters_per_word);
    }
 
    size_type capacity() const noexcept { return data.capacity() * letters_per_word; }
 
    void reserve(size_type const new_cap)
    {
        data.reserve(new_cap / letters_per_word + (new_cap % letters_per_word != 0));
    }
 
    void shrink_to_fit() { data.shrink_to_fit(); }
 
    void clear() noexcept
    {
        data.clear();
        size_ = 0;
    }
 
    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 v = views::repeat_n(value, count);
        return insert(pos, v.begin(), v.end());
    }
 
    template <std::forward_iterator begin_iterator_type, typename end_iterator_type>
    iterator insert(const_iterator pos, begin_iterator_type begin_it, end_iterator_type end_it)
        requires(std::sentinel_for<end_iterator_type, begin_iterator_type> &&
                 std::common_reference_with<std::iter_value_t<begin_iterator_type>, value_type>)
    {
        //TODO UPDATE DOCUMENTATION TO REFLECT THIS
        //TODO this is not ideal, always linear
        size_t const         pos_as_num     = std::distance(cbegin(), pos);
        size_t const         size_of_insert = std::distance(begin_it, end_it);
        bitcompressed_vector tmp;
        tmp.resize(size() + size_of_insert);
        //TODO use constrained algorithms here once proxy_base is out-iterator-compatible
        std::copy(cbegin(), pos, tmp.begin());
        std::copy(begin_it, end_it, tmp.begin() + pos_as_num);
        std::copy(cbegin() + pos_as_num, cend(), tmp.begin() + pos_as_num + size_of_insert);
 
        std::swap(*this, tmp);
        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)
            return end();
 
        //TODO this is not ideal, always linear
        size_t const         begin_pos_of_removal = std::distance(cbegin(), begin_it);
        size_t const         size_of_removal      = std::distance(begin_it, end_it);
        bitcompressed_vector tmp;
        tmp.resize(size() - size_of_removal);
        //TODO use constrained algorithms here once proxy_base is out-iterator-compatible
        std::copy(cbegin(), begin_it, tmp.begin());
        std::copy(end_it, cend(), tmp.begin() + begin_pos_of_removal);
 
        std::swap(*this, tmp);
        return begin() + begin_pos_of_removal + size_of_removal;
    }
 
    iterator erase(const_iterator pos) { return erase(pos, pos + 1); }
 
    void push_back(value_type const value)
    {
        if (data.size() * letters_per_word == size_) // the last word is "full"
            data.emplace_back();
 
        set_rank(data, size(), alphabet::to_rank(value));
        ++size_;
    }
 
    void pop_back()
    {
        assert(size() > 0);
        if ((size_--) % letters_per_word == 1) // the last word contains only one letter
            data.pop_back();
        else
            clear_unused_bits_in_last_word();
    }
 
    void resize(size_type const count)
    {
        assert(count < max_size());
        data.resize(count / letters_per_word + (count % letters_per_word != 0));
        size_ = count;
        clear_unused_bits_in_last_word();
    }
 
    void resize(size_type const count, value_type const value)
    {
        assert(count < max_size());
        size_t old_size = size_;
        resize(count);
        for (size_t i = old_size; i < size(); ++i)
            set_rank(data, i, alphabet::to_rank(value));
    }
 
    constexpr void swap(bitcompressed_vector & rhs) noexcept { std::swap(*this, rhs); }
 
    constexpr void swap(bitcompressed_vector && rhs) noexcept { std::swap(*this, rhs); }
 
    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);
    }
 
    friend auto operator<=>(bitcompressed_vector const & lhs, bitcompressed_vector const & rhs) noexcept = default;
 
    template <typename archive_t>
    void serialize(archive_t & archive)
    {
        archive(size_);
        archive(data);
    }
};
 
} // namespace bio::ranges