SDSL  3.0.0
Succinct Data Structure Library
bp_support_sada.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.
9 #ifndef INCLUDED_SDSL_BP_SUPPORT_SADA
10 #define INCLUDED_SDSL_BP_SUPPORT_SADA
11 
12 #include <map>
13 #include <set>
14 #include <stack>
15 #include <stdexcept>
16 #include <utility>
17 
19 #include <sdsl/fast_cache.hpp>
20 #include <sdsl/int_vector.hpp>
21 #include <sdsl/rank_support.hpp>
22 #include <sdsl/select_support.hpp>
23 #ifndef NDEBUG
24 #include <algorithm>
25 #endif
26 #include <iostream>
27 
28 namespace sdsl
29 {
30 
32 
59 template <uint32_t t_sml_blk = 256,
60  uint32_t t_med_deg = 32,
61  class t_rank = rank_support_v5<>,
62  class t_select = select_support_mcl<>>
64 {
65  public:
70  typedef t_rank rank_type;
71  typedef t_select select_type;
72 
73  private:
74  static_assert(0 < t_sml_blk, "bp_support_sada: t_sml_blk should be greater than 0!");
75  const bit_vector * m_bp = nullptr; // the supported balanced parentheses sequence as bit_vector
76  rank_type m_bp_rank; // RS for the BP sequence => see excess() and rank()
77  select_type m_bp_select; // SS for the BP sequence => see select()
78 
79  sml_block_array_type m_sml_block_min_max;
80  med_block_array_type m_med_block_min_max;
81 
82  size_type m_size = 0; // number of supported parentheses
83  size_type m_sml_blocks = 0; // number of small sized blocks
84  size_type m_med_blocks = 0; // number of medium sized blocks
85  size_type m_med_inner_blocks = 0; // number of inner nodes in the min max tree of the medium sized blocks
86 //#define USE_CACHE
87 #ifdef USE_CACHE
88  mutable fast_cache find_close_cache;
89  mutable fast_cache find_open_cache;
90  mutable fast_cache select_cache;
91 #endif
92 
93  inline static size_type sml_block_idx(size_type i) { return i / t_sml_blk; }
94 
95  inline static size_type med_block_idx(size_type i) { return i / (t_sml_blk * t_med_deg); }
96 
97  inline static bool is_root(size_type v) { return v == 0; }
98 
99  inline static bool is_left_child(size_type v)
100  {
101  assert(!is_root(v));
102  return v % 2;
103  }
104 
105  inline static bool is_right_child(size_type v)
106  {
107  assert(!is_root(v));
108  return !(v % 2);
109  }
110 
111  inline static size_type parent(size_type v)
112  {
113  assert(!is_root(v));
114  return (v - 1) / 2;
115  }
116 
117  inline static size_type left_child(size_type v) { return 2 * v + 1; }
118 
119  inline static size_type right_child(size_type v) { return 2 * v + 2; }
120 
121  inline bool node_exists(size_type v) const { return v < (m_med_inner_blocks + m_med_blocks); }
122 
123  inline static size_type right_sibling(size_type v) { return ++v; }
124 
125  inline static size_type left_sibling(size_type v) { return --v; }
126 
127  inline bool is_leaf(size_type v) const { return v >= m_med_inner_blocks; }
128 
129  inline difference_type min_value(size_type v) const
130  {
131  return m_size - ((difference_type)m_med_block_min_max[2 * v]);
132  }
133 
134  inline difference_type max_value(size_type v) const { return m_med_block_min_max[2 * v + 1] - m_size; }
135 
136  inline difference_type sml_min_value(size_type sml_block) const
137  {
138  return (1 - ((difference_type)m_sml_block_min_max[sml_block << 1]));
139  }
140 
141  inline difference_type sml_max_value(size_type sml_block) const
142  {
143  return (difference_type)m_sml_block_min_max[(sml_block << 1) + 1] - 1;
144  }
145 
146  void print_node(size_type v) const
147  {
148  std::cout << "v = " << v << " (" << min_value(v) << ", " << max_value(v) << ")";
149  if (is_leaf(v))
150  {
151  std::cout << " range: [" << (v - m_med_inner_blocks) * t_med_deg * t_sml_blk << ","
152  << (v - m_med_inner_blocks + 1) * t_med_deg * t_sml_blk - 1 << "]";
153  }
154  std::cout << std::endl;
155  }
156 
158 
164  size_type fwd_excess(size_type i, difference_type rel) const
165  {
166  size_type j;
167  // (1) search the small block for the answer
168  if ((j = near_fwd_excess(*m_bp, i + 1, rel, t_sml_blk)) > i) { return j; }
169  difference_type desired_excess = excess(i) + rel;
170  // (2) scan the small blocks of the current median block for an answer
171  if ((j = fwd_excess_in_med_block(sml_block_idx(i) + 1, desired_excess)) != size()) { return j; }
172  // (3) search the min-max tree of the medium blocks for the right med block
173  if (med_block_idx(i) == m_med_blocks) // if we are already in the last medium block => we are done
174  return size();
175  size_type v = m_med_inner_blocks + med_block_idx(i);
176  // (3 a) go up the tree
177  while (!is_root(v))
178  {
179  if (is_left_child(v))
180  { // if the node is a left child
181  v = right_sibling(v); // choose right sibling
182  if (min_value(v) <= desired_excess and desired_excess <= max_value(v)) // found solution
183  break;
184  }
185  v = parent(v); // choose parent
186  }
187  // (3 b) go down the tree
188  if (!is_root(v))
189  { // found solution for the query
190  while (!is_leaf(v))
191  {
192  v = left_child(v); // choose left child
193  if (!(min_value(v) <= desired_excess and desired_excess <= max_value(v)))
194  {
195  v = right_sibling(v); // choose right child == right sibling of the left child
196  assert((min_value(v) <= desired_excess and desired_excess <= max_value(v)));
197  }
198  }
199  return fwd_excess_in_med_block((v - m_med_inner_blocks) * t_med_deg, desired_excess);
200  }
201  // no solution found
202  return size();
203  }
204 
206 
211  size_type bwd_excess(size_type i, difference_type rel) const
212  {
213  size_type j;
214  if (i == 0) { return rel == 0 ? -1 : size(); }
215  // (1) search the small block for the answer
216  if ((j = near_bwd_excess(*m_bp, i - 1, rel, t_sml_blk)) < i or j == (size_type)-1) { return j; }
217  difference_type desired_excess = excess(i) + rel;
218  // (2) scan the small blocks of the current median block for an answer
219  if ((j = bwd_excess_in_med_block(sml_block_idx(i) - 1, desired_excess)) != size()) { return j; }
220  // (3) search the min-max tree of the medium blocks for the right med block
221  if (med_block_idx(i) == 0)
222  { // if we are already in the first medium block => we are done
223  if (desired_excess == 0) return -1;
224  return size();
225  }
226  size_type v = m_med_inner_blocks + med_block_idx(i);
227  // (3 a) go up the tree
228  while (!is_root(v))
229  {
230  if (is_right_child(v))
231  { // if the node is a right child
232  v = left_sibling(v); // choose left sibling
233  if (min_value(v) <= desired_excess and desired_excess <= max_value(v)) // found solution
234  break;
235  }
236  v = parent(v); // choose parent
237  }
238  // (3 b) go down the tree
239  if (!is_root(v))
240  { // found solution for the query
241  while (!is_leaf(v))
242  {
243  v = right_child(v); // choose child
244  if (!(min_value(v) <= desired_excess and desired_excess <= max_value(v)))
245  {
246  v = left_sibling(v); // choose left child == left sibling of the right child
247  assert((min_value(v) <= desired_excess and desired_excess <= max_value(v)));
248  }
249  }
250  return bwd_excess_in_med_block((v - m_med_inner_blocks) * t_med_deg + (t_med_deg - 1), desired_excess);
251  }
252  else if (desired_excess == 0)
253  {
254  return -1;
255  }
256  // no solution found
257  return size();
258  }
259 
262  size_type bwd_excess_in_med_block(size_type sml_block_idx, difference_type desired_excess) const
263  {
264  // get the first small block in the medium block right to the current med block
265  size_type first_sml_block_in_med_block = (med_block_idx(sml_block_idx * t_sml_blk)) * t_med_deg;
266 
267  while ((sml_block_idx + 1) and sml_block_idx >= first_sml_block_in_med_block)
268  {
269  difference_type ex = (sml_block_idx == 0) ? 0 : excess(sml_block_idx * t_sml_blk - 1);
270  difference_type min_ex = ex + (1 - ((difference_type)m_sml_block_min_max[2 * sml_block_idx]));
271  difference_type max_ex = ex + (m_sml_block_min_max[2 * sml_block_idx + 1] - 1);
272 
273  if (min_ex <= desired_excess and desired_excess <= max_ex)
274  {
275  size_type j = near_bwd_excess(*m_bp,
276  (sml_block_idx + 1) * t_sml_blk - 1,
277  desired_excess - excess((sml_block_idx + 1) * t_sml_blk),
278  t_sml_blk);
279  return j;
280  }
281  --sml_block_idx;
282  }
283  if (sml_block_idx == 0 and desired_excess == 0) return -1;
284  return size();
285  }
286 
289  size_type fwd_excess_in_med_block(size_type sml_block_idx, difference_type desired_excess) const
290  {
291  // get the first small block in the medium block right to the current med block
292  size_type first_sml_block_nr_in_next_med_block = (med_block_idx(sml_block_idx * t_sml_blk) + 1) * t_med_deg;
293  if (first_sml_block_nr_in_next_med_block > m_sml_blocks) first_sml_block_nr_in_next_med_block = m_sml_blocks;
294 
295  assert(sml_block_idx > 0);
296  while (sml_block_idx < first_sml_block_nr_in_next_med_block)
297  {
298  difference_type ex = excess(sml_block_idx * t_sml_blk - 1);
299  difference_type min_ex = ex + (1 - ((difference_type)m_sml_block_min_max[2 * sml_block_idx]));
300  difference_type max_ex = ex + m_sml_block_min_max[2 * sml_block_idx + 1] - 1;
301  if (min_ex <= desired_excess and desired_excess <= max_ex)
302  {
303  size_type j = near_fwd_excess(*m_bp, sml_block_idx * t_sml_blk, desired_excess - ex, t_sml_blk);
304  return j;
305  }
306  ++sml_block_idx;
307  }
308  return size();
309  }
310 
311  public:
312  const rank_type & bp_rank = m_bp_rank;
313  const select_type & bp_select = m_bp_select;
314  const sml_block_array_type & sml_block_min_max = m_sml_block_min_max;
316  const med_block_array_type & med_block_min_max = m_med_block_min_max;
318 
320 
323  : m_bp(v.m_bp)
324  , m_bp_rank(v.m_bp_rank)
325  , m_bp_select(v.m_bp_select)
326  , m_sml_block_min_max(v.m_sml_block_min_max)
327  , m_med_block_min_max(v.m_med_block_min_max)
328  , m_size(v.m_size)
329  , m_sml_blocks(v.m_sml_blocks)
330  , m_med_blocks(v.m_med_blocks)
331  , m_med_inner_blocks(v.m_med_inner_blocks)
332  {
333  m_bp_rank.set_vector(m_bp);
334  m_bp_select.set_vector(m_bp);
335  }
336 
338  bp_support_sada(bp_support_sada && bp_support) { *this = std::move(bp_support); }
339 
342  {
343  if (this != &bp_support)
344  {
345  m_bp = std::move(bp_support.m_bp);
346  m_bp_rank = std::move(bp_support.m_bp_rank);
347  m_bp_rank.set_vector(m_bp);
348  m_bp_select = std::move(bp_support.m_bp_select);
349  m_bp_select.set_vector(m_bp);
350 
351  m_sml_block_min_max = std::move(bp_support.m_sml_block_min_max);
352  m_med_block_min_max = std::move(bp_support.m_med_block_min_max);
353 
354  m_size = std::move(bp_support.m_size);
355  m_sml_blocks = std::move(bp_support.m_sml_blocks);
356  m_med_blocks = std::move(bp_support.m_med_blocks);
357  m_med_inner_blocks = std::move(bp_support.m_med_inner_blocks);
358  }
359  return *this;
360  }
361 
364  {
365  if (this != &v)
366  {
367  bp_support_sada tmp(v);
368  *this = std::move(tmp);
369  }
370  return *this;
371  }
372 
374  explicit bp_support_sada(const bit_vector * bp)
375  : m_bp(bp)
376  , m_size(bp == nullptr ? 0 : bp->size())
377  , m_sml_blocks((m_size + t_sml_blk - 1) / t_sml_blk)
378  , m_med_blocks((m_size + t_sml_blk * t_med_deg - 1) / (t_sml_blk * t_med_deg))
379  , m_med_inner_blocks(0)
380  {
381  if (bp == nullptr or bp->size() == 0) return;
382  // initialize rank and select
383  util::init_support(m_bp_rank, bp);
384  util::init_support(m_bp_select, bp);
385 
386  m_med_inner_blocks = 1;
387  // m_med_inner_blocks = (next power of 2 greater than or equal to m_med_blocks)-1
388  while (m_med_inner_blocks < m_med_blocks)
389  {
390  m_med_inner_blocks <<= 1;
391  assert(m_med_inner_blocks != 0);
392  }
393  --m_med_inner_blocks;
394  assert((m_med_inner_blocks == 0) or (m_med_inner_blocks % 2 == 1));
395 
396  m_sml_block_min_max = int_vector<>(2 * m_sml_blocks, 0, bits::hi(t_sml_blk + 2) + 1);
397  m_med_block_min_max = int_vector<>(2 * (m_med_blocks + m_med_inner_blocks), 0, bits::hi(2 * m_size + 2) + 1);
398 
399  // calculate min/max excess values of the small blocks and medium blocks
400  difference_type min_ex = 1, max_ex = -1, curr_rel_ex = 0, curr_abs_ex = 0;
401  for (size_type i = 0; i < m_size; ++i)
402  {
403  if ((*bp)[i])
404  ++curr_rel_ex;
405  else
406  --curr_rel_ex;
407  if (curr_rel_ex > max_ex) max_ex = curr_rel_ex;
408  if (curr_rel_ex < min_ex) min_ex = curr_rel_ex;
409  if ((i + 1) % t_sml_blk == 0 or i + 1 == m_size)
410  {
411  size_type sidx = i / t_sml_blk;
412  m_sml_block_min_max[2 * sidx] = -(min_ex - 1);
413  m_sml_block_min_max[2 * sidx + 1] = max_ex + 1;
414 
415  size_type v = m_med_inner_blocks + sidx / t_med_deg;
416 
417  if ((difference_type)(-(curr_abs_ex + min_ex) + m_size) > ((difference_type)m_med_block_min_max[2 * v]))
418  {
419  assert(curr_abs_ex + min_ex <= min_value(v));
420  m_med_block_min_max[2 * v] = -(curr_abs_ex + min_ex) + m_size;
421  }
422 
423  if ((difference_type)(curr_abs_ex + max_ex + m_size) > (difference_type)m_med_block_min_max[2 * v + 1])
424  m_med_block_min_max[2 * v + 1] = curr_abs_ex + max_ex + m_size;
425 
426  curr_abs_ex += curr_rel_ex;
427  min_ex = 1;
428  max_ex = -1;
429  curr_rel_ex = 0;
430  }
431  }
432 
433  for (size_type v = m_med_block_min_max.size() / 2 - 1; !is_root(v); --v)
434  {
435  size_type p = parent(v);
436  if (min_value(v) < min_value(p)) // update minimum
437  m_med_block_min_max[2 * p] = m_med_block_min_max[2 * v];
438  if (max_value(v) > max_value(p)) // update maximum
439  m_med_block_min_max[2 * p + 1] = m_med_block_min_max[2 * v + 1];
440  }
441  }
442 
443  void set_vector(const bit_vector * bp)
444  {
445  m_bp = bp;
446  m_bp_rank.set_vector(bp);
447  m_bp_select.set_vector(bp);
448  }
449 
453  inline difference_type excess(size_type i) const { return (m_bp_rank(i + 1) << 1) - i - 1; }
454 
458  size_type rank(size_type i) const { return m_bp_rank(i + 1); }
459 
466  {
467 #ifdef USE_CACHE
468  size_type a = 0;
469  if (select_cache.exists(i, a)) { return a; }
470  else
471  {
472  a = m_bp_select(i);
473  select_cache.write(i, a);
474  return a;
475  }
476 #endif
477  return m_bp_select(i);
478  }
479 
487  {
488  assert(i < m_size);
489  if (!(*m_bp)[i])
490  { // if there is a closing parenthesis at index i return i
491  return i;
492  }
493 #ifdef USE_CACHE
494  size_type a = 0;
495  if (find_close_cache.exists(i, a)) { return a; }
496  else
497  {
498  a = fwd_excess(i, -1);
499  find_close_cache.write(i, a);
500  return a;
501  }
502 #endif
503  return fwd_excess(i, -1);
504  }
505 
507 
513  {
514  assert(i < m_size);
515  if ((*m_bp)[i])
516  { // if there is a opening parenthesis at index i return i
517  return i;
518  }
519 #ifdef USE_CACHE
520  size_type a = 0;
521  if (find_open_cache.exists(i, a)) { return a; }
522  else
523  {
524  size_type bwd_ex = bwd_excess(i, 0);
525  if (bwd_ex == size())
526  a = size();
527  else
528  a = bwd_ex + 1;
529  find_open_cache.write(i, a);
530  return a;
531  }
532 #endif
533  size_type bwd_ex = bwd_excess(i, 0);
534  if (bwd_ex == size())
535  return size();
536  else
537  return bwd_ex + 1;
538  }
539 
542 
547  {
548  assert(i < m_size);
549  if (!(*m_bp)[i])
550  { // if there is closing parenthesis at position i
551  return find_open(i);
552  }
553  size_type bwd_ex = bwd_excess(i, -2);
554  if (bwd_ex == size())
555  return size();
556  else
557  return bwd_ex + 1;
558  }
559 
561 
568  size_type rr_enclose(const size_type i, const size_type j) const
569  {
570  assert(j < m_size);
571  assert((*m_bp)[i] == 1 and (*m_bp)[j] == 1);
572  const size_type mip1 = find_close(i) + 1;
573  if (mip1 >= j) return size();
574  return rmq_open(mip1, j);
575  }
576 
585  size_type rmq_open(const size_type l, const size_type r) const
586  {
587  assert(r < m_bp->size());
588  if (l >= r) return size();
589  size_type res = rmq(l, r - 1);
590  assert(res >= l and res <= r - 1);
591  if ((*m_bp)[res] == 1)
592  { // The parenthesis with minimal excess is opening
593  assert(find_close(res) >= r);
594  return res;
595  }
596  else
597  {
598  res = res + 1; // go to the next parenthesis to the right
599  if (res < r)
600  { // The parenthesis with minimal excess if closing and the next opening parenthesis is less than r
601  assert((*m_bp)[res] == 1);
602  size_type ec = enclose(res);
603  if (ec < l or ec == size())
604  {
605  assert(find_close(res) >= r);
606  return res;
607  }
608  else
609  {
610  assert(find_close(ec) >= r);
611  return ec;
612  }
613  }
614  else if (res == r)
615  {
616  size_type ec = enclose(res); // if m_bp[res]==0 => find_open(res), if m_bp[res]==1 => enclose(res)
617  if (ec >= l)
618  {
619  assert(ec == size() or excess(ec) == excess(res - 1));
620  return ec;
621  }
622  }
623  }
624  return size();
625  }
626 
628  {
629  assert(l_sblock <= r_sblock + 1);
630  size_type pos_min_block = (size_type)-1;
631  difference_type e = 0;
632  if (l_sblock == 0)
633  {
634  if (sml_min_value(0) <= min_ex)
635  {
636  pos_min_block = 0;
637  min_ex = sml_min_value(0);
638  }
639  l_sblock = 1;
640  }
641  for (size_type i = l_sblock; i <= r_sblock; ++i)
642  {
643  if ((e = (excess(i * t_sml_blk - 1) + sml_min_value(i))) <= min_ex)
644  {
645  pos_min_block = i;
646  min_ex = e;
647  }
648  }
649  return pos_min_block;
650  }
651 
653 
657  {
658  assert(l <= r);
659  size_type sbl = sml_block_idx(l);
660  size_type sbr = sml_block_idx(r);
661  difference_type min_rel_ex = 0;
662  if (sbl == sbr)
663  { // if l and r are in the same small block
664  return near_rmq(*m_bp, l, r, min_rel_ex);
665  }
666  else
667  {
668  difference_type min_ex = 0; // current minimal excess value
669  size_type min_pos = 0; // current min pos
670  enum min_pos_type
671  {
672  POS,
673  SMALL_BLOCK_POS,
674  MEDIUM_BLOCK_POS
675  };
676  enum min_pos_type pos_type = POS; // current
677  min_pos = near_rmq(*m_bp, l, (sbl + 1) * t_sml_blk - 1, min_rel_ex); // scan the leftmost small block of l
678  assert(min_pos >= l);
679  min_ex = excess(l) + min_rel_ex;
680 
681  size_type mbl = med_block_idx(l);
682  size_type mbr = med_block_idx(r);
683  assert(mbl <= mbr);
684 
685  size_type temp = median_block_rmq(sbl + 1,
686  std::min((mbl + 1) * t_med_deg - 1, sbr - 1),
687  min_ex); // scan the medium block of l
688  if (temp != (size_type)-1)
689  {
690  assert(temp * t_sml_blk >= l and temp * t_sml_blk <= r);
691  min_pos = temp;
692  assert(min_pos < m_sml_blocks);
693  pos_type = SMALL_BLOCK_POS;
694  }
695 #if 0
696  // sequential scan the medium blocks
697  for (size_type v=mbl+1+m_med_inner_blocks; v < mbr + m_med_inner_blocks; ++v) {
698  assert(is_leaf(v));
699  if (min_value(v) <= min_ex) {
700  min_ex = min_value(v);
701  min_pos = v;
702  assert(min_pos-m_med_inner_blocks >= 0 and min_pos < m_med_blocks-m_med_inner_blocks);
703  pos_type = MEDIUM_BLOCK_POS;
704  }
705  }
706 #else
707  // tree search in the min max tree of the medium blocks
708  if (mbr - mbl > 1)
709  {
710  size_type v = mbl + 1 + m_med_inner_blocks;
711  size_type rcb = mbl + 1; // rightmost covered block
712  size_type h = 0; // subtree height
713  while (rcb < mbr - 1)
714  { // go up the tree until the rightmost covered block >= mbr-1
715  if (min_value(v) <= min_ex)
716  {
717  min_ex = min_value(v);
718  min_pos = v;
719  pos_type = MEDIUM_BLOCK_POS;
720  }
721  if (is_right_child(v))
722  { // v is a right child
723  h += 1;
724  rcb += (1ULL << h);
725  v = right_sibling(parent(v));
726  }
727  else
728  { // it is a left child
729  rcb += (1ULL << h);
730  h += 1;
731  v = parent(v);
732  }
733  }
734  if (rcb <= mbr - 1 and min_value(v) <= min_ex)
735  {
736  min_ex = min_value(v);
737  min_pos = v;
738  pos_type = MEDIUM_BLOCK_POS;
739  }
740  assert(node_exists(v));
741  assert(rcb >= mbr - 1);
742 
743  while (rcb != mbr - 1)
744  { // go down the tree until the rightmost covered block = mbr-1
745  assert(h != (size_type)-1);
746  if (rcb > mbr - 1)
747  {
748  h = h - 1;
749  rcb = rcb - (1ULL << h);
750  v = left_child(v);
751  }
752  else
753  { // rcb < mbr-1
754  h = h - 1;
755  rcb = rcb + (1ULL << h);
756  v = right_sibling(right_child(v));
757  }
758  if (rcb <= mbr - 1 and min_value(v) <= min_ex)
759  {
760  min_ex = min_value(v);
761  min_pos = v;
762  pos_type = MEDIUM_BLOCK_POS;
763  }
764  }
765  if (pos_type == MEDIUM_BLOCK_POS)
766  {
767  while (!is_leaf(min_pos))
768  {
769  min_pos = right_child(min_pos);
770  if (!node_exists(min_pos) or min_value(min_pos) > min_ex) min_pos = left_sibling(min_pos);
771  }
772  }
773  }
774 #endif
775 
776  // search in the medium block of r
777  temp = median_block_rmq(std::max(mbr * t_med_deg, sbl + 1), sbr - 1, min_ex); // scan the medium block of r
778  if (temp != (size_type)-1)
779  {
780  assert(temp * t_sml_blk >= l and temp * t_sml_blk <= r);
781  min_pos = temp;
782  pos_type = SMALL_BLOCK_POS;
783  }
784  // search in the small block of r
785  temp = near_rmq(*m_bp, sbr * t_sml_blk, r, min_rel_ex); // scan the small block of r
786  if ((excess(sbr * t_sml_blk) + min_rel_ex) <= min_ex)
787  { // if it contains the minimum return its position
788  assert(temp >= l and temp <= r);
789  return temp;
790  }
791  // if the found minimum lies in a medium block => find its small block
792  if (pos_type == MEDIUM_BLOCK_POS)
793  {
794  min_pos = min_pos - m_med_inner_blocks;
795  temp = median_block_rmq(min_pos * t_med_deg, (min_pos + 1) * t_med_deg - 1, min_ex);
796  assert(temp != (size_type)-1); // assert that we find a solution
797  assert(temp * t_sml_blk >= l and temp * t_sml_blk <= r);
798  min_pos = temp;
799  pos_type = SMALL_BLOCK_POS;
800  }
801  if (pos_type == SMALL_BLOCK_POS)
802  {
803  min_pos = near_rmq(*m_bp, min_pos * t_sml_blk, (min_pos + 1) * t_sml_blk - 1, min_rel_ex);
804  assert(min_pos >= l and min_pos <= r);
805  }
806  return min_pos;
807  }
808  }
809 
811 
819  {
820  assert(j > i and j < m_size);
821  assert((*m_bp)[i] == 1 and (*m_bp)[j] == 1);
822  size_type mi = find_close(i); // matching parenthesis to i
823  assert(mi > i and mi < j);
824  assert(find_close(j) > j);
825  size_type k = enclose(j);
826  if (k == m_size or k < i) // there exists no opening parenthesis at position mi<k<j.
827  return m_size;
828  size_type kk;
829  do {
830  kk = k;
831  k = enclose(k);
832  } while (k != m_size and k > mi);
833  return kk;
834  }
835 
837 
843  {
844  assert(j > i);
845  assert((*m_bp)[i] == 1 and (*m_bp)[j] == 1);
846  size_type k = rr_enclose(i, j);
847  if (k == size())
848  return enclose(j);
849  else
850  return enclose(k);
851  }
852 
854 
857  {
858  assert(i < m_size);
859  if (!i) return 0;
860  size_type ones = m_bp_rank(i);
861  if (ones)
862  { // ones > 0
863  assert(m_bp_select(ones) < i);
864  return i - m_bp_select(ones) - 1;
865  }
866  else
867  {
868  return i;
869  }
870  }
871 
873 
878  {
879  assert(i < m_size);
880  size_type bwd_ex = bwd_excess(i, -d - 1);
881  if (bwd_ex == size())
882  return size();
883  else
884  return bwd_ex + 1;
885  }
886 
890  size_type size() const { return m_size; }
891 
893 
897  size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
898  {
899  structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
900  size_type written_bytes = 0;
901  written_bytes += write_member(m_size, out, child, "size");
902  written_bytes += write_member(m_sml_blocks, out, child, "sml_block_cnt");
903  written_bytes += write_member(m_med_blocks, out, child, "med_block_cnt");
904  written_bytes += write_member(m_med_inner_blocks, out, child, "med_inner_blocks");
905 
906  written_bytes += m_bp_rank.serialize(out, child, "bp_rank");
907  written_bytes += m_bp_select.serialize(out, child, "bp_select");
908 
909  written_bytes += m_sml_block_min_max.serialize(out, child, "sml_blocks");
910  written_bytes += m_med_block_min_max.serialize(out, child, "med_blocks");
911 
912  structure_tree::add_size(child, written_bytes);
913  return written_bytes;
914  }
915 
917 
921  void load(std::istream & in, const bit_vector * bp)
922  {
923  m_bp = bp;
924  read_member(m_size, in);
925  assert(m_size == bp->size());
926  read_member(m_sml_blocks, in);
927  read_member(m_med_blocks, in);
928  read_member(m_med_inner_blocks, in);
929 
930  m_bp_rank.load(in, m_bp);
931  m_bp_select.load(in, m_bp);
932 
933  m_sml_block_min_max.load(in);
934  m_med_block_min_max.load(in);
935  }
936 
937  template <typename archive_t>
938  void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
939  {
940  ar(CEREAL_NVP(m_size));
941  ar(CEREAL_NVP(m_sml_blocks));
942  ar(CEREAL_NVP(m_med_blocks));
943  ar(CEREAL_NVP(m_med_inner_blocks));
944  ar(CEREAL_NVP(m_bp_rank));
945  ar(CEREAL_NVP(m_bp_select));
946  ar(CEREAL_NVP(m_sml_block_min_max));
947  ar(CEREAL_NVP(m_med_block_min_max));
948  }
949 
950  template <typename archive_t>
951  void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
952  {
953  ar(CEREAL_NVP(m_size));
954  ar(CEREAL_NVP(m_sml_blocks));
955  ar(CEREAL_NVP(m_med_blocks));
956  ar(CEREAL_NVP(m_med_inner_blocks));
957  ar(CEREAL_NVP(m_bp_rank));
958  ar(CEREAL_NVP(m_bp_select));
959  ar(CEREAL_NVP(m_sml_block_min_max));
960  ar(CEREAL_NVP(m_med_block_min_max));
961  }
962 
964  bool operator==(bp_support_sada const & other) const noexcept
965  {
966  return (m_bp_rank == other.m_bp_rank) && (m_bp_select == other.m_bp_select) &&
967  (m_sml_block_min_max == other.m_sml_block_min_max) &&
968  (m_med_block_min_max == other.m_med_block_min_max) && (m_size == other.m_size) &&
969  (m_sml_blocks == other.m_sml_blocks) && (m_med_blocks == other.m_med_blocks) &&
970  (m_med_inner_blocks == other.m_med_inner_blocks);
971  }
972 
974  bool operator!=(bp_support_sada const & other) const noexcept { return !(*this == other); }
975 };
976 
977 } // namespace sdsl
978 
979 #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.
size_type select(size_type i) const
Returns the index of the i-th opening parenthesis.
size_type enclose(size_type i) const
Calculate the index of the opening parenthesis corresponding to the closest matching parenthesis pair...
size_type median_block_rmq(size_type l_sblock, size_type r_sblock, bit_vector::difference_type &min_ex) const
size_type double_enclose(size_type i, size_type j) const
The double enclose operation.
size_type preceding_closing_parentheses(size_type i) const
Return the number of zeros which proceed position i in the balanced parentheses sequence.
size_type rr_enclose_naive(size_type i, size_type j) const
The range restricted enclose operation.
void load(std::istream &in, const bit_vector *bp)
Load the bp_support_sada for a bit_vector v.
size_type level_anc(size_type i, size_type d) const
Returns the level ancestor of the node i.
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 rank(size_type i) const
Returns the number of opening parentheses up to and including index i.
const select_type & bp_select
SS for the underlying BP sequence.
size_type find_close(size_type i) const
Calculate the index of the matching closing parenthesis to the parenthesis at index i.
bool operator!=(bp_support_sada const &other) const noexcept
Inequality operator.
bp_support_sada(const bit_vector *bp)
Constructor.
bp_support_sada(const bp_support_sada &v)
Copy constructor.
size_type find_open(size_type i) const
Calculate the matching opening parenthesis to the closing parenthesis at position i.
void set_vector(const bit_vector *bp)
bp_support_sada(bp_support_sada &&bp_support)
Move constructor.
bool operator==(bp_support_sada const &other) const noexcept
Equality operator.
bit_vector::size_type size_type
bp_support_sada & operator=(const bp_support_sada &v)
Assignment operator.
size_type size() const
The size of the supported balanced parentheses sequence.
bp_support_sada & operator=(bp_support_sada &&bp_support)
Assignment operator.
bit_vector::difference_type difference_type
const rank_type & bp_rank
RS for the underlying BP sequence.
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
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 .
difference_type excess(size_type i) const
Calculates the excess value at index i.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the bp_support_sada to a stream.
const med_block_array_type & med_block_min_max
Array containing the min max tree of the medium blocks.
const sml_block_array_type & sml_block_min_max
Small blocks array.
size_type rr_enclose(const size_type i, const size_type j) const
The range restricted enclose operation for parentheses pairs and .
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
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.
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(const bit_vector &bp, uint64_t l, uint64_t r, bit_vector::difference_type &min_rel_ex)
Calculate the position with minimal excess value in the interval [l..r].
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
uint64_t near_fwd_excess(const bit_vector &bp, uint64_t i, bit_vector::difference_type rel, const uint64_t block_size)
uint64_t near_bwd_excess(const bit_vector &bp, uint64_t i, bit_vector::difference_type rel, const uint64_t block_size)
Near backward excess.
rank_support.hpp contains classes that support a sdsl::bit_vector with constant time rank information...
select_support.hpp contains classes that support a sdsl::bit_vector with constant time select informa...
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
void write(size_type i, size_type x)
Definition: fast_cache.hpp:36
bool exists(size_type i, size_type &x)
Definition: fast_cache.hpp:25