search_scheme_precomputed.hpp

Go to the documentation of this file.

// -----------------------------------------------------------------------------------------------------
// Copyright (c) 2006-2022, Knut Reinert & Freie Universität Berlin
// Copyright (c) 2016-2022, 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/seqan/seqan3/blob/master/LICENSE.md
// -----------------------------------------------------------------------------------------------------
 
#pragma once
 
#include <array>
#include <vector>
 
#include <seqan3/core/platform.hpp>
 
namespace seqan3::detail
{
 
template <uint8_t nbr_blocks>
struct search
{
    typedef std::array<size_t, nbr_blocks> blocks_length_type;
 
    std::array<uint8_t, nbr_blocks> pi;
    std::array<uint8_t, nbr_blocks> l;
    std::array<uint8_t, nbr_blocks> u;
 
    constexpr uint8_t blocks() const noexcept
    {
        return nbr_blocks;
    }
};
 
struct search_dyn
{
    typedef std::vector<size_t> blocks_length_type;
 
    std::vector<uint8_t> pi;
    std::vector<uint8_t> l;
    std::vector<uint8_t> u;
 
    uint8_t blocks() const noexcept
    {
        return pi.size();
    }
};
 
template <uint8_t nbr_searches, uint8_t nbr_blocks>
using search_scheme_type = std::array<search<nbr_blocks>, nbr_searches>;
 
using search_scheme_dyn_type = std::vector<search_dyn>;
 
template <uint8_t min_error, uint8_t max_error>
inline constexpr int optimum_search_scheme{0};
 
 
template <>
inline constexpr search_scheme_type<1, 1> optimum_search_scheme<0, 0>{{{{1}, {0}, {0}}}};
 
template <>
inline constexpr search_scheme_type<2, 2> optimum_search_scheme<0, 1>{
    {{{1, 2}, {0, 0}, {0, 1}}, {{2, 1}, {0, 1}, {0, 1}}}};
 
template <>
inline constexpr search_scheme_type<2, 2> optimum_search_scheme<1, 1>{
    {{{1, 2}, {0, 1}, {0, 1}}, {{2, 1}, {0, 1}, {0, 1}}}};
 
template <>
inline constexpr search_scheme_type<3, 4> optimum_search_scheme<0, 2>{{{{1, 2, 3, 4}, {0, 0, 1, 1}, {0, 0, 2, 2}},
                                                                       {{3, 2, 1, 4}, {0, 0, 0, 0}, {0, 1, 1, 2}},
                                                                       {{4, 3, 2, 1}, {0, 0, 0, 2}, {0, 1, 2, 2}}}};
 
template <>
inline constexpr search_scheme_type<3, 4> optimum_search_scheme<1, 2>{{{{1, 2, 3, 4}, {0, 0, 0, 1}, {0, 0, 2, 2}},
                                                                       {{3, 2, 1, 4}, {0, 0, 1, 1}, {0, 1, 1, 2}},
                                                                       {{4, 3, 2, 1}, {0, 0, 0, 2}, {0, 1, 2, 2}}}};
 
template <>
inline constexpr search_scheme_type<3, 4> optimum_search_scheme<2, 2>{{{{4, 3, 2, 1}, {0, 0, 1, 2}, {0, 0, 2, 2}},
                                                                       {{2, 3, 4, 1}, {0, 0, 0, 2}, {0, 1, 1, 2}},
                                                                       {{1, 2, 3, 4}, {0, 0, 0, 2}, {0, 1, 2, 2}}}};
 
template <>
inline constexpr search_scheme_type<4, 5> optimum_search_scheme<0, 3>{
    {// TODO: benchmark whether the first search is really the fastest one (see \details of optimum_search_scheme)
     {{5, 4, 3, 2, 1}, {0, 0, 0, 0, 0}, {0, 0, 3, 3, 3}},
     {{3, 4, 5, 2, 1}, {0, 0, 1, 1, 1}, {0, 1, 1, 2, 3}},
     {{2, 3, 4, 5, 1}, {0, 0, 0, 2, 2}, {0, 1, 2, 2, 3}},
     {{1, 2, 3, 4, 5}, {0, 0, 0, 0, 3}, {0, 2, 2, 3, 3}}}};
 
template <>
inline constexpr search_scheme_type<4, 5> optimum_search_scheme<1, 3>{
    {{{5, 4, 3, 2, 1}, {0, 0, 0, 0, 1}, {0, 0, 3, 3, 3}},
     {{3, 4, 5, 2, 1}, {0, 0, 1, 1, 1}, {0, 1, 1, 2, 3}},
     {{2, 3, 4, 5, 1}, {0, 0, 0, 2, 2}, {0, 1, 2, 2, 3}},
     {{1, 2, 3, 4, 5}, {0, 0, 0, 0, 3}, {0, 2, 2, 3, 3}}}};
 
template <>
inline constexpr search_scheme_type<4, 5> optimum_search_scheme<2, 3>{
    {{{5, 4, 3, 2, 1}, {0, 0, 0, 0, 2}, {0, 0, 3, 3, 3}},
     {{3, 4, 5, 2, 1}, {0, 0, 1, 1, 2}, {0, 1, 1, 2, 3}},
     {{2, 3, 4, 5, 1}, {0, 0, 0, 2, 2}, {0, 1, 2, 2, 3}},
     {{1, 2, 3, 4, 5}, {0, 0, 0, 0, 3}, {0, 2, 2, 3, 3}}}};
 
template <>
inline constexpr search_scheme_type<4, 5> optimum_search_scheme<3, 3>{
    {{{5, 4, 3, 2, 1}, {0, 0, 0, 0, 3}, {0, 0, 3, 3, 3}},
     {{3, 4, 5, 2, 1}, {0, 0, 1, 1, 3}, {0, 1, 1, 2, 3}},
     {{2, 3, 4, 5, 1}, {0, 0, 0, 2, 3}, {0, 1, 2, 2, 3}},
     {{1, 2, 3, 4, 5}, {0, 0, 0, 0, 3}, {0, 2, 2, 3, 3}}}};
 
// TODO: add the following missing optimum search schemes (computation has not finished yet)
// optimum_search_scheme<i, 4>, 0 < i <= 4
 
 
} // namespace seqan3::detail