38template <std::ranges::view urng_t>
39class 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");
44 "The reference type of the underlying range must model seqan3::semialphabet.");
52 template <
bool const_range>
60 requires std::default_initializable<urng_t>
77 "The alphabet or shape size must be reduced."};
85 template <
typename rng_t>
86 requires (!std::same_as<std::remove_cvref_t<rng_t>,
kmer_hash_view>) && std::ranges::viewable_range<rng_t>
95 "The alphabet or shape size must be reduced."};
146 if constexpr (std::ranges::common_range<urng_t>)
149 return std::ranges::end(
urange);
157 if constexpr (std::ranges::common_range<urng_t const>)
160 return std::ranges::cend(
urange);
168 requires std::ranges::sized_range<urng_t>
170 using size_type = std::ranges::range_size_t<urng_t>;
176 requires
std::ranges::sized_range<urng_t const>
178 using size_type = std::ranges::range_size_t<urng_t const>;
210template <std::ranges::view urng_t>
211template <
bool const_range>
221 template <
bool other_const_range>
256 hash_value{std::move(it.hash_value)},
257 roll_factor{std::move(it.roll_factor)},
258 shape_{std::move(it.shape_)},
259 text_left{std::move(it.text_left)},
260 text_right{std::move(it.text_right)}
277 text_right{
std::ranges::next(text_left,
shape_.
size() - 1, it_end)}
286 if (
shape_.
size() <= std::ranges::distance(text_left, text_right) + 1)
320 auto urange_size = std::ranges::distance(it_start, it_end);
322 text_left = std::ranges::next(it_start, step, it_end);
329 if (
shape_.
size() <= std::ranges::distance(text_left, it_end) + 1)
346 return lhs.text_right == rhs;
352 return lhs == rhs.text_right;
358 return std::tie(lhs.text_right, lhs.shape_) ==
std::tie(rhs.text_right, rhs.shape_);
364 return !(lhs == rhs);
370 return !(lhs == rhs);
376 return !(lhs == rhs);
382 return (lhs.shape_ <= rhs.shape_) && (lhs.text_right < rhs.text_right);
388 return (lhs.shape_ >= rhs.shape_) && (lhs.text_right > rhs.text_right);
394 return (lhs.shape_ <= rhs.shape_) && (lhs.text_right <= rhs.text_right);
400 return (lhs.shape_ >= rhs.shape_) && (lhs.text_right >= rhs.text_right);
424 requires
std::bidirectional_iterator<
it_t>
434 requires std::bidirectional_iterator<it_t>
445 requires std::random_access_iterator<it_t>
455 requires std::random_access_iterator<it_t>
465 requires std::random_access_iterator<it_t>
474 requires std::random_access_iterator<it_t>
485 requires std::random_access_iterator<it_t>
495 requires std::random_access_iterator<it_t>
505 requires std::sized_sentinel_for<it_t, it_t>
514 requires std::sized_sentinel_for<sentinel_t, it_t>
523 requires std::sized_sentinel_for<it_t, sentinel_t>
532 requires std::random_access_iterator<it_t>
540 return hash_value +
to_rank(*text_right);
548 static constexpr auto const sigma{alphabet_size<alphabet_t>};
551 size_t hash_value{0};
554 size_t roll_factor{0};
574 std::ranges::advance(text_left, 1);
584 requires std::random_access_iterator<it_t>
586 std::ranges::advance(text_left, skip);
594 requires std::bidirectional_iterator<
it_t>
598 hash_roll_backward();
602 std::ranges::advance(text_left, -1);
613 std::ranges::advance(text_left, -skip);
620 text_right = text_left;
623 for (
size_t i{0}; i <
shape_.
size() - 1u; ++i)
626 hash_value *=
shape_[i] ? sigma : 1;
627 std::ranges::advance(text_right, 1);
634 hash_value -=
to_rank(*(text_left)) * roll_factor;
635 hash_value +=
to_rank(*(text_right));
638 std::ranges::advance(text_left, 1);
639 std::ranges::advance(text_right, 1);
646 requires std::bidirectional_iterator<
it_t>
648 std::ranges::advance(text_left, -1);
649 std::ranges::advance(text_right, -1);
652 hash_value -=
to_rank(*(text_right));
653 hash_value +=
to_rank(*(text_left)) * roll_factor;
658template <std::ranges::viewable_range rng_t>
683 template <std::ranges::range urng_t>
686 static_assert(std::ranges::viewable_range<urng_t>,
687 "The range parameter to views::kmer_hash cannot be a temporary of a non-view range.");
688 static_assert(std::ranges::forward_range<urng_t>,
689 "The range parameter to views::kmer_hash must model std::ranges::forward_range.");
691 "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:57
Iterator for calculating hash values via a given seqan3::shape.
Definition: kmer_hash.hpp:214
friend bool operator<(basic_iterator const &lhs, basic_iterator const &rhs) noexcept
Compare to another basic_iterator.
Definition: kmer_hash.hpp:380
basic_iterator operator-(difference_type const skip) const noexcept
Return decremented copy of this iterator.
Definition: kmer_hash.hpp:484
basic_iterator & operator-=(difference_type const skip) noexcept
Decrement iterator by skip.
Definition: kmer_hash.hpp:473
constexpr basic_iterator(basic_iterator const &)=default
Defaulted.
size_t value_type
Value type of this iterator.
Definition: kmer_hash.hpp:231
void hash_backward()
Decrements iterator by 1.
Definition: kmer_hash.hpp:593
friend bool operator==(sentinel_t const &lhs, basic_iterator const &rhs) noexcept
Compare to iterator on text.
Definition: kmer_hash.hpp:350
basic_iterator & operator++() noexcept
Pre-increment.
Definition: kmer_hash.hpp:406
shape shape_
The shape to use.
Definition: kmer_hash.hpp:557
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:316
friend bool operator>=(basic_iterator const &lhs, basic_iterator const &rhs) noexcept
Compare to another basic_iterator.
Definition: kmer_hash.hpp:398
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:274
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:253
maybe_const_sentinel_t< const_range, urng_t > sentinel_t
The sentinel type of the underlying range.
Definition: kmer_hash.hpp:219
friend bool operator<=(basic_iterator const &lhs, basic_iterator const &rhs) noexcept
Compare to another basic_iterator.
Definition: kmer_hash.hpp:392
friend bool operator!=(basic_iterator const &lhs, sentinel_t const &rhs) noexcept
Compare to iterator on text.
Definition: kmer_hash.hpp:362
friend bool operator==(basic_iterator const &lhs, sentinel_t const &rhs) noexcept
Compare to iterator on text.
Definition: kmer_hash.hpp:344
value_type operator*() const noexcept
Return the hash value.
Definition: kmer_hash.hpp:538
friend bool operator>(basic_iterator const &lhs, basic_iterator const &rhs) noexcept
Compare to another basic_iterator.
Definition: kmer_hash.hpp:386
value_type reference
Reference to value_type.
Definition: kmer_hash.hpp:235
friend difference_type operator-(basic_iterator const &lhs, basic_iterator const &rhs) noexcept
Return offset between two iterator's positions.
Definition: kmer_hash.hpp:504
void pointer
The pointer type.
Definition: kmer_hash.hpp:233
basic_iterator operator--(int) noexcept
Post-decrement.
Definition: kmer_hash.hpp:433
reference operator[](difference_type const n) const
Move the iterator by a given offset and return the corresponding hash value.
Definition: kmer_hash.hpp:531
void hash_forward()
Increments iterator by 1.
Definition: kmer_hash.hpp:566
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:494
basic_iterator & operator+=(difference_type const skip) noexcept
Forward this iterator.
Definition: kmer_hash.hpp:444
it_t text_left
Iterator to the leftmost position of the k-mer.
Definition: kmer_hash.hpp:560
friend bool operator!=(sentinel_t const &lhs, basic_iterator const &rhs) noexcept
Compare to iterator on text.
Definition: kmer_hash.hpp:368
friend bool operator==(basic_iterator const &lhs, basic_iterator const &rhs) noexcept
Compare to another basic_iterator.
Definition: kmer_hash.hpp:356
typename std::iter_difference_t< it_t > difference_type
Type for distances between iterators.
Definition: kmer_hash.hpp:229
void hash_backward(difference_type const skip)
Decrements iterator by skip.
Definition: kmer_hash.hpp:611
void hash_full()
Calculates a hash value by explicitly looking at each position.
Definition: kmer_hash.hpp:618
basic_iterator operator+(difference_type const skip) const noexcept
Forward copy of this iterator.
Definition: kmer_hash.hpp:454
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:464
void hash_roll_forward()
Calculates the next hash value via rolling hash.
Definition: kmer_hash.hpp:632
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:522
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:513
constexpr basic_iterator()=default
Defaulted.
basic_iterator & operator--() noexcept
Pre-decrement.
Definition: kmer_hash.hpp:423
it_t text_right
Iterator to the rightmost position of the k-mer.
Definition: kmer_hash.hpp:563
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:217
void hash_roll_backward()
Calculates the previous hash value via rolling hash.
Definition: kmer_hash.hpp:645
void hash_forward(difference_type const skip)
Increments iterator by skip.
Definition: kmer_hash.hpp:583
~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:374
basic_iterator operator++(int) noexcept
Post-increment.
Definition: kmer_hash.hpp:413
constexpr basic_iterator & operator=(basic_iterator const &)=default
Defaulted.
The type returned by seqan3::views::kmer_hash.
Definition: kmer_hash.hpp:40
auto end() const noexcept
Returns an iterator to the element following the last element of the range.
Definition: kmer_hash.hpp:153
auto end() noexcept
Returns an iterator to the element following the last element of the range.
Definition: kmer_hash.hpp:143
auto begin() noexcept
Returns an iterator to the first element of the range.
Definition: kmer_hash.hpp:116
urng_t urange
The underlying range.
Definition: kmer_hash.hpp:47
auto begin() const noexcept
Returns an iterator to the first element of the range.
Definition: kmer_hash.hpp:122
kmer_hash_view()=default
Defaulted.
shape shape_
The shape to use.
Definition: kmer_hash.hpp:50
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:88
auto size() const
Returns the size of the range, if the underlying range is a std::ranges::sized_range.
Definition: kmer_hash.hpp:175
auto size()
Returns the size of the range, if the underlying range is a std::ranges::sized_range.
Definition: kmer_hash.hpp:167
constexpr size_type size() const noexcept
Returns the number of elements in the container, i.e. std::distance(begin(), end()).
Definition: dynamic_bitset.hpp:1233
constexpr size_type count() const noexcept
Returns the number of set bits.
Definition: dynamic_bitset.hpp:1037
constexpr bool all() const noexcept
Checks if all bit are set.
Definition: dynamic_bitset.hpp:1008
A class that defines which positions of a pattern to hash.
Definition: shape.hpp:60
constexpr auto alphabet_size
A type trait that holds the size of a (semi-)alphabet.
Definition: alphabet/concept.hpp:849
constexpr auto to_rank
Return the rank representation of a (semi-)alphabet object.
Definition: alphabet/concept.hpp:155
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:49
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:44
constexpr auto all
Returns a view that includes all elements of the range argument.
Definition: all_view.hpp:204
constexpr auto kmer_hash
Computes hash values for each position of a range via a given shape.
Definition: kmer_hash.hpp:750
constexpr size_t size
The size of a type pack.
Definition: type_pack/traits.hpp:146
base_t pow(base_t base, exp_t exp)
Computes the value of base raised to the power exp.
Definition: math.hpp:122
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:29
kmer_hash_view(rng_t &&, shape const &shape_) -> kmer_hash_view< std::views::all_t< rng_t > >
A deduction guide for the view class template.
The SeqAn namespace for views.
Definition: char_strictly_to.hpp:22
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:669
constexpr auto operator()(shape const &shape_) const
Store the shape and return a range adaptor closure object.
Definition: kmer_hash.hpp:671
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:684
Defines iterator_category member if underlying_iterator_t has a valid std::iterator_traits::iterator_...
Definition: iterator_traits.hpp:42