20 namespace seqan3::detail
38 template <std::ranges::view urng_t>
39 class kmer_hash_view :
public std::ranges::view_interface<kmer_hash_view<urng_t>>
42 static_assert(std::ranges::forward_range<urng_t>,
"The kmer_hash_view only works on forward_ranges");
43 static_assert(
semialphabet<std::ranges::range_reference_t<urng_t>>,
44 "The reference type of the underlying range must model seqan3::semialphabet.");
52 template <
bool const_range>
59 kmer_hash_view() =
default;
60 kmer_hash_view(kmer_hash_view
const & rhs) =
default;
61 kmer_hash_view(kmer_hash_view && rhs) =
default;
62 kmer_hash_view & operator=(kmer_hash_view
const & rhs) =
default;
63 kmer_hash_view & operator=(kmer_hash_view && rhs) =
default;
64 ~kmer_hash_view() =
default;
70 kmer_hash_view(urng_t urange_, shape
const & s_) : urange{
std::
move(urange_)}, shape_{s_}
72 if (shape_.count() > (64 / std::log2(
alphabet_size<std::ranges::range_reference_t<urng_t>>)))
75 "The alphabet or shape size must be reduced."};
83 template <
typename rng_t>
86 std::ranges::viewable_range<rng_t> &&
87 std::constructible_from<urng_t, std::ranges::ref_view<std::remove_reference_t<rng_t>>>
89 kmer_hash_view(rng_t && urange_, shape
const & s_) :
90 urange{
std::views::all(
std::
forward<rng_t>(urange_))}, shape_{s_}
92 if (shape_.count() > (64 / std::log2(
alphabet_size<std::ranges::range_reference_t<urng_t>>)))
95 "The alphabet or shape size must be reduced."};
116 auto begin() noexcept
118 return basic_iterator<false>{
std::ranges::begin(urange), std::ranges::end(urange), shape_};
122 auto begin() const noexcept
127 return basic_iterator<true>{
std::ranges::cbegin(urange), std::ranges::cend(urange), shape_};
148 if constexpr (std::ranges::common_range<urng_t>)
149 return basic_iterator<false>{
std::ranges::begin(urange), std::ranges::end(urange), shape_,
true};
151 return std::ranges::end(urange);
155 auto end() const noexcept
161 if constexpr (std::ranges::common_range<urng_t const>)
162 return basic_iterator<true>{
std::ranges::cbegin(urange), std::ranges::cend(urange), shape_,
true};
164 return std::ranges::cend(urange);
173 requires
std::ranges::sized_range<urng_t>
176 using size_type = std::ranges::range_size_t<urng_t>;
177 return std::max<size_type>(
std::ranges::size(urange) + 1, shape_.size()) - shape_.size();
183 requires
std::ranges::sized_range<urng_t const>
186 using size_type = std::ranges::range_size_t<urng_t const>;
187 return std::max<size_type>(
std::ranges::size(urange) + 1, shape_.size()) - shape_.size();
218 template <std::ranges::view urng_t>
219 template <
bool const_range>
220 class kmer_hash_view<urng_t>::basic_iterator
221 :
public maybe_iterator_category<maybe_const_iterator_t<const_range, urng_t>>
225 using it_t = maybe_const_iterator_t<const_range, urng_t>;
227 using sentinel_t = maybe_const_sentinel_t<const_range, urng_t>;
229 template <
bool other_const_range>
230 friend class basic_iterator;
239 using value_type = size_t;
241 using pointer = void;
243 using reference = value_type;
247 detail::iterator_concept_tag_t<it_t>>;
253 constexpr basic_iterator() =
default;
254 constexpr basic_iterator(basic_iterator
const &) =
default;
255 constexpr basic_iterator(basic_iterator &&) =
default;
256 constexpr basic_iterator & operator=(basic_iterator
const &) =
default;
257 constexpr basic_iterator & operator=(basic_iterator &&) =
default;
258 ~basic_iterator() =
default;
261 constexpr basic_iterator(basic_iterator<!const_range>
const & it) noexcept
283 basic_iterator(it_t it_start, sentinel_t it_end, shape s_) :
284 shape_{s_}, text_left{it_start}, text_right{
std::ranges::
next(text_left, shape_.
size() - 1, it_end)}
293 if (shape_.size() <= std::ranges::distance(text_left, text_right) + 1)
323 basic_iterator(it_t it_start, sentinel_t it_end, shape s_,
bool SEQAN3_DOXYGEN_ONLY(is_end)) : shape_{s_}
327 auto urange_size = std::ranges::distance(it_start, it_end);
328 auto step = (shape_.size() > urange_size + 1) ? 0 : urange_size - shape_.size() + 1;
329 text_left = std::ranges::next(it_start, step, it_end);
336 if (shape_.size() <= std::ranges::distance(text_left, it_end) + 1)
351 friend bool operator==(basic_iterator
const & lhs, sentinel_t
const & rhs) noexcept
353 return lhs.text_right == rhs;
357 friend bool operator==(sentinel_t
const & lhs, basic_iterator
const & rhs) noexcept
359 return lhs == rhs.text_right;
363 friend bool operator==(basic_iterator
const & lhs, basic_iterator
const & rhs) noexcept
365 return std::tie(lhs.text_right, lhs.shape_) ==
std::tie(rhs.text_right, rhs.shape_);
369 friend bool operator!=(basic_iterator
const & lhs, sentinel_t
const & rhs) noexcept
371 return !(lhs == rhs);
375 friend bool operator!=(sentinel_t
const & lhs, basic_iterator
const & rhs) noexcept
377 return !(lhs == rhs);
381 friend bool operator!=(basic_iterator
const & lhs, basic_iterator
const & rhs) noexcept
383 return !(lhs == rhs);
387 friend bool operator<(basic_iterator
const & lhs, basic_iterator
const & rhs) noexcept
389 return (lhs.shape_ <= rhs.shape_) && (lhs.text_right < rhs.text_right);
393 friend bool operator>(basic_iterator
const & lhs, basic_iterator
const & rhs) noexcept
395 return (lhs.shape_ >= rhs.shape_) && (lhs.text_right > rhs.text_right);
399 friend bool operator<=(basic_iterator
const & lhs, basic_iterator
const & rhs) noexcept
401 return (lhs.shape_ <= rhs.shape_) && (lhs.text_right <= rhs.text_right);
405 friend bool operator>=(basic_iterator
const & lhs, basic_iterator
const & rhs) noexcept
407 return (lhs.shape_ >= rhs.shape_) && (lhs.text_right >= rhs.text_right);
413 basic_iterator & operator++() noexcept
420 basic_iterator operator++(
int) noexcept
422 basic_iterator tmp{*
this};
430 basic_iterator & operator--() noexcept
432 requires
std::bidirectional_iterator<it_t>
442 basic_iterator operator--(
int) noexcept
444 requires std::bidirectional_iterator<it_t>
447 basic_iterator tmp{*
this};
455 basic_iterator & operator+=(difference_type
const skip) noexcept
457 requires std::random_access_iterator<it_t>
467 basic_iterator operator+(difference_type
const skip)
const noexcept
469 requires std::random_access_iterator<it_t>
472 basic_iterator tmp{*
this};
479 friend basic_iterator operator+(difference_type
const skip, basic_iterator
const & it) noexcept
481 requires std::random_access_iterator<it_t>
490 basic_iterator & operator-=(difference_type
const skip) noexcept
492 requires std::random_access_iterator<it_t>
503 basic_iterator operator-(difference_type
const skip)
const noexcept
505 requires std::random_access_iterator<it_t>
508 basic_iterator tmp{*
this};
515 friend basic_iterator operator-(difference_type
const skip, basic_iterator
const & it) noexcept
517 requires std::random_access_iterator<it_t>
527 friend difference_type operator-(basic_iterator
const & lhs, basic_iterator
const & rhs) noexcept
529 requires std::random_access_iterator<it_t>
532 return static_cast<difference_type
>(lhs.text_right - rhs.text_right);
538 friend difference_type operator-(sentinel_t
const & lhs, basic_iterator
const & rhs) noexcept
540 requires std::sized_sentinel_for<sentinel_t, it_t>
543 return static_cast<difference_type
>(lhs - rhs.text_right);
549 friend difference_type operator-(basic_iterator
const & lhs, sentinel_t
const & rhs) noexcept
551 requires std::sized_sentinel_for<it_t, sentinel_t>
554 return static_cast<difference_type
>(lhs.text_right - rhs);
560 reference operator[](difference_type
const n)
const
562 requires std::random_access_iterator<it_t>
569 value_type operator*() const noexcept
571 return hash_value +
to_rank(*text_right);
579 static constexpr
auto const sigma{alphabet_size<alphabet_t>};
582 size_t hash_value{0};
585 size_t roll_factor{0};
605 std::ranges::advance(text_left, 1);
614 void hash_forward(difference_type
const skip)
616 requires std::random_access_iterator<it_t>
619 std::ranges::advance(text_left, skip);
628 requires
std::bidirectional_iterator<it_t>
633 hash_roll_backward();
637 std::ranges::advance(text_left, -1);
646 void hash_backward(difference_type
const skip)
648 std::ranges::advance(text_left, -skip);
655 text_right = text_left;
658 for (
size_t i{0}; i < shape_.size() - 1u; ++i)
660 hash_value += shape_[i] *
to_rank(*text_right);
661 hash_value *= shape_[i] ? sigma : 1;
662 std::ranges::advance(text_right, 1);
668 void hash_roll_forward()
670 hash_value -=
to_rank(*(text_left)) * roll_factor;
671 hash_value +=
to_rank(*(text_right));
674 std::ranges::advance(text_left, 1);
675 std::ranges::advance(text_right, 1);
681 void hash_roll_backward()
683 requires
std::bidirectional_iterator<it_t>
686 std::ranges::advance(text_left, -1);
687 std::ranges::advance(text_right, -1);
690 hash_value -=
to_rank(*(text_right));
691 hash_value +=
to_rank(*(text_left)) * roll_factor;
696 template <std::ranges::viewable_range rng_t>
697 kmer_hash_view(rng_t &&, shape
const & shape_) -> kmer_hash_view<std::views::all_t<rng_t>>;
708 constexpr
auto operator()(shape
const & shape_)
const
710 return adaptor_from_functor{*
this, shape_};
720 template <std::ranges::range urng_t>
721 constexpr
auto operator()(urng_t && urange, shape
const & shape_)
const
723 static_assert(std::ranges::viewable_range<urng_t>,
724 "The range parameter to views::kmer_hash cannot be a temporary of a non-view range.");
725 static_assert(std::ranges::forward_range<urng_t>,
726 "The range parameter to views::kmer_hash must model std::ranges::forward_range.");
727 static_assert(
semialphabet<std::ranges::range_reference_t<urng_t>>,
728 "The range parameter to views::kmer_hash must be over elements of seqan3::semialphabet.");
730 return kmer_hash_view{std::forward<urng_t>(urange), shape_};
789 inline constexpr
auto kmer_hash = detail::kmer_hash_fn{};
Core alphabet concept and free function/type trait wrappers.
Provides overloads for std::hash.
constexpr auto alphabet_size
A type trait that holds the size of a (semi-)alphabet.
Definition: concept.hpp:858
constexpr auto to_rank
Return the rank representation of a (semi-)alphabet object.
Definition: concept.hpp:155
base_t pow(base_t base, exp_t exp)
Computes the value of base raised to the power exp.
Definition: math.hpp:124
constexpr size_t size
The size of a type pack.
Definition: traits.hpp:151
constexpr auto kmer_hash
Computes hash values for each position of a range via a given shape.
Definition: kmer_hash.hpp:789
auto const move
A view that turns lvalue-references into rvalue-references.
Definition: move.hpp:74
Specifies requirements of an input range type for which the const version of that type satisfies the ...
The basis for seqan3::alphabet, but requires only rank interface (not char).
The SeqAn namespace for views.
Definition: char_to.hpp:22
SeqAn specific customisations in the standard namespace.
Provides math related functionality.