35template <std::ranges::view urng_t>
36class kmer_hash_view :
public std::ranges::view_interface<kmer_hash_view<urng_t>>
39 static_assert(std::ranges::forward_range<urng_t>,
"The kmer_hash_view only works on forward_ranges");
41 "The reference type of the underlying range must model seqan3::semialphabet.");
49 template <
bool const_range>
58 std::string message{
"The shape is too long for the given alphabet.\n"};
59 message +=
"Alphabet: ";
64 message += detail::type_name_as_string<std::remove_cvref_t<std::ranges::range_value_t<urng_t>>>;
65 message +=
"\nMaximum shape count: ";
67 message +=
"\nGiven shape count: ";
84 requires std::default_initializable<urng_t>
105 template <
typename rng_t>
106 requires (!std::same_as<std::remove_cvref_t<rng_t>,
kmer_hash_view>) && std::ranges::viewable_range<rng_t>
109 urange{std::views::all(std::forward<rng_t>(urange_))},
162 if constexpr (std::ranges::common_range<urng_t>)
165 return std::ranges::end(
urange);
173 if constexpr (std::ranges::common_range<urng_t const>)
176 return std::ranges::cend(
urange);
184 requires std::ranges::sized_range<urng_t>
186 using size_type = std::ranges::range_size_t<urng_t>;
192 requires
std::ranges::sized_range<urng_t const>
194 using size_type = std::ranges::range_size_t<urng_t const>;
226template <std::ranges::view urng_t>
227template <
bool const_range>
237 template <
bool other_const_range>
272 hash_value{std::move(it.hash_value)},
273 roll_factor{std::move(it.roll_factor)},
274 shape_{std::move(it.shape_)},
275 text_left{std::move(it.text_left)},
276 text_right{std::move(it.text_right)}
293 text_right{
std::ranges::next(text_left,
shape_.
size() - 1, it_end)}
295 assert(std::ranges::size(
shape_) > 0);
302 if (
shape_.
size() <= std::ranges::distance(text_left, text_right) + 1)
304 roll_factor =
pow(sigma,
static_cast<size_t>(std::ranges::size(
shape_) - 1));
334 assert(std::ranges::size(
shape_) > 0);
336 auto urange_size = std::ranges::distance(it_start, it_end);
338 text_left = std::ranges::next(it_start, step, it_end);
345 if (
shape_.
size() <= std::ranges::distance(text_left, it_end) + 1)
347 roll_factor =
pow(sigma,
static_cast<size_t>(std::ranges::size(
shape_) - 1));
362 return lhs.text_right == rhs;
368 return lhs == rhs.text_right;
374 return std::tie(lhs.text_right, lhs.shape_) ==
std::tie(rhs.text_right, rhs.shape_);
380 return !(lhs == rhs);
386 return !(lhs == rhs);
392 return !(lhs == rhs);
398 return (lhs.shape_ <= rhs.shape_) && (lhs.text_right < rhs.text_right);
404 return (lhs.shape_ >= rhs.shape_) && (lhs.text_right > rhs.text_right);
410 return (lhs.shape_ <= rhs.shape_) && (lhs.text_right <= rhs.text_right);
416 return (lhs.shape_ >= rhs.shape_) && (lhs.text_right >= rhs.text_right);
440 requires
std::bidirectional_iterator<
it_t>
450 requires std::bidirectional_iterator<it_t>
461 requires std::random_access_iterator<it_t>
471 requires std::random_access_iterator<it_t>
481 requires std::random_access_iterator<it_t>
490 requires std::random_access_iterator<it_t>
501 requires std::random_access_iterator<it_t>
511 requires std::random_access_iterator<it_t>
521 requires std::sized_sentinel_for<it_t, it_t>
530 requires std::sized_sentinel_for<sentinel_t, it_t>
539 requires std::sized_sentinel_for<it_t, sentinel_t>
548 requires std::random_access_iterator<it_t>
556 return hash_value +
to_rank(*text_right);
564 static constexpr auto const sigma{alphabet_size<alphabet_t>};
567 size_t hash_value{0};
570 size_t roll_factor{0};
590 std::ranges::advance(text_left, 1);
600 requires std::random_access_iterator<it_t>
602 std::ranges::advance(text_left, skip);
610 requires std::bidirectional_iterator<
it_t>
614 hash_roll_backward();
618 std::ranges::advance(text_left, -1);
629 std::ranges::advance(text_left, -skip);
636 text_right = text_left;
639 for (
size_t i{0}; i <
shape_.
size() - 1u; ++i)
642 hash_value *=
shape_[i] ? sigma : 1;
643 std::ranges::advance(text_right, 1);
650 hash_value -=
to_rank(*(text_left)) * roll_factor;
651 hash_value +=
to_rank(*(text_right));
654 std::ranges::advance(text_left, 1);
655 std::ranges::advance(text_right, 1);
662 requires std::bidirectional_iterator<
it_t>
664 std::ranges::advance(text_left, -1);
665 std::ranges::advance(text_right, -1);
668 hash_value -=
to_rank(*(text_right));
669 hash_value +=
to_rank(*(text_left)) * roll_factor;
674template <std::ranges::viewable_range rng_t>
699 template <std::ranges::range urng_t>
702 static_assert(std::ranges::viewable_range<urng_t>,
703 "The range parameter to views::kmer_hash cannot be a temporary of a non-view range.");
704 static_assert(std::ranges::forward_range<urng_t>,
705 "The range parameter to views::kmer_hash must model std::ranges::forward_range.");
707 "The range parameter to views::kmer_hash must be over elements of seqan3::semialphabet.");
Core alphabet concept and free function/type trait wrappers.
Template for range adaptor closure objects that store arguments and wrap a proto-adaptor.
Definition adaptor_from_functor.hpp:54
Iterator for calculating hash values via a given seqan3::shape.
Definition kmer_hash.hpp:230
friend bool operator<(basic_iterator const &lhs, basic_iterator const &rhs) noexcept
Compare to another basic_iterator.
Definition kmer_hash.hpp:396
basic_iterator operator-(difference_type const skip) const noexcept
Return decremented copy of this iterator.
Definition kmer_hash.hpp:500
basic_iterator & operator-=(difference_type const skip) noexcept
Decrement iterator by skip.
Definition kmer_hash.hpp:489
constexpr basic_iterator(basic_iterator const &)=default
Defaulted.
size_t value_type
Value type of this iterator.
Definition kmer_hash.hpp:247
void hash_backward()
Decrements iterator by 1.
Definition kmer_hash.hpp:609
friend bool operator==(sentinel_t const &lhs, basic_iterator const &rhs) noexcept
Compare to iterator on text.
Definition kmer_hash.hpp:366
basic_iterator & operator++() noexcept
Pre-increment.
Definition kmer_hash.hpp:422
shape shape_
The shape to use.
Definition kmer_hash.hpp:573
basic_iterator(it_t it_start, sentinel_t it_end, shape s_, bool is_end)
Construct from a given iterator on the text and a seqan3::shape. /param[in] it_start Iterator pointin...
Definition kmer_hash.hpp:332
friend bool operator>=(basic_iterator const &lhs, basic_iterator const &rhs) noexcept
Compare to another basic_iterator.
Definition kmer_hash.hpp:414
basic_iterator(it_t it_start, sentinel_t it_end, shape s_)
Construct from a given iterator on the text and a seqan3::shape. /param[in] it_start Iterator pointin...
Definition kmer_hash.hpp:290
constexpr basic_iterator(basic_iterator<!const_range > const &it) noexcept
Allow iterator on a const range to be constructible from an iterator over a non-const range.
Definition kmer_hash.hpp:269
maybe_const_sentinel_t< const_range, urng_t > sentinel_t
The sentinel type of the underlying range.
Definition kmer_hash.hpp:235
friend bool operator<=(basic_iterator const &lhs, basic_iterator const &rhs) noexcept
Compare to another basic_iterator.
Definition kmer_hash.hpp:408
friend bool operator!=(basic_iterator const &lhs, sentinel_t const &rhs) noexcept
Compare to iterator on text.
Definition kmer_hash.hpp:378
friend bool operator==(basic_iterator const &lhs, sentinel_t const &rhs) noexcept
Compare to iterator on text.
Definition kmer_hash.hpp:360
value_type operator*() const noexcept
Return the hash value.
Definition kmer_hash.hpp:554
friend bool operator>(basic_iterator const &lhs, basic_iterator const &rhs) noexcept
Compare to another basic_iterator.
Definition kmer_hash.hpp:402
value_type reference
Reference to value_type.
Definition kmer_hash.hpp:251
friend difference_type operator-(basic_iterator const &lhs, basic_iterator const &rhs) noexcept
Return offset between two iterator's positions.
Definition kmer_hash.hpp:520
void pointer
The pointer type.
Definition kmer_hash.hpp:249
basic_iterator operator--(int) noexcept
Post-decrement.
Definition kmer_hash.hpp:449
reference operator[](difference_type const n) const
Move the iterator by a given offset and return the corresponding hash value.
Definition kmer_hash.hpp:547
void hash_forward()
Increments iterator by 1.
Definition kmer_hash.hpp:582
constexpr basic_iterator(basic_iterator &&)=default
Defaulted.
friend basic_iterator operator-(difference_type const skip, basic_iterator const &it) noexcept
Non-member operator- delegates to non-friend operator-.
Definition kmer_hash.hpp:510
basic_iterator & operator+=(difference_type const skip) noexcept
Forward this iterator.
Definition kmer_hash.hpp:460
it_t text_left
Iterator to the leftmost position of the k-mer.
Definition kmer_hash.hpp:576
friend bool operator!=(sentinel_t const &lhs, basic_iterator const &rhs) noexcept
Compare to iterator on text.
Definition kmer_hash.hpp:384
friend bool operator==(basic_iterator const &lhs, basic_iterator const &rhs) noexcept
Compare to another basic_iterator.
Definition kmer_hash.hpp:372
typename std::iter_difference_t< it_t > difference_type
Type for distances between iterators.
Definition kmer_hash.hpp:245
void hash_backward(difference_type const skip)
Decrements iterator by skip.
Definition kmer_hash.hpp:627
void hash_full()
Calculates a hash value by explicitly looking at each position.
Definition kmer_hash.hpp:634
basic_iterator operator+(difference_type const skip) const noexcept
Forward copy of this iterator.
Definition kmer_hash.hpp:470
friend basic_iterator operator+(difference_type const skip, basic_iterator const &it) noexcept
Non-member operator+ delegates to non-friend operator+.
Definition kmer_hash.hpp:480
void hash_roll_forward()
Calculates the next hash value via rolling hash.
Definition kmer_hash.hpp:648
friend difference_type operator-(basic_iterator const &lhs, sentinel_t const &rhs) noexcept
Return offset this and remote sentinel's position.
Definition kmer_hash.hpp:538
friend difference_type operator-(sentinel_t const &lhs, basic_iterator const &rhs) noexcept
Return offset between remote sentinel's position and this.
Definition kmer_hash.hpp:529
constexpr basic_iterator()=default
Defaulted.
basic_iterator & operator--() noexcept
Pre-decrement.
Definition kmer_hash.hpp:439
it_t text_right
Iterator to the rightmost position of the k-mer.
Definition kmer_hash.hpp:579
constexpr basic_iterator & operator=(basic_iterator &&)=default
Defaulted.
maybe_const_iterator_t< const_range, urng_t > it_t
The iterator type of the underlying range.
Definition kmer_hash.hpp:233
void hash_roll_backward()
Calculates the previous hash value via rolling hash.
Definition kmer_hash.hpp:661
void hash_forward(difference_type const skip)
Increments iterator by skip.
Definition kmer_hash.hpp:599
~basic_iterator()=default
Defaulted.
friend bool operator!=(basic_iterator const &lhs, basic_iterator const &rhs) noexcept
Compare to another basic_iterator.
Definition kmer_hash.hpp:390
basic_iterator operator++(int) noexcept
Post-increment.
Definition kmer_hash.hpp:429
constexpr basic_iterator & operator=(basic_iterator const &)=default
Defaulted.
The type returned by seqan3::views::kmer_hash.
Definition kmer_hash.hpp:37
auto end() const noexcept
Returns an iterator to the element following the last element of the range.
Definition kmer_hash.hpp:169
auto end() noexcept
Returns an iterator to the element following the last element of the range.
Definition kmer_hash.hpp:159
auto begin() noexcept
Returns an iterator to the first element of the range.
Definition kmer_hash.hpp:132
void shape_too_long_error() const
Throws the exception for validate_shape().
Definition kmer_hash.hpp:56
urng_t urange
The underlying range.
Definition kmer_hash.hpp:44
auto begin() const noexcept
Returns an iterator to the first element of the range.
Definition kmer_hash.hpp:138
kmer_hash_view()=default
Defaulted.
shape shape_
The shape to use.
Definition kmer_hash.hpp:47
void validate_shape() const
Checks that the shape is not too long for the given alphabet.
Definition kmer_hash.hpp:73
kmer_hash_view(rng_t &&urange_, shape const &s_)
Construct from a non-view that can be view-wrapped and a given shape.
Definition kmer_hash.hpp:108
auto size() const
Returns the size of the range, if the underlying range is a std::ranges::sized_range.
Definition kmer_hash.hpp:191
auto size()
Returns the size of the range, if the underlying range is a std::ranges::sized_range.
Definition kmer_hash.hpp:183
static int max_shape_count
The maximum shape count for the given alphabet.
Definition kmer_hash.hpp:53
constexpr size_type size() const noexcept
Returns the number of elements in the container, i.e. std::distance(begin(), end()).
Definition dynamic_bitset.hpp:1230
constexpr size_type count() const noexcept
Returns the number of set bits.
Definition dynamic_bitset.hpp:1034
constexpr bool all() const noexcept
Checks if all bit are set.
Definition dynamic_bitset.hpp:1005
A class that defines which positions of a pattern to hash.
Definition shape.hpp:57
constexpr auto alphabet_size
A type trait that holds the size of a (semi-)alphabet.
Definition alphabet/concept.hpp:846
constexpr auto to_rank
Return the rank representation of a (semi-)alphabet object.
Definition alphabet/concept.hpp:152
std::ranges::sentinel_t< maybe_const_range_t< const_v, range_t > > maybe_const_sentinel_t
Returns the const sentinel of range_t if const_range is true; otherwise the non-const sentinel.
Definition core/range/type_traits.hpp:46
std::ranges::iterator_t< maybe_const_range_t< const_range, range_t > > maybe_const_iterator_t
Returns the const iterator of range_t if const_range is true; otherwise the non-const iterator.
Definition core/range/type_traits.hpp:41
constexpr auto kmer_hash
Computes hash values for each position of a range via a given shape.
Definition kmer_hash.hpp:766
base_t pow(base_t base, exp_t exp)
Computes the value of base raised to the power exp.
Definition math.hpp:119
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).
Provides math related functionality.
The internal SeqAn3 namespace.
Definition aligned_sequence_concept.hpp:26
The SeqAn namespace for views.
Definition char_strictly_to.hpp:19
SeqAn specific customisations in the standard namespace.
Provides overloads for std::hash.
views::kmer_hash's range adaptor object type (non-closure).
Definition kmer_hash.hpp:685
constexpr auto operator()(shape const &shape_) const
Store the shape and return a range adaptor closure object.
Definition kmer_hash.hpp:687
constexpr auto operator()(urng_t &&urange, shape const &shape_) const
Call the view's constructor with the underlying view and a seqan3::shape as argument.
Definition kmer_hash.hpp:700
Defines iterator_category member if underlying_iterator_t has a valid std::iterator_traits::iterator_...
Definition iterator_traits.hpp:39