SeqAn3  3.2.0
The Modern C++ library for sequence analysis.
bitpacked_sequence.hpp
Go to the documentation of this file.
1 // -----------------------------------------------------------------------------------------------------
2 // Copyright (c) 2006-2022, Knut Reinert & Freie Universität Berlin
3 // Copyright (c) 2016-2022, Knut Reinert & MPI für molekulare Genetik
4 // This file may be used, modified and/or redistributed under the terms of the 3-clause BSD-License
5 // shipped with this file and also available at: https://github.com/seqan/seqan3/blob/master/LICENSE.md
6 // -----------------------------------------------------------------------------------------------------
7 
13 #pragma once
14 
15 #include <concepts>
16 #include <iterator>
17 #include <ranges>
18 #include <type_traits>
19 
20 #include <sdsl/int_vector.hpp>
21 
27 #include <seqan3/utility/math.hpp>
29 
30 namespace seqan3
31 {
32 
63 template <writable_semialphabet alphabet_type>
64  requires std::regular<alphabet_type>
66 {
67 private:
69  static constexpr size_t bits_per_letter = detail::ceil_log2(alphabet_size<alphabet_type>);
70 
71  static_assert(bits_per_letter <= 64, "alphabet must be representable in at most 64bit.");
72 
74  using data_type = sdsl::int_vector<bits_per_letter>;
75 
77  data_type data;
78 
80  class reference_proxy_type : public alphabet_proxy<reference_proxy_type, alphabet_type>
81  {
82  private:
86  friend base_t;
87 
89  std::ranges::range_reference_t<data_type> internal_proxy;
90 
92  constexpr void on_update() noexcept
93  {
94  internal_proxy = static_cast<base_t &>(*this).to_rank();
95  }
96 
97  public:
98  // Import from base:
99  using base_t::operator=;
100 
105  reference_proxy_type() = delete;
106  constexpr reference_proxy_type(reference_proxy_type const &) noexcept = default;
107  constexpr reference_proxy_type(reference_proxy_type &&) noexcept = default;
108  constexpr reference_proxy_type & operator=(reference_proxy_type const &) noexcept = default;
109  constexpr reference_proxy_type & operator=(reference_proxy_type &&) noexcept = default;
110  ~reference_proxy_type() noexcept = default;
111 
113  reference_proxy_type(std::ranges::range_reference_t<data_type> const & internal) noexcept :
114  internal_proxy{internal}
115  {
116  static_cast<base_t &>(*this).assign_rank(internal);
117  }
119  };
120 
123  //NOTE(h-2): it is entirely unclear to me why we need this
124  template <typename t>
125  requires std::is_same_v<std::ranges::range_value_t<std::remove_cvref_t<t>>, alphabet_type>
126  static constexpr bool has_same_value_type_v = true;
128 
129 public:
137  using value_type = alphabet_type;
143  using reference = reference_proxy_type;
148  using const_reference = alphabet_type;
153  using iterator = detail::random_access_iterator<bitpacked_sequence>;
158  using const_iterator = detail::random_access_iterator<bitpacked_sequence const>;
163  using difference_type = std::ranges::range_difference_t<data_type>;
168  using size_type = std::ranges::range_size_t<data_type>;
170 
174  bitpacked_sequence() = default;
175  constexpr bitpacked_sequence(bitpacked_sequence const &) = default;
176  constexpr bitpacked_sequence(bitpacked_sequence &&) = default;
177  constexpr bitpacked_sequence & operator=(bitpacked_sequence const &) = default;
178  constexpr bitpacked_sequence & operator=(bitpacked_sequence &&) = default;
179  ~bitpacked_sequence() = default;
180 
196  template <typename other_range_t>
197  requires (!std::same_as<bitpacked_sequence, std::remove_cvref_t<other_range_t>>)
198  && std::ranges::input_range<other_range_t> && has_same_value_type_v<other_range_t>
199  explicit bitpacked_sequence(other_range_t && range) :
200  bitpacked_sequence{std::ranges::begin(range), std::ranges::end(range)}
201  {}
202 
217  bitpacked_sequence(size_type const count, value_type const value) : data(count, to_rank(value))
218  {}
219 
237  template <std::forward_iterator begin_iterator_type, typename end_iterator_type>
238  bitpacked_sequence(begin_iterator_type begin_it, end_iterator_type end_it)
239  requires std::sentinel_for<end_iterator_type, begin_iterator_type>
240  && std::common_reference_with<std::iter_value_t<begin_iterator_type>, value_type>
241  {
242  insert(cend(), begin_it, end_it);
243  }
244 
259  {}
260 
275  {
276  assign(std::begin(ilist), std::end(ilist));
277  return *this;
278  }
279 
295  template <std::ranges::input_range other_range_t>
296  void assign(other_range_t && range)
297  requires std::common_reference_with<std::ranges::range_value_t<other_range_t>, value_type>
298  {
299  bitpacked_sequence rhs{std::forward<other_range_t>(range)};
300  swap(rhs);
301  }
302 
317  void assign(size_type const count, value_type const value)
318  {
319  bitpacked_sequence rhs{count, value};
320  swap(rhs);
321  }
322 
340  template <std::forward_iterator begin_iterator_type, typename end_iterator_type>
341  void assign(begin_iterator_type begin_it, end_iterator_type end_it)
342  requires std::sentinel_for<end_iterator_type, begin_iterator_type>
343  && std::common_reference_with<std::iter_value_t<begin_iterator_type>, value_type>
344  {
345  bitpacked_sequence rhs{begin_it, end_it};
346  swap(rhs);
347  }
348 
363  {
364  assign(std::begin(ilist), std::end(ilist));
365  }
366 
368 
387  iterator begin() noexcept
388  {
389  return iterator{*this};
390  }
391 
393  const_iterator begin() const noexcept
394  {
395  return const_iterator{*this};
396  }
397 
399  const_iterator cbegin() const noexcept
400  {
401  return const_iterator{*this};
402  }
403 
419  iterator end() noexcept
420  {
421  return iterator{*this, size()};
422  }
423 
425  const_iterator end() const noexcept
426  {
427  return const_iterator{*this, size()};
428  }
429 
431  const_iterator cend() const noexcept
432  {
433  return const_iterator{*this, size()};
434  }
436 
455  reference at(size_type const i)
456  {
457  if (i >= size()) // [[unlikely]]
458  {
459  throw std::out_of_range{"Trying to access element behind the last in bitpacked_sequence."};
460  }
461  return (*this)[i];
462  }
463 
465  const_reference at(size_type const i) const
466  {
467  if (i >= size()) // [[unlikely]]
468  {
469  throw std::out_of_range{"Trying to access element behind the last in bitpacked_sequence."};
470  }
471  return (*this)[i];
472  }
473 
491  reference operator[](size_type const i) noexcept
492  {
493  assert(i < size());
494  return data[i];
495  }
496 
498  const_reference operator[](size_type const i) const noexcept
499  {
500  assert(i < size());
501  return assign_rank_to(data[i], const_reference{});
502  }
503 
519  reference front() noexcept
520  {
521  assert(size() > 0);
522  return (*this)[0];
523  }
524 
526  const_reference front() const noexcept
527  {
528  assert(size() > 0);
529  return (*this)[0];
530  }
531 
547  reference back() noexcept
548  {
549  assert(size() > 0);
550  return (*this)[size() - 1];
551  }
552 
554  const_reference back() const noexcept
555  {
556  assert(size() > 0);
557  return (*this)[size() - 1];
558  }
559 
569  constexpr data_type & raw_data() noexcept
570  {
571  return data;
572  }
573 
575  constexpr data_type const & raw_data() const noexcept
576  {
577  return data;
578  }
580 
597  bool empty() const noexcept
598  {
599  return size() == 0;
600  }
601 
615  size_type size() const noexcept
616  {
617  return data.size();
618  }
619 
636  size_type max_size() const noexcept
637  {
638  return data.max_size();
639  }
640 
658  size_type capacity() const noexcept
659  {
660  return data.capacity();
661  }
662 
683  void reserve(size_type const new_cap)
684  {
685  data.reserve(new_cap);
686  }
687 
705  void shrink_to_fit()
706  {
707  data.shrink_to_fit();
708  }
710 
726  void clear() noexcept
727  {
728  data.clear();
729  }
730 
751  iterator insert(const_iterator pos, value_type const value)
752  {
753  return insert(pos, 1, value);
754  }
755 
777  iterator insert(const_iterator pos, size_type const count, value_type const value)
778  {
779  auto const pos_as_num = std::distance(cbegin(), pos); // we want to insert BEFORE this position
780 
781  data.insert(data.begin() + pos_as_num, count, to_rank(value));
782 
783  return begin() + pos_as_num;
784  }
785 
812  template <std::forward_iterator begin_iterator_type, typename end_iterator_type>
813  iterator insert(const_iterator pos, begin_iterator_type begin_it, end_iterator_type end_it)
814  requires std::sentinel_for<end_iterator_type, begin_iterator_type>
815  && std::common_reference_with<std::iter_value_t<begin_iterator_type>, value_type>
816  {
817  auto const pos_as_num = std::distance(cbegin(), pos);
818 
819  auto v = std::ranges::subrange<begin_iterator_type, end_iterator_type>{begin_it, end_it}
820  | views::convert<value_type> | views::to_rank;
821  data.insert(data.begin() + pos_as_num, std::ranges::begin(v), std::ranges::end(v));
822 
823  return begin() + pos_as_num;
824  }
825 
847  {
848  return insert(pos, ilist.begin(), ilist.end());
849  }
850 
872  iterator erase(const_iterator begin_it, const_iterator end_it)
873  {
874  if (begin_it >= end_it) // [[unlikely]]
875  return begin() + std::distance(cbegin(), end_it);
876 
877  auto const begin_it_pos = std::distance(cbegin(), begin_it);
878  auto const end_it_pos = std::distance(cbegin(), end_it);
879 
880  data.erase(data.cbegin() + begin_it_pos, data.cbegin() + end_it_pos);
881 
882  return begin() + begin_it_pos;
883  }
884 
907  {
908  return erase(pos, pos + 1);
909  }
910 
928  void push_back(value_type const value)
929  {
930  data.push_back(to_rank(value));
931  }
932 
951  void pop_back()
952  {
953  assert(size() > 0);
954  data.pop_back();
955  }
956 
985  void resize(size_type const count)
986  {
987  assert(count < max_size());
988  data.resize(count);
989  }
990 
995  void resize(size_type const count, value_type const value)
996  {
997  assert(count < max_size());
998  data.resize(count, to_rank(value));
999  }
1000 
1014  constexpr void swap(bitpacked_sequence & rhs) noexcept
1015  {
1016  std::swap(data, rhs.data);
1017  }
1018 
1020  constexpr void swap(bitpacked_sequence && rhs) noexcept
1021  {
1022  std::swap(data, rhs.data);
1023  }
1024 
1039  friend constexpr void swap(bitpacked_sequence & lhs, bitpacked_sequence & rhs) noexcept
1040  {
1041  std::swap(lhs, rhs);
1042  }
1043 
1045  friend constexpr void swap(bitpacked_sequence && lhs, bitpacked_sequence && rhs) noexcept
1046  {
1047  std::swap(lhs, rhs);
1048  }
1050 
1059  constexpr bool operator==(bitpacked_sequence const & rhs) const noexcept
1060  {
1061  return data == rhs.data;
1062  }
1063 
1068  constexpr bool operator!=(bitpacked_sequence const & rhs) const noexcept
1069  {
1070  return data != rhs.data;
1071  }
1072 
1077  constexpr bool operator<(bitpacked_sequence const & rhs) const noexcept
1078  {
1079  return data < rhs.data;
1080  }
1081 
1086  constexpr bool operator>(bitpacked_sequence const & rhs) const noexcept
1087  {
1088  return data > rhs.data;
1089  }
1090 
1095  constexpr bool operator<=(bitpacked_sequence const & rhs) const noexcept
1096  {
1097  return data <= rhs.data;
1098  }
1099 
1104  constexpr bool operator>=(bitpacked_sequence const & rhs) const noexcept
1105  {
1106  return data >= rhs.data;
1107  }
1109 
1117  template <cereal_archive archive_t>
1118  void CEREAL_SERIALIZE_FUNCTION_NAME(archive_t & archive)
1119  {
1120  archive(data);
1121  }
1123 };
1124 
1125 } // 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:65
A space-optimised version of std::vector that compresses multiple letters into a single byte.
Definition: bitpacked_sequence.hpp:66
alphabet_type value_type
Equals the alphabet_type.
Definition: bitpacked_sequence.hpp:137
std::ranges::range_difference_t< data_type > difference_type
A signed integer type (usually std::ptrdiff_t)
Definition: bitpacked_sequence.hpp:163
constexpr bitpacked_sequence(bitpacked_sequence &&)=default
Defaulted.
reference_proxy_type reference
A proxy type (models seqan3::writable_semialphabet) that enables assignment, think of it as value_typ...
Definition: bitpacked_sequence.hpp:143
constexpr bool operator>(bitpacked_sequence const &rhs) const noexcept
Checks whether *this is greater than rhs.
Definition: bitpacked_sequence.hpp:1085
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_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:871
requires(!std::same_as< bitpacked_sequence, std::remove_cvref_t< other_range_t >>) &&std
Construct from a different range.
Definition: bitpacked_sequence.hpp:197
iterator insert(const_iterator pos, value_type const value)
Inserts value before position in the container.
Definition: bitpacked_sequence.hpp:750
~bitpacked_sequence()=default
Defaulted.
void clear() noexcept
Removes all elements from the container.
Definition: bitpacked_sequence.hpp:725
constexpr bool operator<=(bitpacked_sequence const &rhs) const noexcept
Checks whether *this is less than or equal to rhs.
Definition: bitpacked_sequence.hpp:1094
constexpr bool operator>=(bitpacked_sequence const &rhs) const noexcept
Checks whether *this is greater than or equal to rhs.
Definition: bitpacked_sequence.hpp:1103
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:927
constexpr bool operator!=(bitpacked_sequence const &rhs) const noexcept
Checks whether *this is not equal to rhs.
Definition: bitpacked_sequence.hpp:1067
iterator end() noexcept
Returns an iterator to the element following the last element of the container.
Definition: bitpacked_sequence.hpp:418
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:682
detail::random_access_iterator< bitpacked_sequence const > const_iterator
The const_iterator type of this container (a random access iterator).
Definition: bitpacked_sequence.hpp:158
constexpr bitpacked_sequence & operator=(bitpacked_sequence const &)=default
Defaulted.
void shrink_to_fit()
Requests the removal of unused capacity.
Definition: bitpacked_sequence.hpp:704
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:168
void assign(other_range_t &&range) requires std
Assign from a different range.
Definition: bitpacked_sequence.hpp:295
size_type capacity() const noexcept
Returns the number of elements that the container has currently allocated space for.
Definition: bitpacked_sequence.hpp:657
detail::random_access_iterator< bitpacked_sequence > iterator
The iterator type of this container (a random access iterator).
Definition: bitpacked_sequence.hpp:153
alphabet_type const_reference
Equals the alphabet_type / value_type.
Definition: bitpacked_sequence.hpp:148
reference at(size_type const i)
Return the i-th element.
Definition: bitpacked_sequence.hpp:454
constexpr bool operator==(bitpacked_sequence const &rhs) const noexcept
Checks whether *this is equal to rhs.
Definition: bitpacked_sequence.hpp:1058
constexpr data_type & raw_data() noexcept
Provides direct, unsafe access to underlying data structures.
Definition: bitpacked_sequence.hpp:568
const_iterator cend() const noexcept
Returns an iterator to the element following the last element of the container.
Definition: bitpacked_sequence.hpp:430
void resize(size_type const count)
Resizes the container to contain count elements.
Definition: bitpacked_sequence.hpp:984
void pop_back()
Removes the last element of the container.
Definition: bitpacked_sequence.hpp:950
reference back() noexcept
Return the last element.
Definition: bitpacked_sequence.hpp:546
bitpacked_sequence()=default
Defaulted.
constexpr bool operator<(bitpacked_sequence const &rhs) const noexcept
Checks whether *this is less than rhs.
Definition: bitpacked_sequence.hpp:1076
constexpr bitpacked_sequence & operator=(bitpacked_sequence &&)=default
Defaulted.
constexpr void swap(bitpacked_sequence &rhs) noexcept
Swap contents with another instance.
Definition: bitpacked_sequence.hpp:1013
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
The <concepts> header from C++20's standard library.
T data(T... args)
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:66
constexpr auto assign_rank_to
Assign a rank to an alphabet object.
Definition: alphabet/concept.hpp:293
requires requires
The rank_type of the semi-alphabet; defined as the return type of seqan3::to_rank....
Definition: alphabet/concept.hpp:164
constexpr auto to_rank
Return the rank representation of a (semi-)alphabet object.
Definition: alphabet/concept.hpp:155
constexpr ptrdiff_t count
Count the occurrences of a type in a pack.
Definition: type_pack/traits.hpp:164
Refines seqan3::alphabet and adds assignability.
Provides math related functionality.
The main SeqAn3 namespace.
Definition: aligned_sequence_concept.hpp:29
SeqAn specific customisations in the standard namespace.
Provides the seqan3::detail::random_access_iterator class.
The <ranges> header from C++20's standard library.
T swap(T... args)
Provides seqan3::views::to_char.
Provides seqan3::views::to_rank.
Provides seqan3::views::convert.