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 <
typename rng_t>
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<urng_t>{
std::ranges::begin(urange), std::ranges::end(urange), shape_};
122 auto begin() const noexcept
127 return basic_iterator<urng_t const>{
std::ranges::cbegin(urange), std::ranges::cend(urange), shape_};
148 if constexpr (std::ranges::common_range<urng_t>)
149 return basic_iterator<urng_t>{
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<urng_t const>{
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();
216 template <std::ranges::view urng_t>
217 template <
typename rng_t>
218 class kmer_hash_view<urng_t>::basic_iterator
222 using it_t = std::ranges::iterator_t<rng_t>;
224 using sentinel_t = std::ranges::sentinel_t<rng_t>;
226 template <
typename urng2_t>
227 friend class basic_iterator;
236 using value_type = size_t;
238 using pointer = void;
240 using reference = value_type;
242 using iterator_category = detail::iterator_category_tag_t<it_t>;
246 detail::iterator_concept_tag_t<it_t>>;
252 constexpr basic_iterator() =
default;
253 constexpr basic_iterator(basic_iterator
const &) =
default;
254 constexpr basic_iterator(basic_iterator &&) =
default;
255 constexpr basic_iterator & operator=(basic_iterator
const &) =
default;
256 constexpr basic_iterator & operator=(basic_iterator &&) =
default;
257 ~basic_iterator() =
default;
260 template <
typename urng2_t>
262 requires std::same_as<std::remove_const_t<urng_t>, urng2_t>
264 basic_iterator(basic_iterator<urng2_t> it) :
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() + 1 > urange_size) ? 0 : urange_size - shape_.size() + 1;
329 text_left = std::ranges::next(it_start, step, it_end);
337 if (shape_.size() <= std::ranges::distance(text_left, text_right) + 1)
352 friend bool operator==(basic_iterator
const & lhs, sentinel_t
const & rhs) noexcept
354 return lhs.text_right == rhs;
358 friend bool operator==(sentinel_t
const & lhs, basic_iterator
const & rhs) noexcept
360 return lhs == rhs.text_right;
364 friend bool operator==(basic_iterator
const & lhs, basic_iterator
const & rhs) noexcept
366 return std::tie(lhs.text_right, lhs.shape_) ==
std::tie(rhs.text_right, rhs.shape_);
370 friend bool operator!=(basic_iterator
const & lhs, sentinel_t
const & rhs) noexcept
372 return !(lhs == rhs);
376 friend bool operator!=(sentinel_t
const & lhs, basic_iterator
const & rhs) noexcept
378 return !(lhs == rhs);
382 friend bool operator!=(basic_iterator
const & lhs, basic_iterator
const & rhs) noexcept
384 return !(lhs == rhs);
388 friend bool operator<(basic_iterator
const & lhs, basic_iterator
const & rhs) noexcept
390 return (lhs.shape_ <= rhs.shape_) && (lhs.text_right < rhs.text_right);
394 friend bool operator>(basic_iterator
const & lhs, basic_iterator
const & rhs) noexcept
396 return (lhs.shape_ >= rhs.shape_) && (lhs.text_right > rhs.text_right);
400 friend bool operator<=(basic_iterator
const & lhs, basic_iterator
const & rhs) noexcept
402 return (lhs.shape_ <= rhs.shape_) && (lhs.text_right <= rhs.text_right);
406 friend bool operator>=(basic_iterator
const & lhs, basic_iterator
const & rhs) noexcept
408 return (lhs.shape_ >= rhs.shape_) && (lhs.text_right >= rhs.text_right);
414 basic_iterator & operator++() noexcept
421 basic_iterator operator++(
int) noexcept
423 basic_iterator tmp{*
this};
431 basic_iterator & operator--() noexcept
433 requires
std::bidirectional_iterator<it_t>
443 basic_iterator operator--(
int) noexcept
445 requires std::bidirectional_iterator<it_t>
448 basic_iterator tmp{*
this};
456 basic_iterator & operator+=(difference_type
const skip) noexcept
458 requires std::random_access_iterator<it_t>
468 basic_iterator operator+(difference_type
const skip)
const noexcept
470 requires std::random_access_iterator<it_t>
473 basic_iterator tmp{*
this};
480 friend basic_iterator operator+(difference_type
const skip, basic_iterator
const & it) noexcept
482 requires std::random_access_iterator<it_t>
491 basic_iterator & operator-=(difference_type
const skip) noexcept
493 requires std::random_access_iterator<it_t>
504 basic_iterator operator-(difference_type
const skip)
const noexcept
506 requires std::random_access_iterator<it_t>
509 basic_iterator tmp{*
this};
516 friend basic_iterator operator-(difference_type
const skip, basic_iterator
const & it) noexcept
518 requires std::random_access_iterator<it_t>
528 friend difference_type operator-(basic_iterator
const & lhs, basic_iterator
const & rhs) noexcept
530 requires std::random_access_iterator<it_t>
533 return static_cast<difference_type
>(lhs.text_right - rhs.text_right);
539 friend difference_type operator-(sentinel_t
const & lhs, basic_iterator
const & rhs) noexcept
541 requires std::sized_sentinel_for<sentinel_t, it_t>
544 return static_cast<difference_type
>(lhs - rhs.text_right);
550 friend difference_type operator-(basic_iterator
const & lhs, sentinel_t
const & rhs) noexcept
552 requires std::sized_sentinel_for<it_t, sentinel_t>
555 return static_cast<difference_type
>(lhs.text_right - rhs);
561 reference operator[](difference_type
const n)
const
563 requires std::random_access_iterator<it_t>
570 value_type operator*() const noexcept
572 return hash_value +
to_rank(*text_right);
580 static constexpr
auto const sigma{alphabet_size<alphabet_t>};
583 size_t hash_value{0};
586 size_t roll_factor{0};
606 std::ranges::advance(text_left, 1);
615 void hash_forward(difference_type
const skip)
617 requires std::random_access_iterator<it_t>
620 std::ranges::advance(text_left, skip);
629 requires
std::bidirectional_iterator<it_t>
634 hash_roll_backward();
638 std::ranges::advance(text_left, -1);
647 void hash_backward(difference_type
const skip)
649 std::ranges::advance(text_left, -skip);
656 text_right = text_left;
659 for (
size_t i{0}; i < shape_.size() - 1u; ++i)
661 hash_value += shape_[i] *
to_rank(*text_right);
662 hash_value *= shape_[i] ? sigma : 1;
663 std::ranges::advance(text_right, 1);
669 void hash_roll_forward()
671 hash_value -=
to_rank(*(text_left)) * roll_factor;
672 hash_value +=
to_rank(*(text_right));
675 std::ranges::advance(text_left, 1);
676 std::ranges::advance(text_right, 1);
682 void hash_roll_backward()
684 requires
std::bidirectional_iterator<it_t>
687 std::ranges::advance(text_left, -1);
688 std::ranges::advance(text_right, -1);
691 hash_value -=
to_rank(*(text_right));
692 hash_value +=
to_rank(*(text_left)) * roll_factor;
697 template <std::ranges::viewable_range rng_t>
698 kmer_hash_view(rng_t &&, shape
const & shape_) -> kmer_hash_view<std::views::all_t<rng_t>>;
709 constexpr
auto operator()(shape
const & shape_)
const
711 return adaptor_from_functor{*
this, shape_};
721 template <std::ranges::range urng_t>
722 constexpr
auto operator()(urng_t && urange, shape
const & shape_)
const
724 static_assert(std::ranges::viewable_range<urng_t>,
725 "The range parameter to views::kmer_hash cannot be a temporary of a non-view range.");
726 static_assert(std::ranges::forward_range<urng_t>,
727 "The range parameter to views::kmer_hash must model std::ranges::forward_range.");
728 static_assert(
semialphabet<std::ranges::range_reference_t<urng_t>>,
729 "The range parameter to views::kmer_hash must be over elements of seqan3::semialphabet.");
731 return kmer_hash_view{std::forward<urng_t>(urange), shape_};
788 inline constexpr
auto kmer_hash = detail::kmer_hash_fn{};