SeqAn3  3.1.0
The Modern C++ library for sequence analysis.
alphabet_variant.hpp
Go to the documentation of this file.
1 // -----------------------------------------------------------------------------------------------------
2 // Copyright (c) 2006-2021, Knut Reinert & Freie Universität Berlin
3 // Copyright (c) 2016-2021, 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 
15 #pragma once
16 
17 #include <algorithm>
18 #include <array>
19 #include <cassert>
20 #include <utility>
21 #include <variant>
22 
27 
28 namespace seqan3::detail
29 {
30 
31 #if SEQAN3_WORKAROUND_GCC7_AND_8_CONCEPT_ISSUES
32 template <typename t>
33 SEQAN3_CONCEPT variant_guard_pseudoalphabet = requires { requires seqan3::alphabet_size<t> > 0; };
34 #endif // SEQAN3_WORKAROUND_GCC7_AND_8_CONCEPT_ISSUES
35 
37 template <typename other_t, typename ... alternative_types>
38 inline constexpr bool variant_general_guard =
39  (!std::same_as<other_t, alphabet_variant<alternative_types...>>) &&
40  (!std::is_base_of_v<alphabet_variant<alternative_types...>, other_t>) &&
41  (!(std::same_as<other_t, alternative_types> || ...)) &&
42  (!list_traits::contains<alphabet_variant<alternative_types...>, recursive_required_types_t<other_t>>)
43 #if SEQAN3_WORKAROUND_GCC7_AND_8_CONCEPT_ISSUES
44  && variant_guard_pseudoalphabet<other_t>
45 #endif // SEQAN3_WORKAROUND_GCC7_AND_8_CONCEPT_ISSUES
46  ;
47 
49 template <typename lhs_t, typename rhs_t, bool lhs_rhs_switched, typename ... alternative_types>
50 inline constexpr bool variant_comparison_guard =
51  (instantiate_if_v<lazy<weakly_equality_comparable_with_trait, rhs_t, alternative_types>,
52  (std::same_as<lhs_t, alphabet_variant<alternative_types...>>) &&
53  (variant_general_guard<rhs_t, alternative_types...>) &&
54  !(lhs_rhs_switched && is_type_specialisation_of_v<rhs_t, alphabet_variant>)
55  > || ...);
56 } // namespace seqan3::detail
57 
58 namespace seqan3
59 {
60 
120 template <typename ...alternative_types>
122  requires (detail::writable_constexpr_alphabet<alternative_types> && ...) &&
123  (std::regular<alternative_types> && ...) &&
124  (sizeof...(alternative_types) >= 2)
126 class alphabet_variant : public alphabet_base<alphabet_variant<alternative_types...>,
127  (static_cast<size_t>(alphabet_size<alternative_types>) + ...),
128  char>
129 {
130 private:
132  using base_t = alphabet_base<alphabet_variant<alternative_types...>,
133  (static_cast<size_t>(alphabet_size<alternative_types>) + ...),
134  char>;
135 
136  static_assert((std::is_same_v<alphabet_char_t<alternative_types>, char> && ...),
137  "The alphabet_variant is currently only tested for alphabets with char_type char. "
138  "Contact us on GitHub if you have a different use case: https://github.com/seqan/seqan3 .");
139 
141  friend base_t;
142 
144  using alternatives = seqan3::type_list<alternative_types...>;
145 
146  static_assert(((seqan3::list_traits::count<alternative_types, alternatives> == 1) && ... && true),
147  "All types in a alphabet_variant must be distinct.");
148 
149  using typename base_t::char_type;
150  using typename base_t::rank_type;
151 public:
152  using base_t::alphabet_size;
153  using base_t::to_char;
154  using base_t::to_rank;
155  using base_t::assign_rank;
156 
162  using seqan3_required_types = type_list<alternative_types...>;
168  using seqan3_recursive_required_types =
170  detail::transformation_trait_or_t<detail::recursive_required_types<alternative_types>,
171  type_list<>>...>;
172 
180  template <typename alternative_t>
181  static constexpr bool is_alternative() noexcept
182  {
183  return seqan3::pack_traits::contains<alternative_t, alternative_types...>;
184  }
185 
189  constexpr alphabet_variant() noexcept = default;
190  constexpr alphabet_variant(alphabet_variant const &) noexcept = default;
191  constexpr alphabet_variant(alphabet_variant &&) noexcept = default;
192  constexpr alphabet_variant & operator=(alphabet_variant const &) noexcept = default;
193  constexpr alphabet_variant & operator=(alphabet_variant &&) noexcept = default;
194  ~alphabet_variant() noexcept = default;
195 
204  template <typename alternative_t>
206  requires (!std::same_as<alternative_t, alphabet_variant>) &&
207  (!std::is_base_of_v<alphabet_variant, alternative_t>) &&
208  (!list_traits::contains<alphabet_variant,
209  detail::transformation_trait_or_t<detail::recursive_required_types<alternative_t>, type_list<>>>) &&
210  (is_alternative<alternative_t>())
212  constexpr alphabet_variant(alternative_t const alternative) noexcept
213  {
214  assign_rank(rank_by_type_(alternative));
215  }
216 
235  template <typename indirect_alternative_t>
237  requires ((detail::instantiate_if_v<
238  detail::lazy<std::is_convertible, indirect_alternative_t, alternative_types>,
239  detail::variant_general_guard<indirect_alternative_t, alternative_types...>> || ...))
241  constexpr alphabet_variant(indirect_alternative_t const rhs) noexcept
242  {
243  using alternative_predicate = detail::implicitly_convertible_from<indirect_alternative_t>;
244  constexpr auto alternative_position = seqan3::list_traits::find_if<alternative_predicate::template invoke,
245  alternatives>;
247  assign_rank(rank_by_type_(alternative_t(rhs)));
248  }
249 
266  template <typename indirect_alternative_t>
268  requires ((!(detail::instantiate_if_v<
269  detail::lazy<std::is_convertible, indirect_alternative_t, alternative_types>,
270  detail::variant_general_guard<indirect_alternative_t, alternative_types...>> || ...)) &&
271  (detail::instantiate_if_v<
272  detail::lazy<std::is_constructible, alternative_types, indirect_alternative_t>,
273  detail::variant_general_guard<indirect_alternative_t, alternative_types...>> || ...))
275  constexpr explicit alphabet_variant(indirect_alternative_t const rhs) noexcept
276  {
277  using alternative_predicate = detail::constructible_from<indirect_alternative_t>;
278  constexpr auto alternative_position = seqan3::list_traits::find_if<alternative_predicate::template invoke,
279  alternatives>;
281  assign_rank(rank_by_type_(alternative_t(rhs)));
282  }
283 
295  template <typename indirect_alternative_t>
297  requires (detail::variant_general_guard<indirect_alternative_t, alternative_types...> &&
300  constexpr alphabet_variant & operator=(indirect_alternative_t const & rhs) noexcept
301  {
302  using alternative_predicate = detail::assignable_from<indirect_alternative_t>;
303  constexpr auto alternative_position = seqan3::list_traits::find_if<alternative_predicate::template invoke,
304  alternatives>;
306  alternative_t alternative{};
307  alternative = rhs;
308  assign_rank(rank_by_type_(alternative));
309  return *this;
310  }
312 
322  template <size_t index>
323  constexpr bool holds_alternative() const noexcept
324  {
325  static_assert(index < alphabet_size, "The alphabet_variant contains less alternatives than you are checking.");
326  return (to_rank() >= partial_sum_sizes[index]) && (to_rank() < partial_sum_sizes[index + 1]);
327  }
328 
335  template <size_t index>
336  constexpr auto convert_to() const
337  {
338  return convert_impl<index, true>();
339  }
340 
346  template <size_t index>
347  constexpr auto convert_unsafely_to() const noexcept
348  {
349  return convert_impl<index, false>();
350  }
352 
361  template <typename alternative_t>
362  constexpr bool holds_alternative() const noexcept
364  requires (is_alternative<alternative_t>())
366  {
367  constexpr size_t index = seqan3::list_traits::find<alternative_t, alternatives>;
368  return holds_alternative<index>();
369  }
370 
377  template <typename alternative_t>
378  constexpr alternative_t convert_to() const
380  requires (is_alternative<alternative_t>())
382  {
383  constexpr size_t index = seqan3::list_traits::find<alternative_t, alternatives>;
384  return convert_impl<index, true>();
385  }
386 
392  template <typename alternative_t>
393  constexpr alternative_t convert_unsafely_to() const noexcept
395  requires (is_alternative<alternative_t>())
397  {
398  constexpr size_t index = seqan3::list_traits::find<alternative_t, alternatives>;
399  return convert_impl<index, false>();
400  }
402 
425  template <typename alphabet_variant_t, typename indirect_alternative_type>
426  friend constexpr auto operator==(alphabet_variant_t const lhs, indirect_alternative_type const rhs) noexcept
427  -> std::enable_if_t<detail::variant_comparison_guard<alphabet_variant_t,
428  indirect_alternative_type,
429  false,
430  alternative_types...>,
431  bool>
432  {
433  using alternative_predicate = detail::weakly_equality_comparable_with_<indirect_alternative_type>;
434  constexpr auto alternative_position = seqan3::list_traits::find_if<alternative_predicate::template invoke,
435  alternatives>;
437  return lhs.template holds_alternative<alternative_t>() && (lhs.template convert_unsafely_to<alternative_t>() == rhs);
438  }
439 
441  template <typename alphabet_variant_t, typename indirect_alternative_type>
442  friend constexpr auto operator!=(alphabet_variant_t const lhs, indirect_alternative_type const rhs) noexcept
443  -> std::enable_if_t<detail::variant_comparison_guard<alphabet_variant_t,
444  indirect_alternative_type,
445  false,
446  alternative_types...>,
447  bool>
448  {
449  return !(lhs == rhs);
450  }
451 
453  template <typename alphabet_variant_t, typename indirect_alternative_type, typename = void>
454  friend constexpr auto operator==(indirect_alternative_type const lhs, alphabet_variant_t const rhs) noexcept
455  -> std::enable_if_t<detail::variant_comparison_guard<alphabet_variant_t,
456  indirect_alternative_type,
457  true,
458  alternative_types...>,
459  bool>
460  {
461  return rhs == lhs;
462  }
463 
465  template <typename alphabet_variant_t, typename indirect_alternative_type, typename = void>
466  friend constexpr auto operator!=(indirect_alternative_type const lhs, alphabet_variant_t const rhs) noexcept
467  -> std::enable_if_t<detail::variant_comparison_guard<alphabet_variant_t,
468  indirect_alternative_type,
469  true,
470  alternative_types...>,
471  bool>
472  {
473  return rhs != lhs;
474  }
476 
481  static constexpr bool char_is_valid(char_type const chr) noexcept
482  {
483  using index_t = std::make_unsigned_t<char_type>;
484  return first_valid_char_table[static_cast<index_t>(chr)] < sizeof...(alternative_types);
485  }
486 
487 protected:
489 
494  template <size_t index, bool throws>
495  constexpr auto convert_impl() const noexcept(!throws) -> seqan3::list_traits::at<index, alternatives>
496  {
497  static_assert(index < alphabet_size, "The alphabet_variant contains less alternatives than you are checking.");
498  using alternative_t = seqan3::list_traits::at<index, alternatives>;
499 
500  if constexpr (throws)
501  {
502  if (!holds_alternative<index>()) // [[unlikely]]
503  {
504  throw std::bad_variant_access{};
505  }
506  }
507 
508  return seqan3::assign_rank_to(to_rank() - partial_sum_sizes[index], alternative_t{});
509  }
510 
518  static constexpr std::array<rank_type, sizeof...(alternative_types) + 1> partial_sum_sizes = []() constexpr
519  {
520  constexpr size_t N = sizeof...(alternative_types) + 1;
521 
522  std::array<rank_type, N> partial_sum{0, seqan3::alphabet_size<alternative_types>...};
523  for (size_t i = 1u; i < N; ++i)
524  partial_sum[i] += partial_sum[i-1];
525 
526  return partial_sum;
527  }();
528 
530  static constexpr std::array<char_type, alphabet_size> rank_to_char_table = []() constexpr
531  {
532  // Explicitly writing assign_rank_to_char within assign_rank_to_char
533  // causes this bug (g++-7 and g++-8):
534  // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=84684
535  auto assign_rank_to_char = [](auto alternative, size_t rank) constexpr
536  {
537  return seqan3::to_char(seqan3::assign_rank_to(rank, alternative));
538  };
539 
540  auto assign_value_to_char = [assign_rank_to_char] (auto alternative, auto & value_to_char, auto & value) constexpr
541  {
542  using alternative_t = std::decay_t<decltype(alternative)>;
543  for (size_t i = 0u; i < seqan3::alphabet_size<alternative_t>; ++i, ++value)
544  value_to_char[value] = assign_rank_to_char(alternative, i);
545  };
546 
547  unsigned value = 0u;
548  std::array<char_type, alphabet_size> value_to_char{};
549 
550  // initializer lists guarantee sequencing;
551  // the following expression behaves as:
552  // for(auto alternative: alternative_types)
553  // assign_rank_to_char(alternative, rank_to_char, value);
554  ((assign_value_to_char(alternative_types{}, value_to_char, value)),...);
555 
556  return value_to_char;
557  }();
558 
563  template <size_t index, typename alternative_t>
565  requires (is_alternative<alternative_t>())
567  static constexpr rank_type rank_by_index_(alternative_t const & alternative) noexcept
568  {
569  return partial_sum_sizes[index] + static_cast<rank_type>(seqan3::to_rank(alternative));
570  }
571 
576  template <typename alternative_t>
578  requires (is_alternative<alternative_t>())
580  static constexpr rank_type rank_by_type_(alternative_t const & alternative) noexcept
581  {
582  constexpr size_t index = seqan3::list_traits::find<alternative_t, alternatives>;
583  return rank_by_index_<index>(alternative);
584  }
585 
589  static constexpr auto first_valid_char_table
590  {
591  [] () constexpr
592  {
593  constexpr size_t alternative_size = sizeof...(alternative_types);
594  constexpr size_t table_size = detail::size_in_values_v<char_type>;
595  using first_alphabet_t = detail::min_viable_uint_t<alternative_size>;
596 
598 
599  for (size_t i = 0u; i < table_size; ++i)
600  {
601  char_type chr = static_cast<char_type>(i);
602 
603  std::array<bool, alternative_size> valid_chars{char_is_valid_for<alternative_types>(chr)...};
604 
605 #if defined(__cpp_lib_constexpr_algorithms) && __cpp_lib_constexpr_algorithms >= 201806L
606  // the following lines only works beginning from c++20
607  auto found_it = std::find(valid_chars.begin(), valid_chars.end(), true);
608  lookup_table[i] = found_it - valid_chars.begin();
609 #else
610  size_t found_index = 0u;
611  for (; found_index < valid_chars.size() && !valid_chars[found_index]; ++found_index);
612  lookup_table[i] = found_index;
613 #endif // defined(__cpp_lib_constexpr_algorithms) && __cpp_lib_constexpr_algorithms >= 201806L
614  }
615 
616  return lookup_table;
617  }()
618  };
619 
621  static constexpr std::array<rank_type, detail::size_in_values_v<char_type>> char_to_rank_table = []() constexpr
622  {
623  constexpr size_t alternative_size = sizeof...(alternative_types);
624  constexpr size_t table_size = detail::size_in_values_v<char_type>;
625 
626  std::array<rank_type, table_size> char_to_rank{};
627 
628  for (size_t i = 0u; i < table_size; ++i)
629  {
630  char_type chr = static_cast<char_type>(i);
631 
632  std::array<rank_type, alternative_size> ranks{rank_by_type_(assign_char_to(chr, alternative_types{}))...};
633 
634  // if no char_is_valid_for any alternative use the rank of the first alternative
635  char_to_rank[i] = first_valid_char_table[i] < alternative_size ? ranks[first_valid_char_table[i]] : 0;
636  }
637 
638  return char_to_rank;
639  }();
640 
647  static constexpr char_type rank_to_char(rank_type const rank)
648  {
649  return rank_to_char_table[rank];
650  }
651 
658  static constexpr rank_type char_to_rank(char_type const chr)
659  {
660  using index_t = std::make_unsigned_t<char_type>;
661  return char_to_rank_table[static_cast<index_t>(chr)];
662  }
663 };
664 
665 } // namespace seqan3
Provides seqan3::alphabet_base.
A CRTP-base that makes defining a custom alphabet easier.
Definition: alphabet_base.hpp:57
constexpr char_type to_char() const noexcept
Return the letter as a character of char_type.
Definition: alphabet_base.hpp:115
constexpr rank_type to_rank() const noexcept
Return the letter's numeric value (rank in the alphabet).
Definition: alphabet_base.hpp:139
detail::min_viable_uint_t< size - 1 > rank_type
The type of the alphabet when represented as a number (e.g. via to_rank()).
Definition: alphabet_base.hpp:80
static constexpr detail::min_viable_uint_t< size > alphabet_size
The size of the alphabet, i.e. the number of different values it can take.
Definition: alphabet_base.hpp:203
constexpr alphabet_variant< alternative_types... > & assign_rank(rank_type const c) noexcept
Assign from a numeric value.
Definition: alphabet_base.hpp:191
std::conditional_t< std::same_as< char, void >, char, char > char_type
The char representation; conditional needed to make semi alphabet definitions legal.
Definition: alphabet_base.hpp:72
A combined alphabet that can hold values of either of its alternatives.
Definition: alphabet_variant.hpp:129
static constexpr bool char_is_valid(char_type const chr) noexcept
Validate whether a character is valid in the combined alphabet.
Definition: alphabet_variant.hpp:481
static constexpr bool is_alternative() noexcept
Returns true if alternative_t is one of the given alternative types.
Definition: alphabet_variant.hpp:181
constexpr bool holds_alternative() const noexcept
Whether the variant alphabet currently holds a value of the given alternative.
Definition: alphabet_variant.hpp:323
constexpr friend auto operator==(alphabet_variant_t const lhs, indirect_alternative_type const rhs) noexcept -> std::enable_if_t< detail::variant_comparison_guard< alphabet_variant_t, indirect_alternative_type, false, alternative_types... >, bool >
(In-)Equality comparison against types comparable with alternatives but not convertible to the varian...
Definition: alphabet_variant.hpp:426
constexpr friend auto operator!=(indirect_alternative_type const lhs, alphabet_variant_t const rhs) noexcept -> std::enable_if_t< detail::variant_comparison_guard< alphabet_variant_t, indirect_alternative_type, true, alternative_types... >, bool >
(In-)Equality comparison against types comparable with alternatives but not convertible to the varian...
Definition: alphabet_variant.hpp:466
constexpr friend auto operator==(indirect_alternative_type const lhs, alphabet_variant_t const rhs) noexcept -> std::enable_if_t< detail::variant_comparison_guard< alphabet_variant_t, indirect_alternative_type, true, alternative_types... >, bool >
(In-)Equality comparison against types comparable with alternatives but not convertible to the varian...
Definition: alphabet_variant.hpp:454
constexpr auto convert_to() const
Convert to the specified alphabet (throws if holds_alternative() would be false).
Definition: alphabet_variant.hpp:336
constexpr friend auto operator!=(alphabet_variant_t const lhs, indirect_alternative_type const rhs) noexcept -> std::enable_if_t< detail::variant_comparison_guard< alphabet_variant_t, indirect_alternative_type, false, alternative_types... >, bool >
(In-)Equality comparison against types comparable with alternatives but not convertible to the varian...
Definition: alphabet_variant.hpp:442
constexpr alphabet_variant() noexcept=default
Defaulted.
constexpr alternative_t convert_to() const
Convert to the specified alphabet (throws if holds_alternative() would be false).
Definition: alphabet_variant.hpp:378
constexpr auto convert_unsafely_to() const noexcept
Convert to the specified alphabet (undefined behaviour if holds_alternative() would be false).
Definition: alphabet_variant.hpp:347
constexpr alternative_t convert_unsafely_to() const noexcept
Convert to the specified alphabet (undefined behaviour if holds_alternative() would be false).
Definition: alphabet_variant.hpp:393
T find(T... args)
constexpr auto assign_char_to
Assign a character to an alphabet object.
Definition: concept.hpp:526
constexpr auto to_char
Return the char representation of an alphabet object.
Definition: concept.hpp:387
constexpr auto assign_rank_to
Assign a rank to an alphabet object.
Definition: concept.hpp:294
decltype(seqan3::to_char(std::declval< alphabet_type const >())) alphabet_char_t
The char_type of the alphabet; defined as the return type of seqan3::to_char.
Definition: concept.hpp:399
constexpr auto to_rank
Return the rank representation of a (semi-)alphabet object.
Definition: concept.hpp:155
decltype(detail::concat(lists_t{}...)) concat
Join two seqan3::type_list s into one.
Definition: traits.hpp:329
constexpr bool contains
Whether a type occurs in a type list or not.
Definition: traits.hpp:231
typename decltype(detail::at< idx >(list_t{}))::type at
Return the type at given index from the type list.
Definition: traits.hpp:260
constexpr ptrdiff_t find_if
Get the index of the first type in a pack that satisfies the given predicate.
Definition: traits.hpp:210
constexpr bool contains
Whether a type occurs in a pack or not.
Definition: traits.hpp:228
Resolves to std::is_assignable_v<t>.
T is_base_of_v
T is_same_v
Provides lazy template instantiation traits.
The main SeqAn3 namespace.
Definition: aligned_sequence_concept.hpp:29
SeqAn specific customisations in the standard namespace.
T partial_sum(T... args)
Type that contains multiple types.
Definition: type_list.hpp:29
Provides traits for seqan3::type_list.