variant.hpp

Go to the documentation of this file.

// -----------------------------------------------------------------------------------------------------
// Copyright (c) 2022 deCODE Genetics
// Copyright (c) 2006-2021, Knut Reinert & Freie Universität Berlin
// Copyright (c) 2016-2021, Knut Reinert & MPI für molekulare Genetik
// This file may be used, modified and/or redistributed under the terms of the 3-clause BSD-License
// shipped with this file and also available at: https://github.com/biocpp/biocpp-core/blob/main/LICENSE.md
// -----------------------------------------------------------------------------------------------------
 
#pragma once
 
#include <algorithm>
#include <array>
#include <cassert>
#include <utility>
#include <variant>
 
#include <bio/alphabet/base.hpp>
#include <bio/alphabet/composite/detail.hpp>
#include <bio/meta/type_list/traits.hpp>
 
namespace bio::alphabet::detail
{
 
template <typename other_t, typename... alternative_types>
concept variant_general_guard =
  !meta::one_of<other_t, variant<alternative_types...>, alternative_types...> &&
  !meta::list_traits::contains<variant<alternative_types...>, recursive_required_types_t<other_t>>;
 
} // namespace bio::alphabet::detail
 
namespace bio::alphabet
{
 
template <typename... alternative_types>
    requires((detail::writable_constexpr_alphabet<alternative_types> && ...) &&
             (std::regular<alternative_types> && ...) && (sizeof...(alternative_types) >= 2))
class variant : public base<variant<alternative_types...>, (static_cast<size_t>(size<alternative_types>) + ...), char>
{
private:
    using base_t = base<variant<alternative_types...>, (static_cast<size_t>(size<alternative_types>) + ...), char>;
 
    static_assert((std::is_same_v<char_t<alternative_types>, char> && ...),
                  "The variant is currently only tested for alphabets with char_type char. "
                  "Contact us on GitHub if you have a different use case: https://github.com/biocpp/biocpp-core .");
 
    friend base_t;
 
    using alternatives = meta::type_list<alternative_types...>;
 
    static_assert(((meta::list_traits::count<alternative_types, alternatives> == 1) && ... && true),
                  "All types in a variant must be distinct.");
 
    using typename base_t::char_type;
    using typename base_t::rank_type;
 
public:
    using base_t::alphabet_size;
    using base_t::assign_rank;
    using base_t::to_char;
    using base_t::to_rank;
 
    using biocpp_required_types           = meta::type_list<alternative_types...>;
    using biocpp_recursive_required_types = meta::list_traits::concat<
      biocpp_required_types,
      meta::transformation_trait_or_t<detail::recursive_required_types<alternative_types>, meta::type_list<>>...>;
 
    template <typename alternative_t>
    static constexpr bool is_alternative() noexcept
    {
        return meta::detail::pack_traits::contains<alternative_t, alternative_types...>;
    }
 
    constexpr variant() noexcept                            = default; 
    constexpr variant(variant const &) noexcept             = default; 
    constexpr variant(variant &&) noexcept                  = default; 
    constexpr variant & operator=(variant const &) noexcept = default; 
    constexpr variant & operator=(variant &&) noexcept      = default; 
    ~variant() noexcept                                     = default; 
 
    template <typename alternative_t>
        requires(is_alternative<alternative_t>())
    constexpr variant(alternative_t const alternative) noexcept
    {
        assign_rank(rank_by_type_(alternative));
    }
 
    template <typename indirect_alternative_t>
        requires(detail::variant_general_guard<indirect_alternative_t, alternative_types...> &&
                 (std::is_convertible_v<indirect_alternative_t, alternative_types> || ...))
    constexpr variant(indirect_alternative_t const rhs) noexcept
    {
        using alternative_predicate = detail::implicitly_convertible_from<indirect_alternative_t>;
        constexpr auto alternative_position =
          meta::list_traits::find_if<alternative_predicate::template invoke, alternatives>;
        using alternative_t = meta::list_traits::at<alternative_position, alternatives>;
        assign_rank(rank_by_type_(alternative_t(rhs)));
    }
 
