SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
bp_support_gg.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_GG
9#define INCLUDED_SDSL_BP_SUPPORT_GG
10
11#include <assert.h>
12#include <iosfwd>
13#include <memory>
14#include <stdexcept>
15#include <stdint.h>
16#include <string>
17#include <typeinfo>
18
20#include <sdsl/cereal.hpp>
21#include <sdsl/int_vector.hpp>
22#include <sdsl/io.hpp>
28#include <sdsl/util.hpp>
29
30namespace sdsl
31{
32
34
59// TODO: can rrr_vector replace nearest_neighbour_dictionary?
60template <class t_nnd = nearest_neighbour_dictionary<30>,
61 class t_rank = rank_support_v5<>,
62 class t_select = select_support_mcl<>,
63 uint32_t t_bs = 840>
65{
66 static_assert(t_bs > 2, "bp_support_gg: block size must be greater than 2.");
67
68public:
70 typedef t_nnd nnd_type;
71 typedef t_rank rank_type;
72 typedef t_select select_type;
74
75private:
76 bit_vector const * m_bp = nullptr; // balanced parentheses sequence
77 rank_type m_rank_bp; // rank support for m_bp => see excess() and rank()
78 select_type m_select_bp; // select support for m_bp => see select()
79
80 nnd_type m_nnd; // nearest neighbour dictionary for pioneers bit_vector
81
82 bit_vector m_pioneer_bp; // pioneer sequence
83 std::unique_ptr<bp_support_type> m_pioneer_bp_support = nullptr;
84
85 size_type m_size = 0;
86 size_type m_blocks = 0; // number of blocks
87
88public:
89 rank_type const & bp_rank = m_rank_bp;
90 select_type const & bp_select = m_select_bp;
91
92 bp_support_gg() = default;
93
95 explicit bp_support_gg(bit_vector const * bp) :
96 m_bp(bp),
97 m_size(bp == nullptr ? 0 : bp->size()),
98 m_blocks((m_size + t_bs - 1) / t_bs),
99 bp_rank(m_rank_bp),
100 bp_select(m_select_bp)
101 {
102 if (bp == nullptr)
103 { // -> m_bp == nullptr
104 return;
105 }
106
107 util::init_support(m_rank_bp, bp);
108 util::init_support(m_select_bp, bp);
109 {
110 bit_vector pioneer;
111 pioneer = calculate_pioneers_bitmap_succinct(*m_bp, t_bs);
112 m_nnd = nnd_type(pioneer);
113 }
114
115 m_pioneer_bp.resize(m_nnd.ones());
116 if (m_nnd.ones() > 0 and m_nnd.ones() == m_bp->size())
117 { // m_bp != nullptr see above
118 throw std::logic_error(util::demangle(typeid(this).name())
119 + ": recursion in the construction does not terminate!");
120 }
121
122 for (size_type i = 1; i <= m_nnd.ones(); ++i)
123 {
124 m_pioneer_bp[i - 1] = (*m_bp)[m_nnd.select(i)];
125 }
126
127 if (m_bp->size() > 0)
128 { // m_bp != nullptr see above
129 m_pioneer_bp_support = std::unique_ptr<bp_support_type>(new bp_support_type(&m_pioneer_bp));
130 }
131 }
132
135 m_rank_bp(v.m_rank_bp),
136 m_select_bp(v.m_select_bp),
137 m_nnd(v.m_nnd),
138 m_pioneer_bp(v.m_pioneer_bp),
139 m_size(v.m_size),
140 m_blocks(v.m_blocks)
141 {
142
143 m_rank_bp.set_vector(m_bp);
144 m_select_bp.set_vector(m_bp);
145
146 m_pioneer_bp_support.reset(nullptr);
147 if (v.m_pioneer_bp_support != nullptr)
148 {
149 m_pioneer_bp_support.reset(new bp_support_type(*(v.m_pioneer_bp_support)));
150 m_pioneer_bp_support->set_vector(&m_pioneer_bp);
151 }
152 }
153
156 {
157 *this = std::move(bp_support);
158 }
159
161 ~bp_support_gg() = default;
162
165 {
166 if (this != &v)
167 {
168 bp_support_gg tmp(v);
169 *this = std::move(tmp);
170 }
171 return *this;
172 }
173
176 {
177 if (this != &bp_support)
178 {
179 m_bp = bp_support.m_bp;
180 bp_support.m_bp = nullptr;
181
182 m_rank_bp = std::move(bp_support.m_rank_bp);
183 m_rank_bp.set_vector(m_bp);
184 m_select_bp = std::move(bp_support.m_select_bp);
185 m_select_bp.set_vector(m_bp);
186
187 m_nnd = std::move(bp_support.m_nnd);
188
189 m_size = bp_support.m_size;
190 m_blocks = bp_support.m_blocks;
191
192 m_pioneer_bp = std::move(bp_support.m_pioneer_bp);
193
194 m_pioneer_bp_support.reset(nullptr);
195 if (bp_support.m_pioneer_bp_support != nullptr)
196 {
197 std::swap(m_pioneer_bp_support, bp_support.m_pioneer_bp_support);
198 m_pioneer_bp_support->set_vector(&m_pioneer_bp);
199 }
200 }
201 return *this;
202 }
203
204 void set_vector(bit_vector const * bp)
205 {
206 m_bp = bp;
207 m_rank_bp.set_vector(bp);
208 m_select_bp.set_vector(bp);
209 }
210
214 inline size_type excess(size_type i) const
215 {
216 return (m_rank_bp(i + 1) << 1) - i - 1;
217 }
218
223 {
224 return m_rank_bp(i + 1);
225 }
226
233 {
234 return m_select_bp(i);
235 }
236
244 {
245 assert(i < m_size);
246 if (!(*m_bp)[i])
247 { // if there is a closing parenthesis at index i return i
248 return i;
249 }
250 size_type mi = 0; // match for i
251 if ((mi = near_find_closing(*m_bp, i + 1, 1, t_bs)) == i)
252 {
253 const size_type i_ = m_nnd.rank(i + 1) - 1; // lemma that this gives us an opening pioneer
254 assert(m_pioneer_bp[i_] == 1); // assert that i2 is an opening parenthesis
255 size_type mi_ = m_pioneer_bp_support->find_close(i_);
256 assert(m_pioneer_bp[mi_] == 0);
257 mi = m_nnd.select(mi_ + 1); /* matching pioneer position in bp */
258 assert((*m_bp)[mi] == 0);
259 mi = (mi / t_bs) * t_bs;
260 size_type epb2 = excess(mi - 1); // excess of first parenthesis in the pioneer block
261 const size_type ei = excess(i); // excess at position i
262 /* invariant: epb >= ei-1 */ // assert( epb+1 >= ei );
263 return near_find_closing(*m_bp, mi, epb2 - ei + 1, t_bs);
264 }
265 return mi;
266 }
267
269
276 {
277 assert(i < m_size);
278 if ((*m_bp)[i])
279 { // if there is a opening parenthesis
280 return i; // return i
281 }
282 size_type mi = 0; // match for i
283 if ((mi = near_find_opening(*m_bp, i - 1, 1, t_bs)) == i)
284 {
285 const size_type i_ = m_nnd.rank(i); // lemma that this gives us an closing pioneer
286 assert(m_pioneer_bp[i_] == 0); // assert that i' is an opening parenthesis
287 const size_type mi_ = m_pioneer_bp_support->find_open(i_);
288 assert(m_pioneer_bp[mi_] == 1);
289 mi = m_nnd.select(mi_ + 1); /* matching pioneer position in bp */
290 assert((*m_bp)[mi] == 1);
291 mi = (mi / t_bs) * t_bs + t_bs - 1;
292 assert(mi < i);
293 size_type epb2 = excess(mi + 1); // excess of last parenthesis in the pioneer block
294 const size_type ei = excess(i); // excess at position i
295 /*invariant: epb >= ei+1*/ // assert( epb >= ei+1 );
296 return near_find_opening(*m_bp, mi, epb2 - ei + 1 - 2 * ((*m_bp)[mi + 1]), t_bs);
297 }
298 return mi;
299 }
300
302
308 {
309 assert(i < m_size);
310 if (!(*m_bp)[i])
311 { // if there is closing parenthesis at position i
312 return find_open(i);
313 }
314 const size_type exi = excess(i);
315 if (exi == 1) // if i is not enclosed by a parentheses pair..
316 return size();
317 size_type ei; // enclose for i
318 if ((ei = near_find_opening(*m_bp, i - 1, 1, t_bs)) == i)
319 {
320 const size_type i_ = m_nnd.rank(i); // next parenthesis in the pioneer bitmap
321 size_type ei_; // enclose for i'
322 ei_ = m_pioneer_bp_support->enclose(i_);
323 assert(m_pioneer_bp[ei_] == 1);
324 ei = m_nnd.select(ei_ + 1);
325 assert((*m_bp)[ei] == 1);
326 ei = (ei / t_bs) * t_bs + t_bs - 1;
327 assert(ei < i);
328 size_type epb2 = excess(ei + 1); // excess of last parenthesis in the pioneer block
329 /* invariant epb+1 >= exi */ // assert( epb+1 >= exi );
330 return near_find_opening(*m_bp, ei, epb2 - exi + 1 + 2 * ((*m_bp)[ei + 1] == 0), t_bs);
331 }
332 return ei;
333 }
334
336
346 size_type rr_enclose(const size_type i, const size_type j) const
347 {
348 assert(j < m_size);
349 assert((*m_bp)[i] == 1 and (*m_bp)[j] == 1);
350 const size_type mip1 = find_close(i) + 1;
351 if (mip1 >= j)
352 return size();
353 return rmq_open(mip1, j);
354 }
355
364 size_type rmq_open(const size_type l, const size_type r) const
365 {
366 if (l >= r)
367 return size();
368 size_type min_ex_pos = r;
369
370 if (l / t_bs == r / t_bs)
371 {
372 min_ex_pos = near_rmq_open(*m_bp, l, r);
373 }
374 else
375 { // parentheses pair does not start in the same block
376 // note: l and r are not in the same block
377 size_type k, ex; // helper variables
378 size_type min_ex = excess(r) + 2 * ((*m_bp)[r] == 0); // minimal excess
379
380 // 1.2
381 size_type l_ = m_nnd.rank(l); // l_ inclusive
382 size_type r_ = m_nnd.rank(r); // r_ exclusive
383
384 size_type min_ex_pos_ = m_pioneer_bp_support->rmq_open(l_, r_);
385 if (min_ex_pos_ < r_)
386 {
387 k = m_nnd.select(min_ex_pos_ + 1);
388 min_ex = excess(k);
389 min_ex_pos = k;
390 }
391 else
392 {
393 // 1.1
394 k = near_rmq_open(*m_bp, (r / t_bs) * t_bs, r);
395 if (k < r)
396 {
397 assert(excess(k) < min_ex);
398 min_ex = excess(k);
399 min_ex_pos = k;
400 }
401 }
402 // 1.3
403 k = near_rmq_open(*m_bp, l, (l / t_bs + 1) * t_bs);
404 if (k < (l / t_bs + 1) * t_bs and (ex = excess(k)) < min_ex)
405 {
406 min_ex = ex;
407 min_ex_pos = k;
408 }
409 }
410 // 1.4
411 if (min_ex_pos < r)
412 return min_ex_pos;
413 else
414 return size();
415 }
416
418
426 {
427 assert(j > i and j < m_size);
428 assert((*m_bp)[i] == 1 and (*m_bp)[j] == 1);
429 size_type mi = find_close(i); // matching parenthesis to i
430 assert(mi > i and mi < j);
431 assert(find_close(j) > j);
432 size_type k = enclose(j);
433 if (k == m_size or k < i) // there exists no opening parenthesis at position mi<k<j.
434 return m_size;
435 size_type kk;
436 do
437 {
438 kk = k;
439 k = enclose(k);
440 }
441 while (k != m_size and k > mi);
442 return kk;
443 }
444
446
451 {
452 assert(l <= r);
453 size_type m = rmq_open(l, r + 1);
454 if (m == size())
455 return r;
456 else if (m == l)
457 return l;
458 else
459 { // m>l and m<=r
460 assert(0 == (*m_bp)[m - 1]);
461 return m - 1;
462 }
463 }
464
466
472 {
473 assert(j > i);
474 assert((*m_bp)[i] == 1 and (*m_bp)[j] == 1);
475 size_type k = rr_enclose(i, j);
476 if (k == size())
477 return enclose(j);
478 else
479 return enclose(k);
480 }
481
483
486 {
487 assert(i < m_size);
488 if (!i)
489 return 0;
490 size_type ones = m_rank_bp(i);
491 if (ones)
492 { // ones > 0
493 assert(m_select_bp(ones) < i);
494 return i - m_select_bp(ones) - 1;
495 }
496 else
497 {
498 return i;
499 }
500 }
501
506 {
507 return m_size;
508 }
509
511
515 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
516 {
517 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
518 size_type written_bytes = 0;
519 written_bytes += write_member(m_size, out, child, "size");
520 written_bytes += write_member(m_blocks, out, child, "block_cnt");
521
522 written_bytes += m_rank_bp.serialize(out, child, "bp_rank");
523 written_bytes += m_select_bp.serialize(out, child, "bp_select");
524 written_bytes += m_nnd.serialize(out, child, "nearest_neighbour_dictionary");
525
526 written_bytes += m_pioneer_bp.serialize(out, child, "pioneer_bp");
527 if (m_bp != nullptr and m_bp->size() > 0)
528 written_bytes += m_pioneer_bp_support->serialize(out, child, "pioneer_bp_support");
529 structure_tree::add_size(child, written_bytes);
530 return written_bytes;
531 }
532
534
538 void load(std::istream & in, bit_vector const * bp)
539 {
540 m_bp = bp;
541 read_member(m_size, in);
542 read_member(m_blocks, in);
543
544 m_rank_bp.load(in, m_bp);
545 m_select_bp.load(in, m_bp);
546 m_nnd.load(in);
547
548 m_pioneer_bp.load(in);
549 m_pioneer_bp_support.reset(nullptr);
550 if (m_bp != nullptr and m_bp->size() > 0)
551 {
552 m_pioneer_bp_support.reset(new bp_support_type());
553 m_pioneer_bp_support->load(in, &m_pioneer_bp);
554 }
555 }
556
557 template <typename archive_t>
558 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
559 {
560 ar(CEREAL_NVP(m_size));
561 ar(CEREAL_NVP(m_blocks));
562 ar(CEREAL_NVP(m_rank_bp));
563 ar(CEREAL_NVP(m_select_bp));
564 ar(CEREAL_NVP(m_nnd));
565 ar(CEREAL_NVP(m_pioneer_bp));
566 ar(CEREAL_NVP(m_pioneer_bp_support));
567 }
568
569 template <typename archive_t>
570 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
571 {
572 ar(CEREAL_NVP(m_size));
573 ar(CEREAL_NVP(m_blocks));
574 ar(CEREAL_NVP(m_rank_bp));
575 ar(CEREAL_NVP(m_select_bp));
576 ar(CEREAL_NVP(m_nnd));
577 ar(CEREAL_NVP(m_pioneer_bp));
578 ar(CEREAL_NVP(m_pioneer_bp_support));
579 if (m_pioneer_bp_support != nullptr)
580 {
581 m_pioneer_bp_support->set_vector(&m_pioneer_bp);
582 }
583 }
584
586 bool operator==(bp_support_gg const & other) const noexcept
587 {
588 return (m_size == other.m_size) && (m_blocks == other.m_blocks) && (m_rank_bp == other.m_rank_bp)
589 && (m_select_bp == other.m_select_bp) && (m_nnd == other.m_nnd) && (m_pioneer_bp == other.m_pioneer_bp)
590 && ((m_pioneer_bp_support == other.m_pioneer_bp_support)
591 || (*m_pioneer_bp_support == *other.m_pioneer_bp_support));
592 }
593
595 bool operator!=(bp_support_gg const & other) const noexcept
596 {
597 return !(*this == other);
598 }
599};
600
601} // namespace sdsl
602
603#endif
bp_support_algorithm.hpp contains algorithms for balanced parentheses sequences.
cereal.hpp offers cereal support
#define CEREAL_NVP(X)
Definition cereal.hpp:31
A class that provides support for bit_vectors that represent a BP sequence.
bp_support_gg & operator=(bp_support_gg const &v)
Assignment operator.
size_type rr_enclose(const size_type i, const size_type j) const
Range restricted enclose operation.
void set_vector(bit_vector const *bp)
size_type preceding_closing_parentheses(size_type i) const
Return the number of zeros which procede position i in the balanced parentheses sequence.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the bp_support_gg to a stream.
size_type size() const
The size of the supported balanced parentheses 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 double_enclose(size_type i, size_type j) const
The double enclose operation.
size_type find_open(size_type i) const
Calculate the matching opening parenthesis.
size_type rank(size_type i) const
Returns the number of opening parentheses up to and including index i.
rank_type const & bp_rank
bp_support_gg & operator=(bp_support_gg &&bp_support)
Assignment Move operator.
void load(std::istream &in, bit_vector const *bp)
Load the bp_support_gg for a bit_vector v.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
size_type rr_enclose_naive(size_type i, size_type j) const
The range restricted enclose operation.
size_type find_close(size_type i) const
Calculate the index of the matching closing parenthesis to the parenthesis at index i.
bp_support_gg< nnd_type, rank_type, select_support_scan<>, t_bs > bp_support_type
select_type const & bp_select
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.
bp_support_gg(bp_support_gg const &v)
Copy constructor.
bp_support_gg()=default
bool operator==(bp_support_gg const &other) const noexcept
Equality operator.
bit_vector::size_type size_type
bool operator!=(bp_support_gg const &other) const noexcept
Inequality operator.
bp_support_gg(bit_vector const *bp)
Constructor.
bp_support_gg(bp_support_gg &&bp_support)
Move constructor.
size_type enclose(size_type i) const
Calculate enclose.
~bp_support_gg()=default
Destructor.
size_type select(size_type i) const
Returns the index of the i-th opening parenthesis.
int_vector_size_type size_type
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.
void resize(const size_type size)
Resize the int_vector in terms of elements.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the int_vector to a stream.
static structure_tree_node * add_child(structure_tree_node *v, std::string const &name, std::string const &type)
static void add_size(structure_tree_node *v, uint64_t value)
int_vector.hpp contains the sdsl::int_vector class.
io.hpp contains some methods for reading/writing sdsl structures.
Namespace for the succinct data structure library.
bit_vector calculate_pioneers_bitmap_succinct(bit_vector const &bp, uint64_t block_size)
Space-efficient version of calculate_pioneers_bitmap.
uint64_t near_find_closing(bit_vector const &bp, uint64_t i, uint64_t closings, const uint64_t block_size)
size_t write_member(T const &t, std::ostream &out, sdsl::structure_tree_node *v=nullptr, std::string name="")
Definition io.hpp:94
uint64_t near_rmq_open(bit_vector const &bp, const uint64_t begin, const uint64_t end)
void read_member(T &t, std::istream &in)
Definition io.hpp:119
uint64_t near_find_opening(bit_vector const &bp, uint64_t i, const uint64_t openings, const uint64_t block_size)
nearest_neighbour_dictionary.hpp contains a class which supports rank/select for sparse populated sds...
rank_support_v5.hpp contains rank_support_v5.5
select_support_mcl.hpp contains classes that support a sdsl::bit_vector with constant time select inf...
select_support_scan.hpp contains classes that support a sdsl::bit_vector with linear time select.
structure_tree.hpp contains a helper class which can represent the memory structure of a class.
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.