SeqAn3 3.4.0-rc.1
The Modern C++ library for sequence analysis.
Loading...
Searching...
No Matches
bitpacked_sequence.hpp
Go to the documentation of this file.
1// SPDX-FileCopyrightText: 2006-2024 Knut Reinert & Freie Universität Berlin
2// SPDX-FileCopyrightText: 2016-2024 Knut Reinert & MPI für molekulare Genetik
3// SPDX-License-Identifier: BSD-3-Clause
4
10#pragma once
11
12#include <concepts>
13#include <iterator>
14#include <ranges>
15#include <type_traits>
16
17#include <sdsl/int_vector.hpp>
18
26
27namespace seqan3
28{
29
60template <writable_semialphabet alphabet_type>
61 requires std::regular<alphabet_type>
63{
64private:
66 static constexpr size_t bits_per_letter = detail::ceil_log2(alphabet_size<alphabet_type>);
67
68 static_assert(bits_per_letter <= 64, "alphabet must be representable in at most 64bit.");
69
71 using data_type = sdsl::int_vector<bits_per_letter>;
72
74 data_type data;
75
77 class reference_proxy_type : public alphabet_proxy<reference_proxy_type, alphabet_type>
78 {
79 private:
83 friend base_t;
84
86 std::ranges::range_reference_t<data_type> internal_proxy;
87
89 constexpr void on_update() noexcept
90 {
91 internal_proxy = base_t::to_rank();
92 }
93
94 public:
95 // Import from base:
96 using base_t::operator=;
97
102 reference_proxy_type() = delete;
103 constexpr reference_proxy_type(reference_proxy_type const &) noexcept = default;
104 constexpr reference_proxy_type(reference_proxy_type &&) noexcept = default;
105 constexpr reference_proxy_type & operator=(reference_proxy_type const &) noexcept = default;
106 constexpr reference_proxy_type & operator=(reference_proxy_type &&) noexcept = default;
107 ~reference_proxy_type() noexcept = default;
108
110 reference_proxy_type(std::ranges::range_reference_t<data_type> const internal) noexcept :
111 internal_proxy{internal}
112 {
113 // Call alphabet_base's assign_rank to prevent calling on_update() during construction
114 // which is not necessary, because internal_proxy is already correctly initialised!
116 }
118 };
119
122 //NOTE(h-2): it is entirely unclear to me why we need this
123 template <typename t>
124 requires std::is_same_v<std::ranges::range_value_t<std::remove_cvref_t<t>>, alphabet_type>
125 static constexpr bool has_same_value_type_v = true;
127
128public:
136 using value_type = alphabet_type;
142 using reference = reference_proxy_type;
147 using const_reference = alphabet_type;
152 using iterator = detail::random_access_iterator<bitpacked_sequence>;
157 using const_iterator = detail::random_access_iterator<bitpacked_sequence const>;
162 using difference_type = std::ranges::range_difference_t<data_type>;
167 using size_type = std::ranges::range_size_t<data_type>;
169
173 bitpacked_sequence() = default;
174 constexpr bitpacked_sequence(bitpacked_sequence const &) = default;
175 constexpr bitpacked_sequence(bitpacked_sequence &&) = default;
176 constexpr bitpacked_sequence & operator=(bitpacked_sequence const &) = default;
179
195 template <typename other_range_t>
196 requires (!std::same_as<bitpacked_sequence, std::remove_cvref_t<other_range_t>>)
197 && std::ranges::input_range<other_range_t> && has_same_value_type_v<other_range_t>
198 explicit bitpacked_sequence(other_range_t && range) :
199 bitpacked_sequence{std::ranges::begin(range), std::ranges::end(range)}
200 {}
201
216 bitpacked_sequence(size_type const count, value_type const value) : data(count, to_rank(value))
217 {}
218
236 template <std::forward_iterator begin_iterator_type, typename end_iterator_type>
237 bitpacked_sequence(begin_iterator_type begin_it, end_iterator_type end_it)
238 requires std::sentinel_for<end_iterator_type, begin_iterator_type>
239 && std::common_reference_with<std::iter_value_t<begin_iterator_type>, value_type>
240 {
241 insert(cend(), begin_it, end_it);
242 }
243
259
274 {
275 assign(std::begin(ilist), std::end(ilist));
276 return *this;
277 }
278
294 template <std::ranges::input_range other_range_t>
295 void assign(other_range_t && range)
296 requires std::common_reference_with<std::ranges::range_value_t<other_range_t>, value_type>
297 {
298 bitpacked_sequence rhs{std::forward<other_range_t>(range)};
299 swap(rhs);
300 }
301
316 void assign(size_type const count, value_type const value)
317 {
318 bitpacked_sequence rhs{count, value};
319 swap(rhs);
320 }
321
339 template <std::forward_iterator begin_iterator_type, typename end_iterator_type>
340 void assign(begin_iterator_type begin_it, end_iterator_type end_it)
341 requires std::sentinel_for<end_iterator_type, begin_iterator_type>
342 && std::common_reference_with<std::iter_value_t<begin_iterator_type>, value_type>
343 {
344 bitpacked_sequence rhs{begin_it, end_it};
345 swap(rhs);
346 }
347
362 {
363 assign(std::begin(ilist), std::end(ilist));
364 }
365
367
386 iterator begin() noexcept
387 {
388 return iterator{*this};
389 }
390
392 const_iterator begin() const noexcept
393 {
394 return const_iterator{*this};
395 }
396
398 const_iterator cbegin() const noexcept
399 {
400 return const_iterator{*this};
401 }
402
418 iterator end() noexcept
419 {
420 return iterator{*this, size()};
421 }
422
424 const_iterator end() const noexcept
425 {
426 return const_iterator{*this, size()};
427 }
428
430 const_iterator cend() const noexcept
431 {
432 return const_iterator{*this, size()};
433 }
435
455 {
456 if (i >= size()) // [[unlikely]]
457 {
458 throw std::out_of_range{"Trying to access element behind the last in bitpacked_sequence."};
459 }
460 return (*this)[i];
461 }
462
465 {
466 if (i >= size()) // [[unlikely]]
467 {
468 throw std::out_of_range{"Trying to access element behind the last in bitpacked_sequence."};
469 }
470 return (*this)[i];
471 }
472
491 {
492 assert(i < size());
493 return data[i];
494 }
495
497 const_reference operator[](size_type const i) const noexcept
498 {
499 assert(i < size());
500 return assign_rank_to(data[i], const_reference{});
501 }
502
518 reference front() noexcept
519 {
520 assert(size() > 0);
521 return (*this)[0];
522 }
523
525 const_reference front() const noexcept
526 {
527 assert(size() > 0);
528 return (*this)[0];
529 }
530
546 reference back() noexcept
547 {
548 assert(size() > 0);
549 return (*this)[size() - 1];
550 }
551
553 const_reference back() const noexcept
554 {
555 assert(size() > 0);
556 return (*this)[size() - 1];
557 }
558
568 constexpr data_type & raw_data() noexcept
569 {
570 return data;
571 }
572
574 constexpr data_type const & raw_data() const noexcept
575 {
576 return data;
577 }
579
596 bool empty() const noexcept
597 {
598 return size() == 0;
599 }
600
614 size_type size() const noexcept
615 {
616 return data.size();
617 }
618
635 size_type max_size() const noexcept
636 {
637 return data.max_size();
638 }
639
653 size_type capacity() const noexcept
654 {
655 return data.capacity();
656 }
657
678 void reserve(size_type const new_cap)
679 {
680 data.reserve(new_cap);
681 }
682
701 {
702 data.shrink_to_fit();
703 }
705
721 void clear() noexcept
722 {
723 data.clear();
724 }
725
747 {
748 return insert(pos, 1, value);
749 }
750
772 iterator insert(const_iterator pos, size_type const count, value_type const value)
773 {
774 auto const pos_as_num = std::distance(cbegin(), pos); // we want to insert BEFORE this position
775
776 data.insert(data.begin() + pos_as_num, count, to_rank(value));
777
778 return begin() + pos_as_num;
779 }
780
807 template <std::forward_iterator begin_iterator_type, typename end_iterator_type>
808 iterator insert(const_iterator pos, begin_iterator_type begin_it, end_iterator_type end_it)
809 requires std::sentinel_for<end_iterator_type, begin_iterator_type>
810 && std::common_reference_with<std::iter_value_t<begin_iterator_type>, value_type>
811 {
812 auto const pos_as_num = std::distance(cbegin(), pos);
813
814 auto v = std::ranges::subrange<begin_iterator_type, end_iterator_type>{begin_it, end_it}
815 | views::convert<value_type> | views::to_rank;
816 data.insert(data.begin() + pos_as_num, std::ranges::begin(v), std::ranges::end(v));
817
818 return begin() + pos_as_num;
819 }
820
842 {
843 return insert(pos, ilist.begin(), ilist.end());
844 }
845
868 {
869 if (begin_it >= end_it) // [[unlikely]]
870 return begin() + std::distance(cbegin(), end_it);
871
872 auto const begin_it_pos = std::distance(cbegin(), begin_it);
873 auto const end_it_pos = std::distance(cbegin(), end_it);
874
875 data.erase(data.cbegin() + begin_it_pos, data.cbegin() + end_it_pos);
876
877 return begin() + begin_it_pos;
878 }
879
902 {
903 return erase(pos, pos + 1);
904 }
905
923 void push_back(value_type const value)
924 {
925 data.push_back(to_rank(value));
926 }
927
946 void pop_back()
947 {
948 assert(size() > 0);
949 data.pop_back();
950 }
951
980 void resize(size_type const count)
981 {
982 assert(count < max_size());
983 data.resize(count);
984 }
985
990 void resize(size_type const count, value_type const value)
991 {
992 assert(count < max_size());
993 data.resize(count, to_rank(value));
994 }
995
1009 constexpr void swap(bitpacked_sequence & rhs) noexcept
1010 {
1011 std::swap(data, rhs.data);
1012 }
1013
1015 constexpr void swap(bitpacked_sequence && rhs) noexcept
1016 {
1017 std::swap(data, rhs.data);
1018 }
1019
1034 friend constexpr void swap(bitpacked_sequence & lhs, bitpacked_sequence & rhs) noexcept
1035 {
1036 std::swap(lhs, rhs);
1037 }
1038
1040 friend constexpr void swap(bitpacked_sequence && lhs, bitpacked_sequence && rhs) noexcept
1041 {
1042 std::swap(lhs, rhs);
1043 }
1045
1054 constexpr bool operator==(bitpacked_sequence const & rhs) const noexcept
1055 {
1056 return data == rhs.data;
1057 }
1058
1063 constexpr bool operator!=(bitpacked_sequence const & rhs) const noexcept
1064 {
1065 return data != rhs.data;
1066 }
1067
1072 constexpr bool operator<(bitpacked_sequence const & rhs) const noexcept
1073 {
1074 return data < rhs.data;
1075 }
1076
1081 constexpr bool operator>(bitpacked_sequence const & rhs) const noexcept
1082 {
1083 return data > rhs.data;
1084 }
1085
1090 constexpr bool operator<=(bitpacked_sequence const & rhs) const noexcept
1091 {
1092 return data <= rhs.data;
1093 }
1094
1099 constexpr bool operator>=(bitpacked_sequence const & rhs) const noexcept
1100 {
1101 return data >= rhs.data;
1102 }
1104
1112 template <cereal_archive archive_t>
1113 void CEREAL_SERIALIZE_FUNCTION_NAME(archive_t & archive)
1114 {
1115 archive(data);
1116 }
1118};
1119
1120} // namespace seqan3
Provides seqan3::alphabet_proxy.
T begin(T... args)
Adaptions of concepts from the Cereal library.
A CRTP-base that eases the definition of proxy types returned in place of regular alphabets.
Definition alphabet_proxy.hpp:62
constexpr reference_proxy_type & assign_rank(alphabet_rank_t< alphabet_type > const r) noexcept
Assigns a rank.
Definition alphabet_proxy.hpp:142
constexpr auto to_rank() const noexcept
Returns the rank.
Definition alphabet_proxy.hpp:204
A space-optimised version of std::vector that compresses multiple letters into a single byte.
Definition bitpacked_sequence.hpp:63
void assign(size_type const count, value_type const value)
Assign with count times value.
Definition bitpacked_sequence.hpp:316
alphabet_type value_type
Equals the alphabet_type.
Definition bitpacked_sequence.hpp:136
std::ranges::range_difference_t< data_type > difference_type
A signed integer type (usually std::ptrdiff_t)
Definition bitpacked_sequence.hpp:162
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:808
constexpr bitpacked_sequence(bitpacked_sequence &&)=default
Defaulted.
iterator erase(const_iterator pos)
Removes specified elements from the container.
Definition bitpacked_sequence.hpp:901
reference_proxy_type reference
A proxy type (models seqan3::writable_semialphabet) that enables assignment, think of it as value_typ...
Definition bitpacked_sequence.hpp:142
constexpr bool operator>(bitpacked_sequence const &rhs) const noexcept
Checks whether *this is greater than rhs.
Definition bitpacked_sequence.hpp:1081
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:635
bool empty() const noexcept
Checks whether the container is empty.
Definition bitpacked_sequence.hpp:596
reference operator[](size_type const i) noexcept
Return the i-th element.
Definition bitpacked_sequence.hpp:490
const_reference back() const noexcept
Return the last element.
Definition bitpacked_sequence.hpp:553
const_iterator cbegin() const noexcept
Returns an iterator to the first element of the container.
Definition bitpacked_sequence.hpp:398
iterator erase(const_iterator begin_it, const_iterator end_it)
Removes specified elements from the container.
Definition bitpacked_sequence.hpp:867
iterator insert(const_iterator pos, value_type const value)
Inserts value before position in the container.
Definition bitpacked_sequence.hpp:746
~bitpacked_sequence()=default
Defaulted.
void resize(size_type const count, value_type const value)
Resizes the container to contain count elements.
Definition bitpacked_sequence.hpp:990
void clear() noexcept
Removes all elements from the container.
Definition bitpacked_sequence.hpp:721
constexpr bool operator<=(bitpacked_sequence const &rhs) const noexcept
Checks whether *this is less than or equal to rhs.
Definition bitpacked_sequence.hpp:1090
const_iterator end() const noexcept
Returns an iterator to the element following the last element of the container.
Definition bitpacked_sequence.hpp:424
constexpr bool operator>=(bitpacked_sequence const &rhs) const noexcept
Checks whether *this is greater than or equal to rhs.
Definition bitpacked_sequence.hpp:1099
constexpr bitpacked_sequence(bitpacked_sequence const &)=default
Defaulted.
void push_back(value_type const value)
Appends the given element value to the end of the container.
Definition bitpacked_sequence.hpp:923
const_reference at(size_type const i) const
Return the i-th element.
Definition bitpacked_sequence.hpp:464
constexpr bool operator!=(bitpacked_sequence const &rhs) const noexcept
Checks whether *this is not equal to rhs.
Definition bitpacked_sequence.hpp:1063
iterator end() noexcept
Returns an iterator to the element following the last element of the container.
Definition bitpacked_sequence.hpp:418
void assign(std::initializer_list< value_type > ilist)
Assign from std::initializer_list.
Definition bitpacked_sequence.hpp:361
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:678
const_iterator begin() const noexcept
Returns an iterator to the first element of the container.
Definition bitpacked_sequence.hpp:392
detail::random_access_iterator< bitpacked_sequence const > const_iterator
The const_iterator type of this container (a random access iterator).
Definition bitpacked_sequence.hpp:157
bitpacked_sequence(std::initializer_list< value_type > ilist)
Construct from std::initializer_list.
Definition bitpacked_sequence.hpp:257
void shrink_to_fit()
Requests the removal of unused capacity.
Definition bitpacked_sequence.hpp:700
const_reference operator[](size_type const i) const noexcept
Return the i-th element.
Definition bitpacked_sequence.hpp:497
iterator begin() noexcept
Returns an iterator to the first element of the container.
Definition bitpacked_sequence.hpp:386
std::ranges::range_size_t< data_type > size_type
An unsigned integer type (usually std::size_t)
Definition bitpacked_sequence.hpp:167
size_type capacity() const noexcept
Returns the number of elements that the container has currently allocated space for.
Definition bitpacked_sequence.hpp:653
void assign(other_range_t &&range)
Assign from a different range.
Definition bitpacked_sequence.hpp:295
detail::random_access_iterator< bitpacked_sequence > iterator
The iterator type of this container (a random access iterator).
Definition bitpacked_sequence.hpp:152
alphabet_type const_reference
Equals the alphabet_type / value_type.
Definition bitpacked_sequence.hpp:147
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:841
reference at(size_type const i)
Return the i-th element.
Definition bitpacked_sequence.hpp:454
bitpacked_sequence(begin_iterator_type begin_it, end_iterator_type end_it)
Construct from pair of iterators.
Definition bitpacked_sequence.hpp:237
friend constexpr void swap(bitpacked_sequence &lhs, bitpacked_sequence &rhs) noexcept
Swap contents with another instance.
Definition bitpacked_sequence.hpp:1034
const_reference front() const noexcept
Return the first element. Calling front on an empty container is undefined.
Definition bitpacked_sequence.hpp:525
constexpr bitpacked_sequence & operator=(bitpacked_sequence const &)=default
Defaulted.
constexpr data_type const & raw_data() const noexcept
Provides direct, unsafe access to underlying data structures.
Definition bitpacked_sequence.hpp:574
constexpr bool operator==(bitpacked_sequence const &rhs) const noexcept
Checks whether *this is equal to rhs.
Definition bitpacked_sequence.hpp:1054
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:1040
const_iterator cend() const noexcept
Returns an iterator to the element following the last element of the container.
Definition bitpacked_sequence.hpp:430
bitpacked_sequence(size_type const count, value_type const value)
Construct with count times value.
Definition bitpacked_sequence.hpp:216
bitpacked_sequence & operator=(std::initializer_list< value_type > ilist)
Assign from std::initializer_list.
Definition bitpacked_sequence.hpp:273
void resize(size_type const count)
Resizes the container to contain count elements.
Definition bitpacked_sequence.hpp:980
void pop_back()
Removes the last element of the container.
Definition bitpacked_sequence.hpp:946
reference back() noexcept
Return the last element.
Definition bitpacked_sequence.hpp:546
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:772
bitpacked_sequence()=default
Defaulted.
constexpr void swap(bitpacked_sequence &&rhs) noexcept
Swap contents with another instance.
Definition bitpacked_sequence.hpp:1015
bitpacked_sequence(other_range_t &&range)
Construct from a different range.
Definition bitpacked_sequence.hpp:198
constexpr data_type & raw_data() noexcept
Provides direct, unsafe access to underlying data structures.
Definition bitpacked_sequence.hpp:568
constexpr bool operator<(bitpacked_sequence const &rhs) const noexcept
Checks whether *this is less than rhs.
Definition bitpacked_sequence.hpp:1072
constexpr void swap(bitpacked_sequence &rhs) noexcept
Swap contents with another instance.
Definition bitpacked_sequence.hpp:1009
size_type size() const noexcept
Returns the number of elements in the container, i.e. std::distance(begin(), end()).
Definition bitpacked_sequence.hpp:614
reference front() noexcept
Return the first element. Calling front on an empty container is undefined.
Definition bitpacked_sequence.hpp:518
constexpr bitpacked_sequence & operator=(bitpacked_sequence &&)=default
Defaulted.
void assign(begin_iterator_type begin_it, end_iterator_type end_it)
Assign from pair of iterators.
Definition bitpacked_sequence.hpp:340
T distance(T... args)
T end(T... args)
auto const to_rank
A view that calls seqan3::to_rank() on each element in the input range.
Definition to_rank.hpp:63
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:166
constexpr auto assign_rank_to
Assign a rank to an alphabet object.
Definition alphabet/concept.hpp:290
constexpr auto to_rank
Return the rank representation of a (semi-)alphabet object.
Definition alphabet/concept.hpp:152
Refines seqan3::alphabet and adds assignability.
Provides math related functionality.
The main SeqAn3 namespace.
Definition aligned_sequence_concept.hpp:26
SeqAn specific customisations in the standard namespace.
Provides the seqan3::detail::random_access_iterator class.
T swap(T... args)
Provides seqan3::views::to_char.
Provides seqan3::views::to_rank.
Provides seqan3::views::convert.
Hide me