SeqAn3  3.2.0-rc.1
The Modern C++ library for sequence analysis.
alphabet_variant.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 
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 
32 template <typename other_t, typename... alternative_types>
33 inline constexpr bool variant_general_guard =
34  (!std::same_as<other_t, alphabet_variant<alternative_types...>>)&&(
35  !std::is_base_of_v<alphabet_variant<alternative_types...>,
36  other_t>)&&(!(std::same_as<other_t, alternative_types> || ...))
37  && (!list_traits::contains<alphabet_variant<alternative_types...>, recursive_required_types_t<other_t>>);
38 
40 template <typename lhs_t, typename rhs_t, bool lhs_rhs_switched, typename... alternative_types>
41 inline constexpr bool variant_comparison_guard =
42  (instantiate_if_v<
43  lazy<weakly_equality_comparable_with_trait, rhs_t, alternative_types>,
44  (std::same_as<lhs_t, alphabet_variant<alternative_types...>>)&&(
45  variant_general_guard<rhs_t, alternative_types...>)&&!(lhs_rhs_switched
46  && is_type_specialisation_of_v<rhs_t,
47  alphabet_variant>)>
48  || ...);
49 } // namespace seqan3::detail
50 
51 namespace seqan3
52 {
53 
113 template <typename... alternative_types>
114  requires (detail::writable_constexpr_alphabet<alternative_types> && ...) && (std::regular<alternative_types> && ...)
115  && (sizeof...(alternative_types) >= 2)
116 class alphabet_variant :
117  public alphabet_base<alphabet_variant<alternative_types...>,
118  (static_cast<size_t>(alphabet_size<alternative_types>) + ...),
119  char>
120 {
121 private:
123  using base_t = alphabet_base<alphabet_variant<alternative_types...>,
124  (static_cast<size_t>(alphabet_size<alternative_types>) + ...),
125  char>;
126 
127  static_assert((std::is_same_v<alphabet_char_t<alternative_types>, char> && ...),
128  "The alphabet_variant is currently only tested for alphabets with char_type char. "
129  "Contact us on GitHub if you have a different use case: https://github.com/seqan/seqan3 .");
130 
132  friend base_t;
133 
135  using alternatives = seqan3::type_list<alternative_types...>;
136 
137  static_assert(((seqan3::list_traits::count<alternative_types, alternatives> == 1) && ... && true),
138  "All types in a alphabet_variant must be distinct.");
139 
140  using typename base_t::char_type;
141  using typename base_t::rank_type;
142 
143 public:
144  using base_t::alphabet_size;
145  using base_t::assign_rank;
146  using base_t::to_char;
147  using base_t::to_rank;
148 
154  using seqan3_required_types = type_list<alternative_types...>;
160  using seqan3_recursive_required_types = list_traits::concat<
161  seqan3_required_types,
162  detail::transformation_trait_or_t<detail::recursive_required_types<alternative_types>, type_list<>>...>;
163 
171  template <typename alternative_t>
172  static constexpr bool is_alternative() noexcept
173  {
174  return seqan3::pack_traits::contains<alternative_t, alternative_types...>;
175  }
176 
180  constexpr alphabet_variant() noexcept = default;
181  constexpr alphabet_variant(alphabet_variant const &) noexcept = default;
182  constexpr alphabet_variant(alphabet_variant &&) noexcept = default;
183  constexpr alphabet_variant & operator=(alphabet_variant const &) noexcept = default;
184  constexpr alphabet_variant & operator=(alphabet_variant &&) noexcept = default;
185  ~alphabet_variant() noexcept = default;
186 
195  template <typename alternative_t>
196  requires (!std::same_as<alternative_t, alphabet_variant>)
197  && (!std::is_base_of_v<alphabet_variant, alternative_t>)
198  && (!list_traits::contains<
199  alphabet_variant,
200  detail::transformation_trait_or_t<detail::recursive_required_types<alternative_t>, type_list<>>>)
201  && (is_alternative<alternative_t>())
202  constexpr alphabet_variant(alternative_t const alternative) noexcept
203  {
204  assign_rank(rank_by_type_(alternative));
205  }
206 
225  template <typename indirect_alternative_t>
226  requires (
227  (detail::instantiate_if_v<detail::lazy<std::is_convertible, indirect_alternative_t, alternative_types>,
228  detail::variant_general_guard<indirect_alternative_t, alternative_types...>>
229  || ...))
230  constexpr alphabet_variant(indirect_alternative_t const rhs) noexcept
231  {
232  using alternative_predicate = detail::implicitly_convertible_from<indirect_alternative_t>;
233  constexpr auto alternative_position =
234  seqan3::list_traits::find_if<alternative_predicate::template invoke, alternatives>;
235  using alternative_t = seqan3::list_traits::at<alternative_position, alternatives>;
236  assign_rank(rank_by_type_(alternative_t(rhs)));
237  }
238 
255  template <typename indirect_alternative_t>
256  requires (
257  (!(detail::instantiate_if_v<detail::lazy<std::is_convertible, indirect_alternative_t, alternative_types>,
258  detail::variant_general_guard<indirect_alternative_t, alternative_types...>>
259  || ...))
260  && (detail::instantiate_if_v<detail::lazy<std::is_constructible, alternative_types, indirect_alternative_t>,
261  detail::variant_general_guard<indirect_alternative_t, alternative_types...>>
262  || ...))
263  constexpr explicit alphabet_variant(indirect_alternative_t const rhs) noexcept
264  {
265  using alternative_predicate = detail::constructible_from<indirect_alternative_t>;
266  constexpr auto alternative_position =
267  seqan3::list_traits::find_if<alternative_predicate::template invoke, alternatives>;
268  using alternative_t = seqan3::list_traits::at<alternative_position, alternatives>;
269  assign_rank(rank_by_type_(alternative_t(rhs)));
270  }
271 
283  template <typename indirect_alternative_t>
284  requires (detail::variant_general_guard<indirect_alternative_t, alternative_types...>
286  constexpr alphabet_variant & operator=(indirect_alternative_t const & rhs) noexcept
287  {
288  using alternative_predicate = detail::assignable_from<indirect_alternative_t>;
289  constexpr auto alternative_position =
290  seqan3::list_traits::find_if<alternative_predicate::template invoke, alternatives>;
291  using alternative_t = seqan3::list_traits::at<alternative_position, alternatives>;
292  alternative_t alternative{};
293  alternative = rhs;
294  assign_rank(rank_by_type_(alternative));
295  return *this;
296  }
298 
308  template <size_t index>
309  constexpr bool holds_alternative() const noexcept
310  {
311  static_assert(index < alphabet_size, "The alphabet_variant contains less alternatives than you are checking.");
312  return (to_rank() >= partial_sum_sizes[index]) && (to_rank() < partial_sum_sizes[index + 1]);
313  }
314 
321  template <size_t index>
322  constexpr auto convert_to() const
323  {
324  return convert_impl<index, true>();
325  }
326 
332  template <size_t index>
333  constexpr auto convert_unsafely_to() const noexcept
334  {
335  return convert_impl<index, false>();
336  }
338 
347  template <typename alternative_t>
348  constexpr bool holds_alternative() const noexcept
349  requires (is_alternative<alternative_t>())
350  {
351  constexpr size_t index = seqan3::list_traits::find<alternative_t, alternatives>;
352  return holds_alternative<index>();
353  }
354 
361  template <typename alternative_t>
362  constexpr alternative_t convert_to() const
363  requires (is_alternative<alternative_t>())
364  {
365  constexpr size_t index = seqan3::list_traits::find<alternative_t, alternatives>;
366  return convert_impl<index, true>();
367  }
368 
374  template <typename alternative_t>
375  constexpr alternative_t convert_unsafely_to() const noexcept
376  requires (is_alternative<alternative_t>())
377  {
378  constexpr size_t index = seqan3::list_traits::find<alternative_t, alternatives>;
379  return convert_impl<index, false>();
380  }
382 
405  template <typename alphabet_variant_t, typename indirect_alternative_type>
406  friend constexpr auto
407  operator==(alphabet_variant_t const lhs, indirect_alternative_type const rhs) noexcept -> std::enable_if_t<
408  detail::variant_comparison_guard<alphabet_variant_t, indirect_alternative_type, false, alternative_types...>,
409  bool>
410  {
411  using alternative_predicate = detail::weakly_equality_comparable_with_<indirect_alternative_type>;
412  constexpr auto alternative_position =
413  seqan3::list_traits::find_if<alternative_predicate::template invoke, alternatives>;
414  using alternative_t = seqan3::list_traits::at<alternative_position, alternatives>;
415  return lhs.template holds_alternative<alternative_t>()
416  && (lhs.template convert_unsafely_to<alternative_t>() == rhs);
417  }
418 
420  template <typename alphabet_variant_t, typename indirect_alternative_type>
421  friend constexpr auto
422  operator!=(alphabet_variant_t const lhs, indirect_alternative_type const rhs) noexcept -> std::enable_if_t<
423  detail::variant_comparison_guard<alphabet_variant_t, indirect_alternative_type, false, alternative_types...>,
424  bool>
425  {
426  return !(lhs == rhs);
427  }
428 
430  template <typename alphabet_variant_t, typename indirect_alternative_type, typename = void>
431  friend constexpr auto operator==(indirect_alternative_type const lhs, alphabet_variant_t const rhs) noexcept
432  -> std::enable_if_t<
433  detail::variant_comparison_guard<alphabet_variant_t, indirect_alternative_type, true, alternative_types...>,
434  bool>
435  {
436  return rhs == lhs;
437  }
438 
440  template <typename alphabet_variant_t, typename indirect_alternative_type, typename = void>
441  friend constexpr auto operator!=(indirect_alternative_type const lhs, alphabet_variant_t const rhs) noexcept
442  -> std::enable_if_t<
443  detail::variant_comparison_guard<alphabet_variant_t, indirect_alternative_type, true, alternative_types...>,
444  bool>
445  {
446  return rhs != lhs;
447  }
449 
454  static constexpr bool char_is_valid(char_type const chr) noexcept
455  {
456  using index_t = std::make_unsigned_t<char_type>;
457  return first_valid_char_table[static_cast<index_t>(chr)] < sizeof...(alternative_types);
458  }
459 
460 protected:
462 
467  template <size_t index, bool throws>
468  constexpr auto convert_impl() const noexcept(!throws) -> seqan3::list_traits::at<index, alternatives>
469  {
470  static_assert(index < alphabet_size, "The alphabet_variant contains less alternatives than you are checking.");
471  using alternative_t = seqan3::list_traits::at<index, alternatives>;
472 
473  if constexpr (throws)
474  {
475  if (!holds_alternative<index>()) // [[unlikely]]
476  {
477  throw std::bad_variant_access{};
478  }
479  }
480 
481  return seqan3::assign_rank_to(to_rank() - partial_sum_sizes[index], alternative_t{});
482  }
483 
491  static constexpr std::array<rank_type, sizeof...(alternative_types) + 1> partial_sum_sizes = []() constexpr
492  {
493  constexpr size_t N = sizeof...(alternative_types) + 1;
494 
495  std::array<rank_type, N> partial_sum{0, seqan3::alphabet_size<alternative_types>...};
496  for (size_t i = 1u; i < N; ++i)
497  partial_sum[i] += partial_sum[i - 1];
498 
499  return partial_sum;
500  }
501  ();
502 
504  static constexpr std::array<char_type, alphabet_size> rank_to_char_table = []() constexpr
505  {
506  // Explicitly writing assign_rank_to_char within assign_rank_to_char
507  // causes this bug (g++-7 and g++-8):
508  // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=84684
509  auto assign_rank_to_char = [](auto alternative, size_t rank) constexpr
510  {
511  return seqan3::to_char(seqan3::assign_rank_to(rank, alternative));
512  };
513 
514  auto assign_value_to_char = [assign_rank_to_char](auto alternative,
515  auto & value_to_char,
516  auto & value) constexpr
517  {
518  using alternative_t = std::decay_t<decltype(alternative)>;
519  for (size_t i = 0u; i < seqan3::alphabet_size<alternative_t>; ++i, ++value)
520  value_to_char[value] = assign_rank_to_char(alternative, i);
521  };
522 
523  unsigned value = 0u;
524  std::array<char_type, alphabet_size> value_to_char{};
525 
526  // initializer lists guarantee sequencing;
527  // the following expression behaves as:
528  // for(auto alternative: alternative_types)
529  // assign_rank_to_char(alternative, rank_to_char, value);
530  ((assign_value_to_char(alternative_types{}, value_to_char, value)), ...);
531 
532  return value_to_char;
533  }
534  ();
535 
540  template <size_t index, typename alternative_t>
541  requires (is_alternative<alternative_t>())
542  static constexpr rank_type rank_by_index_(alternative_t const & alternative) noexcept
543  {
544  return partial_sum_sizes[index] + static_cast<rank_type>(seqan3::to_rank(alternative));
545  }
546 
551  template <typename alternative_t>
552  requires (is_alternative<alternative_t>())
553  static constexpr rank_type rank_by_type_(alternative_t const & alternative) noexcept
554  {
555  constexpr size_t index = seqan3::list_traits::find<alternative_t, alternatives>;
556  return rank_by_index_<index>(alternative);
557  }
558 
562  static constexpr auto first_valid_char_table{
563  []() constexpr {constexpr size_t alternative_size = sizeof...(alternative_types);
564  constexpr size_t table_size = detail::size_in_values_v<char_type>;
565  using first_alphabet_t = detail::min_viable_uint_t<alternative_size>;
566 
568 
569  for (size_t i = 0u; i < table_size; ++i)
570  {
571  char_type chr = static_cast<char_type>(i);
572 
573  std::array<bool, alternative_size> valid_chars{char_is_valid_for<alternative_types>(chr)...};
574 
575 #if defined(__cpp_lib_constexpr_algorithms) && __cpp_lib_constexpr_algorithms >= 201806L
576  // the following lines only works beginning from c++20
577  auto found_it = std::find(valid_chars.begin(), valid_chars.end(), true);
578  lookup_table[i] = found_it - valid_chars.begin();
579 #else
580  size_t found_index = 0u;
581  for (; found_index < valid_chars.size() && !valid_chars[found_index]; ++found_index)
582  ;
583  lookup_table[i] = found_index;
584 #endif // defined(__cpp_lib_constexpr_algorithms) && __cpp_lib_constexpr_algorithms >= 201806L
585  }
586 
587  return lookup_table;
588 }()
589 }; // namespace seqan3
590 
592 static constexpr std::array<rank_type, detail::size_in_values_v<char_type>> char_to_rank_table = []() constexpr
593 {
594  constexpr size_t alternative_size = sizeof...(alternative_types);
595  constexpr size_t table_size = detail::size_in_values_v<char_type>;
596 
597  std::array<rank_type, table_size> char_to_rank{};
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<rank_type, alternative_size> ranks{rank_by_type_(assign_char_to(chr, alternative_types{}))...};
604 
605  // if no char_is_valid_for any alternative use the rank of the first alternative
606  char_to_rank[i] = first_valid_char_table[i] < alternative_size ? ranks[first_valid_char_table[i]] : 0;
607  }
608 
609  return char_to_rank;
610 }
611 ();
612 
619 static constexpr char_type rank_to_char(rank_type const rank)
620 {
621  return rank_to_char_table[rank];
622 }
623 
630 static constexpr rank_type char_to_rank(char_type const chr)
631 {
632  using index_t = std::make_unsigned_t<char_type>;
633  return char_to_rank_table[static_cast<index_t>(chr)];
634 }
635 }
636 ;
637 
638 } // namespace seqan3
Provides seqan3::alphabet_base.
T find(T... args)
constexpr auto assign_char_to
Assign a character to an alphabet object.
Definition: alphabet/concept.hpp:524
constexpr auto to_char
Return the char representation of an alphabet object.
Definition: alphabet/concept.hpp:386
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
requires constexpr seqan3::detail::template_specialisation_of< list_t, seqan3::type_list > bool contains
Whether a type occurs in a type list or not.
Definition: type_list/traits.hpp:252
constexpr bool contains
Whether a type occurs in a pack or not.
Definition: type_pack/traits.hpp:223
T holds_alternative(T... args)
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 operator!=(T... args)
T partial_sum(T... args)
Type that contains multiple types.
Definition: type_list.hpp:29
Provides traits for seqan3::type_list.