SDSL  3.0.0
Succinct Data Structure Library
cst_fully.hpp
Go to the documentation of this file.
1 // Copyright (c) 2016, the SDSL Project Authors. All rights reserved.
2 // Please see the AUTHORS file for details. Use of this source code is governed
3 // by a BSD license that can be found in the LICENSE file.
8 #ifndef INCLUDED_SDSL_CST_FULLY
9 #define INCLUDED_SDSL_CST_FULLY
10 
11 #include <sdsl/bit_vectors.hpp>
12 #include <sdsl/bp_support.hpp>
13 #include <sdsl/construct.hpp>
14 #include <sdsl/cst_iterators.hpp>
15 #include <sdsl/cst_sada.hpp>
16 #include <sdsl/sdsl_concepts.hpp>
17 #include <sdsl/suffix_arrays.hpp>
20 #include <sdsl/util.hpp>
21 #include <sdsl/vectors.hpp>
22 
23 namespace sdsl
24 {
25 
26 template <typename t_cst>
27 class lcp_fully
28 {
29  public:
30  typedef typename t_cst::size_type size_type;
34 
36 
37  enum
38  {
41  sa_order = 0
42  };
43 
44  private:
45  const t_cst * m_cst;
46 
47  public:
48  lcp_fully() = default;
49  lcp_fully(const t_cst * cst)
50  : m_cst(cst){};
51 
52  lcp_fully(const lcp_fully &) = default;
53  lcp_fully(lcp_fully &&) = default;
54  lcp_fully & operator=(const lcp_fully &) = default;
55  lcp_fully & operator=(lcp_fully &&) = default;
56  ~lcp_fully() = default;
57 
58  size_type size() const { return m_cst->size(); }
59 
61  {
62  if (0 == i) { return 0; }
63  else
64  {
65  using leaf_type = typename t_cst::leaf_type;
66  using sampled_node_type = typename t_cst::sampled_node_type;
67  leaf_type v_l = i - 1;
68  leaf_type v_r = i;
69 
70  size_type i;
71  sampled_node_type u;
72  return m_cst->depth_lca(v_l, v_r, i, u);
73  }
74  }
75 
77  const_iterator begin() const { return const_iterator(this, 0); }
78 
80  const_iterator end() const { return const_iterator(this, size()); }
81 };
82 
84 
116 template <class t_csa = csa_wt<>,
117  uint32_t t_delta = 0,
118  class t_s_support = bp_support_sada<>,
119  class t_b = sd_vector<>,
120  class t_depth = dac_vector<>,
121  bool t_sample_leaves = false>
123 {
124  public:
126  typedef typename t_csa::size_type size_type;
127  typedef t_csa csa_type;
129  typedef typename t_csa::char_type char_type;
130  typedef std::pair<size_type, size_type> node_type; // Nodes are represented by their interval over the CSA
131  typedef size_type leaf_type; // Index of a leaf
132  typedef size_type sampled_node_type; // Node in the sampled tree represented by its index in s
133  typedef t_s_support s_support_type;
134  typedef t_b b_type;
135  typedef typename t_b::select_0_type b_select_0_type;
136  typedef typename t_b::select_1_type b_select_1_type;
137  typedef t_depth depth_type;
138 
139  typedef typename t_csa::alphabet_category alphabet_category;
141 
142  private:
143  size_type m_delta;
144  size_type m_nodes;
145  csa_type m_csa;
146  bit_vector m_s;
147  s_support_type m_s_support;
148  b_type m_b;
149  b_select_0_type m_b_select0;
150  b_select_1_type m_b_select1;
151  depth_type m_depth;
152  lcp_type m_lcp = lcp_type(this);
153 
154  public:
155  const size_type & delta = m_delta;
156  const csa_type & csa = m_csa;
157  const bit_vector & s = m_s;
158  const s_support_type & s_support = m_s_support;
159  const b_type & b = m_b;
160  const b_select_0_type & b_select_0 = m_b_select0;
161  const b_select_1_type & b_select_1 = m_b_select1;
162  const depth_type & depth_sampling = m_depth;
163  const lcp_type & lcp = m_lcp;
164 
166  cst_fully() = default;
167 
169  cst_fully(const cst_fully & cst)
170  : m_delta(cst.m_delta)
171  , m_nodes(cst.m_nodes)
172  , m_csa(cst.m_csa)
173  , m_s(cst.m_s)
174  , m_s_support(cst.m_s_support)
175  , m_b(cst.m_b)
176  , m_b_select0(cst.m_b_select0)
177  , m_b_select1(cst.m_b_select1)
178  , m_depth(cst.m_depth)
179  {
180  m_s_support.set_vector(&m_s);
181  m_b_select0.set_vector(&m_b);
182  m_b_select1.set_vector(&m_b);
183  }
184 
186  cst_fully(cst_fully && cst) { *this = std::move(cst); }
187 
189  cst_fully(cache_config & config);
190 
191  size_type size() const { return m_csa.size(); }
192 
193  static size_type max_size() { return t_csa::max_size(); }
194 
195  bool empty() const { return m_csa.empty(); }
196 
198  {
199  if (m_b.size() == 0) { return end(); }
200  return const_iterator(this, root(), false, true);
201  }
202 
203  const_iterator end() const { return const_iterator(this, root(), true, false); }
204 
207  {
208  if (this != &cst)
209  {
210  cst_fully tmp(cst);
211  *this = std::move(tmp);
212  }
213  return *this;
214  }
215 
218  {
219  if (this != &cst)
220  {
221  m_delta = cst.m_delta;
222  m_nodes = cst.m_nodes;
223  m_csa = std::move(cst.m_csa);
224  m_s = std::move(cst.m_s);
225  m_s_support = std::move(cst.m_s_support);
226  m_s_support.set_vector(&m_s);
227  m_b = std::move(cst.m_b);
228  m_b_select0 = std::move(cst.m_b_select0);
229  m_b_select0.set_vector(&m_b);
230  m_b_select1 = std::move(cst.m_b_select1);
231  m_b_select1.set_vector(&m_b);
232  m_depth = std::move(cst.m_depth);
233  }
234  return *this;
235  }
236 
238 
241  size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
242  {
243  structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
244  size_type written_bytes = 0;
245  written_bytes += write_member(m_delta, out, child, "m_delta");
246  written_bytes += write_member(m_nodes, out, child, "m_nodes");
247  written_bytes += m_csa.serialize(out, child, "csa");
248  written_bytes += m_s.serialize(out, child, "s");
249  written_bytes += m_s_support.serialize(out, child, "s_support");
250  written_bytes += m_b.serialize(out, child, "b");
251  written_bytes += m_b_select0.serialize(out, child, "b_select0");
252  written_bytes += m_b_select1.serialize(out, child, "b_select1");
253  written_bytes += m_depth.serialize(out, child, "depth");
254  structure_tree::add_size(child, written_bytes);
255  return written_bytes;
256  }
257 
259 
261  void load(std::istream & in)
262  {
263  read_member(m_delta, in);
264  read_member(m_nodes, in);
265  m_csa.load(in);
266  m_s.load(in);
267  m_s_support.load(in, &m_s);
268  m_b.load(in);
269  m_b_select0.load(in, &m_b);
270  m_b_select1.load(in, &m_b);
271  m_depth.load(in);
272  }
273 
274  template <typename archive_t>
275  void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
276  {
277  ar(CEREAL_NVP(m_delta));
278  ar(CEREAL_NVP(m_nodes));
279  ar(CEREAL_NVP(m_csa));
280  ar(CEREAL_NVP(m_s));
281  ar(CEREAL_NVP(m_s_support));
282  ar(CEREAL_NVP(m_b));
283  ar(CEREAL_NVP(m_b_select0));
284  ar(CEREAL_NVP(m_b_select1));
285  ar(CEREAL_NVP(m_depth));
286  }
287 
288  template <typename archive_t>
289  void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
290  {
291  ar(CEREAL_NVP(m_delta));
292  ar(CEREAL_NVP(m_nodes));
293  ar(CEREAL_NVP(m_csa));
294  ar(CEREAL_NVP(m_s));
295  ar(CEREAL_NVP(m_s_support));
296  m_s_support.set_vector(&m_s);
297  ar(CEREAL_NVP(m_b));
298  ar(CEREAL_NVP(m_b_select0));
299  m_b_select0.set_vector(&m_b);
300  ar(CEREAL_NVP(m_b_select1));
301  m_b_select1.set_vector(&m_b);
302  ar(CEREAL_NVP(m_depth));
303  }
304 
306  bool operator==(cst_fully const & other) const noexcept
307  {
308  return (m_delta == other.m_delta) && (m_nodes == other.m_nodes) && (m_csa == other.m_csa) &&
309  (m_s == other.m_s) && (m_s_support == other.m_s_support) && (m_b == other.m_b) &&
310  (m_b_select0 == other.m_b_select0) && (m_b_select1 == other.m_b_select1) && (m_depth == other.m_depth);
311  }
312 
314  bool operator!=(cst_fully const & other) const noexcept { return !(*this == other); }
315 
317  node_type root() const { return node_type(0, m_csa.size() - 1); }
318 
320  sampled_node_type sampled_root() const { return 0; }
321 
323  bool is_leaf(node_type v) const { return v.first == v.second; }
324 
326 
334  {
335  assert(i > 0 and i <= m_csa.size());
336  return node_type(i - 1, i - 1);
337  }
338 
341 
343  leaf_type lb(node_type v) const { return v.first; }
344 
346  leaf_type rb(node_type v) const { return v.second; }
347 
349 
354  size_type size(const node_type & v) const { return v.second - v.first + 1; }
355 
357 
362  node_type leftmost_leaf(const node_type v) const { return node_type(v.first, v.first); }
363 
365 
370  node_type rightmost_leaf(const node_type v) const { return node_type(v.second, v.second); }
371 
373  bool ancestor(node_type v, node_type w) const { return v.first <= w.first && v.second >= w.second; }
374 
376 
380  sampled_node_type pred(leaf_type v) const { return m_b_select0.select(v + 1) - v - 1; }
381 
383 
390  {
391  sampled_node_type p = pred(l);
392  if (m_s[p]) { return p; }
393  else
394  {
395  return m_s_support.enclose(m_s_support.find_open(p));
396  }
397  }
398 
400 
407  {
408  assert(m_s[u] == 1);
409  size_type u_end = m_s_support.find_close(u);
410  size_type b_left = m_b_select1.select(u + 1);
411  size_type b_right = m_b_select1.select(u_end + 1);
412 
413  return node_type(b_left - u, b_right - u_end - 1);
414  }
415 
417 
425  {
426  assert(m_s[u] == 1 and m_s[q] == 1);
427  if (u > q) { std::swap(u, q); }
428  else if (u == q)
429  {
430  return u;
431  }
432  if (u == sampled_root()) { return sampled_root(); }
433  if (m_s_support.find_close(u) > q) { return u; }
434 
435  return m_s_support.double_enclose(u, q);
436  }
437 
439 
446  {
447  assert(m_s[u] == 1);
448 
449  size_type idx = m_s_support.rank(u) - 1;
450  return m_depth[idx] * (m_delta / 2);
451  }
452 
454 
462  {
463  if (v == root()) // if v is the root
464  return 0;
465  else if (is_leaf(v))
466  {
467  return m_csa.size() - m_csa[v.first];
468  }
469 
470  size_type i;
472  return depth_lca(v.first, v.second, i, u);
473  }
474 
476 
484  {
485  leaf_type l = std::min(v.first, w.first);
486  leaf_type r = std::max(v.second, w.second);
487 
488  if (l == r) { return node_type(l, r); }
489  else
490  {
491  return lca(l, r);
492  }
493  }
494 
496 
504  {
505  assert(l < r);
506 
507  size_type i;
509  std::vector<char_type> c(delta, 0);
510  depth_lca(l, r, i, u, c);
511 
512  node_type v = sampled_node(u);
513  leaf_type lb = v.first;
514  leaf_type rb = v.second;
515 
516  for (size_type k = 0; k < i; k++) { backward_search(m_csa, lb, rb, c[i - k - 1], lb, rb); }
517 
518  return node_type(lb, rb);
519  }
520 
522 
532  // TODO: return by reference really necessary?
534  leaf_type r,
535  size_type & res_i,
536  sampled_node_type & res_u,
537  std::vector<char_type> & res_label) const
538  {
539  assert(l < r);
540 
541  size_type max_d = 0;
542  size_type max_d_i = 0;
543  sampled_node_type max_d_node = 0;
544 
545  for (size_type i = 0; i < m_delta; i++)
546  {
548  size_type d = i + depth(node);
549 
550  if (d > max_d)
551  {
552  max_d = d;
553  max_d_i = i;
554  max_d_node = node;
555  }
556 
557  char_type c = m_csa.F[l];
558  char_type comp = csa.char2comp[c];
559  res_label[i] = c;
560 
561  // break if LCA of lb and rb is root
562  if (l < m_csa.C[comp] || r >= m_csa.C[comp + 1]) { break; }
563 
564  l = m_csa.psi[l];
565  r = m_csa.psi[r];
566  }
567 
568  res_i = max_d_i;
569  res_u = max_d_node;
570 
571  return max_d;
572  }
573 
576  {
577  assert(l < r);
578 
579  size_type max_d = 0;
580  size_type max_d_i = 0;
581  sampled_node_type max_d_node = 0;
582 
583  for (size_type i = 0; i < m_delta; i++)
584  {
586  size_type d = i + depth(node);
587 
588  if (d > max_d)
589  {
590  max_d = d;
591  max_d_i = i;
592  max_d_node = node;
593  }
594 
595  char_type c = m_csa.F[l];
596  char_type comp = csa.char2comp[c];
597 
598  // break if LCA of lb and rb is root
599  if (l < m_csa.C[comp] || r >= m_csa.C[comp + 1]) { break; }
600 
601  l = m_csa.psi[l];
602  r = m_csa.psi[r];
603  }
604 
605  res_i = max_d_i;
606  res_u = max_d_node;
607 
608  return max_d;
609  }
610 
612 
619  {
620  if (v == root()) { return root(); }
621  else if (is_leaf(v))
622  {
623  size_t leaf = m_csa.psi[v.first];
624  return node_type(leaf, leaf);
625  }
626 
627  return lca(m_csa.psi[v.first], m_csa.psi[v.second]);
628  }
629 
631  /*
632  * \param v A valid node of a cst_fully.
633  * \param c The character which should be prepended to the string of the current node.
634  * \return root() if the Weiner link of (v, c) does not exist, otherwise the Weiner link is returned.
635  * \par Time complexity
636  * \f$ \Order{ t_{rank\_bwt} + t_{lca}}\f$
637  */
638  node_type wl(node_type v, const char_type c) const
639  {
640  size_type l, r;
641  std::tie(l, r) = v;
642  backward_search(m_csa, l, r, c, l, r);
643  return node_type(l, r);
644  }
645 
647 
653  {
654  assert(is_leaf(v));
655  return m_csa[v.first];
656  }
657 
659 
666  {
667  const leaf_type l = v.first;
668  const leaf_type r = v.second;
669 
670  node_type left_parent = root();
671  node_type right_parent = root();
672 
673  if (l > 0) { left_parent = lca(l - 1, r); }
674  if (r < m_csa.size() - 1) { right_parent = lca(l, r + 1); }
675  return ancestor(right_parent, left_parent) ? left_parent : right_parent;
676  }
677 
679 
688  {
689  if (is_leaf(v)) { return root(); }
690  size_type d = depth(v);
691  return child(v, c, d);
692  }
693 
695  {
696  leaf_type lower;
697  leaf_type upper;
698 
699  {
700  leaf_type begin = v.first;
701  leaf_type end = v.second + 1;
702 
703  while (begin < end)
704  {
705  leaf_type sample_pos = (begin + end) / 2;
706  size_type char_pos = get_char_pos(sample_pos, d, m_csa);
707  char_type sample = m_csa.F[char_pos];
708  if (sample < c) { begin = sample_pos + 1; }
709  else
710  {
711  end = sample_pos;
712  }
713  }
714 
715  lower = begin;
716  }
717 
718  {
719  leaf_type begin = v.first;
720  leaf_type end = v.second + 1;
721 
722  while (begin < end)
723  {
724  leaf_type sample_pos = (begin + end) / 2;
725  size_type char_pos = get_char_pos(sample_pos, d, m_csa);
726  char_type sample = m_csa.F[char_pos];
727  if (sample <= c) { begin = sample_pos + 1; }
728  else
729  {
730  end = sample_pos;
731  }
732  }
733 
734  upper = begin;
735  }
736 
737  if (lower == upper) { return root(); }
738 
739  return node_type(lower, upper - 1);
740  }
741 
743 
748  node_type select_child(node_type v, size_type i) const
749  {
750  if (is_leaf(v)) { return root(); }
751 
752  size_type d = depth(v);
753  size_type char_pos = get_char_pos(v.first, d, m_csa);
754  char_type c = m_csa.F[char_pos];
755  node_type res = child(v, c, d);
756  while (i > 1)
757  {
758  if (res.second >= v.second) { return root(); }
759  char_pos = get_char_pos(res.second + 1, d, m_csa);
760  c = m_csa.F[char_pos];
761  res = child(v, c, d);
762  i--;
763  }
764 
765  return res;
766  }
767 
769 
773  size_type degree(const node_type & v) const
774  {
775  if (is_leaf(v)) { return 0; }
776  else
777  {
778  size_type res = 1;
779  size_type d = depth(v);
780  size_type char_pos = get_char_pos(v.first, d, m_csa);
781  char_type c = m_csa.F[char_pos];
782  node_type v_i = child(v, c, d);
783  while (v_i.second < v.second)
784  {
785  ++res;
786  char_pos = get_char_pos(v_i.second + 1, d, m_csa);
787  c = m_csa.F[char_pos];
788  v_i = child(v, c, d);
789  }
790  return res;
791  }
792  }
793 
795 
798  cst_node_child_proxy<cst_fully> children(const node_type & v) const
799  {
800  return cst_node_child_proxy<cst_fully>(this, v);
801  }
802 
804 
808  node_type sibling(node_type v) const
809  {
810  node_type p = parent(v);
811  if (v.second >= p.second) { return root(); }
812  size_type d = depth(p);
813  size_type char_pos = get_char_pos(v.second + 1, d, m_csa);
814  char_type c = m_csa.F[char_pos];
815  return child(p, c, d);
816  }
817 
818  char_type edge(node_type v, size_type d) const
819  {
820  assert(d >= 1 and d <= depth(v));
821  size_type char_pos = get_char_pos(v.first, d - 1, m_csa);
822  return m_csa.F[char_pos];
823  }
824 
826 
830  size_type node_depth(node_type v) const
831  {
832  size_type d = 0;
833  while (v != root())
834  {
835  ++d;
836  v = parent(v);
837  }
838  return d;
839  }
840 
842  size_type nodes() const { return m_nodes; }
843 
845 
850  size_type sampled_nodes() const { return m_s.size() / 2; }
851 };
852 
853 template <class t_csa, uint32_t t_delta, class t_s_support, class t_b, class t_depth, bool t_sample_leaves>
855 {
856  // 1. Construct CST
857  cst_sada<csa_type, lcp_dac<>> cst(config);
858  m_nodes = cst.nodes();
859 
860  if (t_delta > 0) { m_delta = t_delta; }
861  else
862  {
863  const size_type n = cst.size();
864  m_delta = (bits::hi(n - 1) + 1) * (bits::hi(bits::hi(n - 1)) + 1);
865  if (m_delta < 2) { m_delta = 2; }
866  }
867 
868  size_type delta_half = m_delta / 2;
869 
870  bit_vector is_sampled(cst.nodes(), false);
871  is_sampled[cst.id(cst.root())] = true; // always sample root
872  size_type sample_count = 1;
873 
874  // 2a. Scan and mark leaves to be sampled
875  if (t_sample_leaves)
876  {
877  auto event = memory_monitor::event("scan-leaves");
878  size_type leaf_idx = 0;
879  for (size_type i = 0; i < cst.size(); i++)
880  {
881  const size_type d = i + 1;
882  if (d + delta_half <= cst.size() and d % delta_half == 0)
883  {
884  const auto node = cst.select_leaf(leaf_idx + 1);
885  const size_type id = cst.id(node);
886  if (!is_sampled[id])
887  {
888  is_sampled[id] = true;
889  sample_count++;
890  }
891  }
892  leaf_idx = cst.csa.lf[leaf_idx];
893  }
894  }
895 
896  // 2b. Scan and mark inner nodes to be sampled
897  {
898  auto event = memory_monitor::event("scan-nodes");
899  for (auto it = cst.begin(); it != cst.end(); ++it)
900  {
901  if (it.visit() == 1 and cst.is_leaf(*it) == false)
902  {
903  const auto node = *it;
904  const size_type d = cst.depth(node);
905  if (d % delta_half == 0)
906  {
907  auto v = cst.sl(node, delta_half);
908  const size_type id = cst.id(v);
909  if (!is_sampled[id])
910  {
911  is_sampled[id] = true;
912  sample_count++;
913  }
914  }
915  }
916  }
917  }
918 
919  m_s.resize(2 * sample_count);
920  util::set_to_value(m_s, 0);
921  // increase size of tmp_b resp. m_b by two if text is empty
922  bit_vector tmp_b(2 * sample_count + cst.size() + 2 * (cst.size() == 1), 0);
923  int_vector<64> tmp_depth;
924  tmp_depth.resize(sample_count);
925 
926  // 3. Create sampled tree data structures
927  {
928  auto event = memory_monitor::event("node-sampling");
929 
930  size_type s_idx = 0;
931  size_type b_idx = 0;
932  size_type sample_idx = 0;
933 
934  for (auto it = cst.begin(); it != cst.end(); ++it)
935  {
936  auto node = *it;
937  if (it.visit() == 1 && is_sampled[cst.id(node)])
938  {
939  m_s[s_idx++] = 1;
940  tmp_b[b_idx++] = 1;
941  tmp_depth[sample_idx++] = cst.depth(node) / delta_half;
942  }
943  if (cst.is_leaf(node)) { b_idx++; }
944  if ((cst.is_leaf(node) || it.visit() == 2) && is_sampled[cst.id(node)])
945  {
946  s_idx++;
947  tmp_b[b_idx++] = 1;
948  }
949  }
950  }
951 
952  {
953  auto event = memory_monitor::event("ss-depth");
954  m_csa = std::move(cst.csa);
955  util::init_support(m_s_support, &m_s);
956  m_b = b_type(tmp_b);
957  util::init_support(m_b_select0, &m_b);
958  util::init_support(m_b_select1, &m_b);
959  m_depth = depth_type(tmp_depth);
960  }
961 }
962 
963 } // end namespace sdsl
964 
965 #endif // INCLUDED_SDSL_CST_FULLY
bit_vectors.hpp contains classes for uncompressed and compressed bit vector representations.
bp_support.hpp contains several classed which support find_open, find_close, enclose and rr-enclose q...
#define CEREAL_NVP(X)
Definition: cereal.hpp:30
An forward iterator for (compressed) suffix trees.
A class for the Fully-Compressed Suffix Tree (FCST) proposed by Russo et al.
Definition: cst_fully.hpp:123
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serialize to a stream.
Definition: cst_fully.hpp:241
cst_dfs_const_forward_iterator< cst_fully > const_iterator
Definition: cst_fully.hpp:125
const bit_vector & s
Definition: cst_fully.hpp:157
bool ancestor(node_type v, node_type w) const
Returns true iff v is an ancestor of w.
Definition: cst_fully.hpp:373
node_type parent(node_type v) const
Calculate the parent node of a node v.
Definition: cst_fully.hpp:665
node_type wl(node_type v, const char_type c) const
Compute the Weiner link of node v and character c.
Definition: cst_fully.hpp:638
const b_select_1_type & b_select_1
Definition: cst_fully.hpp:161
node_type leftmost_leaf(const node_type v) const
Calculates the leftmost leaf in the subtree rooted at node v.
Definition: cst_fully.hpp:362
const s_support_type & s_support
Definition: cst_fully.hpp:158
bool is_leaf(node_type v) const
Returns true iff node v is a leaf.
Definition: cst_fully.hpp:323
leaf_type rb(node_type v) const
Returns the rightmost leaf (right boundary) of a node.
Definition: cst_fully.hpp:346
bool operator==(cst_fully const &other) const noexcept
Equality operator.
Definition: cst_fully.hpp:306
cst_tag index_category
Definition: cst_fully.hpp:140
t_csa::alphabet_category alphabet_category
Definition: cst_fully.hpp:139
const_iterator end() const
Definition: cst_fully.hpp:203
cst_fully()=default
Default constructor.
t_s_support s_support_type
Definition: cst_fully.hpp:133
t_b::select_1_type b_select_1_type
Definition: cst_fully.hpp:136
size_type depth_lca(leaf_type l, leaf_type r, size_type &res_i, sampled_node_type &res_u, std::vector< char_type > &res_label) const
Calculate the depth of the LCA of two leaves l and r.
Definition: cst_fully.hpp:533
node_type child(node_type v, char_type c) const
Get the child w of node v which edge label (v,w) starts with character c.
Definition: cst_fully.hpp:687
void load(std::istream &in)
Load from a stream.
Definition: cst_fully.hpp:261
leaf_type lb(node_type v) const
Returns the leftmost leaf (left boundary) of a node.
Definition: cst_fully.hpp:343
size_type sn(node_type v) const
Compute the suffix number of a leaf node v.
Definition: cst_fully.hpp:652
t_csa::size_type size_type
Definition: cst_fully.hpp:126
node_type sl(node_type v) const
Compute the suffix link of a node v.
Definition: cst_fully.hpp:618
size_type sampled_node_type
Definition: cst_fully.hpp:132
const lcp_type & lcp
Definition: cst_fully.hpp:163
const b_type & b
Definition: cst_fully.hpp:159
size_type size() const
Definition: cst_fully.hpp:191
size_type depth(node_type v) const
Returns the depth of a node v.
Definition: cst_fully.hpp:461
node_type lca(node_type v, node_type w) const
Calculate the LCA of two nodes v and w.
Definition: cst_fully.hpp:483
sampled_node_type sampled_root() const
Returns the root of the sampled tree.
Definition: cst_fully.hpp:320
node_type select_leaf(size_type i) const
Return the i-th leaf (1-based from left to right) of the suffix tree.
Definition: cst_fully.hpp:333
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Definition: cst_fully.hpp:275
size_type depth_lca(leaf_type l, leaf_type r, size_type &res_i, sampled_node_type &res_u) const
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition: cst_fully.hpp:575
cst_fully & operator=(cst_fully &&cst)
Move Assignment Operator.
Definition: cst_fully.hpp:217
const size_type & delta
Definition: cst_fully.hpp:155
cst_fully(const cst_fully &cst)
Copy constructor.
Definition: cst_fully.hpp:169
const depth_type & depth_sampling
Definition: cst_fully.hpp:162
sampled_node_type lsa_leaf(leaf_type l) const
Returns the LSA (lowest sampled ancestor) for a leaf with index l.
Definition: cst_fully.hpp:389
static size_type max_size()
Definition: cst_fully.hpp:193
const b_select_0_type & b_select_0
Definition: cst_fully.hpp:160
size_type depth(sampled_node_type u) const
Returns the depth of a sampled node u.
Definition: cst_fully.hpp:445
const csa_type & csa
Definition: cst_fully.hpp:156
sampled_node_type sampled_lca(sampled_node_type u, sampled_node_type q) const
Returns the LCA of two nodes in the sampled tree.
Definition: cst_fully.hpp:424
std::pair< size_type, size_type > node_type
Definition: cst_fully.hpp:130
bool empty() const
Definition: cst_fully.hpp:195
t_csa::char_type char_type
Definition: cst_fully.hpp:129
bool operator!=(cst_fully const &other) const noexcept
Inequality operator.
Definition: cst_fully.hpp:314
node_type child(node_type v, char_type c, size_type d) const
Definition: cst_fully.hpp:694
node_type lca(leaf_type l, leaf_type r) const
Calculate the LCA of two leaves l and r.
Definition: cst_fully.hpp:503
t_b::select_0_type b_select_0_type
Definition: cst_fully.hpp:135
node_type root() const
Returns the root of the suffix tree.
Definition: cst_fully.hpp:317
node_type sampled_node(sampled_node_type u) const
Returns the node in the suffix tree corresponding to the node u in the sampled tree.
Definition: cst_fully.hpp:406
node_type node(size_type lb, size_type rb) const
Get the node in the suffix tree which corresponds to the sa-interval [lb..rb].
Definition: cst_fully.hpp:340
cst_fully(cst_fully &&cst)
Move constructor.
Definition: cst_fully.hpp:186
size_type leaf_type
Definition: cst_fully.hpp:131
size_type size(const node_type &v) const
Calculate the number of leaves in the subtree rooted at node v.
Definition: cst_fully.hpp:354
sampled_node_type pred(leaf_type v) const
Returns the index of the last bracket in S before the leaf with index l.
Definition: cst_fully.hpp:380
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Definition: cst_fully.hpp:289
lcp_fully< cst_fully > lcp_type
Definition: cst_fully.hpp:128
node_type rightmost_leaf(const node_type v) const
Calculates the rightmost leaf in the subtree rooted at node v.
Definition: cst_fully.hpp:370
t_depth depth_type
Definition: cst_fully.hpp:137
cst_fully & operator=(const cst_fully &cst)
Copy Assignment Operator.
Definition: cst_fully.hpp:206
const_iterator begin() const
Definition: cst_fully.hpp:197
A class for the Compressed Suffix Tree (CST) proposed by Sadakane.
Definition: cst_sada.hpp:73
size_type id(node_type v) const
Computes a unique identification number for a node of the suffix tree in the range [0....
Definition: cst_sada.hpp:805
node_type select_leaf(size_type i) const
Return the i-th leaf (1-based from left to right) of the suffix tree.
Definition: cst_sada.hpp:443
const t_csa & csa
Definition: cst_sada.hpp:111
node_type sl(node_type v) const
Compute the suffix link of node v.
Definition: cst_sada.hpp:716
const_iterator begin() const
Returns a const_iterator to the first element.
Definition: cst_sada.hpp:270
size_type size() const
Number of leaves in the suffix tree.
Definition: cst_sada.hpp:252
bool is_leaf(node_type v) const
Decide if a node is a leaf in the suffix tree.
Definition: cst_sada.hpp:428
size_type nodes() const
Get the number of nodes of the suffix tree.
Definition: cst_sada.hpp:866
const_iterator end() const
Returns a const_iterator to the element after the last element.
Definition: cst_sada.hpp:288
node_type root() const
Return the root of the suffix tree.
Definition: cst_sada.hpp:419
size_type depth(node_type v) const
Returns the depth of node v.
Definition: cst_sada.hpp:457
void load(std::istream &in)
Load the int_vector for a stream.
size_type size() const noexcept
The number of elements in the int_vector.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the int_vector to a stream.
void resize(const size_type size)
Resize the int_vector in terms of elements.
Definition: int_vector.hpp:545
lcp_fully()=default
value_type operator[](size_type i) const
Definition: cst_fully.hpp:60
random_access_const_iterator< lcp_fully > const_iterator
Definition: cst_fully.hpp:32
lcp_fully(const t_cst *cst)
Definition: cst_fully.hpp:49
t_cst::size_type size_type
Definition: cst_fully.hpp:30
size_type size() const
Definition: cst_fully.hpp:58
lcp_fully(const lcp_fully &)=default
lcp_tag lcp_category
Definition: cst_fully.hpp:35
const_iterator end() const
Returns a const_iterator to the element after the last element.
Definition: cst_fully.hpp:80
const_iterator iterator
Definition: cst_fully.hpp:33
lcp_fully & operator=(const lcp_fully &)=default
size_type value_type
Definition: cst_fully.hpp:31
const_iterator begin() const
Returns a const_iterator to the first element.
Definition: cst_fully.hpp:77
lcp_fully & operator=(lcp_fully &&)=default
lcp_fully(lcp_fully &&)=default
~lcp_fully()=default
static mm_event_proxy event(const std::string &name)
Generic iterator for a random access container.
Definition: iterators.hpp:24
static void add_size(structure_tree_node *v, uint64_t value)
static structure_tree_node * add_child(structure_tree_node *v, const std::string &name, const std::string &type)
construct.hpp contains methods to construct indexes (compressed suffix arrays and trees).
cst_iterators.hpp contains iterator classes for traversing (compressed) suffix arrays.
cst_sada.hpp contains an implementation of Sadakane's CST.
int_vector ::size_type size_type
uint64_t id()
void set_to_value(t_int_vec &v, uint64_t k)
Set all entries of int_vector to value k.
Definition: util.hpp:566
Namespace for the succinct data structure library.
t_csa::size_type get_char_pos(typename t_csa::size_type idx, typename t_csa::size_type d, const t_csa &csa)
void swap(int_vector_reference< t_int_vector > x, int_vector_reference< t_int_vector > y) noexcept
Definition: int_vector.hpp:970
size_t write_member(const T &t, std::ostream &out, sdsl::structure_tree_node *v=nullptr, std::string name="")
Definition: io.hpp:84
void read_member(T &t, std::istream &in)
Definition: io.hpp:111
t_csa::size_type backward_search(const t_csa &csa, typename t_csa::size_type l, typename t_csa::size_type r, typename t_csa::char_type c, typename t_csa::size_type &l_res, typename t_csa::size_type &r_res, SDSL_UNUSED typename std::enable_if< std::is_same< csa_tag, typename t_csa::index_category >::value, csa_tag >::type x=csa_tag())
Backward search for a character c in an -interval in the CSA.
Contains declarations and definitions of data structure concepts.
static SDSL_CONSTEXPR uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Definition: bits.hpp:661
Helper class for construction process.
Definition: config.hpp:67
suffix_arrays.hpp contains generic classes for different suffix array classes.
suffix_tree_algorithm.hpp contains algorithms on CSTs
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.