SDSL  3.0.0
Succinct Data Structure Library
bp_support_algorithm.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_ALGORITHM
9 #define INCLUDED_SDSL_BP_SUPPORT_ALGORITHM
10 
11 #include <map> // for calculate_pioneers_bitmap method
12 #include <stack> // for calculate_pioneers_bitmap method
13 
14 #include <sdsl/int_vector.hpp> // for bit_vector
16 
17 namespace sdsl
18 {
19 
20 // This structure contains lookup tables
21 template <typename T = void>
22 struct excess
23 {
24  struct impl
25  {
26  // Given an excess value x in [-8,8] and a 8-bit
27  // word w interpreted as parentheses sequence.
28  // near_fwd_pos[(x+8)<<8 | w] contains the minimal position
29  // p in [0..7] where the excess value x is reached, or 8
30  // if x is not reached in w.
31  uint8_t near_fwd_pos[(8 - (-8)) * 256];
32 
33  // Given an excess value of x in [-8,8] and a 8-bit
34  // word w interpreted as parentheses sequence.
35  // near_bwd_pos[(x+8)<<8 | w] contains the maximal position
36  // p in [0..7] where the excess value x is reached, or 8
37  // if x is not reached in w.
38  uint8_t near_bwd_pos[(8 - (-8)) * 256];
39 
40  // Given a 8-bit word w. word_sum[w] contains the
41  // excess value of w.
42  int8_t word_sum[256];
43 
44  // Given a 8-bit word w. min[w] contains the
45  // minimal excess value in w.
46  int8_t min[256];
47 
48  // Given a 8-bit word w. min_pos_max[w] contains
49  // the maximal position p in w, where min[w] is
50  // reached
51  int8_t min_pos_max[256];
52 
53  // Given an excess value x in [1,8] and a 8-bit
54  // word w interpreted as parentheses sequence.
55  // min_match_pos_packed[w]:[(x-1)*4,x*4] contains
56  // the minimal position, where excess value
57  // -x is reached and 9, if there is no such position.
58  uint32_t min_match_pos_packed[256];
59 
60  // Given an excess value x in [1,8] and a 8-bit
61  // word w interpreted as parentheses sequence.
62  // max_match_pos_packed[w]:[(x-1)*4,x*4] contains
63  // the maximal position, where excess value
64  // -x is reached and 9, if there is no such position.
65  uint32_t max_match_pos_packed[256];
66 
67  // Given a 8-bit word w. x=min_and_info[w] contains
68  // the following information.
69  // * [0..7] the minimum excess value in w + 8 of an opening parenthesis
70  // * [8..11] the maximal position of the minimal excess value
71  // * [12..15] the number of ones in the word
72  // if w != 0, and 17 for w=0.
73  uint16_t min_open_excess_info[256];
74 
75  impl()
76  {
77  for (int32_t x = -8; x < 8; ++x)
78  {
79  for (uint16_t w = 0; w < 256; ++w)
80  {
81  uint16_t i = (x + 8) << 8 | w;
82  near_fwd_pos[i] = 8;
83  int8_t p = 0;
84  int8_t excess = 0;
85  do {
86  excess += 1 - 2 * ((w & (1 << p)) == 0);
87  if (excess == x)
88  {
89  near_fwd_pos[i] = p;
90  break;
91  }
92  ++p;
93  } while (p < 8);
94 
95  near_bwd_pos[i] = 8;
96  p = 7;
97  excess = 0;
98  do {
99  excess += 1 - 2 * ((w & (1 << p)) > 0);
100  if (excess == x)
101  {
102  near_bwd_pos[i] = p;
103  break;
104  }
105  --p;
106  } while (p > -1);
107  }
108  }
109  int_vector<> packed_mins(1, 0, 32);
110  int_vector<> packed_maxs(1, 0, 32);
111  for (uint16_t w = 0; w < 256; ++w)
112  {
113  int8_t excess = 0;
114  int8_t rev_excess = 0;
115  int32_t min_excess_of_open = 17;
116  int32_t min_excess_of_open_pos = 0;
117  uint32_t ones = 0;
118  min[w] = 8;
119  packed_mins[0] = 0x99999999U;
120  packed_maxs[0] = 0x99999999U;
121  packed_mins.width(4);
122  packed_maxs.width(4);
123  for (uint16_t p = 0; p < 8; ++p)
124  {
125  ones += (w & (1 << p)) != 0;
126  excess += 1 - 2 * ((w & (1 << p)) == 0);
127  if (excess <= min[w])
128  {
129  min[w] = excess;
130  min_pos_max[w] = p;
131  }
132  if (excess < 0 and packed_mins[-excess - 1] == 9) { packed_mins[-excess - 1] = p; }
133  if (w & (1 << p) and excess + 8 <= min_excess_of_open)
134  {
135  min_excess_of_open = excess + 8;
136  min_excess_of_open_pos = p;
137  }
138  rev_excess += 1 - 2 * ((w & (1 << (7 - p))) > 0);
139  if (rev_excess < 0 and packed_maxs[-rev_excess - 1] == 9) { packed_maxs[-rev_excess - 1] = 7 - p; }
140  }
141  word_sum[w] = excess;
142  packed_mins.width(32);
143  min_match_pos_packed[w] = packed_mins[0];
144  packed_maxs.width(32);
145  max_match_pos_packed[w] = packed_maxs[0];
146  min_open_excess_info[w] = (min_excess_of_open) | (min_excess_of_open_pos << 8) | (ones << 12);
147  }
148  }
149  };
150  static impl data;
151 };
152 
153 template <typename T>
155 
157 
166 {
167  bit_vector pioneer_bitmap(bp.size(), 0);
168 
169  std::stack<uint64_t> opening_parenthesis;
170  uint64_t blocks = (bp.size() + block_size - 1) / block_size;
171  // calculate positions of findclose and findopen pioneers
172  for (uint64_t block_nr = 0; block_nr < blocks; ++block_nr)
173  {
174  std::map<uint64_t, uint64_t> block_and_position; // for find_open and find_close
175  std::map<uint64_t, uint64_t> matching_position; // for find_open and find_close
176  for (uint64_t i = 0, j = block_nr * block_size; i < block_size and j < bp.size(); ++i, ++j)
177  {
178  if (bp[j])
179  { // opening parenthesis
180  opening_parenthesis.push(j);
181  }
182  else
183  { // closing parenthesis
184  uint64_t position = opening_parenthesis.top();
185  uint64_t blockpos = position / block_size;
186  opening_parenthesis.pop();
187  block_and_position[blockpos] = position;
188  matching_position[blockpos] = j; // greatest j is pioneer
189  }
190  }
191  for (std::map<uint64_t, uint64_t>::const_iterator it = block_and_position.begin(),
192  end = block_and_position.end(),
193  mit = matching_position.begin();
194  it != end and it->first != block_nr;
195  ++it, ++mit)
196  {
197  // opening and closing pioneers are symmetric
198  pioneer_bitmap[it->second] = 1;
199  pioneer_bitmap[mit->second] = 1;
200  }
201  }
202  // assert that the sequence is balanced
203  assert(opening_parenthesis.empty());
204  return pioneer_bitmap;
205 }
206 
208 
219 {
220  bit_vector pioneer_bitmap(bp.size(), 0);
221 
222  sorted_stack_support opening_parenthesis(bp.size());
223  uint64_t cur_pioneer_block = 0, last_start = 0, last_j = 0, cur_block = 0, first_index_in_block = 0;
224  // calculate positions of findclose and findopen pioneers
225  for (uint64_t j = 0, new_block = block_size; j < bp.size(); ++j, --new_block)
226  {
227  if (!(new_block))
228  {
229  cur_pioneer_block = j / block_size;
230  ++cur_block;
231  first_index_in_block = j;
232  new_block = block_size;
233  }
234 
235  if (bp[j])
236  { // opening parenthesis
237  if (/*j < bp.size() is not necessary as the last parenthesis is always a closing one*/
238  new_block > 1 and !bp[j + 1])
239  {
240  ++j;
241  --new_block;
242  continue;
243  }
244  opening_parenthesis.push(j);
245  }
246  else
247  {
248  assert(!opening_parenthesis.empty());
249  uint64_t start = opening_parenthesis.top();
250  opening_parenthesis.pop();
251  if (start < first_index_in_block)
252  {
253  if ((start / block_size) == cur_pioneer_block)
254  {
255  pioneer_bitmap[last_start] = pioneer_bitmap[last_j] = 0; // override false pioneer
256  }
257  pioneer_bitmap[start] = pioneer_bitmap[j] = 1;
258  cur_pioneer_block = start / block_size;
259  last_start = start;
260  last_j = j;
261  }
262  }
263  }
264  // assert that the sequence is balanced
265  assert(opening_parenthesis.empty());
266  return pioneer_bitmap;
267 }
268 
270 
278 template <class int_vector>
279 void calculate_matches(const bit_vector & bp, int_vector & matches)
280 {
281  matches = int_vector(bp.size(), 0, bits::hi(bp.size()) + 1);
282  std::stack<uint64_t> opening_parenthesis;
283  for (uint64_t i = 0; i < bp.size(); ++i)
284  {
285  if (bp[i])
286  { // opening parenthesis
287  opening_parenthesis.push(i);
288  }
289  else
290  { // closing parenthesis
291  assert(!opening_parenthesis.empty());
292  uint64_t position = opening_parenthesis.top();
293  opening_parenthesis.pop();
294  matches[i] = position;
295  assert(matches[i] == position);
296  matches[position] = i;
297  assert(matches[position] == i);
298  }
299  }
300  // assert that the sequence is balanced
301  assert(opening_parenthesis.empty());
302 }
303 
305 
313 template <class int_vector>
314 void calculate_enclose(const bit_vector & bp, int_vector & enclose)
315 {
316  enclose = int_vector(bp.size(), 0, bits::hi(bp.size()) + 1);
317  std::stack<uint64_t> opening_parenthesis;
318  for (uint64_t i = 0; i < bp.size(); ++i)
319  {
320  if (bp[i])
321  { // opening parenthesis
322  if (!opening_parenthesis.empty())
323  {
324  uint64_t position = opening_parenthesis.top();
325  enclose[i] = position;
326  assert(enclose[i] == position);
327  }
328  else
329  enclose[i] = bp.size();
330  opening_parenthesis.push(i);
331  }
332  else
333  { // closing parenthesis
334  uint64_t position = opening_parenthesis.top();
335  enclose[i] = position; // find open answer if i is a closing parenthesis
336  opening_parenthesis.pop();
337  }
338  }
339  // assert that the sequence is balanced
340  assert(opening_parenthesis.empty());
341 }
342 
343 inline uint64_t near_find_close(const bit_vector & bp, const uint64_t i, const uint64_t block_size)
344 {
345  typedef bit_vector::difference_type difference_type;
346  difference_type excess_v = 1;
347 
348  const uint64_t end = ((i + 1) / block_size + 1) * block_size;
349  const uint64_t l = (((i + 1) + 7) / 8) * 8;
350  const uint64_t r = (end / 8) * 8;
351  for (uint64_t j = i + 1; j < std::min(end, l); ++j)
352  {
353  if (bp[j])
354  ++excess_v;
355  else
356  {
357  --excess_v;
358  if (excess_v == 0) { return j; }
359  }
360  }
361  const uint64_t * b = bp.data();
362  for (uint64_t j = l; j < r; j += 8)
363  {
364  if (excess_v <= 8)
365  {
366  assert(excess_v > 0);
367  uint32_t x = excess<>::data.min_match_pos_packed[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
368  uint8_t p = (x >> ((excess_v - 1) << 2)) & 0xF;
369  if (p < 9) { return j + p; }
370  }
371  excess_v += excess<>::data.word_sum[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
372  }
373  for (uint64_t j = std::max(l, r); j < end; ++j)
374  {
375  if (bp[j])
376  ++excess_v;
377  else
378  {
379  --excess_v;
380  if (excess_v == 0) { return j; }
381  }
382  }
383  return i;
384 }
385 
386 inline uint64_t near_find_closing(const bit_vector & bp, uint64_t i, uint64_t closings, const uint64_t block_size)
387 {
388  typedef bit_vector::difference_type difference_type;
389  difference_type excess_v = 0;
390  difference_type succ_excess = -closings;
391 
392  const uint64_t end = (i / block_size + 1) * block_size;
393  const uint64_t l = (((i) + 7) / 8) * 8;
394  const uint64_t r = (end / 8) * 8;
395  for (uint64_t j = i; j < std::min(end, l); ++j)
396  {
397  if (bp[j])
398  ++excess_v;
399  else
400  {
401  --excess_v;
402  if (excess_v == succ_excess) { return j; }
403  }
404  }
405  const uint64_t * b = bp.data();
406  for (uint64_t j = l; j < r; j += 8)
407  {
408  if (excess_v - succ_excess <= 8)
409  {
410  uint32_t x = excess<>::data.min_match_pos_packed[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
411  uint8_t p = (x >> (((excess_v - succ_excess) - 1) << 2)) & 0xF;
412  if (p < 9) { return j + p; }
413  }
414  excess_v += excess<>::data.word_sum[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
415  }
416  for (uint64_t j = std::max(l, r); j < end; ++j)
417  {
418  if (bp[j])
419  ++excess_v;
420  else
421  {
422  --excess_v;
423  if (excess_v == succ_excess) { return j; }
424  }
425  }
426  return i - 1;
427 }
428 
429 inline uint64_t near_fwd_excess(const bit_vector & bp,
430  uint64_t i,
432  const uint64_t block_size)
433 {
434  typedef bit_vector::difference_type difference_type;
435  difference_type excess_v = rel;
436 
437  const uint64_t end = (i / block_size + 1) * block_size;
438  const uint64_t l = (((i) + 7) / 8) * 8;
439  const uint64_t r = (end / 8) * 8;
440  for (uint64_t j = i; j < std::min(end, l); ++j)
441  {
442  excess_v += 1 - 2 * bp[j];
443  if (!excess_v) { return j; }
444  }
445  excess_v += 8;
446  const uint64_t * b = bp.data();
447  for (uint64_t j = l; j < r; j += 8)
448  {
449  if (excess_v >= 0 and excess_v <= 16)
450  {
451  uint32_t x = excess<>::data.near_fwd_pos[(excess_v << 8) + (((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF)];
452  if (x < 8) { return j + x; }
453  }
454  excess_v -= excess<>::data.word_sum[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
455  }
456  excess_v -= 8;
457  for (uint64_t j = std::max(l, r); j < end; ++j)
458  {
459  excess_v += 1 - 2 * bp[j];
460  if (!excess_v) { return j; }
461  }
462  return i - 1;
463 }
464 
466 
471 inline uint64_t near_rmq(const bit_vector & bp, uint64_t l, uint64_t r, bit_vector::difference_type & min_rel_ex)
472 {
473  typedef bit_vector::difference_type difference_type;
474  const uint64_t l8 = (((l + 1) + 7) / 8) * 8;
475  const uint64_t r8 = (r / 8) * 8;
476  difference_type excess_v = 0;
477  difference_type min_pos = l;
478  min_rel_ex = 0;
479  for (uint64_t j = l + 1; j < std::min(l8, r + 1); ++j)
480  {
481  if (bp[j])
482  ++excess_v;
483  else
484  {
485  --excess_v;
486  if (excess_v <= min_rel_ex)
487  {
488  min_rel_ex = excess_v;
489  min_pos = j;
490  }
491  }
492  }
493 
494  const uint64_t * b = bp.data();
495  for (uint64_t j = l8; j < r8; j += 8)
496  {
497  int8_t x = excess<>::data.min[(((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF)];
498  if ((excess_v + x) <= min_rel_ex)
499  {
500  min_rel_ex = excess_v + x;
501  min_pos = j + excess<>::data.min_pos_max[(((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF)];
502  }
503  excess_v += excess<>::data.word_sum[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
504  }
505  for (uint64_t j = std::max(l8, r8); j < r + 1; ++j)
506  {
507  if (bp[j])
508  ++excess_v;
509  else
510  {
511  --excess_v;
512  if (excess_v <= min_rel_ex)
513  {
514  min_rel_ex = excess_v;
515  min_pos = j;
516  }
517  }
518  }
519  return min_pos;
520 }
521 
523 /* This method searches the maximal parenthesis j, with \f$ j\leq i \f$,
524  * such that \f$ excess(j) = excess(i+1)+rel \f$ and i < bp.size()-1
525  */
526 inline uint64_t near_bwd_excess(const bit_vector & bp,
527  uint64_t i,
529  const uint64_t block_size)
530 {
531  typedef bit_vector::difference_type difference_type;
532  difference_type excess_v = rel;
533  const difference_type begin = ((difference_type)(i) / block_size) * block_size;
534  const difference_type r = ((difference_type)(i) / 8) * 8;
535  const difference_type l = ((difference_type)((begin + 7) / 8)) * 8;
536  for (difference_type j = i + 1; j >= /*begin*/ std::max(r, begin); --j)
537  {
538  if (bp[j])
539  ++excess_v;
540  else
541  --excess_v;
542  if (!excess_v) return j - 1;
543  }
544 
545  excess_v += 8;
546  const uint64_t * b = bp.data();
547  for (difference_type j = r - 8; j >= l; j -= 8)
548  {
549  if (excess_v >= 0 and excess_v <= 16)
550  {
551  uint32_t x = excess<>::data.near_bwd_pos[(excess_v << 8) + (((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF)];
552  if (x < 8) { return j + x - 1; }
553  }
554  excess_v += excess<>::data.word_sum[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
555  }
556  excess_v -= 8;
557  for (difference_type j = std::min(l, r); j > begin; --j)
558  {
559  if (bp[j])
560  ++excess_v;
561  else
562  --excess_v;
563  if (!excess_v) return j - 1;
564  }
565  if (0 == begin and -1 == rel) { return -1; }
566  return i + 1;
567 }
568 
569 inline uint64_t near_find_open(const bit_vector & bp, uint64_t i, const uint64_t block_size)
570 {
571  typedef bit_vector::difference_type difference_type;
572  difference_type excess_v = -1;
573  const difference_type begin = ((difference_type)(i - 1) / block_size) * block_size;
574  const difference_type r = ((difference_type)(i - 1) / 8) * 8;
575  const difference_type l = ((difference_type)((begin + 7) / 8)) * 8;
576  for (difference_type j = i - 1; j >= std::max(r, begin); --j)
577  {
578  if (bp[j])
579  {
580  if (++excess_v == 0) { return j; }
581  }
582  else
583  --excess_v;
584  }
585  const uint64_t * b = bp.data();
586  for (difference_type j = r - 8; j >= l; j -= 8)
587  {
588  if (excess_v >= -8)
589  {
590  assert(excess_v < 0);
591  uint32_t x = excess<>::data.max_match_pos_packed[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
592  uint8_t p = (x >> ((-excess_v - 1) << 2)) & 0xF;
593  if (p < 9) { return j + p; }
594  }
595  excess_v += excess<>::data.word_sum[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
596  }
597  for (difference_type j = std::min(l, r) - 1; j >= begin; --j)
598  {
599  if (bp[j])
600  {
601  if (++excess_v == 0) { return j; }
602  }
603  else
604  --excess_v;
605  }
606  return i;
607 }
608 
609 inline uint64_t near_find_opening(const bit_vector & bp, uint64_t i, const uint64_t openings, const uint64_t block_size)
610 {
611  typedef bit_vector::difference_type difference_type;
612  difference_type excess_v = 0;
613  difference_type succ_excess = openings;
614 
615  const difference_type begin = ((difference_type)(i) / block_size) * block_size;
616  const difference_type r = ((difference_type)(i) / 8) * 8;
617  const difference_type l = ((difference_type)((begin + 7) / 8)) * 8;
618  for (difference_type j = i; j >= std::max(r, begin); --j)
619  {
620  if (bp[j])
621  {
622  if (++excess_v == succ_excess) { return j; }
623  }
624  else
625  --excess_v;
626  }
627  const uint64_t * b = bp.data();
628  for (difference_type j = r - 8; j >= l; j -= 8)
629  {
630  if (succ_excess - excess_v <= 8)
631  {
632  assert(succ_excess - excess_v > 0);
633  uint32_t x = excess<>::data.max_match_pos_packed[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
634  uint8_t p = (x >> ((succ_excess - excess_v - 1) << 2)) & 0xF;
635  if (p < 9) { return j + p; }
636  }
637  excess_v += excess<>::data.word_sum[((*(b + (j >> 6))) >> (j & 0x3F)) & 0xFF];
638  }
639  for (difference_type j = std::min(l, r) - 1; j >= begin; --j)
640  {
641  if (bp[j])
642  {
643  if (++excess_v == succ_excess) { return j; }
644  }
645  else
646  --excess_v;
647  }
648  return i + 1;
649 }
650 
652 
659 // TODO: implement a fast version using lookup-tables of size 8
660 inline uint64_t near_enclose(const bit_vector & bp, uint64_t i, const uint64_t block_size)
661 {
662  uint64_t opening_parentheses = 1;
663  for (uint64_t j = i; j + block_size - 1 > i and j > 0; --j)
664  {
665  if (bp[j - 1])
666  {
667  ++opening_parentheses;
668  if (opening_parentheses == 2) { return j - 1; }
669  }
670  else
671  --opening_parentheses;
672  }
673  return i;
674 }
675 
676 inline uint64_t near_rmq_open(const bit_vector & bp, const uint64_t begin, const uint64_t end)
677 {
678  typedef bit_vector::difference_type difference_type;
679  difference_type min_excess = end - begin + 1, ex = 0;
680  uint64_t result = end;
681 
682  const uint64_t l = ((begin + 7) / 8) * 8;
683  const uint64_t r = (end / 8) * 8;
684 
685  for (uint64_t k = begin; k < std::min(end, l); ++k)
686  {
687  if (bp[k])
688  {
689  ++ex;
690  if (ex <= min_excess)
691  {
692  result = k;
693  min_excess = ex;
694  }
695  }
696  else
697  {
698  --ex;
699  }
700  }
701  const uint64_t * b = bp.data();
702  for (uint64_t k = l; k < r; k += 8)
703  {
704  uint16_t x = excess<>::data.min_open_excess_info[((*(b + (k >> 6))) >> (k & 0x3F)) & 0xFF];
705  int8_t ones = (x >> 12);
706  if (ones)
707  {
708  int8_t min_ex = (x & 0xFF) - 8;
709  if (ex + min_ex <= min_excess)
710  {
711  result = k + ((x >> 8) & 0xF);
712  min_excess = ex + min_ex;
713  }
714  }
715  ex += ((ones << 1) - 8);
716  }
717  for (uint64_t k = std::max(r, l); k < end; ++k)
718  {
719  if (bp[k])
720  {
721  ++ex;
722  if (ex <= min_excess)
723  {
724  result = k;
725  min_excess = ex;
726  }
727  }
728  else
729  {
730  --ex;
731  }
732  }
733  if (min_excess <= ex) return result;
734  return end;
735 }
736 
737 } // end namespace sdsl
738 
739 #endif
const uint64_t * data() const noexcept
Pointer to the raw data of the int_vector.
Definition: int_vector.hpp:590
uint8_t width() const noexcept
Returns the width of the integers which are accessed via the [] operator.
Definition: int_vector.hpp:619
size_type size() const noexcept
The number of elements in the int_vector.
A stack which contains strictly increasing numbers in the range from to .
size_type top() const
Returns the topmost index on the stack.
void pop()
Pop the topmost index of the stack.
bool empty() const
Returns if the stack is empty.
void push(size_type x)
Push the index x of vector vec onto the stack.
int_vector.hpp contains the sdsl::int_vector class.
Namespace for the succinct data structure library.
uint64_t near_find_closing(const bit_vector &bp, uint64_t i, uint64_t closings, const uint64_t block_size)
size_t block_size(void *ptr)
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.
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].
uint64_t near_find_opening(const bit_vector &bp, uint64_t i, const uint64_t openings, const uint64_t block_size)
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)
bit_vector calculate_pioneers_bitmap_succinct(const bit_vector &bp, uint64_t block_size)
Space-efficient version of calculate_pioneers_bitmap.
uint64_t near_fwd_excess(const bit_vector &bp, uint64_t i, bit_vector::difference_type rel, 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_bwd_excess(const bit_vector &bp, uint64_t i, bit_vector::difference_type rel, const uint64_t block_size)
Near backward excess.
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.
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
uint8_t near_bwd_pos[(8 -(-8)) *256]
uint8_t near_fwd_pos[(8 -(-8)) *256]
uint32_t max_match_pos_packed[256]
uint16_t min_open_excess_info[256]
uint32_t min_match_pos_packed[256]