SeqAn3  3.1.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-2021, Knut Reinert & Freie Universität Berlin
3 // Copyright (c) 2016-2021, 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 <seqan3/std/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;
86  using locate_result_value_type = std::pair<size_type, size_type>;
88  using locate_result_type = std::vector<locate_result_value_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>
148  requires (std::same_as<csa_t, typename index_type::sdsl_index_type> ||
149  std::same_as<csa_t, typename index_type::rev_sdsl_index_type>)
151  bool bidirectional_search(csa_t const & csa, sdsl_char_type const c,
152  size_type & l_fwd, size_type & r_fwd,
153  size_type & l_bwd, size_type & r_bwd) const noexcept
154  {
155  assert((l_fwd <= r_fwd) && (r_fwd < csa.size()));
156  assert(r_fwd + 1 >= l_fwd);
157  assert(r_bwd + 1 - l_bwd == r_fwd + 1 - l_fwd);
158 
159  size_type _l_fwd, _r_fwd, _l_bwd, _r_bwd;
160 
161  size_type cc = c;
162  if constexpr(!std::same_as<index_alphabet_type, sdsl::plain_byte_alphabet>)
163  {
164  cc = csa.char2comp[c];
165  if (cc == 0 && c > 0) // [[unlikely]]
166  return false;
167  }
168 
169  size_type const c_begin = csa.C[cc];
170  if (r_fwd + 1 - l_fwd == csa.size()) // [[unlikely]]
171  {
172  _l_fwd = c_begin;
173  _l_bwd = c_begin;
174  _r_fwd = csa.C[cc + 1] - 1;
175  _r_bwd = _r_fwd;
176  // if we use not the plain_byte_alphabet, we could return always return true here
177  }
178  else
179  {
180  auto const r_s_b = csa.wavelet_tree.lex_count(l_fwd, r_fwd + 1, c);
181  size_type const rank_l = std::get<0>(r_s_b);
182  size_type const s = std::get<1>(r_s_b), b = std::get<2>(r_s_b);
183  size_type const rank_r = r_fwd - l_fwd - s - b + rank_l;
184  _l_fwd = c_begin + rank_l;
185  _r_fwd = c_begin + rank_r;
186  _l_bwd = l_bwd + s;
187  _r_bwd = r_bwd - b;
188  }
189 
190  if (_r_fwd >= _l_fwd)
191  {
192  l_fwd = _l_fwd;
193  r_fwd = _r_fwd;
194  l_bwd = _l_bwd;
195  r_bwd = _r_bwd;
196  assert(r_fwd + 1 >= l_fwd);
197  assert(r_bwd + 1 - l_bwd == r_fwd + 1 - l_fwd);
198  return true;
199  }
200  return false;
201  }
202 
204  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>)
209  bool bidirectional_search_cycle(csa_t const & csa, sdsl_char_type const c,
210  size_type const l_parent, size_type const r_parent,
211  size_type & l_fwd, size_type & r_fwd,
212  size_type & l_bwd, size_type & r_bwd) const noexcept
213  {
214  assert((l_parent <= r_parent) && (r_parent < csa.size()));
215 
216  size_type c_begin;
217  if constexpr(std::same_as<index_alphabet_type, sdsl::plain_byte_alphabet>)
218  c_begin = csa.C[c]; // TODO: check whether this can be removed
219  else
220  c_begin = csa.C[csa.char2comp[c]];
221 
222  auto const r_s_b = csa.wavelet_tree.lex_count(l_parent, r_parent + 1, c);
223  size_type const s = std::get<1>(r_s_b),
224  b = std::get<2>(r_s_b),
225  rank_l = std::get<0>(r_s_b),
226  rank_r = r_parent - l_parent - s - b + rank_l;
227 
228  size_type const _l_fwd = c_begin + rank_l;
229  size_type const _r_fwd = c_begin + rank_r;
230  size_type const _l_bwd = r_bwd + 1;
231  size_type const _r_bwd = r_bwd + 1 + rank_r - rank_l;
232 
233  if (_r_fwd >= _l_fwd)
234  {
235  l_fwd = _l_fwd;
236  r_fwd = _r_fwd;
237  l_bwd = _l_bwd;
238  r_bwd = _r_bwd;
239  assert(r_fwd + 1 >= l_fwd);
240  assert(r_bwd + 1 - l_bwd == r_fwd + 1 - l_fwd);
241  return true;
242  }
243  return false;
244  }
245 
246 public:
247 
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 : index(&_index),
263  fwd_lb(0), fwd_rb(_index.size() - 1),
264  rev_lb(0), rev_rb(_index.size() - 1),
265  sigma(_index.fwd_fm.index.sigma - index_t::text_layout_mode),
266  depth(0)
267  {}
268  //\}
269 
282  bool operator==(bi_fm_index_cursor const & rhs) const noexcept
283  {
284  assert(index != nullptr);
285  // equal SA interval implies equal parent node information (or both are root nodes)
286  assert(!(fwd_lb == rhs.fwd_lb && fwd_rb == rhs.fwd_rb && depth == rhs.depth) ||
287  (depth == 0) ||
288  (parent_lb == rhs.parent_lb && parent_rb == rhs.parent_rb && _last_char == rhs._last_char));
289 
290  return std::tie(fwd_lb, fwd_rb, depth) == std::tie(rhs.fwd_lb, rhs.fwd_rb, rhs.depth);
291  }
292 
305  bool operator!=(bi_fm_index_cursor const & rhs) const noexcept
306  {
307  assert(index != nullptr);
308 
309  return !(*this == rhs);
310  }
311 
329  bool extend_right() noexcept
330  {
331  #ifndef NDEBUG
332  fwd_cursor_last_used = true;
333  #endif
334 
335  assert(index != nullptr);
336 
337  size_type new_parent_lb = fwd_lb, new_parent_rb = fwd_rb;
338 
339  sdsl_char_type c = 1; // NOTE: start with 0 or 1 depending on implicit_sentintel
340  while (c < sigma &&
341  !bidirectional_search(index->fwd_fm.index, index->fwd_fm.index.comp2char[c],
342  fwd_lb, fwd_rb, rev_lb, rev_rb))
343  {
344  ++c;
345  }
346 
347  if (c != sigma)
348  {
349  parent_lb = new_parent_lb;
350  parent_rb = new_parent_rb;
351 
352  _last_char = c;
353  ++depth;
354 
355  return true;
356  }
357  return false;
358  }
359 
377  bool extend_left() noexcept
378  {
379  #ifndef NDEBUG
380  fwd_cursor_last_used = false;
381  #endif
382 
383  assert(index != nullptr);
384 
385  size_type new_parent_lb = rev_lb, new_parent_rb = rev_rb;
386 
387  sdsl_char_type c = 1; // NOTE: start with 0 or 1 depending on implicit_sentintel
388  while (c < sigma &&
389  !bidirectional_search(index->rev_fm.index, index->rev_fm.index.comp2char[c],
390  rev_lb, rev_rb, fwd_lb, fwd_rb))
391  {
392  ++c;
393  }
394 
395  if (c != sigma)
396  {
397  parent_lb = new_parent_lb;
398  parent_rb = new_parent_rb;
399 
400  _last_char = c;
401  ++depth;
402 
403  return true;
404  }
405  return false;
406  }
407 
421  template <typename char_t>
423  requires std::convertible_to<char_t, index_alphabet_type>
425  bool extend_right(char_t const c) noexcept
426  {
427  #ifndef NDEBUG
428  fwd_cursor_last_used = true;
429  #endif
430 
431  assert(index != nullptr);
432  // The rank cannot exceed 255 for single text and 254 for text collections as they are reserved as sentinels
433  // for the indexed text.
434  assert(seqan3::to_rank(static_cast<index_alphabet_type>(c)) <
435  ((index_type::text_layout_mode == text_layout::single) ? 255 : 254));
436 
437  size_type new_parent_lb = fwd_lb, new_parent_rb = fwd_rb;
438 
439  auto c_char = seqan3::to_rank(static_cast<index_alphabet_type>(c)) + 1;
440  if (bidirectional_search(index->fwd_fm.index, c_char, fwd_lb, fwd_rb, rev_lb, rev_rb))
441  {
442  parent_lb = new_parent_lb;
443  parent_rb = new_parent_rb;
444 
445  _last_char = c_char;
446  ++depth;
447 
448  return true;
449  }
450  return false;
451  }
452 
454  template <typename char_type>
456  requires seqan3::detail::is_char_adaptation_v<char_type>
458  bool extend_right(char_type const * cstring) noexcept
459  {
460  return extend_right(std::basic_string_view<char_type>{cstring});
461  }
462 
476  template <typename char_t>
478  requires std::convertible_to<char_t, index_alphabet_type>
480  bool extend_left(char_t const c) noexcept
481  {
482  #ifndef NDEBUG
483  fwd_cursor_last_used = false;
484  #endif
485 
486  assert(index != nullptr);
487  // The rank cannot exceed 255 for single text and 254 for text collections as they are reserved as sentinels
488  // for the indexed text.
489  assert(seqan3::to_rank(static_cast<index_alphabet_type>(c)) <
490  ((index_type::text_layout_mode == text_layout::single) ? 255 : 254));
491 
492  size_type new_parent_lb = rev_lb, new_parent_rb = rev_rb;
493 
494  auto c_char = seqan3::to_rank(static_cast<index_alphabet_type>(c)) + 1;
495  if (bidirectional_search(index->rev_fm.index, c_char, rev_lb, rev_rb, fwd_lb, fwd_rb))
496  {
497  parent_lb = new_parent_lb;
498  parent_rb = new_parent_rb;
499 
500  _last_char = c_char;
501  ++depth;
502 
503  return true;
504  }
505  return false;
506  }
507 
509  template <typename char_type>
511  requires seqan3::detail::is_char_adaptation_v<char_type>
513  bool extend_left(char_type const * cstring) noexcept
514  {
515  return extend_left(std::basic_string_view<char_type>{cstring});
516  }
517 
534  template <std::ranges::range seq_t>
535  bool extend_right(seq_t && seq) noexcept
536  {
537  static_assert(std::ranges::forward_range<seq_t>, "The query must model forward_range.");
538  static_assert(std::convertible_to<range_innermost_value_t<seq_t>, index_alphabet_type>,
539  "The alphabet of the sequence must be convertible to the alphabet of the index.");
540 
541  assert(index != nullptr);
542 
543  auto first = std::ranges::begin(seq);
544  auto last = std::ranges::end(seq);
545 
546  #ifndef NDEBUG
547  fwd_cursor_last_used = (first != last); // only if seq was not empty
548  #endif
549 
550  size_type _fwd_lb = fwd_lb, _fwd_rb = fwd_rb, _rev_lb = rev_lb, _rev_rb = rev_rb;
551  size_type new_parent_lb = parent_lb, new_parent_rb = parent_rb;
552  sdsl_char_type c = _last_char;
553  size_t len{0};
554 
555  for (auto it = first; it != last; ++len, ++it)
556  {
557  // The rank cannot exceed 255 for single text and 254 for text collections as they are reserved as sentinels
558  // for the indexed text.
559  assert(seqan3::to_rank(static_cast<index_alphabet_type>(*it)) <
560  ((index_type::text_layout_mode == text_layout::single) ? 255 : 254));
561 
562  c = seqan3::to_rank(static_cast<index_alphabet_type>(*it)) + 1;
563 
564  new_parent_lb = _fwd_lb;
565  new_parent_rb = _fwd_rb;
566  if (!bidirectional_search(index->fwd_fm.index, c, _fwd_lb, _fwd_rb, _rev_lb, _rev_rb))
567  return false;
568  }
569 
570  fwd_lb = _fwd_lb;
571  fwd_rb = _fwd_rb;
572  rev_lb = _rev_lb;
573  rev_rb = _rev_rb;
574 
575  parent_lb = new_parent_lb;
576  parent_rb = new_parent_rb;
577 
578  _last_char = c;
579  depth += len;
580 
581  return true;
582  }
583 
604  template <std::ranges::range seq_t>
605  bool extend_left(seq_t && seq) noexcept
606  {
607  static_assert(std::ranges::bidirectional_range<seq_t>, "The query must model bidirectional_range.");
608  static_assert(std::convertible_to<range_innermost_value_t<seq_t>, index_alphabet_type>,
609  "The alphabet of the sequence must be convertible to the alphabet of the index.");
610  assert(index != nullptr);
611 
612  auto rev_seq = std::views::reverse(seq);
613  auto first = std::ranges::begin(rev_seq);
614  auto last = std::ranges::end(rev_seq);
615 
616  #ifndef NDEBUG
617  if (first != last) // only if seq was not empty
618  fwd_cursor_last_used = false;
619  #endif
620 
621  size_type _fwd_lb = fwd_lb, _fwd_rb = fwd_rb,
622  _rev_lb = rev_lb, _rev_rb = rev_rb;
623  size_type new_parent_lb = parent_lb, new_parent_rb = parent_rb;
624  sdsl_char_type c = _last_char;
625  size_t len{0};
626 
627  for (auto it = first; it != last; ++len, ++it)
628  {
629  // The rank cannot exceed 255 for single text and 254 for text collections as they are reserved as sentinels
630  // for the indexed text.
631  assert(seqan3::to_rank(static_cast<index_alphabet_type>(*it)) <
632  ((index_type::text_layout_mode == text_layout::single) ? 255 : 254));
633 
634  c = seqan3::to_rank(static_cast<index_alphabet_type>(*it)) + 1;
635 
636  new_parent_lb = _rev_lb;
637  new_parent_rb = _rev_rb;
638  if (!bidirectional_search(index->rev_fm.index, c, _rev_lb, _rev_rb, _fwd_lb, _fwd_rb))
639  return false;
640  }
641 
642  fwd_lb = _fwd_lb;
643  fwd_rb = _fwd_rb;
644  rev_lb = _rev_lb;
645  rev_rb = _rev_rb;
646 
647  parent_lb = new_parent_lb;
648  parent_rb = new_parent_rb;
649  _last_char = c;
650  depth += len;
651 
652  return true;
653  }
654 
681  bool cycle_back() noexcept
682  {
683  #ifndef NDEBUG
684  // cycle_back() can only be used if the last extension was to the right.
685  assert(fwd_cursor_last_used);
686  #endif
687 
688  assert(index != nullptr && query_length() > 0);
689 
690  sdsl_char_type c = _last_char + 1;
691 
692  while (c < sigma &&
693  !bidirectional_search_cycle(index->fwd_fm.index, index->fwd_fm.index.comp2char[c],
694  parent_lb, parent_rb, fwd_lb, fwd_rb, rev_lb, rev_rb))
695  {
696  ++c;
697  }
698 
699  if (c != sigma)
700  {
701  _last_char = c;
702 
703  return true;
704  }
705  return false;
706  }
707 
734  bool cycle_front() noexcept
735  {
736  #ifndef NDEBUG
737  // cycle_front() can only be used if the last extension was to the left.
738  assert(!fwd_cursor_last_used);
739  #endif
740 
741  assert(index != nullptr && query_length() > 0);
742 
743  sdsl_char_type c = _last_char + 1;
744  while (c < sigma &&
745  !bidirectional_search_cycle(index->rev_fm.index, index->rev_fm.index.comp2char[c],
746  parent_lb, parent_rb, rev_lb, rev_rb, fwd_lb, fwd_rb))
747  {
748  ++c;
749  }
750 
751  if (c != sigma)
752  {
753  _last_char = c;
754 
755  return true;
756  }
757  return false;
758  }
759 
760 
777  size_type last_rank() noexcept
778  {
779  assert(index != nullptr && query_length() > 0);
780 
781  return index->fwd_fm.index.comp2char[_last_char] - 1; // text is not allowed to contain ranks of 0
782  }
783 
796  size_type query_length() const noexcept
797  {
798  assert(index != nullptr);
799  // depth == 0 -> root node
800  assert(depth != 0 ||
801  (fwd_lb == rev_lb &&
802  fwd_rb == rev_rb &&
803  fwd_lb == 0 &&
804  fwd_rb == index->size() - 1));
805 
806  return depth;
807  }
808 
828  fwd_cursor to_fwd_cursor() const noexcept
829  {
830  assert(index != nullptr);
831 
832  fwd_cursor cur{index->fwd_fm};
833  cur.parent_lb = parent_lb;
834  cur.parent_rb = parent_rb;
835  cur.node = {fwd_lb, fwd_rb, depth, _last_char};
836 
837  #ifndef NDEBUG
838  if (!fwd_cursor_last_used)
839  {
840  // invalidate parent interval
841  cur.parent_lb = 1;
842  cur.parent_rb = 0;
843  }
844  #endif
845 
846  return cur;
847  }
848 
865  template <std::ranges::range text_t>
866  auto path_label(text_t && text) const noexcept
868  requires (index_t::text_layout_mode == text_layout::single)
870  {
871  static_assert(std::ranges::input_range<text_t>, "The text must model input_range.");
872  static_assert(range_dimension_v<text_t> == 1, "The input cannot be a text collection.");
873  static_assert(std::same_as<range_innermost_value_t<text_t>, index_alphabet_type>,
874  "The alphabet types of the given text and index differ.");
875  assert(index != nullptr);
876 
877  size_type const query_begin = offset() - index->fwd_fm.index[fwd_lb];
878  return text | views::slice(query_begin, query_begin + query_length());
879  }
880 
882  template <std::ranges::range text_t>
883  auto path_label(text_t && text) const noexcept
885  requires (index_t::text_layout_mode == text_layout::collection)
887  {
888  static_assert(std::ranges::input_range<text_t>, "The text collection must model input_range.");
889  static_assert(range_dimension_v<text_t> == 2, "The input must be a text collection.");
890  static_assert(std::same_as<range_innermost_value_t<text_t>, index_alphabet_type>,
891  "The alphabet types of the given text and index differ.");
892  assert(index != nullptr);
893 
894  // Position of query in concatenated text.
895  size_type const location = offset() - index->fwd_fm.index[fwd_lb];
896 
897  // The rank represents the number of start positions of the individual sequences/texts in the collection
898  // before position `location + 1` and thereby also the number of delimiters.
899  size_type const rank = index->fwd_fm.text_begin_rs.rank(location + 1);
900  assert(rank > 0);
901  size_type const text_id = rank - 1;
902 
903  // The start location of the `text_id`-th text in the sequence (position of the `rank`-th 1 in the bitvector).
904  size_type const start_location = index->fwd_fm.text_begin_ss.select(rank);
905  // Substract lengths of previous sequences.
906  size_type const query_begin = location - start_location;
907 
908  // Take subtext, slice query out of it
909  return text[text_id] | views::slice(query_begin, query_begin + query_length());
910  }
911 
923  size_type count() const noexcept
924  {
925  assert(index != nullptr && (1 + fwd_rb - fwd_lb == 1 + rev_rb - rev_lb));
926 
927  return 1 + fwd_rb - fwd_lb;
928  }
929 
941  locate_result_type locate() const
943  requires (index_t::text_layout_mode == text_layout::single)
945  {
946  assert(index != nullptr);
947 
948  locate_result_type occ{};
949  occ.reserve(count());
950  for (size_type i = 0; i < count(); ++i)
951  {
952  occ.emplace_back(0, offset() - index->fwd_fm.index[fwd_lb + i]);
953  }
954  return occ;
955  }
956 
958  std::vector<std::pair<size_type, size_type>> locate() const
960  requires (index_t::text_layout_mode == text_layout::collection)
962  {
963  assert(index != nullptr);
964 
965  std::vector<std::pair<size_type, size_type>> occ;
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
991  requires (index_t::text_layout_mode == text_layout::single)
993  {
994  assert(index != nullptr);
995 
996  return std::views::iota(fwd_lb, fwd_lb + count())
997  | std::views::transform([*this, _offset = offset()] (auto sa_pos)
998  {
999  return locate_result_value_type{0u, _offset - index->fwd_fm.index[sa_pos]};
1000  });
1001  }
1002 
1004  auto lazy_locate() const
1006  requires (index_t::text_layout_mode == text_layout::collection)
1008  {
1009  assert(index != nullptr);
1010 
1011  return std::views::iota(fwd_lb, fwd_lb + count())
1012  | std::views::transform([*this, _offset = offset()] (auto sa_pos)
1013  {
1014  auto loc = _offset - index->fwd_fm.index[sa_pos];
1015  size_type sequence_rank = index->fwd_fm.text_begin_rs.rank(loc + 1);
1016  size_type sequence_position = loc - index->fwd_fm.text_begin_ss.select(sequence_rank);
1017  return locate_result_value_type{sequence_rank-1, sequence_position};
1018  });
1019  }
1020 
1028  template <cereal_archive archive_t>
1029  void CEREAL_SERIALIZE_FUNCTION_NAME(archive_t & archive)
1030  {
1031  archive(fwd_lb);
1032  archive(fwd_rb);
1033  archive(rev_lb);
1034  archive(rev_rb);
1035  archive(sigma);
1036  archive(parent_lb);
1037  archive(parent_rb);
1038  archive(_last_char);
1039  archive(depth);
1040  }
1042 };
1043 
1044 } // 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
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:329
size_type count() const noexcept
Counts the number of occurrences of the searched query in the text.
Definition: bi_fm_index_cursor.hpp:923
bool extend_left(seq_t &&seq) noexcept
Tries to extend the query by seq to the left.
Definition: bi_fm_index_cursor.hpp:605
bool operator==(bi_fm_index_cursor const &rhs) const noexcept
Compares two cursors.
Definition: bi_fm_index_cursor.hpp:282
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:513
auto path_label(text_t &&text) const noexcept
Returns the searched query.
Definition: bi_fm_index_cursor.hpp:866
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:377
locate_result_type locate() const
Locates the occurrences of the searched query in the text.
Definition: bi_fm_index_cursor.hpp:941
std::vector< std::pair< size_type, size_type > > locate() const
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition: bi_fm_index_cursor.hpp:958
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:681
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:734
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:828
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:796
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:777
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 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:480
bool operator!=(bi_fm_index_cursor const &rhs) const noexcept
Compares two cursors.
Definition: bi_fm_index_cursor.hpp:305
bi_fm_index_cursor() noexcept=default
Default constructor. Accessing member functions on a default constructed object is undefined behavior...
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:458
bool extend_right(seq_t &&seq) noexcept
Tries to extend the query by seq to the right.
Definition: bi_fm_index_cursor.hpp:535
auto lazy_locate() const
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
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:425
The SeqAn FM Index Cursor.
Definition: fm_index_cursor.hpp:87
The SeqAn FM Index.
Definition: fm_index.hpp:192
Provides various transformation traits used by the range module.
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: concept.hpp:155
typename range_innermost_value< t >::type range_innermost_value_t
Shortcut for seqan3::range_innermost_value (transformation_trait shortcut).
Definition: type_traits.hpp:91
@ 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: concept.hpp:72
@ single
The text is a single range.
Definition: concept.hpp:74
@ collection
The text is a range of ranges.
Definition: concept.hpp:76
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: traits.hpp:471
constexpr size_t size
The size of a type pack.
Definition: traits.hpp:151
constexpr auto slice
A view adaptor that returns a half-open interval on the underlying range.
Definition: slice.hpp:183
The main SeqAn3 namespace.
Definition: aligned_sequence_concept.hpp:29
Adaptations of concepts from the Ranges TS.
Provides seqan3::views::slice.
Provides alphabet adaptations for standard uint types.