    template <typename indirect_alternative_t>
        requires(detail::variant_general_guard<indirect_alternative_t, alternative_types...> &&
                 !(std::is_convertible_v<indirect_alternative_t, alternative_types> || ...) &&
                 (std::is_constructible_v<alternative_types, indirect_alternative_t> || ...))
    constexpr explicit variant(indirect_alternative_t const rhs) noexcept
    {
        using alternative_predicate = detail::constructible_from<indirect_alternative_t>;
        constexpr auto alternative_position =
          meta::list_traits::find_if<alternative_predicate::template invoke, alternatives>;
        using alternative_t = meta::list_traits::at<alternative_position, alternatives>;
        assign_rank(rank_by_type_(alternative_t(rhs)));
    }
 
    template <typename indirect_alternative_t>
        requires(detail::variant_general_guard<indirect_alternative_t, alternative_types...> &&
                 (meta::weakly_assignable_from<alternative_types, indirect_alternative_t> || ...))
    constexpr variant & operator=(indirect_alternative_t const & rhs) noexcept
    {
        using alternative_predicate = detail::assignable_from<indirect_alternative_t>;
        constexpr auto alternative_position =
          meta::list_traits::find_if<alternative_predicate::template invoke, alternatives>;
        using alternative_t = meta::list_traits::at<alternative_position, alternatives>;
        alternative_t alternative{};
        alternative = rhs;
        assign_rank(rank_by_type_(alternative));
        return *this;
    }
 
    template <size_t index>
    constexpr bool holds_alternative() const noexcept
    {
        static_assert(index < alphabet_size, "The variant contains less alternatives than you are checking.");
        return (to_rank() >= partial_sum_sizes[index]) && (to_rank() < partial_sum_sizes[index + 1]);
    }
 
    template <size_t index>
    constexpr auto convert_to() const
    {
        return convert_impl<index, true>();
    }
 
    template <size_t index>
    constexpr auto convert_unsafely_to() const noexcept
    {
        return convert_impl<index, false>();
    }
 
    template <typename alternative_t>
    constexpr bool holds_alternative() const noexcept
        requires(is_alternative<alternative_t>())
    {
        constexpr size_t index = meta::list_traits::find<alternative_t, alternatives>;
        return holds_alternative<index>();
    }
 
    template <typename alternative_t>
    constexpr alternative_t convert_to() const
        requires(is_alternative<alternative_t>())
    {
        constexpr size_t index = meta::list_traits::find<alternative_t, alternatives>;
        return convert_impl<index, true>();
    }
 
    template <typename alternative_t>
    constexpr alternative_t convert_unsafely_to() const noexcept
        requires(is_alternative<alternative_t>())
    {
        constexpr size_t index = meta::list_traits::find<alternative_t, alternatives>;
        return convert_impl<index, false>();
    }
 
    template <std::same_as<variant> variant_t, typename indirect_alternative_type>
        requires((detail::variant_general_guard<indirect_alternative_type, alternative_types...>) &&
                 (meta::weakly_equality_comparable_with<indirect_alternative_type, alternative_types> || ...))
    friend constexpr bool operator==(variant_t const lhs, indirect_alternative_type const rhs) noexcept
    {
        using alternative_predicate = detail::weakly_equality_comparable_with_<indirect_alternative_type>;
        constexpr auto alternative_position =
          meta::list_traits::find_if<alternative_predicate::template invoke, alternatives>;
        using alternative_t = meta::list_traits::at<alternative_position, alternatives>;
        return lhs.template holds_alternative<alternative_t>() &&
               (lhs.template convert_unsafely_to<alternative_t>() == rhs);
    }
 
    static constexpr bool char_is_valid(char_type const chr) noexcept
    {
        using index_t = std::make_unsigned_t<char_type>;
        return first_valid_char_table[static_cast<index_t>(chr)] < sizeof...(alternative_types);
    }
 
protected:
 
    template <size_t index, bool throws>
    constexpr auto convert_impl() const noexcept(!throws) -> meta::list_traits::at<index, alternatives>
    {
        static_assert(index < alphabet_size, "The variant contains less alternatives than you are checking.");
        using alternative_t = meta::list_traits::at<index, alternatives>;
 
        if constexpr (throws)
        {
            if (!holds_alternative<index>()) // [[unlikely]]
            {
                throw std::bad_variant_access{};
            }
        }
 
        return bio::alphabet::assign_rank_to(to_rank() - partial_sum_sizes[index], alternative_t{});
    }
 
