SeqAn3  3.2.0-rc.1
The Modern C++ library for sequence analysis.
bi_fm_index_cursor.hpp
Go to the documentation of this file.
1 // -----------------------------------------------------------------------------------------------------
2 // Copyright (c) 2006-2022, Knut Reinert & Freie Universität Berlin
3 // Copyright (c) 2016-2022, Knut Reinert & MPI für molekulare Genetik
4 // This file may be used, modified and/or redistributed under the terms of the 3-clause BSD-License
5 // shipped with this file and also available at: https://github.com/seqan/seqan3/blob/master/LICENSE.md
6 // -----------------------------------------------------------------------------------------------------
7 
13 #pragma once
14 
15 #include <array>
16 #include <ranges>
17 
18 #include <sdsl/suffix_trees.hpp>
19 
27 
28 namespace seqan3
29 {
30 
53 template <typename index_t>
55 {
56 public:
58  using index_type = index_t;
59 
64  using size_type = typename index_type::size_type;
66 
71  using fwd_cursor = fm_index_cursor<fm_index<typename index_type::alphabet_type,
72  index_type::text_layout_mode,
73  typename index_type::sdsl_index_type>>;
75 
76 private:
78  using sdsl_char_type = typename index_type::sdsl_char_type;
80  using sdsl_index_type = typename index_t::sdsl_index_type;
82  using sdsl_sigma_type = typename index_type::sdsl_sigma_type;
84  using index_alphabet_type = typename index_t::alphabet_type;
89 
91  index_type const * index{nullptr};
92 
97  size_type fwd_lb{};
99  size_type fwd_rb{};
101  size_type rev_lb{};
103  size_type rev_rb{};
104  //\}
105 
107  sdsl_sigma_type sigma{};
108 
115  // parent_* and _last_char only have to be stored for the (unidirectional) cursor that has been used last for
116  // extend_right() or cycle_back() resp. extend_left() or cycle_front(), (i.e. either fwd or rev). Thus there is no
117  // need to store it twice. Once the cursor is switched, the information becomes invalid anyway.
118 
120  size_type parent_lb{};
122  size_type parent_rb{};
124  sdsl_char_type _last_char{};
125  //\}
126 
128  size_type depth{}; // equal for both cursors. only stored once
129 
130  // supports assertions to check whether cycle_back() resp. cycle_front() is called on the same direction as the last
131  // extend_right([...]) resp. extend_left([...])
132 #ifndef NDEBUG
134  // cycle_back() and cycle_front()
135  bool fwd_cursor_last_used = false;
136 #endif
137 
139  size_type offset() const noexcept
140  {
141  assert(index->size() > query_length());
142  return index->size() - query_length() - 1; // since the string is reversed during construction
143  }
144 
146  template <typename csa_t>
147  requires (std::same_as<csa_t, typename index_type::sdsl_index_type>
148  || std::same_as<csa_t, typename index_type::rev_sdsl_index_type>) bool
149  bidirectional_search(csa_t const & csa,
150  sdsl_char_type const c,
151  size_type & l_fwd,
152  size_type & r_fwd,
153  size_type & l_bwd,
154  size_type & r_bwd) const noexcept
155  {
156  assert((l_fwd <= r_fwd) && (r_fwd < csa.size()));
157  assert(r_fwd + 1 >= l_fwd);
158  assert(r_bwd + 1 - l_bwd == r_fwd + 1 - l_fwd);
159 
160  size_type _l_fwd, _r_fwd, _l_bwd, _r_bwd;
161 
162  size_type cc = c;
163  if constexpr (!std::same_as<index_alphabet_type, sdsl::plain_byte_alphabet>)
164  {
165  cc = csa.char2comp[c];
166  if (cc == 0 && c > 0) // [[unlikely]]
167  return false;
168  }
169 
170  size_type const c_begin = csa.C[cc];
171  if (r_fwd + 1 - l_fwd == csa.size()) // [[unlikely]]
172  {
173  _l_fwd = c_begin;
174  _l_bwd = c_begin;
175  _r_fwd = csa.C[cc + 1] - 1;
176  _r_bwd = _r_fwd;
177  // if we use not the plain_byte_alphabet, we could return always return true here
178  }
179  else
180  {
181  auto const r_s_b = csa.wavelet_tree.lex_count(l_fwd, r_fwd + 1, c);
182  size_type const rank_l = std::get<0>(r_s_b);
183  size_type const s = std::get<1>(r_s_b), b = std::get<2>(r_s_b);
184  size_type const rank_r = r_fwd - l_fwd - s - b + rank_l;
185  _l_fwd = c_begin + rank_l;
186  _r_fwd = c_begin + rank_r;
187  _l_bwd = l_bwd + s;
188  _r_bwd = r_bwd - b;
189  }
190 
191  if (_r_fwd >= _l_fwd)
192  {
193  l_fwd = _l_fwd;
194  r_fwd = _r_fwd;
195  l_bwd = _l_bwd;
196  r_bwd = _r_bwd;
197  assert(r_fwd + 1 >= l_fwd);
198  assert(r_bwd + 1 - l_bwd == r_fwd + 1 - l_fwd);
199  return true;
200  }
201  return false;
202  }
203 
205  template <typename csa_t>
206  requires (std::same_as<csa_t, typename index_type::sdsl_index_type>
207  || std::same_as<csa_t, typename index_type::rev_sdsl_index_type>) bool
208  bidirectional_search_cycle(csa_t const & csa,
209  sdsl_char_type const c,
210  size_type const l_parent,
211  size_type const r_parent,
212  size_type & l_fwd,
213  size_type & r_fwd,
214  size_type & l_bwd,
215  size_type & r_bwd) const noexcept
216  {
217  assert((l_parent <= r_parent) && (r_parent < csa.size()));
218 
219  size_type c_begin;
220  if constexpr (std::same_as<index_alphabet_type, sdsl::plain_byte_alphabet>)
221  c_begin = csa.C[c]; // TODO: check whether this can be removed
222  else
223  c_begin = csa.C[csa.char2comp[c]];
224 
225  auto const r_s_b = csa.wavelet_tree.lex_count(l_parent, r_parent + 1, c);
226  size_type const s = std::get<1>(r_s_b), b = std::get<2>(r_s_b), rank_l = std::get<0>(r_s_b),
227  rank_r = r_parent - l_parent - s - b + rank_l;
228 
229  size_type const _l_fwd = c_begin + rank_l;
230  size_type const _r_fwd = c_begin + rank_r;
231  size_type const _l_bwd = r_bwd + 1;
232  size_type const _r_bwd = r_bwd + 1 + rank_r - rank_l;
233 
234  if (_r_fwd >= _l_fwd)
235  {
236  l_fwd = _l_fwd;
237  r_fwd = _r_fwd;
238  l_bwd = _l_bwd;
239  r_bwd = _r_bwd;
240  assert(r_fwd + 1 >= l_fwd);
241  assert(r_bwd + 1 - l_bwd == r_fwd + 1 - l_fwd);
242  return true;
243  }
244  return false;
245  }
246 
247 public:
252  // Default construction is necessary to make this class semi-regular and e.g., to allow construction of
253  // std::array of cursors.
254  bi_fm_index_cursor() noexcept = default;
255  bi_fm_index_cursor(bi_fm_index_cursor const &) noexcept = default;
256  bi_fm_index_cursor & operator=(bi_fm_index_cursor const &) noexcept = default;
257  bi_fm_index_cursor(bi_fm_index_cursor &&) noexcept = default;
258  bi_fm_index_cursor & operator=(bi_fm_index_cursor &&) noexcept = default;
259  ~bi_fm_index_cursor() = default;
260 
262  bi_fm_index_cursor(index_t const & _index) noexcept :
263  index(&_index),
264  fwd_lb(0),
265  fwd_rb(_index.size() - 1),
266  rev_lb(0),
267  rev_rb(_index.size() - 1),
268  sigma(_index.fwd_fm.index.sigma - index_t::text_layout_mode),
269  depth(0)
270  {}
271  //\}
272 
285  bool operator==(bi_fm_index_cursor const & rhs) const noexcept
286  {
287  assert(index != nullptr);
288  // equal SA interval implies equal parent node information (or both are root nodes)
289  assert(!(fwd_lb == rhs.fwd_lb && fwd_rb == rhs.fwd_rb && depth == rhs.depth) || (depth == 0)
290  || (parent_lb == rhs.parent_lb && parent_rb == rhs.parent_rb && _last_char == rhs._last_char));
291 
292  return std::tie(fwd_lb, fwd_rb, depth) == std::tie(rhs.fwd_lb, rhs.fwd_rb, rhs.depth);
293  }
294 
307  bool operator!=(bi_fm_index_cursor const & rhs) const noexcept
308  {
309  assert(index != nullptr);
310 
311  return !(*this == rhs);
312  }
313 
331  bool extend_right() noexcept
332  {
333 #ifndef NDEBUG
334  fwd_cursor_last_used = true;
335 #endif
336 
337  assert(index != nullptr);
338 
339  size_type new_parent_lb = fwd_lb, new_parent_rb = fwd_rb;
340 
341  sdsl_char_type c = 1; // NOTE: start with 0 or 1 depending on implicit_sentintel
342  while (c < sigma
343  && !bidirectional_search(index->fwd_fm.index,
344  index->fwd_fm.index.comp2char[c],
345  fwd_lb,
346  fwd_rb,
347  rev_lb,
348  rev_rb))
349  {
350  ++c;
351  }
352 
353  if (c != sigma)
354  {
355  parent_lb = new_parent_lb;
356  parent_rb = new_parent_rb;
357 
358  _last_char = c;
359  ++depth;
360 
361  return true;
362  }
363  return false;
364  }
365 
383  bool extend_left() noexcept
384  {
385 #ifndef NDEBUG
386  fwd_cursor_last_used = false;
387 #endif
388 
389  assert(index != nullptr);
390 
391  size_type new_parent_lb = rev_lb, new_parent_rb = rev_rb;
392 
393  sdsl_char_type c = 1; // NOTE: start with 0 or 1 depending on implicit_sentintel
394  while (c < sigma
395  && !bidirectional_search(index->rev_fm.index,
396  index->rev_fm.index.comp2char[c],
397  rev_lb,
398  rev_rb,
399  fwd_lb,
400  fwd_rb))
401  {
402  ++c;
403  }
404 
405  if (c != sigma)
406  {
407  parent_lb = new_parent_lb;
408  parent_rb = new_parent_rb;
409 
410  _last_char = c;
411  ++depth;
412 
413  return true;
414  }
415  return false;
416  }
417 
431  template <typename char_t>
432  requires std::convertible_to<char_t, index_alphabet_type> bool
433  extend_right(char_t const c) noexcept
434  {
435 #ifndef NDEBUG
436  fwd_cursor_last_used = true;
437 #endif
438 
439  assert(index != nullptr);
440  // The rank cannot exceed 255 for single text and 254 for text collections as they are reserved as sentinels
441  // for the indexed text.
442  assert(seqan3::to_rank(static_cast<index_alphabet_type>(c))
443  < ((index_type::text_layout_mode == text_layout::single) ? 255 : 254));
444 
445  size_type new_parent_lb = fwd_lb, new_parent_rb = fwd_rb;
446 
447  auto c_char = seqan3::to_rank(static_cast<index_alphabet_type>(c)) + 1;
448  if (bidirectional_search(index->fwd_fm.index, c_char, fwd_lb, fwd_rb, rev_lb, rev_rb))
449  {
450  parent_lb = new_parent_lb;
451  parent_rb = new_parent_rb;
452 
453  _last_char = c_char;
454  ++depth;
455 
456  return true;
457  }
458  return false;
459  }
460 
462  template <typename char_type>
463  requires seqan3::detail::is_char_adaptation_v<char_type> bool
464  extend_right(char_type const * cstring) noexcept
465  {
467  }
468 
482  template <typename char_t>
483  requires std::convertible_to<char_t, index_alphabet_type> bool
484  extend_left(char_t const c) noexcept
485  {
486 #ifndef NDEBUG
487  fwd_cursor_last_used = false;
488 #endif
489 
490  assert(index != nullptr);
491  // The rank cannot exceed 255 for single text and 254 for text collections as they are reserved as sentinels
492  // for the indexed text.
493  assert(seqan3::to_rank(static_cast<index_alphabet_type>(c))
494  < ((index_type::text_layout_mode == text_layout::single) ? 255 : 254));
495 
496  size_type new_parent_lb = rev_lb, new_parent_rb = rev_rb;
497 
498  auto c_char = seqan3::to_rank(static_cast<index_alphabet_type>(c)) + 1;
499  if (bidirectional_search(index->rev_fm.index, c_char, rev_lb, rev_rb, fwd_lb, fwd_rb))
500  {
501  parent_lb = new_parent_lb;
502  parent_rb = new_parent_rb;
503 
504  _last_char = c_char;
505  ++depth;
506 
507  return true;
508  }
509  return false;
510  }
511 
513  template <typename char_type>
514  requires seqan3::detail::is_char_adaptation_v<char_type> bool
515  extend_left(char_type const * cstring) noexcept
516  {
518  }
519 
536  template <std::ranges::range seq_t>
537  bool extend_right(seq_t && seq) noexcept
538  {
539  static_assert(std::ranges::forward_range<seq_t>, "The query must model forward_range.");
540  static_assert(std::convertible_to<range_innermost_value_t<seq_t>, index_alphabet_type>,
541  "The alphabet of the sequence must be convertible to the alphabet of the index.");
542 
543  assert(index != nullptr);
544 
545  auto first = std::ranges::begin(seq);
546  auto last = std::ranges::end(seq);
547 
548 #ifndef NDEBUG
549  fwd_cursor_last_used = (first != last); // only if seq was not empty
550 #endif
551 
552  size_type _fwd_lb = fwd_lb, _fwd_rb = fwd_rb, _rev_lb = rev_lb, _rev_rb = rev_rb;
553  size_type new_parent_lb = parent_lb, new_parent_rb = parent_rb;
554  sdsl_char_type c = _last_char;
555  size_t len{0};
556 
557  for (auto it = first; it != last; ++len, ++it)
558  {
559  // The rank cannot exceed 255 for single text and 254 for text collections as they are reserved as sentinels
560  // for the indexed text.
561  assert(seqan3::to_rank(static_cast<index_alphabet_type>(*it))
562  < ((index_type::text_layout_mode == text_layout::single) ? 255 : 254));
563 
564  c = seqan3::to_rank(static_cast<index_alphabet_type>(*it)) + 1;
565 
566  new_parent_lb = _fwd_lb;
567  new_parent_rb = _fwd_rb;
568  if (!bidirectional_search(index->fwd_fm.index, c, _fwd_lb, _fwd_rb, _rev_lb, _rev_rb))
569  return false;
570  }
571 
572  fwd_lb = _fwd_lb;
573  fwd_rb = _fwd_rb;
574  rev_lb = _rev_lb;
575  rev_rb = _rev_rb;
576 
577  parent_lb = new_parent_lb;
578  parent_rb = new_parent_rb;
579 
580  _last_char = c;
581  depth += len;
582 
583  return true;
584  }
585 
606  template <std::ranges::range seq_t>
607  bool extend_left(seq_t && seq) noexcept
608  {
609  static_assert(std::ranges::bidirectional_range<seq_t>, "The query must model bidirectional_range.");
610  static_assert(std::convertible_to<range_innermost_value_t<seq_t>, index_alphabet_type>,
611  "The alphabet of the sequence must be convertible to the alphabet of the index.");
612  assert(index != nullptr);
613 
614  auto rev_seq = std::views::reverse(seq);
615  auto first = std::ranges::begin(rev_seq);
616  auto last = std::ranges::end(rev_seq);
617 
618 #ifndef NDEBUG
619  if (first != last) // only if seq was not empty
620  fwd_cursor_last_used = false;
621 #endif
622 
623  size_type _fwd_lb = fwd_lb, _fwd_rb = fwd_rb, _rev_lb = rev_lb, _rev_rb = rev_rb;
624  size_type new_parent_lb = parent_lb, new_parent_rb = parent_rb;
625  sdsl_char_type c = _last_char;
626  size_t len{0};
627 
628  for (auto it = first; it != last; ++len, ++it)
629  {
630  // The rank cannot exceed 255 for single text and 254 for text collections as they are reserved as sentinels
631  // for the indexed text.
632  assert(seqan3::to_rank(static_cast<index_alphabet_type>(*it))
633  < ((index_type::text_layout_mode == text_layout::single) ? 255 : 254));
634 
635  c = seqan3::to_rank(static_cast<index_alphabet_type>(*it)) + 1;
636 
637  new_parent_lb = _rev_lb;
638  new_parent_rb = _rev_rb;
639  if (!bidirectional_search(index->rev_fm.index, c, _rev_lb, _rev_rb, _fwd_lb, _fwd_rb))
640  return false;
641  }
642 
643  fwd_lb = _fwd_lb;
644  fwd_rb = _fwd_rb;
645  rev_lb = _rev_lb;
646  rev_rb = _rev_rb;
647 
648  parent_lb = new_parent_lb;
649  parent_rb = new_parent_rb;
650  _last_char = c;
651  depth += len;
652 
653  return true;
654  }
655 
682  bool cycle_back() noexcept
683  {
684 #ifndef NDEBUG
685  // cycle_back() can only be used if the last extension was to the right.
686  assert(fwd_cursor_last_used);
687 #endif
688 
689  assert(index != nullptr && query_length() > 0);
690 
691  sdsl_char_type c = _last_char + 1;
692 
693  while (c < sigma
694  && !bidirectional_search_cycle(index->fwd_fm.index,
695  index->fwd_fm.index.comp2char[c],
696  parent_lb,
697  parent_rb,
698  fwd_lb,
699  fwd_rb,
700  rev_lb,
701  rev_rb))
702  {
703  ++c;
704  }
705 
706  if (c != sigma)
707  {
708  _last_char = c;
709 
710  return true;
711  }
712  return false;
713  }
714 
741  bool cycle_front() noexcept
742  {
743 #ifndef NDEBUG
744  // cycle_front() can only be used if the last extension was to the left.
745  assert(!fwd_cursor_last_used);
746 #endif
747 
748  assert(index != nullptr && query_length() > 0);
749 
750  sdsl_char_type c = _last_char + 1;
751  while (c < sigma
752  && !bidirectional_search_cycle(index->rev_fm.index,
753  index->rev_fm.index.comp2char[c],
754  parent_lb,
755  parent_rb,
756  rev_lb,
757  rev_rb,
758  fwd_lb,
759  fwd_rb))
760  {
761  ++c;
762  }
763 
764  if (c != sigma)
765  {
766  _last_char = c;
767 
768  return true;
769  }
770  return false;
771  }
772 
789  size_type last_rank() noexcept
790  {
791  assert(index != nullptr && query_length() > 0);
792 
793  return index->fwd_fm.index.comp2char[_last_char] - 1; // text is not allowed to contain ranks of 0
794  }
795 
808  size_type query_length() const noexcept
809  {
810  assert(index != nullptr);
811  // depth == 0 -> root node
812  assert(depth != 0 || (fwd_lb == rev_lb && fwd_rb == rev_rb && fwd_lb == 0 && fwd_rb == index->size() - 1));
813 
814  return depth;
815  }
816 
836  fwd_cursor to_fwd_cursor() const noexcept
837  {
838  assert(index != nullptr);
839 
840  fwd_cursor cur{index->fwd_fm};
841  cur.parent_lb = parent_lb;
842  cur.parent_rb = parent_rb;
843  cur.node = {fwd_lb, fwd_rb, depth, _last_char};
844 
845 #ifndef NDEBUG
846  if (!fwd_cursor_last_used)
847  {
848  // invalidate parent interval
849  cur.parent_lb = 1;
850  cur.parent_rb = 0;
851  }
852 #endif
853 
854  return cur;
855  }
856 
873  template <std::ranges::range text_t>
874  auto path_label(text_t && text) const noexcept
875  requires (index_t::text_layout_mode == text_layout::single)
876  {
877  static_assert(std::ranges::input_range<text_t>, "The text must model input_range.");
878  static_assert(range_dimension_v<text_t> == 1, "The input cannot be a text collection.");
879  static_assert(std::same_as<range_innermost_value_t<text_t>, index_alphabet_type>,
880  "The alphabet types of the given text and index differ.");
881  assert(index != nullptr);
882 
883  size_type const query_begin = offset() - index->fwd_fm.index[fwd_lb];
884  return text | views::slice(query_begin, query_begin + query_length());
885  }
886 
888  template <std::ranges::range text_t>
889  auto path_label(text_t && text) const noexcept
890  requires (index_t::text_layout_mode == text_layout::collection)
891  {
892  static_assert(std::ranges::input_range<text_t>, "The text collection must model input_range.");
893  static_assert(range_dimension_v<text_t> == 2, "The input must be a text collection.");
894  static_assert(std::same_as<range_innermost_value_t<text_t>, index_alphabet_type>,
895  "The alphabet types of the given text and index differ.");
896  assert(index != nullptr);
897 
898  // Position of query in concatenated text.
899  size_type const location = offset() - index->fwd_fm.index[fwd_lb];
900 
901  // The rank represents the number of start positions of the individual sequences/texts in the collection
902  // before position `location + 1` and thereby also the number of delimiters.
903  size_type const rank = index->fwd_fm.text_begin_rs.rank(location + 1);
904  assert(rank > 0);
905  size_type const text_id = rank - 1;
906 
907  // The start location of the `text_id`-th text in the sequence (position of the `rank`-th 1 in the bitvector).
908  size_type const start_location = index->fwd_fm.text_begin_ss.select(rank);
909  // Substract lengths of previous sequences.
910  size_type const query_begin = location - start_location;
911 
912  // Take subtext, slice query out of it
913  return text[text_id] | views::slice(query_begin, query_begin + query_length());
914  }
915 
927  size_type count() const noexcept
928  {
929  assert(index != nullptr && (1 + fwd_rb - fwd_lb == 1 + rev_rb - rev_lb));
930 
931  return 1 + fwd_rb - fwd_lb;
932  }
933 
946  requires (index_t::text_layout_mode == text_layout::single)
947  {
948  assert(index != nullptr);
949 
950  locate_result_type occ{};
951  occ.reserve(count());
952  for (size_type i = 0; i < count(); ++i)
953  {
954  occ.emplace_back(0, offset() - index->fwd_fm.index[fwd_lb + i]);
955  }
956  return occ;
957  }
958 
961  requires (index_t::text_layout_mode == text_layout::collection)
962  {
963  assert(index != nullptr);
964 
966  occ.reserve(count());
967  for (size_type i = 0; i < count(); ++i)
968  {
969  size_type loc = offset() - index->fwd_fm.index[fwd_lb + i];
970  size_type sequence_rank = index->fwd_fm.text_begin_rs.rank(loc + 1);
971  size_type sequence_position = loc - index->fwd_fm.text_begin_ss.select(sequence_rank);
972  occ.emplace_back(sequence_rank - 1, sequence_position);
973  }
974  return occ;
975  }
976 
989  auto lazy_locate() const
990  requires (index_t::text_layout_mode == text_layout::single)
991  {
992  assert(index != nullptr);
993 
994  return std::views::iota(fwd_lb, fwd_lb + count())
996  [*this, _offset = offset()](auto sa_pos)
997  {
998  return locate_result_value_type{0u, _offset - index->fwd_fm.index[sa_pos]};
999  });
1000  }
1001 
1003  auto lazy_locate() const
1004  requires (index_t::text_layout_mode == text_layout::collection)
1005  {
1006  assert(index != nullptr);
1007 
1008  return std::views::iota(fwd_lb, fwd_lb + count())
1010  [*this, _offset = offset()](auto sa_pos)
1011  {
1012  auto loc = _offset - index->fwd_fm.index[sa_pos];
1013  size_type sequence_rank = index->fwd_fm.text_begin_rs.rank(loc + 1);
1014  size_type sequence_position = loc - index->fwd_fm.text_begin_ss.select(sequence_rank);
1015  return locate_result_value_type{sequence_rank - 1, sequence_position};
1016  });
1017  }
1018 
1026  template <cereal_archive archive_t>
1027  void CEREAL_SERIALIZE_FUNCTION_NAME(archive_t & archive)
1028  {
1029  archive(fwd_lb);
1030  archive(fwd_rb);
1031  archive(rev_lb);
1032  archive(rev_rb);
1033  archive(sigma);
1034  archive(parent_lb);
1035  archive(parent_rb);
1036  archive(_last_char);
1037  archive(depth);
1038  }
1040 };
1041 
1042 } // namespace seqan3
Core alphabet concept and free function/type trait wrappers.
Provides alphabet adaptations for standard char types.
The SeqAn Bidirectional FM Index Cursor.
Definition: bi_fm_index_cursor.hpp:55
std::vector< std::pair< size_type, size_type > > locate() const requires(index_t
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition: bi_fm_index_cursor.hpp:960
bool extend_right() noexcept
Tries to extend the query by the smallest possible character to the right such that the query is foun...
Definition: bi_fm_index_cursor.hpp:331
size_type count() const noexcept
Counts the number of occurrences of the searched query in the text.
Definition: bi_fm_index_cursor.hpp:927
requires seqan3::detail::is_char_adaptation_v< char_type > bool extend_left(char_type const *cstring) noexcept
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition: bi_fm_index_cursor.hpp:515
bool extend_left(seq_t &&seq) noexcept
Tries to extend the query by seq to the left.
Definition: bi_fm_index_cursor.hpp:607
bool operator==(bi_fm_index_cursor const &rhs) const noexcept
Compares two cursors.
Definition: bi_fm_index_cursor.hpp:285
requires std::convertible_to< char_t, index_alphabet_type > bool extend_left(char_t const c) noexcept
Tries to extend the query by the character c to the left.
Definition: bi_fm_index_cursor.hpp:484
bool extend_left() noexcept
Tries to extend the query by the smallest possible character to the left such that the query is found...
Definition: bi_fm_index_cursor.hpp:383
bool cycle_back() noexcept
Tries to replace the rightmost character of the query by the next lexicographically larger character ...
Definition: bi_fm_index_cursor.hpp:682
bool cycle_front() noexcept
Tries to replace the leftmost character of the query by the next lexicographically larger character s...
Definition: bi_fm_index_cursor.hpp:741
fwd_cursor to_fwd_cursor() const noexcept
Returns a unidirectional seqan3::fm_index_cursor on the original text. path_label() on the returned u...
Definition: bi_fm_index_cursor.hpp:836
locate_result_type locate() const requires(index_t
Locates the occurrences of the searched query in the text.
Definition: bi_fm_index_cursor.hpp:945
size_type query_length() const noexcept
Returns the depth of the cursor node in the implicit suffix tree, i.e. the length of the sequence sea...
Definition: bi_fm_index_cursor.hpp:808
size_type last_rank() noexcept
Outputs the rightmost respectively leftmost rank depending on whether extend_right() or extend_left()...
Definition: bi_fm_index_cursor.hpp:789
index_t index_type
Type of the index.
Definition: bi_fm_index_cursor.hpp:58
typename index_type::size_type size_type
Type for representing positions in the indexed text.
Definition: bi_fm_index_cursor.hpp:64
bool operator!=(bi_fm_index_cursor const &rhs) const noexcept
Compares two cursors.
Definition: bi_fm_index_cursor.hpp:307
bi_fm_index_cursor() noexcept=default
Default constructor. Accessing member functions on a default constructed object is undefined behavior...
requires std::convertible_to< char_t, index_alphabet_type > bool extend_right(char_t const c) noexcept
Tries to extend the query by the character c to the right.
Definition: bi_fm_index_cursor.hpp:433
bool extend_right(seq_t &&seq) noexcept
Tries to extend the query by seq to the right.
Definition: bi_fm_index_cursor.hpp:537
auto lazy_locate() const requires(index_t
Locates the occurrences of the searched query in the text on demand, i.e. a std::ranges::view is retu...
Definition: bi_fm_index_cursor.hpp:989
requires seqan3::detail::is_char_adaptation_v< char_type > bool extend_right(char_type const *cstring) noexcept
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition: bi_fm_index_cursor.hpp:464
auto path_label(text_t &&text) const noexcept requires(index_t
Returns the searched query.
Definition: bi_fm_index_cursor.hpp:874
The SeqAn FM Index Cursor.
Definition: fm_index_cursor.hpp:87
The SeqAn FM Index.
Definition: fm_index.hpp:189
Provides various transformation traits used by the range module.
T emplace_back(T... args)
Provides the unidirectional seqan3::fm_index.
Provides the seqan3::fm_index_cursor for searching in the unidirectional seqan3::fm_index.
constexpr auto to_rank
Return the rank representation of a (semi-)alphabet object.
Definition: alphabet/concept.hpp:155
typename range_innermost_value< t >::type range_innermost_value_t
Shortcut for seqan3::range_innermost_value (transformation_trait shortcut).
Definition: core/range/type_traits.hpp:98
@ seq
The "sequence", usually a range of nucleotides or amino acids.
text_layout
The possible text layouts (single, collection) the seqan3::fm_index and seqan3::bi_fm_index can suppo...
Definition: search/fm_index/concept.hpp:91
@ single
The text is a single range.
Definition: search/fm_index/concept.hpp:93
@ collection
The text is a range of ranges.
Definition: search/fm_index/concept.hpp:95
decltype(detail::transform< trait_t >(list_t{})) transform
Apply a transformation trait to every type in the list and return a seqan3::type_list of the results.
Definition: type_list/traits.hpp:469
constexpr size_t size
The size of a type pack.
Definition: type_pack/traits.hpp:146
constexpr auto slice
A view adaptor that returns a half-open interval on the underlying range.
Definition: slice.hpp:178
The main SeqAn3 namespace.
Definition: aligned_sequence_concept.hpp:29
The <ranges> header from C++20's standard library.
T reserve(T... args)
Provides seqan3::views::slice.
T tie(T... args)
Provides alphabet adaptations for standard uint types.