SDSL  3.0.0
Succinct Data Structure Library
cst_sct3.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_SCT3
9 #define INCLUDED_SDSL_CST_SCT3
10 
11 #include <algorithm>
12 #include <cassert>
13 #include <cstring> // for strlen
14 #include <iomanip>
15 #include <iostream>
16 #include <iterator>
17 #include <ostream>
18 #include <stack> // for the calculation of the balanced parentheses sequence
19 
20 #include <sdsl/bp_support.hpp>
21 #include <sdsl/construct.hpp>
22 #include <sdsl/csa_wt.hpp> // for std initialization of cst_sct3
23 #include <sdsl/cst_iterators.hpp>
24 #include <sdsl/int_vector.hpp>
25 #include <sdsl/iterators.hpp>
26 #include <sdsl/lcp.hpp>
27 #include <sdsl/rank_support.hpp>
28 #include <sdsl/sdsl_concepts.hpp>
29 #include <sdsl/select_support.hpp>
32 #include <sdsl/util.hpp>
33 
34 #include <type_traits>
35 
36 namespace sdsl
37 {
38 
39 // Declaration of the CST's node type
41 struct bp_interval;
42 
44 
77 template <class t_csa = csa_wt<>,
78  class t_lcp = lcp_dac<>,
79  class t_bp_support = bp_support_sada<>,
80  class t_bv = bit_vector,
81  class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value,
82  rank_support_v5<>,
83  typename t_bv::rank_1_type>::type,
84  class
85  t_sel = typename std::conditional<std::is_same<t_bv,
86  bit_vector>::value and std::is_same<typename t_csa::alphabet_category,
87  byte_alphabet_tag>::value,
88  select_support_scan<>,
89  typename t_bv::select_1_type>::type>
90 class cst_sct3
91 {
92  static_assert(std::is_same<typename index_tag<t_csa>::type, csa_tag>::value,
93  "First template argument has to be a compressed suffix array.");
94 
95  public:
98  typedef typename t_csa::size_type size_type;
99  typedef ptrdiff_t difference_type;
100  typedef t_csa csa_type;
101  typedef typename t_lcp::template type<cst_sct3> lcp_type;
102  typedef t_bp_support bp_support_type;
103  typedef typename t_csa::char_type char_type;
104  typedef typename t_csa::string_type string_type;
106  typedef t_bv bv_type;
107  typedef t_rank rank_type;
108  typedef t_sel sel_type;
109 
110  typedef typename t_csa::alphabet_type::comp_char_type comp_char_type;
111  typedef typename t_csa::alphabet_type::sigma_type sigma_type;
112 
113  typedef typename t_csa::alphabet_category alphabet_category;
115 
116  private:
117  csa_type m_csa;
118  lcp_type m_lcp;
119  bit_vector m_bp;
120  bp_support_type m_bp_support;
121  bv_type m_first_child;
122  rank_type m_first_child_rank;
123  sel_type m_first_child_select;
124  size_type m_nodes;
125 
126  // Get the first l index of a [i,j] interval.
127  /* I.e. given an interval [i,j], the function returns the position of
128  * the smallest entry lcp[k] with \f$ i<k\leq j \f$
129  * \par Time complexity
130  * \f$ \Order{1} \f$
131  */
132  inline size_type first_l_index(const node_type & node, size_type & kpos, size_type & ckpos) const
133  {
134  if (node.cipos > node.jp1pos)
135  { // corresponds to m_lcp[i] <= m_lcp[j+1]
136  ckpos = node.jp1pos - 1;
137  }
138  else
139  { // corresponds to m_lcp[i] > m_lcp[j+1]
140  ckpos = node.cipos - 1;
141  }
142  assert(m_bp[ckpos] == 0);
143  kpos = m_bp_support.find_open(ckpos);
144  return m_bp_support.rank(kpos) - 1;
145  }
146 
147  // Get the i-th l-index of a node
148  // if there exists no ith l-index return node.j+1
149  /* \param v Node
150  * \param i l-index in [1..degree()]
151  * \paran
152  */
153  size_type select_l_index(const node_type & v, size_type i, size_type & kpos, size_type & ckpos) const
154  {
155  assert(i > 0);
156  if (v.cipos > v.jp1pos)
157  { // corresponds to m_lcp[i] <= m_lcp[j+1]
158  ckpos = v.jp1pos - 1;
159  }
160  else
161  { // corresponds to m_lcp[i] > m_lcp[j+1]
162  ckpos = v.cipos - 1;
163  }
164  assert(m_bp[ckpos] == 0); // at least the first l-index should be present, i.e. node is not leaf
165  if (1 == i)
166  {
167  kpos = m_bp_support.find_open(ckpos);
168  return m_bp_support.rank(kpos) - 1;
169  }
170  else
171  { // i > 1
172  // numbers of closing parentheses - 1 = index of first child in m_first_child
173  size_type r = ckpos - m_bp_support.rank(ckpos);
174  if (r + 1 >= i)
175  { // if there exist more than i l-indices
176  // check if m_first_child[r-i+1..r-1] consists of zeros
177  if (i < degree(v))
178  { // there exists an i-th l-index
179  ckpos -= (i - 1);
180  assert(m_bp[ckpos] == 0);
181  kpos = m_bp_support.find_open(ckpos);
182  return m_bp_support.rank(kpos) - 1;
183  }
184  }
185  // if i >= degree(node)
186  kpos = v.jp1pos;
187  if (kpos < m_bp.size())
188  ckpos = m_bp_support.find_close(kpos);
189  else
190  ckpos = m_bp.size();
191  return v.j + 1;
192  }
193  }
194 
195  // Position of the first l-index of a l-[i,j] interval in the BP.
196  /* \par Time complexity
197  * \f$ \Order{1} \f$
198  */
199  inline size_type closing_pos_of_first_l_index(const node_type & node) const
200  {
201  if (node.cipos > node.jp1pos)
202  { // corresponds to m_lcp[i] <= m_lcp[j+1]
203  return node.jp1pos - 1;
204  }
205  else
206  { // corresponds to m_lcp[i] > m_lcp[j+1]
207  return node.cipos - 1;
208  }
209  }
210 
211  // Get the next smaller value.
212  /*
213  * \param i Position in the original vector.
214  * \param ipos Position of the corresponding opening parenthesis in BP.
215  * \return Position of the next smaller value in [i+1..n-1], and n when
216  * no such value exists.
217  * \par Time complexity
218  * \f$ \Order{1} \f$
219  */
220  // possible optimization: calculate also position of nsv,
221  // i.e. next ( following position cipos
222  inline size_type nsv(SDSL_UNUSED size_type i, size_type ipos) const
223  {
224  size_type cipos = m_bp_support.find_close(ipos);
225  size_type result = m_bp_support.rank(cipos);
226  return result;
227  }
228 
229  // Get the previous smaller value.
230  /*
231  * \param i Position in the original vector.
232  * \param ipos Corresponding opening parenthesis in m_bp
233  * \param cipos Corresponding closing parenthesis to ipos
234  * \par Time complexity
235  * \f$ \Order{\frac{\sigma}{w}} \f$, where w=64 is the word size,
236  * can be implemented in \f$\Order{1}\f$ with rank and select.
237  */
238  inline size_type psv(SDSL_UNUSED size_type i,
239  size_type ipos,
240  size_type cipos,
241  size_type & psvpos,
242  size_type & psvcpos) const
243  {
244  // if lcp[i]==0 => psv is the 0-th index by definition
245  if ((cipos + (size_type)m_csa.sigma) >= m_bp.size())
246  {
247  psvpos = 0;
248  psvcpos = m_bp.size() - 1;
249  return 0;
250  }
251  if (m_bp[cipos + 1])
252  {
253  psvpos = m_bp_support.enclose(ipos);
254  psvcpos = m_bp_support.find_close(psvpos);
255  return m_bp_support.rank(psvpos) - 1;
256  }
257  // r0 = index of clothing parenthesis in m_first_child
258  size_type r0 = cipos - m_bp_support.rank(cipos);
259  size_type next_first_child = 0;
260  const uint64_t * p = m_first_child.data() + (r0 >> 6);
261  uint64_t w = (*p) >> (r0 & 0x3F);
262  if (w)
263  { // if w!=0
264  next_first_child = cipos + bits::lo(w);
265  if (cipos == next_first_child and m_bp[next_first_child + 1])
266  {
267  psvpos = m_bp_support.enclose(ipos);
268  psvcpos = m_bp_support.find_close(psvpos);
269  return m_bp_support.rank(psvpos) - 1;
270  }
271  }
272  else
273  {
274  size_type delta = 63 - (r0 & 0x3F);
275  ++p;
276  int steps = 4;
277  while (!(w = *p) and steps-- > 0)
278  { // while w==0
279  ++p;
280  delta += 64;
281  }
282  if (w != 0) { delta += bits::lo(w) + 1; }
283  else
284  {
285  auto pos = m_first_child_select(m_first_child_rank(r0 + 1) + 1);
286  delta = pos - r0;
287  }
288  next_first_child = cipos + delta;
289  }
290  if (!m_bp[next_first_child + 1])
291  { // if next parenthesis is a closing one
292  psvcpos = next_first_child + 1;
293  psvpos = m_bp_support.find_open(psvcpos);
294  return m_bp_support.rank(psvpos) - 1;
295  }
296  else
297  {
298  psvpos = m_bp_support.enclose(m_bp_support.find_open(next_first_child));
299  psvcpos = m_bp_support.find_close(psvpos);
300  return m_bp_support.rank(psvpos) - 1;
301  }
302  }
303 
304  // Range minimum query based on the rr_enclose method.
305  /* \par Time complexity
306  * \f$ \Order{\rrenclose} \f$
307  */
308  inline size_type rmq(size_type l, size_type r) const
309  {
310  size_type i = m_bp_support.select(l + 1);
311  size_type j = m_bp_support.select(r + 1);
312  size_type fc_i = m_bp_support.find_close(i);
313  if (j < fc_i)
314  { // i < j < find_close(j) < find_close(i)
315  return l;
316  }
317  else
318  { // i < find_close(i) < j < find_close(j)
319  size_type ec = m_bp_support.rr_enclose(i, j);
320  if (ec == m_bp_support.size())
321  { // no restricted enclosing pair found
322  return r;
323  }
324  else
325  { // found range restricted enclosing pair
326  return m_bp_support.rank(ec) - 1; // subtract 1, as the index is 0 based
327  }
328  }
329  }
330 
331  public:
332  const csa_type & csa = m_csa;
333  const lcp_type & lcp = m_lcp;
334  const bit_vector & bp = m_bp;
335  const bp_support_type & bp_support = m_bp_support;
336 
337  const bv_type & first_child_bv = m_first_child;
338  const rank_type & first_child_rank = m_first_child_rank;
339  const sel_type & first_child_select = m_first_child_select;
340 
342  /* @{ */
343 
345  cst_sct3() = default;
346 
348  cst_sct3(cache_config & cache, bool build_only_bps = false);
349 
351 
356  cst_sct3(const cst_sct3 & cst)
357  : m_csa(cst.m_csa)
358  , m_bp(cst.m_bp)
359  , m_bp_support(cst.m_bp_support)
360  , m_first_child(cst.m_first_child)
361  , m_first_child_rank(cst.m_first_child_rank)
362  , m_first_child_select(cst.m_first_child_select)
363  , m_nodes(cst.m_nodes)
364  {
365  copy_lcp(m_lcp, cst.m_lcp, *this);
366  m_bp_support.set_vector(&m_bp);
367  m_first_child_rank.set_vector(&m_first_child);
368  m_first_child_select.set_vector(&m_first_child);
369  }
370 
372 
376  : m_csa(std::move(cst.m_csa))
377  , m_bp(std::move(cst.m_bp))
378  , m_bp_support(std::move(cst.m_bp_support))
379  , m_first_child(std::move(cst.m_first_child))
380  , m_first_child_rank(std::move(cst.m_first_child_rank))
381  , m_first_child_select(std::move(cst.m_first_child_select))
382  , m_nodes(cst.m_nodes)
383  {
384  move_lcp(m_lcp, cst.m_lcp, *this);
385  m_bp_support.set_vector(&m_bp);
386  m_first_child_rank.set_vector(&m_first_child);
387  m_first_child_select.set_vector(&m_first_child);
388  }
389 
390  /* @} */
391 
393 
396  size_type size() const { return m_bp.size() >> 1; }
397 
399 
402  static size_type max_size() { return t_csa::max_size(); }
403 
405 
408  bool empty() const { return m_csa.empty(); }
409 
411 
415  {
416  if (0 == m_bp.size()) // special case: tree is uninitialized
417  return end();
418  return const_iterator(this, root(), false, true);
419  };
420 
422  const_iterator begin(const node_type & v) const
423  {
424  if (0 == m_bp.size() and root() == v) return end();
425  return const_iterator(this, v, false, true);
426  }
427 
429 
432  const_iterator end() const { return const_iterator(this, root(), true, false); }
433 
435  const_iterator end(const node_type & v) const
436  {
437  if (root() == v) return end();
438  return ++const_iterator(this, v, true, true);
439  }
440 
443  {
444  if (0 == m_bp.size()) // special case: tree is uninitialized
445  return end_bottom_up();
447  }
448 
451 
453 
456  cst_sct3 & operator=(const cst_sct3 & cst)
457  {
458  if (this != &cst)
459  {
460  cst_sct3 tmp(cst);
461  *this = std::move(tmp);
462  }
463  return *this;
464  }
465 
467 
471  {
472  if (this != &cst)
473  {
474  m_csa = std::move(cst.m_csa);
475  move_lcp(m_lcp, cst.m_lcp, *this);
476  m_bp = std::move(cst.m_bp);
477  m_bp_support = std::move(cst.m_bp_support);
478  m_bp_support.set_vector(&m_bp);
479  m_first_child = std::move(cst.m_first_child);
480  m_first_child_rank = std::move(cst.m_first_child_rank);
481  m_first_child_rank.set_vector(&m_first_child);
482  m_first_child_select = std::move(cst.m_first_child_select);
483  m_first_child_select.set_vector(&m_first_child);
484  m_nodes = std::move(cst.m_nodes);
485  }
486  return *this;
487  }
488 
490 
493  size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const;
494 
496 
498  void load(std::istream & in);
499 
501  template <typename archive_t>
502  void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const;
503 
505  template <typename archive_t>
506  void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar);
507 
509  bool operator==(cst_sct3 const & other) const noexcept
510  {
511  return (m_csa == other.m_csa) && (m_lcp == other.m_lcp) && (m_bp == other.m_bp) &&
512  (m_bp_support == other.m_bp_support) && (m_first_child == other.m_first_child) &&
513  (m_first_child_rank == other.m_first_child_rank) &&
514  (m_first_child_select == other.m_first_child_select) /*&& (m_nodes == other.m_nodes)*/;
515  }
516 
518  bool operator!=(cst_sct3 const & other) const noexcept { return !(*this == other); }
519 
521  /* @{ */
522 
524 
528  node_type root() const { return node_type(0, size() - 1, 0, m_bp.size() - 1, m_bp.size()); }
529 
531 
537  bool is_leaf(const node_type & v) const { return v.i == v.j; }
538 
540 
548  {
549  assert(i > 0 and i <= size());
550  size_type ipos = m_bp_support.select(i);
551  size_type jp1pos;
552  if (i == size())
553  jp1pos = m_bp.size();
554  else if (m_bp[ipos + 1])
555  jp1pos = ipos + 1;
556  else
557  jp1pos = m_bp_support.select(i + 1);
558  return node_type(i - 1, i - 1, ipos, m_bp_support.find_close(ipos), jp1pos);
559  }
560 
562 
567  size_type size(const node_type & v) const { return v.j - v.i + 1; }
568 
570 
575  node_type leftmost_leaf(const node_type & v) const { return select_leaf(v.i + 1); }
576 
578 
583  node_type rightmost_leaf(const node_type & v) const { return select_leaf(v.j + 1); }
584 
586 
593  size_type lb(const node_type & v) const { return v.i; }
594 
596 
603  size_type rb(const node_type & v) const { return v.j; }
604 
606 
611  node_type parent(const node_type & v) const
612  {
613  if (v.cipos > v.jp1pos)
614  { // LCP[i] <= LCP[j+1]
615  size_type psv_pos, psv_cpos, psv_v, nsv_v, nsv_p1pos;
616  psv_v = psv(v.j + 1, v.jp1pos, m_bp_support.find_close(v.jp1pos), psv_pos, psv_cpos);
617  nsv_v = nsv(v.j + 1, v.jp1pos) - 1;
618  if (nsv_v == size() - 1) { nsv_p1pos = m_bp.size(); }
619  else
620  { // nsv_v < size()-1
621  nsv_p1pos = m_bp_support.select(nsv_v + 2);
622  }
623  return node_type(psv_v, nsv_v, psv_pos, psv_cpos, nsv_p1pos);
624  }
625  else
626  { // LCP[i] > LCP[j+1]
627  size_type psv_pos, psv_cpos, psv_v;
628  psv_v = psv(v.i, v.ipos, v.cipos, psv_pos, psv_cpos);
629  return node_type(psv_v, v.j, psv_pos, psv_cpos, v.jp1pos);
630  }
631  }
632 
634 
640  {
641  return cst_node_child_proxy<cst_sct3>(this, v);
642  }
643 
645 
651  node_type sibling(const node_type & v) const
652  {
653  // Procedure:(1) Determine, if v has a right sibling.
654  if (v.cipos < v.jp1pos)
655  { // LCP[i] > LCP[j+1] => v has the same right border as parent(v) => no right sibling
656  return root();
657  }
658  // (2) There exists a right sibling, LCP[j+1] >= LCP[i] and j>i
659  // Now it holds: v.cipos > v.jp1pos
660  size_type cjp1posm1 = m_bp_support.find_close(v.jp1pos) - 1; // v.cipos-2 ???
661  // m_bp[cjp1posm1] equals 1 => v is the last child
662  bool last_child = m_bp[cjp1posm1];
663  // otherwise if m_bp[cjp1posm1] equals 0 => we don't know if it is the last child
664  if (!last_child)
665  {
666  size_type first_child_idx = cjp1posm1 - m_bp_support.rank(cjp1posm1);
667  last_child = m_first_child[first_child_idx]; // if first_child indicator is true => the new sibling is the
668  // rightmost sibling
669  }
670  if (last_child)
671  {
672  size_type nsv_v = nsv(v.j + 1, v.jp1pos) - 1, nsv_p1pos;
673  if (nsv_v == size() - 1) { nsv_p1pos = m_bp.size(); }
674  else
675  {
676  nsv_p1pos = m_bp_support.select(nsv_v + 2);
677  }
678  return node_type(v.j + 1, nsv_v, v.jp1pos, m_bp_support.find_close(v.jp1pos), nsv_p1pos);
679  }
680  else
681  {
682  size_type new_j = m_bp_support.rank(m_bp_support.find_open(cjp1posm1)) - 2;
683  return node_type(v.j + 1,
684  new_j,
685  v.jp1pos,
686  m_bp_support.find_close(v.jp1pos),
687  m_bp_support.select(new_j + 2));
688  }
689  }
690 
692 
703  {
704  assert(i > 0);
705  if (is_leaf(v)) // if v is a leave, v has no child
706  return root();
707  if (1 == i)
708  {
709  size_type k = 0, kpos = 0, k_find_close = 0;
710  // v is not a leave: v has at least two children
711  k = select_l_index(v, 1, kpos, k_find_close); // get first l-index k and the position of k
712  return node_type(v.i, k - 1, v.ipos, v.cipos, kpos);
713  }
714  else
715  { // i > 1
716  size_type k1, kpos1, k_find_close1;
717  k1 = select_l_index(v, i - 1, kpos1, k_find_close1);
718  if (k1 == v.j + 1) return root();
719  size_type k2, kpos2, k_find_close2;
720  k2 = select_l_index(v, i, kpos2, k_find_close2);
721  return node_type(k1, k2 - 1, kpos1, k_find_close1, kpos2);
722  }
723  }
724 
726 
733  size_type degree(const node_type & v) const
734  {
735  if (is_leaf(v)) // if v is a leave, v has no child
736  return 0;
737  // v is not a leave: v has at least two children
738  size_type r = closing_pos_of_first_l_index(v);
739  size_type r0 = r - m_bp_support.rank(r);
740  const uint64_t * p = m_first_child.data() + (r0 >> 6);
741  uint8_t offset = r0 & 0x3F;
742 
743  uint64_t w = (*p) & bits::lo_set[offset];
744  if (w)
745  { // if there is a bit set in the current word
746  return offset - bits::hi(w) + 1;
747  }
748  else if (m_first_child.data() == p)
749  { // no bit set and we are in the first word
750  return offset + 2; // since would have to be bits::hi(w)=-1, child marked in previous word
751  }
752  else
753  {
754  size_type res = offset + 2;
755  int steps = 4;
756  // search in previous four words for result
757  while (p > m_first_child.data() and steps-- > 0)
758  {
759  w = *(--p);
760  if (0 == w)
761  res += 64;
762  else
763  {
764  return res + (63 - bits::hi(w));
765  }
766  }
767  // if not found: use rank + select to answer query
768  auto goal_rank = m_first_child_rank(r0);
769  if (goal_rank == 0) { return r0 + 2; }
770  else
771  {
772  return r0 - m_first_child_select(goal_rank) + 1;
773  }
774  }
775  }
776 
778 
788  node_type child(const node_type & v, const char_type c, size_type & char_pos) const
789  {
790  if (is_leaf(v)) // if v is a leaf = (), v has no child
791  return root();
792  // else v = ( ( ))
793  comp_char_type cc = m_csa.char2comp[c];
794  if (cc == 0 and c != 0) // TODO: change char2comp so that we don't need this special case
795  return root();
796  size_type char_ex_max_pos = m_csa.C[((size_type)1) + cc], char_inc_min_pos = m_csa.C[cc];
797 
798  size_type d = depth(v);
799 
800  // (1) check the first child
801  char_pos = get_char_pos(v.i, d, m_csa);
802  if (char_pos >= char_ex_max_pos)
803  { // the first character of the first child interval is lex. greater than c
804  // => all other first characters of the child intervals are also greater than c => no solution
805  return root();
806  }
807  else if (char_pos >= char_inc_min_pos)
808  { // i.e. char_pos < char_ex_max_pos and char_pos >= char_inc_min_pos
809  return select_child(v, 1);
810  }
811 
812  size_type child_cnt = degree(v);
813 
814  // (2) check the last child
815  char_pos = get_char_pos(v.j, d, m_csa);
816  if (char_pos < char_inc_min_pos)
817  { // the first character of the last child interval is lex. smaller than c
818  // => all other first characters of the child intervals are also smaller than c => no solution
819  return root();
820  }
821  else if (char_pos < char_ex_max_pos)
822  { // i.e. char_pos < char_ex_max_pos and char_pos >= char_inc_min_pos
823  return select_child(v, child_cnt);
824  }
825 
826  // (3) binary search for c in the children [2..children)
827  size_type l_bound = 2, r_bound = child_cnt, mid, kpos, ckpos, l_index;
828  while (l_bound < r_bound)
829  {
830  mid = (l_bound + r_bound) >> 1;
831 
832  l_index = select_l_index(v, mid - 1, kpos, ckpos);
833  char_pos = get_char_pos(l_index, d, m_csa);
834 
835  if (char_inc_min_pos > char_pos) { l_bound = mid + 1; }
836  else if (char_ex_max_pos <= char_pos)
837  {
838  r_bound = mid;
839  }
840  else
841  { // char_inc_min_pos <= char_pos < char_ex_max_pos => found child
842  // we know that the child is not the last child, see (2)
843  // find next l_index: we know that a new l_index exists: i.e. assert( 0 == m_bp[ckpos-1]);
844  size_type lp1_index = m_bp_support.rank(m_bp_support.find_open(ckpos - 1)) - 1;
845  size_type jp1pos = m_bp.size();
846  if (lp1_index - 1 < size() - 1) { jp1pos = m_bp_support.select(lp1_index + 1); }
847  return node_type(l_index, lp1_index - 1, kpos, ckpos, jp1pos);
848  }
849  }
850  return root();
851  }
852 
854  // \sa child(node_type v, const char_type c, size_type &char_pos)
855  node_type child(const node_type & v, const char_type c) const
856  {
857  size_type char_pos;
858  return child(v, c, char_pos);
859  }
860 
862 
870  char_type edge(const node_type & v, size_type d) const
871  {
872  assert(1 <= d);
873  assert(d <= depth(v));
874  size_type order = get_char_pos(v.i, d - 1, m_csa);
875  size_type c_begin = 1, c_end = ((size_type)m_csa.sigma) + 1, mid;
876  while (c_begin < c_end)
877  {
878  mid = (c_begin + c_end) >> 1;
879  if (m_csa.C[mid] <= order) { c_begin = mid + 1; }
880  else
881  {
882  c_end = mid;
883  }
884  }
885  return m_csa.comp2char[c_begin - 1];
886  }
887 
889 
898  {
899  if (v.i > w.i or (v.i == w.i and v.j < w.j)) { std::swap(v, w); }
900  if (v.j >= w.j)
901  { // v encloses w or v==w
902  return v;
903  }
904  else
905  { // v.i < v.j < w.i < w.j
906  size_type min_index = rmq(v.i + 1, w.j);
907  size_type min_index_pos = m_bp_support.select(min_index + 1);
908  size_type min_index_cpos = m_bp_support.find_close(min_index_pos);
909 
910  if (min_index_cpos >= (m_bp.size() - m_csa.sigma))
911  { // if lcp[min_index]==0 => return root
912  return root();
913  }
914  size_type new_j = nsv(min_index, min_index_pos) - 1;
915  size_type new_ipos, new_icpos;
916  size_type new_i = psv(min_index, min_index_pos, min_index_cpos, new_ipos, new_icpos);
917  size_type jp1pos = m_bp.size();
918  if (new_j < size() - 1) { jp1pos = m_bp_support.select(new_j + 2); }
919  return node_type(new_i, new_j, new_ipos, new_icpos, jp1pos);
920  }
921  }
922 
924 
930  size_type depth(const node_type & v) const
931  {
932  if (v == root()) { return 0; }
933  else if (v.i == v.j)
934  {
935  return size() - m_csa[v.i];
936  }
937  else
938  {
939  size_type kpos, ckpos;
940  size_type l = select_l_index(v, 1, kpos, ckpos);
941  return m_lcp[l];
942  }
943  }
944 
946 
958  {
959  size_type d = 0;
960  while (v != root())
961  {
962  ++d;
963  v = parent(v);
964  }
965  return d;
966  }
967 
969 
975  node_type sl(const node_type & v) const
976  {
977  if (v == root()) return root();
978  // get interval with first char deleted
979  size_type i = m_csa.psi[v.i];
980  if (is_leaf(v))
981  {
982  if (v.i == 0 and v.j == 0) // if( v.l==1 )
983  return root();
984  else
985  return select_leaf(i + 1);
986  }
987  size_type j = m_csa.psi[v.j];
988  assert(i < j);
989  size_type min_index = rmq(i + 1, j); // rmq
990  size_type min_index_pos = m_bp_support.select(min_index + 1);
991  size_type min_index_cpos = m_bp_support.find_close(min_index_pos);
992  if (min_index_cpos >= (m_bp.size() - m_csa.sigma))
993  { // if lcp[min_index]==0 => return root
994  return root();
995  }
996  size_type new_j = nsv(min_index, min_index_pos) - 1;
997  size_type new_ipos, new_icpos;
998  size_type new_i = psv(min_index, min_index_pos, min_index_cpos, new_ipos, new_icpos);
999  size_type jp1pos = m_bp.size();
1000  if (new_j < size() - 1) { jp1pos = m_bp_support.select(new_j + 2); }
1001  return node_type(new_i, new_j, new_ipos, new_icpos, jp1pos);
1002  }
1003 
1005 
1013  node_type wl(const node_type & v, const char_type c) const
1014  {
1015  size_type c_left = m_csa.bwt.rank(v.i, c);
1016  size_type c_right = m_csa.bwt.rank(v.j + 1, c);
1017  if (c_left == c_right) // there exists no Weiner link
1018  return root();
1019  if (c_left + 1 == c_right)
1020  return select_leaf(m_csa.C[m_csa.char2comp[c]] + c_left + 1);
1021  else
1022  {
1023  size_type left = m_csa.C[m_csa.char2comp[c]] + c_left;
1024  size_type right = m_csa.C[m_csa.char2comp[c]] + c_right - 1;
1025  assert(left < right);
1026 
1027  size_type ipos = m_bp_support.select(left + 1);
1028  size_type jp1pos = m_bp.size();
1029  if (right < size() - 1) { jp1pos = m_bp_support.select(right + 2); }
1030  return node_type(left, right, ipos, m_bp_support.find_close(ipos), jp1pos);
1031  }
1032  }
1033 
1035 
1040  size_type sn(const node_type & v) const
1041  {
1042  assert(is_leaf(v));
1043  return m_csa[v.i];
1044  }
1045 
1047 
1053  size_type id(const node_type & v) const
1054  {
1055  if (is_leaf(v))
1056  { // return id in the range from 0..csa.size()-1
1057  return v.i;
1058  }
1059  size_type ckpos; // closing parentheses of the l-index
1060  if (v.cipos > v.jp1pos)
1061  { // corresponds to m_lcp[i] <= m_lcp[j+1]
1062  ckpos = v.jp1pos - 1;
1063  }
1064  else
1065  { // corresponds to m_lcp[i] > m_lcp[j+1]
1066  ckpos = v.cipos - 1;
1067  }
1068  assert(m_bp[ckpos] == 0);
1069  size_type r0ckpos = ckpos - m_bp_support.rank(ckpos); // determine the rank of the closing parenthesis
1070  return size() + m_first_child_rank(r0ckpos);
1071  }
1072 
1074 
1082  {
1083  if (id < size())
1084  { // the corresponding node is a leaf
1085  return select_leaf(id + 1);
1086  }
1087  else
1088  { // the corresponding node is a inner node
1089  // (1) get index of the closing parenthesis in m_first_child
1090  size_type r0ckpos = 0;
1091  {
1092  // binary search for the position of the (id-size()+1)-th set bit in
1093  id = id - size() + 1;
1094  size_type lb = 0, rb = m_bp.size(); // lb inclusive, rb exclusive
1095  // invariant: arg(lb) < id, arg(rb) >= id
1096  while (rb - lb > 1)
1097  {
1098  size_type mid = lb + (rb - lb) / 2;
1099  size_type arg = m_first_child_rank(mid); // ones in the prefix [0..mid-1]
1100  if (arg < id) { lb = mid; }
1101  else
1102  { // arg >= id
1103  rb = mid;
1104  }
1105  }
1106  r0ckpos = lb;
1107  }
1108  // (2) determine position clpos of the r0clpos-th closing parentheses in the parentheses sequence
1109  size_type ckpos = 0;
1110  {
1111  // binary search for the position of the (r0ckpos+1)-th closing parenthesis
1112  size_type lb = 0, rb = m_bp.size(); // lb inclusive, rb exclusive
1113  // invariant: arg(lb) < r0ckpos+1, arg(rb) >= r0ckpos+1
1114  while (rb - lb > 1)
1115  {
1116  size_type mid = lb + (rb - lb) / 2;
1117  size_type arg = mid - m_bp_support.rank(mid - 1); // zeros in the prefix [0..mid-1]
1118  if (arg < r0ckpos + 1) { lb = mid; }
1119  else
1120  { // arg >= x
1121  rb = mid;
1122  }
1123  }
1124  ckpos = lb;
1125  }
1126  if (ckpos == m_bp.size() - 1) { return root(); }
1127  if (m_bp[ckpos + 1])
1128  { // jp1pos < cipos
1129  size_type jp1pos = ckpos + 1;
1130  size_type j = m_bp_support.rank(jp1pos - 1) - 1;
1131  size_type kpos = m_bp_support.find_open(ckpos);
1132  size_type ipos = m_bp_support.enclose(kpos);
1133  size_type cipos = m_bp_support.find_close(ipos);
1134  size_type i = m_bp_support.rank(ipos - 1);
1135  return node_type(i, j, ipos, cipos, jp1pos);
1136  }
1137  else
1138  { //
1139  size_type cipos = ckpos + 1;
1140  size_type ipos = m_bp_support.find_open(cipos);
1141  size_type i = m_bp_support.rank(ipos - 1);
1142  size_type j = nsv(i, ipos) - 1;
1143  size_type jp1pos = m_bp.size();
1144  if (j != size() - 1) { jp1pos = m_bp_support.select(j + 2); }
1145  return node_type(i, j, ipos, cipos, jp1pos);
1146  }
1147  }
1148  }
1149 
1151  size_type nodes() const { return m_nodes; }
1152 
1154  /* \param lb Left bound of the lcp-interval [lb..rb] (inclusive).
1155  * \param rb Right bound of the lcp-interval [lb..rb] (inclusive).
1156  * \return The node in the suffix tree corresponding lcp-interval [lb..rb]
1157  * \par Time complexity
1158  * \f$ \Order{1} \f$
1159  */
1161  {
1162  size_type ipos = m_bp_support.select(lb + 1);
1163  size_type jp1pos;
1164  if (rb == size() - 1) { jp1pos = m_bp.size(); }
1165  else
1166  {
1167  jp1pos = m_bp_support.select(rb + 2);
1168  }
1169  return node_type(lb, rb, ipos, m_bp_support.find_close(ipos), jp1pos);
1170  }
1171 
1173 
1178  {
1179  size_type ipos = m_bp_support.select(i + 1);
1180  size_type cipos = m_bp_support.find_close(ipos);
1181  return m_first_child_rank.rank(((ipos + cipos - 1) >> 1) - i);
1182  }
1183  /* @} */
1184 };
1185 
1186 // == template functions ==
1187 
1188 template <class t_csa, class t_lcp, class t_bp_support, class t_bv, class t_rank, class t_sel>
1190 {
1191  {
1192  auto event = memory_monitor::event("bps-sct");
1194  m_nodes = construct_supercartesian_tree_bp_succinct_and_first_child(lcp_buf, m_bp, m_first_child);
1195  m_nodes += m_bp.size() / 2;
1196  if (m_bp.size() == 2)
1197  { // handle special case, when the tree consists only of the root node
1198  m_nodes = 1;
1199  }
1200  }
1201  {
1202  auto event = memory_monitor::event("bpss-sct");
1203  util::init_support(m_bp_support, &m_bp);
1204  util::init_support(m_first_child_rank, &m_first_child);
1205  util::init_support(m_first_child_select, &m_first_child);
1206  }
1207  if (!build_only_bps)
1208  {
1209  auto event = memory_monitor::event("clcp");
1210  cache_config tmp_config(false, config.dir, config.id, config.file_map);
1211  construct_lcp(m_lcp, *this, tmp_config);
1212  config.file_map = tmp_config.file_map;
1213  }
1214  if (!build_only_bps)
1215  {
1216  auto event = memory_monitor::event("load csa");
1217  load_from_cache(m_csa, std::string(conf::KEY_CSA) + "_" + util::class_to_hash(m_csa), config);
1218  }
1219 }
1220 
1221 template <class t_csa, class t_lcp, class t_bp_support, class t_bv, class t_rank, class t_sel>
1223  structure_tree_node * v,
1224  std::string name) const -> size_type
1225 {
1226  structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
1227  size_type written_bytes = 0;
1228  written_bytes += m_csa.serialize(out, child, "csa");
1229  written_bytes += m_lcp.serialize(out, child, "lcp");
1230  written_bytes += m_bp.serialize(out, child, "bp");
1231  written_bytes += m_bp_support.serialize(out, child, "bp_support");
1232  written_bytes += m_first_child.serialize(out, child, "mark_child");
1233  written_bytes += m_first_child_rank.serialize(out, child, "mark_child_rank");
1234  written_bytes += m_first_child_select.serialize(out, child, "mark_child_select");
1235  written_bytes += write_member(m_nodes, out, child, "node_cnt");
1236  structure_tree::add_size(child, written_bytes);
1237  return written_bytes;
1238 }
1239 
1240 template <class t_csa, class t_lcp, class t_bp_support, class t_bv, class t_rank, class t_sel>
1242 {
1243  m_csa.load(in);
1244  load_lcp(m_lcp, in, *this);
1245  m_bp.load(in);
1246  m_bp_support.load(in, &m_bp);
1247  m_first_child.load(in);
1248  m_first_child_rank.load(in, &m_first_child);
1249  m_first_child_select.load(in, &m_first_child);
1250  read_member(m_nodes, in);
1251 }
1252 
1253 template <class t_csa, class t_lcp, class t_bp_support, class t_bv, class t_rank, class t_sel>
1254 template <typename archive_t>
1256 {
1257  ar(CEREAL_NVP(m_csa));
1258  ar(CEREAL_NVP(m_lcp));
1259  ar(CEREAL_NVP(m_bp));
1260  ar(CEREAL_NVP(m_bp_support));
1261  ar(CEREAL_NVP(m_first_child));
1262  ar(CEREAL_NVP(m_first_child_rank));
1263  ar(CEREAL_NVP(m_first_child_select));
1264  ar(CEREAL_NVP(m_nodes));
1265 }
1266 
1267 template <class t_csa, class t_lcp, class t_bp_support, class t_bv, class t_rank, class t_sel>
1268 template <typename archive_t>
1270 {
1271  ar(CEREAL_NVP(m_csa));
1272  ar(CEREAL_NVP(m_lcp));
1273  set_lcp_pointer(m_lcp, *this);
1274  ar(CEREAL_NVP(m_bp));
1275  ar(CEREAL_NVP(m_bp_support));
1276  m_bp_support.set_vector(&m_bp);
1277  ar(CEREAL_NVP(m_first_child));
1278  ar(CEREAL_NVP(m_first_child_rank));
1279  m_first_child_rank.set_vector(&m_first_child);
1280  ar(CEREAL_NVP(m_first_child_select));
1281  m_first_child_select.set_vector(&m_first_child);
1282  ar(CEREAL_NVP(m_nodes));
1283 }
1284 
1285 template <class t_int>
1287 {
1288  t_int i;
1289  t_int j;
1290  t_int ipos; // position of the i+1th opening parenthesis in the balanced parentheses sequence
1291  t_int cipos; // position of the matching closing parenthesis of the i+1th opening parenthesis in the balanced
1292  // parentheses sequence
1293  t_int jp1pos; // position of the j+2th opening parenthesis in the balanced parentheses sequence
1294 
1296  bp_interval(t_int i = 0, t_int j = 0, t_int ipos = 0, t_int cipos = 0, t_int jp1pos = 0)
1297  : i(i)
1298  , j(j)
1299  , ipos(ipos)
1300  , cipos(cipos)
1301  , jp1pos(jp1pos){};
1302 
1304  bp_interval(const bp_interval & iv) = default;
1306  bp_interval(bp_interval && iv) = default;
1307 
1308  bool operator<(const bp_interval & interval) const
1309  {
1310  if (i != interval.i) return i < interval.i;
1311  return j < interval.j;
1312  }
1313 
1315 
1317  bool operator==(const bp_interval & interval) const { return i == interval.i and j == interval.j; }
1318 
1320 
1323  bool operator!=(const bp_interval & interval) const { return !(*this == interval); }
1324 
1326  bp_interval & operator=(const bp_interval & interval) = default;
1328  bp_interval & operator=(bp_interval && interval) = default;
1329 };
1330 
1331 template <class t_int>
1332 inline std::ostream & operator<<(std::ostream & os, const bp_interval<t_int> & interval)
1333 {
1334  os << "-[" << interval.i << "," << interval.j << "](" << interval.ipos << "," << interval.cipos << ","
1335  << interval.jp1pos << ")";
1336  return os;
1337 }
1338 
1339 } // end namespace sdsl
1340 #endif
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
A forward iterator for a bottom up traversal of a suffix tree.
An forward iterator for (compressed) suffix trees.
A class for the Compressed Suffix Tree (CST) proposed by Ohlebusch and Gog.
Definition: cst_sct3.hpp:91
t_csa::alphabet_type::sigma_type sigma_type
Definition: cst_sct3.hpp:111
size_type id(const node_type &v) const
Computes a unique identification number for a node of the suffx tree in the range [0....
Definition: cst_sct3.hpp:1053
node_type parent(const node_type &v) const
Calculate the parent node of a node v.
Definition: cst_sct3.hpp:611
node_type lca(node_type v, node_type w) const
Calculate the LCA of two nodes v and w
Definition: cst_sct3.hpp:897
const_iterator begin() const
Returns a const_iterator to the first element of a depth first traversal of the tree.
Definition: cst_sct3.hpp:414
const_bottom_up_iterator end_bottom_up() const
Returns an iterator to the element after the last element of a bottom-up traversal of the tree.
Definition: cst_sct3.hpp:450
node_type rightmost_leaf(const node_type &v) const
Calculates the rightmost leaf in the subtree rooted at node v.
Definition: cst_sct3.hpp:583
size_type size(const node_type &v) const
Calculate the number of leaves in the subtree rooted at node v.
Definition: cst_sct3.hpp:567
node_type wl(const node_type &v, const char_type c) const
Compute the Weiner link of node v and character c.
Definition: cst_sct3.hpp:1013
const sel_type & first_child_select
Definition: cst_sct3.hpp:339
t_bp_support bp_support_type
Definition: cst_sct3.hpp:102
const lcp_type & lcp
Definition: cst_sct3.hpp:333
static size_type max_size()
Returns the largest size that cst_sct3 can ever have.
Definition: cst_sct3.hpp:402
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Serialise (load) via cereal.
Definition: cst_sct3.hpp:1269
cst_sct3 & operator=(cst_sct3 &&cst)
Assignment Move Operator.
Definition: cst_sct3.hpp:470
node_type select_leaf(size_type i) const
Return the i-th leaf (1-based from left to right).
Definition: cst_sct3.hpp:547
node_type root() const
Return the root of the suffix tree.
Definition: cst_sct3.hpp:528
node_type inv_id(size_type id)
Computes the node for such that id(v)=id.
Definition: cst_sct3.hpp:1081
size_type node_depth(node_type v) const
Returns the node depth of node v.
Definition: cst_sct3.hpp:957
const_bottom_up_iterator begin_bottom_up() const
Returns an iterator to the first element of a bottom-up traversal of the tree.
Definition: cst_sct3.hpp:442
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serialize to a stream.
Definition: cst_sct3.hpp:1222
node_type node(size_type lb, size_type rb) const
Get the node in the suffix tree which corresponds to the lcp-interval [lb..rb].
Definition: cst_sct3.hpp:1160
size_type nodes() const
Get the number of nodes of the suffix tree.
Definition: cst_sct3.hpp:1151
cst_bottom_up_const_forward_iterator< cst_sct3 > const_bottom_up_iterator
Definition: cst_sct3.hpp:97
const_iterator begin(const node_type &v) const
Returns a const_iterator to the first element of a depth first traversal of the subtree rooted at nod...
Definition: cst_sct3.hpp:422
t_csa::string_type string_type
Definition: cst_sct3.hpp:104
const bv_type & first_child_bv
Definition: cst_sct3.hpp:337
const bit_vector & bp
Definition: cst_sct3.hpp:334
bool empty() const
Returns if the data structure is empty.
Definition: cst_sct3.hpp:408
cst_sct3(cst_sct3 &&cst)
Move constructor.
Definition: cst_sct3.hpp:375
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Serialise (save) via cereal.
Definition: cst_sct3.hpp:1255
t_csa::char_type char_type
Definition: cst_sct3.hpp:103
bool operator==(cst_sct3 const &other) const noexcept
Equality operator.
Definition: cst_sct3.hpp:509
bool operator!=(cst_sct3 const &other) const noexcept
Inequality operator.
Definition: cst_sct3.hpp:518
size_type size() const
Number of leaves of the suffix tree.
Definition: cst_sct3.hpp:396
cst_tag index_category
Definition: cst_sct3.hpp:114
cst_sct3 & operator=(const cst_sct3 &cst)
Assignment Operator.
Definition: cst_sct3.hpp:456
node_type child(const node_type &v, const char_type c) const
Get the child w of node v which edge label (v,w) starts with character c.
Definition: cst_sct3.hpp:855
const rank_type & first_child_rank
Definition: cst_sct3.hpp:338
const bp_support_type & bp_support
Definition: cst_sct3.hpp:335
char_type edge(const node_type &v, size_type d) const
Returns the d-th character (1-based indexing) of the edge-label pointing to v.
Definition: cst_sct3.hpp:870
node_type sl(const node_type &v) const
Compute the suffix link of node v.
Definition: cst_sct3.hpp:975
node_type child(const node_type &v, const char_type c, size_type &char_pos) const
Get the child w of node v which edge label (v,w) starts with character c.
Definition: cst_sct3.hpp:788
bool is_leaf(const node_type &v) const
Decide if a node is a leaf.
Definition: cst_sct3.hpp:537
const_iterator end(const node_type &v) const
Returns a const_iterator to the element past the end of a depth first traversal of the subtree rooted...
Definition: cst_sct3.hpp:435
const_iterator end() const
Returns a const_iterator to the element after the last element of a depth first traversal of the tree...
Definition: cst_sct3.hpp:432
cst_dfs_const_forward_iterator< cst_sct3 > const_iterator
Definition: cst_sct3.hpp:93
t_csa::size_type size_type
Definition: cst_sct3.hpp:98
bp_interval< size_type > node_type
Type for the nodes in the tree.
Definition: cst_sct3.hpp:105
node_type sibling(const node_type &v) const
Returns the next sibling of node v.
Definition: cst_sct3.hpp:651
node_type leftmost_leaf(const node_type &v) const
Calculates the leftmost leaf in the subtree rooted at node v.
Definition: cst_sct3.hpp:575
size_type depth(const node_type &v) const
Returns the string depth of node v.
Definition: cst_sct3.hpp:930
t_lcp::template type< cst_sct3 > lcp_type
Definition: cst_sct3.hpp:101
ptrdiff_t difference_type
Definition: cst_sct3.hpp:99
size_type sn(const node_type &v) const
Computes the suffix number of a leaf node v.
Definition: cst_sct3.hpp:1040
size_type rb(const node_type &v) const
Calculates the index of the rightmost leaf in the corresponding suffix array.
Definition: cst_sct3.hpp:603
cst_sct3(const cst_sct3 &cst)
Copy constructor.
Definition: cst_sct3.hpp:356
t_csa::alphabet_category alphabet_category
Definition: cst_sct3.hpp:113
t_csa::alphabet_type::comp_char_type comp_char_type
Definition: cst_sct3.hpp:110
void load(std::istream &in)
Load from a stream.
Definition: cst_sct3.hpp:1241
node_type select_child(const node_type &v, size_type i) const
Get the i-th child of a node v.
Definition: cst_sct3.hpp:702
t_rank rank_type
Definition: cst_sct3.hpp:107
size_type lb(const node_type &v) const
Calculates the index of the leftmost leaf in the corresponding suffix array.
Definition: cst_sct3.hpp:593
cst_node_child_proxy< cst_sct3 > children(const node_type &v) const
Return a proxy object which allows iterating over the children of a node.
Definition: cst_sct3.hpp:639
const csa_type & csa
Definition: cst_sct3.hpp:332
size_type tlcp_idx(size_type i) const
Maps an index i to the position in TLCP where LCP[i] can be found.
Definition: cst_sct3.hpp:1177
size_type degree(const node_type &v) const
Get the number of children of a node v.
Definition: cst_sct3.hpp:733
cst_sct3()=default
Default constructor.
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.
static mm_event_proxy event(const std::string &name)
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)
#define SDSL_UNUSED
Definition: config.hpp:13
construct.hpp contains methods to construct indexes (compressed suffix arrays and trees).
csa_wt.hpp contains an implementation of the compressed suffix array based on a wavelet tree.
cst_iterators.hpp contains iterator classes for traversing (compressed) suffix arrays.
int_vector.hpp contains the sdsl::int_vector class.
iterators.hpp contains an generic iterator for random access containers.
lcp.hpp contains classes for lcp information.
constexpr char KEY_CSA[]
Definition: config.hpp:38
constexpr char KEY_LCP[]
Definition: config.hpp:44
int_vector ::size_type size_type
Namespace for the succinct data structure library.
std::string cache_file_name(const std::string &key, const cache_config &config)
Returns the file name of the resource.
Definition: io.hpp:630
t_csa::size_type get_char_pos(typename t_csa::size_type idx, typename t_csa::size_type d, const t_csa &csa)
bool load_from_cache(T &v, const std::string &key, const cache_config &config, bool add_type_hash=false)
Definition: io.hpp:711
std::ostream & operator<<(std::ostream &os, const bp_interval< t_int > &interval)
Definition: cst_sct3.hpp:1332
void move_lcp(t_lcp &&lcp, t_lcp &&lcp_c, const t_cst &cst)
Definition: lcp.hpp:92
void swap(int_vector_reference< t_int_vector > x, int_vector_reference< t_int_vector > y) noexcept
Definition: int_vector.hpp:970
void copy_lcp(t_lcp &lcp, const t_lcp &lcp_c, const t_cst &cst)
Definition: lcp.hpp:57
bit_vector::size_type construct_supercartesian_tree_bp_succinct_and_first_child(int_vector_buffer< t_width > &lcp_buf, bit_vector &bp, bit_vector &bp_fc, const bool minimum=true)
Calculate the balanced parentheses of the Super-Cartesian tree, described in Ohlebusch and Gog (SPIRE...
void construct_lcp(t_lcp &lcp, const t_cst &cst, cache_config &config)
Definition: lcp.hpp:25
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
void set_lcp_pointer(t_lcp &lcp, const t_cst &cst)
Definition: lcp.hpp:159
void load_lcp(t_lcp &lcp, std::istream &in, const t_cst &cst)
Definition: lcp.hpp:127
rank_support.hpp contains classes that support a sdsl::bit_vector with constant time rank information...
Contains declarations and definitions of data structure concepts.
select_support.hpp contains classes that support a sdsl::bit_vector with constant time select informa...
static SDSL_CONSTEXPR uint32_t lo(uint64_t x)
Calculates the position of the rightmost 1-bit in the 64bit integer x if it exists.
Definition: bits.hpp:696
constexpr static uint64_t lo_set[65]
lo_set[i] is a 64-bit word with the i least significant bits set and the high bits not set.
Definition: bits.hpp:197
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
t_int i
The left border of the lcp-interval .
Definition: cst_sct3.hpp:1288
bp_interval(t_int i=0, t_int j=0, t_int ipos=0, t_int cipos=0, t_int jp1pos=0)
Constructor.
Definition: cst_sct3.hpp:1296
bp_interval(const bp_interval &iv)=default
Copy constructor.
bp_interval & operator=(bp_interval &&interval)=default
Move assignment.
t_int j
The right border of the lcp-interval .
Definition: cst_sct3.hpp:1289
bp_interval & operator=(const bp_interval &interval)=default
Assignment operator.
bool operator!=(const bp_interval &interval) const
Inequality operator.
Definition: cst_sct3.hpp:1323
bool operator==(const bp_interval &interval) const
Equality operator.
Definition: cst_sct3.hpp:1317
bool operator<(const bp_interval &interval) const
Definition: cst_sct3.hpp:1308
bp_interval(bp_interval &&iv)=default
Move copy constructor.
Helper class for construction process.
Definition: config.hpp:67
std::string id
Definition: config.hpp:72
std::string dir
Definition: config.hpp:71
suffix_tree_algorithm.hpp contains algorithms on CSTs
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.