Loading...
Searching...
No Matches
bitpacked_sequence.hpp
Go to the documentation of this file.
// SPDX-FileCopyrightText: 2006-2025 Knut Reinert & Freie Universität Berlin
// SPDX-FileCopyrightText: 2016-2025 Knut Reinert & MPI für molekulare Genetik
// SPDX-License-Identifier: BSD-3-Clause
#pragma once
#include <concepts>
#include <iterator>
#include <ranges>
#include <type_traits>
#include <seqan3/alphabet/detail/alphabet_proxy.hpp>
#include <seqan3/alphabet/views/to_char.hpp>
#include <seqan3/alphabet/views/to_rank.hpp>
#include <seqan3/contrib/sdsl-lite.hpp>
#include <seqan3/core/concept/cereal.hpp>
#include <seqan3/core/range/detail/random_access_iterator.hpp>
#include <seqan3/utility/math.hpp>
#include <seqan3/utility/views/convert.hpp>
namespace seqan3
{
template <writable_semialphabet alphabet_type>
requires std::regular<alphabet_type>
class bitpacked_sequence
{
private:
static constexpr size_t bits_per_letter = detail::ceil_log2(alphabet_size<alphabet_type>);
static_assert(bits_per_letter <= 64, "alphabet must be representable in at most 64bit.");
using data_type = seqan3::contrib::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;
std::ranges::range_reference_t<data_type> internal_proxy;
constexpr void on_update() noexcept
{
internal_proxy = base_t::to_rank();
}
public:
// Import from base:
using base_t::operator=;
reference_proxy_type() = delete;
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(std::ranges::range_reference_t<data_type> const internal) noexcept :
internal_proxy{internal}
{
// Call alphabet_base's assign_rank to prevent calling on_update() during construction
// which is not necessary, because internal_proxy is already correctly initialised!
base_t::base_t::assign_rank(static_cast<alphabet_rank_t<alphabet_type>>(internal));
}
};
static_assert(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<bitpacked_sequence>;
using const_iterator = detail::random_access_iterator<bitpacked_sequence const>;
using difference_type = std::ranges::range_difference_t<data_type>;
using size_type = std::ranges::range_size_t<data_type>;
bitpacked_sequence() = default;
constexpr bitpacked_sequence(bitpacked_sequence const &) = default;
constexpr bitpacked_sequence(bitpacked_sequence &&) = default;
constexpr bitpacked_sequence & operator=(bitpacked_sequence const &) = default;
constexpr bitpacked_sequence & operator=(bitpacked_sequence &&) = default;
~bitpacked_sequence() = default;
template <typename other_range_t>
requires (!std::same_as<bitpacked_sequence, std::remove_cvref_t<other_range_t>>)
&& std::ranges::input_range<other_range_t> && has_same_value_type_v<other_range_t>
explicit bitpacked_sequence(other_range_t && range) :
bitpacked_sequence{std::ranges::begin(range), std::ranges::end(range)}
{}
bitpacked_sequence(size_type const count, value_type const value) : data(count, to_rank(value))
{}
template <std::forward_iterator begin_iterator_type, typename end_iterator_type>
bitpacked_sequence(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);
}
bitpacked_sequence(std::initializer_list<value_type> ilist) : bitpacked_sequence(std::begin(ilist), std::end(ilist))
{}
bitpacked_sequence & 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>
{
bitpacked_sequence rhs{std::forward<other_range_t>(range)};
swap(rhs);
}
void assign(size_type const count, value_type const value)
{
bitpacked_sequence 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>
{
bitpacked_sequence 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 bitpacked_sequence."};
}
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 bitpacked_sequence."};
}
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];
}
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 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::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>
{
auto const pos_as_num = std::distance(cbegin(), pos);
auto v = std::ranges::subrange<begin_iterator_type, end_iterator_type>{begin_it, end_it}
| views::convert<value_type> | views::to_rank;
data.insert(data.begin() + pos_as_num, std::ranges::begin(v), std::ranges::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(bitpacked_sequence & rhs) noexcept
{
std::swap(data, rhs.data);
}
constexpr void swap(bitpacked_sequence && rhs) noexcept
{
std::swap(data, rhs.data);
}
friend constexpr void swap(bitpacked_sequence & lhs, bitpacked_sequence & rhs) noexcept
{
std::swap(lhs, rhs);
}
friend constexpr void swap(bitpacked_sequence && lhs, bitpacked_sequence && rhs) noexcept
{
std::swap(lhs, rhs);
}
constexpr bool operator==(bitpacked_sequence const & rhs) const noexcept
{
return data == rhs.data;
}
constexpr bool operator!=(bitpacked_sequence const & rhs) const noexcept
{
return data != rhs.data;
}
constexpr bool operator<(bitpacked_sequence const & rhs) const noexcept
{
return data < rhs.data;
}
constexpr bool operator>(bitpacked_sequence const & rhs) const noexcept
{
return data > rhs.data;
}
constexpr bool operator<=(bitpacked_sequence const & rhs) const noexcept
{
return data <= rhs.data;
}
constexpr bool operator>=(bitpacked_sequence const & rhs) const noexcept
{
return data >= rhs.data;
}
template <cereal_archive archive_t>
void CEREAL_SERIALIZE_FUNCTION_NAME(archive_t & archive)
{
archive(data);
}
};
} // namespace seqan3
alphabet_proxy.hpp
Provides seqan3::alphabet_proxy.
std::begin
T begin(T... args)
cereal.hpp
Adaptions of concepts from the Cereal library.
seqan3::alphabet_proxy
A CRTP-base that eases the definition of proxy types returned in place of regular alphabets.
Definition alphabet_proxy.hpp:62
seqan3::alphabet_proxy< reference_proxy_type, alphabet_type >::assign_rank
constexpr reference_proxy_type & assign_rank(alphabet_rank_t< alphabet_type > const r) noexcept
Definition alphabet_proxy.hpp:142
seqan3::alphabet_proxy< reference_proxy_type, alphabet_type >::to_rank
constexpr auto to_rank() const noexcept
Definition alphabet_proxy.hpp:204
seqan3::bitpacked_sequence::assign
void assign(size_type const count, value_type const value)
Assign with count times value.
Definition bitpacked_sequence.hpp:315
seqan3::bitpacked_sequence::value_type
alphabet_type value_type
Equals the alphabet_type.
Definition bitpacked_sequence.hpp:135
seqan3::bitpacked_sequence::difference_type
std::ranges::range_difference_t< data_type > difference_type
A signed integer type (usually std::ptrdiff_t).
Definition bitpacked_sequence.hpp:161
seqan3::bitpacked_sequence::insert
iterator insert(const_iterator pos, begin_iterator_type begin_it, end_iterator_type end_it)
Inserts elements from range [begin_it, end_it) before position in the container.
Definition bitpacked_sequence.hpp:807
seqan3::bitpacked_sequence::bitpacked_sequence
constexpr bitpacked_sequence(bitpacked_sequence &&)=default
Defaulted.
seqan3::bitpacked_sequence::erase
iterator erase(const_iterator pos)
Removes specified elements from the container.
Definition bitpacked_sequence.hpp:900
seqan3::bitpacked_sequence::reference
reference_proxy_type reference
A proxy type (models seqan3::writable_semialphabet) that enables assignment, think of it as value_typ...
Definition bitpacked_sequence.hpp:141
seqan3::bitpacked_sequence::operator>
constexpr bool operator>(bitpacked_sequence const &rhs) const noexcept
Checks whether *this is greater than rhs.
Definition bitpacked_sequence.hpp:1080
seqan3::bitpacked_sequence::max_size
size_type max_size() const noexcept
Returns the maximum number of elements the container is able to hold due to system or library impleme...
Definition bitpacked_sequence.hpp:634
seqan3::bitpacked_sequence::empty
bool empty() const noexcept
Checks whether the container is empty.
Definition bitpacked_sequence.hpp:595
seqan3::bitpacked_sequence::operator[]
reference operator[](size_type const i) noexcept
Return the i-th element.
Definition bitpacked_sequence.hpp:489
seqan3::bitpacked_sequence::back
const_reference back() const noexcept
Return the last element.
Definition bitpacked_sequence.hpp:552
seqan3::bitpacked_sequence::cbegin
const_iterator cbegin() const noexcept
Returns an iterator to the first element of the container.
Definition bitpacked_sequence.hpp:397
seqan3::bitpacked_sequence::erase
iterator erase(const_iterator begin_it, const_iterator end_it)
Removes specified elements from the container.
Definition bitpacked_sequence.hpp:866
seqan3::bitpacked_sequence::insert
iterator insert(const_iterator pos, value_type const value)
Inserts value before position in the container.
Definition bitpacked_sequence.hpp:745
seqan3::bitpacked_sequence::~bitpacked_sequence
~bitpacked_sequence()=default
Defaulted.
seqan3::bitpacked_sequence::resize
void resize(size_type const count, value_type const value)
Resizes the container to contain count elements.
Definition bitpacked_sequence.hpp:989
seqan3::bitpacked_sequence::clear
void clear() noexcept
Removes all elements from the container.
Definition bitpacked_sequence.hpp:720
seqan3::bitpacked_sequence::operator<=
constexpr bool operator<=(bitpacked_sequence const &rhs) const noexcept
Checks whether *this is less than or equal to rhs.
Definition bitpacked_sequence.hpp:1089
seqan3::bitpacked_sequence::end
const_iterator end() const noexcept
Returns an iterator to the element following the last element of the container.
Definition bitpacked_sequence.hpp:423
seqan3::bitpacked_sequence::operator>=
constexpr bool operator>=(bitpacked_sequence const &rhs) const noexcept
Checks whether *this is greater than or equal to rhs.
Definition bitpacked_sequence.hpp:1098
seqan3::bitpacked_sequence::bitpacked_sequence
constexpr bitpacked_sequence(bitpacked_sequence const &)=default
Defaulted.
seqan3::bitpacked_sequence::push_back
void push_back(value_type const value)
Appends the given element value to the end of the container.
Definition bitpacked_sequence.hpp:922
seqan3::bitpacked_sequence::at
const_reference at(size_type const i) const
Return the i-th element.
Definition bitpacked_sequence.hpp:463
seqan3::bitpacked_sequence::operator!=
constexpr bool operator!=(bitpacked_sequence const &rhs) const noexcept
Checks whether *this is not equal to rhs.
Definition bitpacked_sequence.hpp:1062
seqan3::bitpacked_sequence::end
iterator end() noexcept
Returns an iterator to the element following the last element of the container.
Definition bitpacked_sequence.hpp:417
seqan3::bitpacked_sequence::assign
void assign(std::initializer_list< value_type > ilist)
Assign from std::initializer_list.
Definition bitpacked_sequence.hpp:360
seqan3::bitpacked_sequence::reserve
void reserve(size_type const new_cap)
Increase the capacity to a value that's greater or equal to new_cap.
Definition bitpacked_sequence.hpp:677
seqan3::bitpacked_sequence::begin
const_iterator begin() const noexcept
Returns an iterator to the first element of the container.
Definition bitpacked_sequence.hpp:391
seqan3::bitpacked_sequence::const_iterator
detail::random_access_iterator< bitpacked_sequence const > const_iterator
The const_iterator type of this container (a random access iterator).
Definition bitpacked_sequence.hpp:156
seqan3::bitpacked_sequence::bitpacked_sequence
bitpacked_sequence(std::initializer_list< value_type > ilist)
Construct from std::initializer_list.
Definition bitpacked_sequence.hpp:256
seqan3::bitpacked_sequence::shrink_to_fit
void shrink_to_fit()
Requests the removal of unused capacity.
Definition bitpacked_sequence.hpp:699
seqan3::bitpacked_sequence::operator[]
const_reference operator[](size_type const i) const noexcept
Return the i-th element.
Definition bitpacked_sequence.hpp:496
seqan3::bitpacked_sequence::begin
iterator begin() noexcept
Returns an iterator to the first element of the container.
Definition bitpacked_sequence.hpp:385
seqan3::bitpacked_sequence::size_type
std::ranges::range_size_t< data_type > size_type
An unsigned integer type (usually std::size_t).
Definition bitpacked_sequence.hpp:166
seqan3::bitpacked_sequence::capacity
size_type capacity() const noexcept
Returns the number of elements that the container has currently allocated space for.
Definition bitpacked_sequence.hpp:652
seqan3::bitpacked_sequence::assign
void assign(other_range_t &&range)
Assign from a different range.
Definition bitpacked_sequence.hpp:294
seqan3::bitpacked_sequence::iterator
detail::random_access_iterator< bitpacked_sequence > iterator
The iterator type of this container (a random access iterator).
Definition bitpacked_sequence.hpp:151
seqan3::bitpacked_sequence::const_reference
alphabet_type const_reference
Equals the alphabet_type / value_type.
Definition bitpacked_sequence.hpp:146
seqan3::bitpacked_sequence::insert
iterator insert(const_iterator pos, std::initializer_list< value_type > const &ilist)
Inserts elements from initializer list before position in the container.
Definition bitpacked_sequence.hpp:840
seqan3::bitpacked_sequence::at
reference at(size_type const i)
Return the i-th element.
Definition bitpacked_sequence.hpp:453
seqan3::bitpacked_sequence::bitpacked_sequence
bitpacked_sequence(begin_iterator_type begin_it, end_iterator_type end_it)
Construct from pair of iterators.
Definition bitpacked_sequence.hpp:236
seqan3::bitpacked_sequence::swap
friend constexpr void swap(bitpacked_sequence &lhs, bitpacked_sequence &rhs) noexcept
Swap contents with another instance.
Definition bitpacked_sequence.hpp:1033
seqan3::bitpacked_sequence::front
const_reference front() const noexcept
Return the first element. Calling front on an empty container is undefined.
Definition bitpacked_sequence.hpp:524
seqan3::bitpacked_sequence::operator=
constexpr bitpacked_sequence & operator=(bitpacked_sequence const &)=default
Defaulted.
seqan3::bitpacked_sequence::raw_data
constexpr data_type const & raw_data() const noexcept
Provides direct, unsafe access to underlying data structures.
Definition bitpacked_sequence.hpp:573
seqan3::bitpacked_sequence::operator==
constexpr bool operator==(bitpacked_sequence const &rhs) const noexcept
Checks whether *this is equal to rhs.
Definition bitpacked_sequence.hpp:1053
seqan3::bitpacked_sequence::swap
friend constexpr void swap(bitpacked_sequence &&lhs, bitpacked_sequence &&rhs) noexcept
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition bitpacked_sequence.hpp:1039
seqan3::bitpacked_sequence::cend
const_iterator cend() const noexcept
Returns an iterator to the element following the last element of the container.
Definition bitpacked_sequence.hpp:429
seqan3::bitpacked_sequence::bitpacked_sequence
bitpacked_sequence(size_type const count, value_type const value)
Construct with count times value.
Definition bitpacked_sequence.hpp:215
seqan3::bitpacked_sequence::operator=
bitpacked_sequence & operator=(std::initializer_list< value_type > ilist)
Assign from std::initializer_list.
Definition bitpacked_sequence.hpp:272
seqan3::bitpacked_sequence::resize
void resize(size_type const count)
Resizes the container to contain count elements.
Definition bitpacked_sequence.hpp:979
seqan3::bitpacked_sequence::pop_back
void pop_back()
Removes the last element of the container.
Definition bitpacked_sequence.hpp:945
seqan3::bitpacked_sequence::back
reference back() noexcept
Return the last element.
Definition bitpacked_sequence.hpp:545
seqan3::bitpacked_sequence::insert
iterator insert(const_iterator pos, size_type const count, value_type const value)
Inserts count copies of value before position in the container.
Definition bitpacked_sequence.hpp:771
seqan3::bitpacked_sequence::bitpacked_sequence
bitpacked_sequence()=default
Defaulted.
seqan3::bitpacked_sequence::swap
constexpr void swap(bitpacked_sequence &&rhs) noexcept
Swap contents with another instance.
Definition bitpacked_sequence.hpp:1014
seqan3::bitpacked_sequence::bitpacked_sequence
bitpacked_sequence(other_range_t &&range)
Construct from a different range.
Definition bitpacked_sequence.hpp:197
seqan3::bitpacked_sequence::raw_data
constexpr data_type & raw_data() noexcept
Provides direct, unsafe access to underlying data structures.
Definition bitpacked_sequence.hpp:567
seqan3::bitpacked_sequence::operator<
constexpr bool operator<(bitpacked_sequence const &rhs) const noexcept
Checks whether *this is less than rhs.
Definition bitpacked_sequence.hpp:1071
seqan3::bitpacked_sequence::swap
constexpr void swap(bitpacked_sequence &rhs) noexcept
Swap contents with another instance.
Definition bitpacked_sequence.hpp:1008
seqan3::bitpacked_sequence::size
size_type size() const noexcept
Returns the number of elements in the container, i.e. std::distance(begin(), end()).
Definition bitpacked_sequence.hpp:613
seqan3::bitpacked_sequence::front
reference front() noexcept
Return the first element. Calling front on an empty container is undefined.
Definition bitpacked_sequence.hpp:517
seqan3::bitpacked_sequence::operator=
constexpr bitpacked_sequence & operator=(bitpacked_sequence &&)=default
Defaulted.
seqan3::bitpacked_sequence::assign
void assign(begin_iterator_type begin_it, end_iterator_type end_it)
Assign from pair of iterators.
Definition bitpacked_sequence.hpp:339
std::distance
T distance(T... args)
std::end
T end(T... args)
std::forward
T forward(T... args)
seqan3::views::to_rank
auto const to_rank
A view that calls seqan3::to_rank() on each element in the input range.
Definition to_rank.hpp:63
seqan3::alphabet_size
constexpr auto alphabet_size
A type trait that holds the size of a (semi-)alphabet.
Definition alphabet/concept.hpp:834
seqan3::assign_rank_to
constexpr auto assign_rank_to
Assign a rank to an alphabet object.
Definition alphabet/concept.hpp:288
seqan3::alphabet_rank_t
decltype(seqan3::to_rank(std::declval< semi_alphabet_type >())) alphabet_rank_t
The rank_type of the semi-alphabet; defined as the return type of seqan3::to_rank....
Definition alphabet/concept.hpp:164
seqan3::to_rank
constexpr auto to_rank
Return the rank representation of a (semi-)alphabet object.
Definition alphabet/concept.hpp:152
seqan3::views::convert
constexpr auto convert
A view that converts each element in the input range (implicitly or via static_cast).
Definition utility/views/convert.hpp:66
std::initializer_list
writable_alphabet
Refines seqan3::alphabet and adds assignability.
std::is_same_v
T is_same_v
iterator
math.hpp
Provides math related functionality.
seqan3
The main SeqAn3 namespace.
Definition aligned_sequence_concept.hpp:26
std
SeqAn specific customisations in the standard namespace.
std::out_of_range
random_access_iterator.hpp
Provides the seqan3::detail::random_access_iterator class.
std::swap
T swap(T... args)
to_char.hpp
Provides seqan3::views::to_char.
to_rank.hpp
Provides seqan3::views::to_rank.
type_traits
convert.hpp
Provides seqan3::views::convert.
Hide me