    static constexpr std::array<rank_type, sizeof...(alternative_types) + 1> partial_sum_sizes = []() constexpr
    {
        constexpr size_t N = sizeof...(alternative_types) + 1;
 
        std::array<rank_type, N> partial_sum{0, bio::alphabet::size<alternative_types>...};
        for (size_t i = 1u; i < N; ++i)
            partial_sum[i] += partial_sum[i - 1];
 
        return partial_sum;
    }();
 
    static constexpr std::array<char_type, alphabet_size> rank_to_char = []() constexpr
    {
        // Explicitly writing assign_rank_to_char within assign_rank_to_char
        // causes this bug (g++-7 and g++-8):
        // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=84684
        auto assign_rank_to_char = [](auto alternative, size_t rank) constexpr
        { return bio::alphabet::to_char(bio::alphabet::assign_rank_to(rank, alternative)); };
 
        auto assign_value_to_char =
          [assign_rank_to_char](auto alternative, auto & value_to_char, auto & value) constexpr
        {
            using alternative_t = std::decay_t<decltype(alternative)>;
            for (size_t i = 0u; i < bio::alphabet::size<alternative_t>; ++i, ++value)
                value_to_char[value] = assign_rank_to_char(alternative, i);
        };
 
        unsigned                             value = 0u;
        std::array<char_type, alphabet_size> value_to_char{};
 
        // initializer lists guarantee sequencing;
        // the following expression behaves as:
        // for(auto alternative: alternative_types)
        //    assign_rank_to_char(alternative, rank_to_char, value);
        ((assign_value_to_char(alternative_types{}, value_to_char, value)), ...);
 
        return value_to_char;
    }();
 
    template <size_t index, typename alternative_t>
        requires(is_alternative<alternative_t>())
    static constexpr rank_type rank_by_index_(alternative_t const & alternative) noexcept
    {
        return partial_sum_sizes[index] + static_cast<rank_type>(bio::alphabet::to_rank(alternative));
    }
 
    template <typename alternative_t>
        requires(is_alternative<alternative_t>())
    static constexpr rank_type rank_by_type_(alternative_t const & alternative) noexcept
    {
        constexpr size_t index = meta::list_traits::find<alternative_t, alternatives>;
        return rank_by_index_<index>(alternative);
    }
 
    static constexpr auto first_valid_char_table = []() constexpr
    {
        constexpr size_t alternative_size = sizeof...(alternative_types);
        constexpr size_t table_size       = meta::detail::size_in_values_v<char_type>;
        using first_alphabet_t            = meta::detail::min_viable_uint_t<alternative_size>;
 
        std::array<first_alphabet_t, table_size> lookup_table{};
 
        for (size_t i = 0u; i < table_size; ++i)
        {
            char_type chr = static_cast<char_type>(i);
 
            std::array<bool, alternative_size> valid_chars{char_is_valid_for<alternative_types>(chr)...};
 
            auto found_it   = std::find(valid_chars.begin(), valid_chars.end(), true);
            lookup_table[i] = found_it - valid_chars.begin();
        }
 
        return lookup_table;
    }();
 
    static constexpr std::array<rank_type, meta::detail::size_in_values_v<char_type>> char_to_rank = []() constexpr
    {
        constexpr size_t alternative_size = sizeof...(alternative_types);
        constexpr size_t table_size       = meta::detail::size_in_values_v<char_type>;
 
        std::array<rank_type, table_size> char_to_rank{};
 
        for (size_t i = 0u; i < table_size; ++i)
        {
            char_type chr = static_cast<char_type>(i);
 
            std::array<rank_type, alternative_size> ranks{rank_by_type_(assign_char_to(chr, alternative_types{}))...};
 
            // if no char_is_valid_for any alternative use the rank of the first alternative
            char_to_rank[i] = first_valid_char_table[i] < alternative_size ? ranks[first_valid_char_table[i]] : 0;
        }
 
        return char_to_rank;
    }();
};
 
} // namespace bio::alphabet