SDSL  3.0.0
Succinct Data Structure Library
bp_support_g.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_BP_SUPPORT_G
9 #define INCLUDED_SDSL_BP_SUPPORT_G
10 
11 #include <map>
12 #include <set>
13 #include <stack>
14 #include <stdexcept>
15 #include <utility>
16 
18 #include <sdsl/int_vector.hpp>
20 #include <sdsl/rank_support.hpp>
21 #include <sdsl/rmq_support.hpp>
22 #include <sdsl/select_support.hpp>
23 #include <sdsl/util.hpp>
24 
25 namespace sdsl
26 {
27 
29 
52 template <class t_nnd = nearest_neighbour_dictionary<30>,
53  class t_rank = rank_support_v5<>,
54  class t_select = select_support_mcl<>,
55  class t_rmq = range_maximum_support_sparse_table<>,
56  uint32_t t_bs = 840>
58 {
59  static_assert(t_bs > 2, "bp_support_g: block size must be greater than 2.");
60 
61  public:
63  typedef t_nnd nnd_type;
64  typedef t_rank rank_type;
65  typedef t_select select_type;
66  typedef t_rmq rmq_type;
67 
68  private:
69  const bit_vector * m_bp; // the supported BP sequence as bit_vector
70  rank_type m_rank_bp; // rank support for the BP sequence => see excess() and rank()
71  select_type m_select_bp; // select support for the BP sequence => see select()
72 
73  nnd_type m_nnd; // nearest neighbour dictionary for pioneers bit_vector
74 
75  bit_vector m_pioneer_bp; // first level of recursion: BP sequence of the pioneers
76  rank_type m_rank_pioneer_bp; // rank for the BP sequence of the pioneers
77  nnd_type m_nnd2; // nearest neighbour dictionary for pioneers of pioneers bit_vector
78  int_vector<> m_match; //
79  int_vector<> m_enclose; //
80  rmq_type m_range_max_match; // range maximum support for m_match
81 
82  size_type m_size;
83  size_type m_blocks; // number of blocks
84 
88  inline size_type excess_pioneer(size_type i) const { return (m_rank_pioneer_bp(i + 1) << 1) - i - 1; }
89 
90  public:
91  const rank_type & bp_rank = m_rank_bp;
92  const select_type & bp_select = m_select_bp;
93 
95  explicit bp_support_g(const bit_vector * bp = nullptr)
96  : m_bp(bp)
97  , m_size(bp == nullptr ? 0 : bp->size())
98  , m_blocks((m_size + t_bs - 1) / t_bs)
99  {
100  if (bp == nullptr) return;
101  util::init_support(m_rank_bp, bp);
102  util::init_support(m_select_bp, bp);
103  bit_vector pioneer = calculate_pioneers_bitmap(*m_bp, t_bs);
104  m_nnd = nnd_type(pioneer);
105  m_pioneer_bp.resize(m_nnd.ones());
106  for (size_type i = 1; i <= m_nnd.ones(); ++i) m_pioneer_bp[i - 1] = (*m_bp)[m_nnd.select(i)];
107  util::init_support(m_rank_pioneer_bp, &m_pioneer_bp);
108  pioneer = calculate_pioneers_bitmap(m_pioneer_bp, t_bs);
109  m_nnd2 = nnd_type(pioneer);
110 
111  bit_vector pioneer_bp2 = bit_vector(m_nnd2.ones());
112  for (size_type i = 1; i <= m_nnd2.ones(); ++i) pioneer_bp2[i - 1] = m_pioneer_bp[m_nnd2.select(i)];
113  calculate_matches(pioneer_bp2, m_match);
114  calculate_enclose(pioneer_bp2, m_enclose);
115  m_range_max_match = rmq_type(&m_match);
116  }
117 
120  : m_bp(v.m_bp)
121  , m_rank_bp(v.m_rank_bp)
122  , m_select_bp(v.m_select_bp)
123  , m_nnd(v.m_nnd)
124  , m_pioneer_bp(v.m_pioneer_bp)
125  , m_rank_pioneer_bp(v.m_rank_pioneer_bp)
126  , m_nnd2(v.m_nnd2)
127  , m_match(v.m_match)
128  , m_enclose(v.m_enclose)
129  , m_range_max_match(v.m_range_max_match)
130  , m_size(v.m_size)
131  , m_blocks(v.m_blocks)
132  {
133  m_rank_bp.set_vector(m_bp);
134  m_select_bp.set_vector(m_bp);
135  m_rank_pioneer_bp.set_vector(&m_pioneer_bp);
136  m_range_max_match.set_vector(&m_match);
137  }
138 
140  bp_support_g(bp_support_g && bp_support) { *this = std::move(bp_support); }
141 
143  bp_support_g & operator=(const bp_support_g & bp_support)
144  {
145  if (this != &bp_support)
146  {
147  bp_support_g tmp(bp_support);
148  *this = std::move(tmp);
149  }
150  return *this;
151  }
152 
155  {
156  if (this != &bp_support)
157  {
158  m_bp = std::move(bp_support.m_bp);
159  m_rank_bp = std::move(bp_support.m_rank_bp);
160  m_rank_bp.set_vector(m_bp);
161  m_select_bp = std::move(bp_support.m_select_bp);
162  m_select_bp.set_vector(m_bp);
163 
164  m_nnd = std::move(bp_support.m_nnd);
165 
166  m_pioneer_bp = std::move(bp_support.m_pioneer_bp);
167  m_rank_pioneer_bp = std::move(bp_support.m_rank_pioneer_bp);
168  m_rank_pioneer_bp.set_vector(&m_pioneer_bp);
169  m_nnd2 = std::move(bp_support.m_nnd2);
170  m_match = std::move(bp_support.m_match);
171  m_enclose = std::move(bp_support.m_enclose);
172  m_range_max_match = std::move(bp_support.m_range_max_match);
173  m_range_max_match.set_vector(&m_match);
174 
175  m_size = std::move(bp_support.m_size);
176  m_blocks = std::move(bp_support.m_blocks);
177  }
178  return *this;
179  }
180 
181  void set_vector(const bit_vector * bp)
182  {
183  m_bp = bp;
184  m_rank_bp.set_vector(bp);
185  m_select_bp.set_vector(bp);
186  }
187 
191  inline size_type excess(size_type i) const { return (m_rank_bp(i + 1) << 1) - i - 1; }
192 
196  size_type rank(size_type i) const { return m_rank_bp(i + 1); }
197 
203  size_type select(size_type i) const { return m_select_bp(i); }
204 
212  {
213  assert(i < m_size);
214  if (!(*m_bp)[i])
215  { // if there is a closing parenthesis at index i return i
216  return i;
217  }
218  size_type mi = 0; // match for i
219  if ((mi = near_find_close(*m_bp, i, t_bs)) == i)
220  {
221  const size_type i2 = m_nnd.rank(i + 1) - 1; // lemma that this gives us an opening pioneer
222  assert(m_pioneer_bp[i2] == 1); // assert that i2 is an opening parenthesis
223  size_type mi2 = 0; // match for i2
224  if ((mi2 = near_find_close(m_pioneer_bp, i2, t_bs)) == i2)
225  {
226  const size_type i3 = m_nnd2.rank(i2 + 1) - 1;
227  const size_type mi3 = m_match[i3];
228  assert(mi3 > i3); // assert that i3 is an opening parenthesis
229  mi2 = m_nnd2.select(mi3 + 1); // matching pioneer position in pioneer_bp
230  mi2 = (mi2 / t_bs) * t_bs;
231  size_type epb = excess_pioneer(mi2); // excess of first parenthesis in the pioneer block
232  const size_type ei = excess_pioneer(i2); // excess of pioneer
233  /* invariant: epb >= ei-1 */ assert(epb + 1 >= ei);
234  while (epb + 1 != ei)
235  {
236  assert(mi2 < m_pioneer_bp.size());
237  if (m_pioneer_bp[++mi2])
238  ++epb;
239  else
240  --epb;
241  }
242  }
243  mi = m_nnd.select(mi2 + 1); /* matching pioneer position in bp */
244  assert((*m_bp)[mi] == 0);
245  mi = (mi / t_bs) * t_bs;
246  size_type epb = excess(mi); // excess of first parenthesis in the pioneer block
247  const size_type ei = excess(i); // excess at position i
248  /* invariant: epb >= ei-1 */ assert(epb + 1 >= ei);
249  while (epb + 1 != ei)
250  {
251  assert(mi < m_size);
252  if ((*m_bp)[++mi])
253  ++epb;
254  else
255  --epb;
256  }
257  }
258  return mi;
259  }
260 
262 
268  {
269  assert(i < m_size);
270  if ((*m_bp)[i])
271  { // if there is a opening parenthesis at index i return i
272  return i;
273  }
274  size_type mi = 0; // match for i
275  if ((mi = near_find_open(*m_bp, i, t_bs)) == i)
276  {
277  const size_type i2 = m_nnd.rank(i); // lemma that this gives us an closing pioneer
278  assert(m_pioneer_bp[i2] == 0); // assert that i2 is an opening parenthesis
279  const size_type mi2 = find_open_in_pioneers(i2);
280  assert(m_pioneer_bp[mi2] == 1);
281  mi = m_nnd.select(mi2 + 1); /* matching pioneer position in bp */
282  assert((*m_bp)[mi] == 1);
283  mi = (mi / t_bs) * t_bs + t_bs - 1;
284  assert(mi < i);
285  size_type epb = excess(mi); // excess of last parenthesis in the pioneer block
286  const size_type ei = excess(i); // excess at position i
287  /*invariant: epb >= ei+1*/ assert(epb >= ei + 1);
288  while (epb != ei)
289  {
290  assert(mi < m_size);
291  if ((*m_bp)[mi--])
292  --epb;
293  else
294  ++epb;
295  }
296  ++mi;
297  }
298  return mi;
299  }
300 
302  {
303  size_type mi = 0; // match for i
304  if ((mi = near_find_open(m_pioneer_bp, i, t_bs)) == i)
305  {
306  const size_type i3 = m_nnd2.rank(i);
307  const size_type mi3 = m_match[i3];
308  assert(mi3 < i3); // assert that i3 is an closing parenthesis
309  mi = m_nnd2.select(mi3 + 1); // matching pioneer position in pioneer_bp
310  mi = (mi / t_bs) * t_bs + t_bs - 1;
311  size_type epb2 = excess_pioneer(mi); // excess of last parenthesis in the pioneer block
312  const size_type ei = excess_pioneer(i); // excess of pioneer
313  /* invariant: epb2 >= ei+1 */ assert(epb2 >= ei + 1);
314  while (epb2 != ei)
315  {
316  assert(mi < m_pioneer_bp.size());
317  if (m_pioneer_bp[mi--])
318  --epb2;
319  else
320  ++epb2;
321  }
322  ++mi;
323  }
324  return mi;
325  }
326 
329 
334  {
335  assert(i < m_size);
336  if (!(*m_bp)[i])
337  { // if there is closing parenthesis at position i
338  return find_open(i);
339  }
340  const size_type exi = excess(i);
341  if (exi == 1) // if i is not enclosed by a parentheses pair..
342  return size();
343  size_type ei; // enclose for i
344  if ((ei = near_enclose(*m_bp, i, t_bs)) == i)
345  {
346  const size_type i2 = m_nnd.rank(i); // next parenthesis in the pioneer bitmap
347  size_type ei2; // enclose for i2
348  if (m_pioneer_bp[i2])
349  { // search enclose in the pioneer bp
350  if ((ei2 = near_enclose(m_pioneer_bp, i2, t_bs)) == i2)
351  {
352  const size_type i3 = m_nnd2.rank(i2); // next parenthesis in the pioneer2 bitmap
353  const size_type ei3 = m_enclose[i3];
354  assert(ei3 < i3); // assert that enclose answer is valid
355  ei2 = m_nnd2.select(ei3 + 1);
356  assert(m_pioneer_bp[ei2] == 1);
357  ei2 = (ei2 / t_bs) * t_bs + t_bs - 1;
358  assert(ei2 < i2);
359  size_type epb2 = excess_pioneer(ei2); // excess of the last parenthesis in the pioneer block
360  const size_type exi2 = excess_pioneer(i2); // excess
361  /* invariant epb2+1 >= exi2 */ assert(epb2 + 1 >= exi2);
362  while (epb2 + 2 != exi2)
363  {
364  if (m_pioneer_bp[ei2--])
365  --epb2;
366  else
367  ++epb2;
368  }
369  ++ei2;
370  }
371  }
372  else
373  {
374  // if the next parenthesis in the pioneer bitmap is an closing parenthesis findopen on m_pioneer_bp
375  ei2 = find_open_in_pioneers(i2);
376  }
377  assert(m_pioneer_bp[ei2] == 1);
378  ei = m_nnd.select(ei2 + 1);
379  assert((*m_bp)[ei] == 1);
380  ei = (ei / t_bs) * t_bs + t_bs - 1;
381  assert(ei < i);
382  size_type epb = excess(ei); // excess of the last parenthesis in the pioneer block
383  /* invariant epb+1 >= exi */ assert(epb + 1 >= exi);
384  while (epb + 2 != exi)
385  {
386  if ((*m_bp)[ei--])
387  --epb;
388  else
389  ++epb;
390  }
391  ++ei;
392  }
393  return ei;
394  }
395 
397 
404  size_type rr_enclose(const size_type i, const size_type j) const
405  {
406  assert(j > i and j < m_size);
407  const size_type mip1 = find_close(i) + 1;
408  if (mip1 >= j) return size();
409  return rmq_open(mip1, j);
410  }
411 
425  size_type rmq_open(const size_type l, const size_type r) const
426  {
427  if (l >= r) return size();
428  size_type min_ex_pos = r;
429 
430  if (l / t_bs == r / t_bs) { min_ex_pos = near_rmq_open(*m_bp, l, r); }
431  else
432  { // parentheses pair does not start in the same block
433  // assert( l>1 ); // mi is at greater or equal than 1
434  // note: mi and r are not in the same block
435  size_type k, ex; // helper variables
436  size_type min_ex = excess(r); // + 2*((*m_bp[r])==0); // minimal excess
437  const size_type bl = (l / t_bs + 1) *
438  t_bs; // leftmost position of the leftmost block between the blocks of l and r
439  const size_type br = (r / t_bs) * t_bs; // leftmost position of the block of r
440 
441  // 1.2
442  size_type l_ = m_nnd.rank(l); // l_ inclusive
443  size_type r_ = m_nnd.rank(r); // r_ exclusive
444 
445  if (r_ > l_)
446  {
447  size_type min_ex_pos_ = r_;
448  if (l_ / t_bs == r_ / t_bs) { min_ex_pos_ = near_rmq_open(m_pioneer_bp, l_, r_); }
449  else if (r_ < m_pioneer_bp.size())
450  {
451  size_type min_ex_ = excess_pioneer(r_) + 2 * (m_pioneer_bp[r_] == 0);
452  const size_type bl_ = (l_ / t_bs + 1) * t_bs;
453  const size_type br_ = (r_ / t_bs) * t_bs;
454 
455  // 2.2
456  size_type l__ = m_nnd2.rank(l_); // l__ inclusive
457  size_type r__ = m_nnd2.rank(r_); // r__ exclusive
458  if (r__ > l__)
459  {
460  size_type max_match = 0;
461  k = m_range_max_match(l__, r__ - 1);
462  max_match = m_match[k];
463  if (max_match >= r__)
464  {
465  k = m_nnd2.select(k + 1);
466  if (k < r_ and (ex = excess_pioneer(k)) < min_ex_)
467  {
468  min_ex_ = ex;
469  min_ex_pos_ = k;
470  }
471  }
472  }
473  if (min_ex_pos_ == r_)
474  {
475  // 2.1
476  k = near_rmq_open(m_pioneer_bp, br_, r_);
477  if (k < r_ and (ex = excess_pioneer(k)) < min_ex_)
478  {
479  min_ex_ = ex;
480  min_ex_pos_ = k;
481  }
482  }
483  // 2.3
484  k = near_rmq_open(m_pioneer_bp, l_, bl_);
485  if (k < bl_ and (ex = excess_pioneer(k)) < min_ex_)
486  {
487  min_ex_ = ex;
488  min_ex_pos_ = k;
489  }
490  }
491  // 2.4
492  if (min_ex_pos_ < r_)
493  {
494  k = m_nnd.select(min_ex_pos_ + 1);
495  if ((ex = excess(k)) < min_ex)
496  {
497  min_ex = ex;
498  min_ex_pos = k;
499  }
500  }
501  }
502  if (min_ex_pos == r)
503  {
504  // 1.1
505  k = near_rmq_open(*m_bp, br, r);
506  if (k < r and (ex = excess(k)) < min_ex)
507  {
508  min_ex = ex;
509  min_ex_pos = k;
510  }
511  }
512  // 1.3
513  k = near_rmq_open(*m_bp, l, bl);
514  if (k < bl and (ex = excess(k)) < min_ex)
515  {
516  min_ex = ex;
517  min_ex_pos = k;
518  }
519  }
520  // 1.4
521  if (min_ex_pos < r)
522  return min_ex_pos;
523  else
524  return size();
525  }
526 
528 
534  {
535  assert(j > i and j < m_size);
536  size_type mi = find_close(i); // matching parenthesis to i
537  assert(mi > i and mi < j);
538  assert(find_close(j) > j);
539  size_type k = enclose(j);
540  if (k == m_size or k < i) // there exists no opening parenthesis at position mi<k<j.
541  return m_size;
542  size_type kk;
543  do {
544  kk = k;
545  k = enclose(k);
546  } while (k != m_size and k > mi);
547  return kk;
548  }
549 
551 
555  {
556  assert(l <= r);
557  size_type m = rmq_open(l, r + 1);
558  if (m == l)
559  return l;
560  else
561  { // m>l and m<=r
562  assert(0 == (*m_bp)[m - 1]);
563  size_type prev_open = m_rank_bp(m);
564  if (prev_open == 0 or m_select_bp(prev_open) < l)
565  { // if there exists no opening parenthesis to the left of m which is greater or equal than l
566  return l;
567  }
568  else
569  {
570  return m - 1;
571  }
572  }
573  }
574 
576 
582  {
583  assert(j > i);
584  assert((*m_bp)[i] == 1 and (*m_bp)[j] == 1);
585  size_type k = rr_enclose(i, j);
586  if (k == size())
587  return enclose(j);
588  else
589  return enclose(k);
590  }
591 
593 
596  {
597  assert(i < m_size);
598  if (!i) return 0;
599  size_type ones = m_rank_bp(i);
600  if (ones)
601  { // ones > 0
602  assert(m_select_bp(ones) < i);
603  return i - m_select_bp(ones) - 1;
604  }
605  else
606  {
607  return i;
608  }
609  }
610 
614  size_type size() const { return m_size; }
615 
617 
621  size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
622  {
623  structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
624  size_type written_bytes = 0;
625  written_bytes += m_rank_bp.serialize(out, child, "bp_rank");
626  written_bytes += m_select_bp.serialize(out, child, "bp_select");
627  written_bytes += m_nnd.serialize(out, child, "nearest_neighbor_dictionary");
628 
629  written_bytes += m_pioneer_bp.serialize(out, child, "pioneer_bp");
630  written_bytes += m_rank_pioneer_bp.serialize(out, child, "pioneer_bp_rank");
631  written_bytes += m_nnd2.serialize(out, child, "nearest_neighbor_dictionary2");
632  written_bytes += m_match.serialize(out, child, "match_answers");
633  written_bytes += m_enclose.serialize(out, child, "enclose_answers");
634  written_bytes += m_range_max_match.serialize(out, child, "rmq_answers");
635 
636  written_bytes += write_member(m_size, out, child, "size");
637  written_bytes += write_member(m_blocks, out, child, "block_cnt");
638  structure_tree::add_size(child, written_bytes);
639  return written_bytes;
640  }
641 
643 
647  void load(std::istream & in, const bit_vector * bp)
648  {
649  m_bp = bp;
650  m_rank_bp.load(in, m_bp);
651  m_select_bp.load(in, m_bp);
652  m_nnd.load(in);
653 
654  m_pioneer_bp.load(in);
655  m_rank_pioneer_bp.load(in, &m_pioneer_bp);
656  m_nnd2.load(in);
657  m_match.load(in);
658  m_enclose.load(in);
659  m_range_max_match.load(in, &m_match);
660  read_member(m_size, in);
661  assert(m_size == bp->size());
662  read_member(m_blocks, in);
663  }
664 
665  template <typename archive_t>
666  void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
667  {
668  ar(CEREAL_NVP(m_rank_bp));
669  ar(CEREAL_NVP(m_select_bp));
670  ar(CEREAL_NVP(m_nnd));
671  ar(CEREAL_NVP(m_pioneer_bp));
672  ar(CEREAL_NVP(m_rank_pioneer_bp));
673  ar(CEREAL_NVP(m_nnd2));
674  ar(CEREAL_NVP(m_match));
675  ar(CEREAL_NVP(m_enclose));
676  ar(CEREAL_NVP(m_range_max_match));
677  ar(CEREAL_NVP(m_size));
678  ar(CEREAL_NVP(m_blocks));
679  }
680 
681  template <typename archive_t>
682  void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
683  {
684  ar(CEREAL_NVP(m_rank_bp));
685  ar(CEREAL_NVP(m_select_bp));
686  ar(CEREAL_NVP(m_nnd));
687  ar(CEREAL_NVP(m_pioneer_bp));
688  ar(CEREAL_NVP(m_rank_pioneer_bp));
689  m_rank_pioneer_bp.set_vector(&m_pioneer_bp);
690  ar(CEREAL_NVP(m_nnd2));
691  ar(CEREAL_NVP(m_match));
692  ar(CEREAL_NVP(m_enclose));
693  ar(CEREAL_NVP(m_range_max_match));
694  m_range_max_match.set_vector(&m_match);
695  ar(CEREAL_NVP(m_size));
696  ar(CEREAL_NVP(m_blocks));
697  }
698 
700  bool operator==(bp_support_g const & other) const noexcept
701  {
702  return (m_rank_bp == other.m_rank_bp) && (m_select_bp == other.m_select_bp) && (m_nnd == other.m_nnd) &&
703  (m_pioneer_bp == other.m_pioneer_bp) && (m_rank_pioneer_bp == other.m_rank_pioneer_bp) &&
704  (m_nnd2 == other.m_nnd2) && (m_match == other.m_match) && (m_enclose == other.m_enclose) &&
705  (m_range_max_match == other.m_range_max_match) && (m_size == other.m_size) &&
706  (m_blocks == other.m_blocks);
707  }
708 
710  bool operator!=(bp_support_g const & other) const noexcept { return !(*this == other); }
711 };
712 
713 } // namespace sdsl
714 
715 #endif
bp_support_algorithm.hpp contains algorithms for balanced parentheses sequences.
#define CEREAL_NVP(X)
Definition: cereal.hpp:30
A class that provides support for bit_vectors that represent a BP sequence.
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
size_type rmq_open(const size_type l, const size_type r) const
Search the interval [l,r-1] for an opening parenthesis, say i, such that find_close(i) >= r.
size_type select(size_type i) const
Returns the index of the i-th opening parenthesis.
size_type rmq(size_type l, size_type r) const
The range minimum query (rmq) returns the index of the parenthesis with minimal excess in the range .
size_type excess(size_type i) const
Calculates the excess value at index i.
size_type rr_enclose(const size_type i, const size_type j) const
The range restricted enclose operation.
void set_vector(const bit_vector *bp)
size_type rr_enclose_naive(size_type i, size_type j) const
The range restricted enclose operation.
const rank_type & bp_rank
bp_support_g & operator=(bp_support_g &&bp_support)
Assignment operator.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the bp_support_g to a stream.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
const select_type & bp_select
size_type preceding_closing_parentheses(size_type i) const
Return the number of zeros which procede position i in the balanced parentheses sequence.
bp_support_g & operator=(const bp_support_g &bp_support)
Assignment operator.
bp_support_g(bp_support_g &&bp_support)
Move constructor.
void load(std::istream &in, const bit_vector *bp)
Load the bp_support_g for a bit_vector v.
size_type size() const
The size of the supported balanced parentheses sequence.
bit_vector::size_type size_type
bp_support_g(const bit_vector *bp=nullptr)
Constructor.
size_type find_open(size_type i) const
Calculate the matching opening parenthesis to the closing parenthesis at position i.
size_type find_close(size_type i) const
Calculate the index of the matching closing parenthesis to the parenthesis at index i.
size_type find_open_in_pioneers(size_type i) const
size_type double_enclose(size_type i, size_type j) const
The double enclose operation.
bool operator!=(bp_support_g const &other) const noexcept
Inequality operator.
size_type enclose(size_type i) const
Calculate the index of the opening parenthesis corresponding to the closest matching parenthesis pair...
bool operator==(bp_support_g const &other) const noexcept
Equality operator.
size_type rank(size_type i) const
Returns the number of opening parentheses up to and including index i.
bp_support_g(const bp_support_g &v)
Copy constructor.
int_vector_size_type size_type
Definition: int_vector.hpp:266
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
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)
int_vector.hpp contains the sdsl::int_vector class.
Namespace for the succinct data structure library.
uint64_t near_rmq_open(const bit_vector &bp, const uint64_t begin, const uint64_t end)
void calculate_matches(const bit_vector &bp, int_vector &matches)
find_open/find_close for closing/opening parentheses.
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
int_vector< 1 > bit_vector
bit_vector is a specialization of the int_vector.
Definition: int_vector.hpp:51
bit_vector calculate_pioneers_bitmap(const bit_vector &bp, uint64_t block_size)
Calculate pioneers as defined in the paper of Geary et al. (CPM 2004)
uint64_t near_find_open(const bit_vector &bp, uint64_t i, const uint64_t block_size)
uint64_t near_find_close(const bit_vector &bp, const uint64_t i, const uint64_t block_size)
void calculate_enclose(const bit_vector &bp, int_vector &enclose)
Calculates enclose answers for a balanced parentheses sequence.
uint64_t near_enclose(const bit_vector &bp, uint64_t i, const uint64_t block_size)
Find the opening parenthesis of the enclosing pair if this parenthesis is near.
nearest_neighbour_dictionary.hpp contains a class which supports rank/select for sparse populated sds...
rank_support.hpp contains classes that support a sdsl::bit_vector with constant time rank information...
rmq_support.hpp contains different range minimum support data structures.
select_support.hpp contains classes that support a sdsl::bit_vector with constant time select informa...
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.