SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
csa_alphabet_strategy.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
9#ifndef INCLUDED_CSA_ALPHABET_STRATEGY
10#define INCLUDED_CSA_ALPHABET_STRATEGY
11
12// TODO: Strategy with 1-to-1 mapping and C_array type as template parameter
13// This can be also used for a integer based CSA.
14
15/* A alphabet strategy provides the following features:
16 * * Member `sigma` which contains the size (=number of unique symbols) of the alphabet.
17 * * Container `char2comp` which maps a symbol to a number [0..sigma-1]. The alphabetic
18 * order is preserved.
19 * * Container `comp2char` which is the inverse mapping of char2comp.
20 * * Container `C` contains the cumulative counts of occurrences. C[i] is the cumulative
21 * count of occurrences of symbols `comp2char[0]` to `comp2char[i-1]` in the text.
22 * C is of size `sigma+1`.
23 * * Typedefs for the four above members:
24 * * char2comp_type
25 * * comp2char_type
26 * * C_type
27 * * sigma_type
28 * * Constructor. Takes a int_vector_buffer<8> for byte-alphabets
29 * and int_vector_buffer<0> for integer-alphabets.
30 *
31 * \par Note
32 * sigma_type has to be large enough to represent the alphabet size 2*sigma,
33 * since there is code which will perform a binary search on array `C`.
34 */
35
36#include <assert.h>
37#include <iosfwd>
38#include <map>
39#include <stdint.h>
40#include <string>
41#include <utility>
42#include <vector>
43
44#include <sdsl/bits.hpp>
45#include <sdsl/cereal.hpp>
46#include <sdsl/config.hpp>
47#include <sdsl/int_vector.hpp>
49#include <sdsl/io.hpp>
51#include <sdsl/sd_vector.hpp>
55#include <sdsl/util.hpp>
56
57namespace sdsl
58{
59
60// forward declarations
61
62class byte_alphabet; // IWYU pragma: keep
63
64template <class bit_vector_type = bit_vector,
65 class rank_support_type = rank_support_scan<>,
66 class select_support_type = select_support_scan<>,
67 class C_array_type = int_vector<>>
68class succinct_byte_alphabet; // IWYU pragma: keep
69
70template <class bit_vector_type = sd_vector<>,
71 class rank_support_type = typename bit_vector_type::rank_1_type,
72 class select_support_type = typename bit_vector_type::select_1_type,
73 class C_array_type = int_vector<>>
74class int_alphabet; // IWYU pragma: keep
75
76template <uint8_t int_width>
77constexpr char const * key_text()
78{
79 return conf::KEY_TEXT_INT;
80}
81
82template <uint8_t int_width>
83constexpr char const * key_bwt()
84{
85 return conf::KEY_BWT_INT;
86}
87
88template <>
89inline constexpr char const * key_text<8>()
90{
91 return conf::KEY_TEXT;
92}
93
94template <>
95inline constexpr char const * key_bwt<8>()
96{
97 return conf::KEY_BWT;
98}
99
100template <class t_alphabet_strategy>
102{
104};
105
106template <>
111
112// see
113// http://stackoverflow.com/questions/13514587/c-check-for-nested-typedef-of-a-template-parameter-to-get-its-scalar-base-type
114// for the next three functions
115
116template <class t_wt, class t_enable = void>
118{
119 typedef t_enable type;
120};
121
122template <class t_wt>
123struct wt_alphabet_trait<t_wt, typename enable_if_type<typename t_wt::alphabet_category>::type>
124{
126};
127
129
137{
138public:
143 typedef uint16_t sigma_type;
144 typedef uint8_t char_type;
145 typedef uint8_t comp_char_type;
146 typedef std::string string_type;
147 enum
148 {
150 };
151
153
156 C_type const & C;
158
159private:
160 char2comp_type m_char2comp; // Mapping from a character into the compact alphabet.
161 comp2char_type m_comp2char; // Inverse mapping of m_char2comp.
162 C_type m_C; // Cumulative counts for the compact alphabet [0..sigma].
163 sigma_type m_sigma; // Effective size of the alphabet.
164
165public:
167 byte_alphabet() : char2comp(m_char2comp), comp2char(m_comp2char), C(m_C), sigma(m_sigma), m_sigma(0)
168 {}
169
171
176 char2comp(m_char2comp),
177 comp2char(m_comp2char),
178 C(m_C),
179 sigma(m_sigma)
180 {
181 m_sigma = 0;
182 if (0 == len or 0 == text_buf.size())
183 return;
184 assert(len <= text_buf.size());
185 // initialize vectors
186 m_C = int_vector<64>(257, 0);
187 m_char2comp = int_vector<8>(256, 0);
188 m_comp2char = int_vector<8>(256, 0);
189 // count occurrences of each symbol
190 for (size_type i = 0; i < len; ++i)
191 {
192 ++m_C[text_buf[i]];
193 }
194 assert(1 == m_C[0]); // null-byte should occur exactly once
195 m_sigma = 0;
196 for (int i = 0; i < 256; ++i)
197 if (m_C[i])
198 {
199 m_char2comp[i] = m_sigma;
200 m_comp2char[sigma] = i;
201 m_C[m_sigma] = m_C[i];
202 ++m_sigma;
203 }
204 m_comp2char.resize(m_sigma);
205 m_C.resize(m_sigma + 1);
206 for (int i = (int)m_sigma; i > 0; --i)
207 m_C[i] = m_C[i - 1];
208 m_C[0] = 0;
209 for (int i = 1; i <= (int)m_sigma; ++i)
210 m_C[i] += m_C[i - 1];
211 assert(C[sigma] == len);
212 }
213
215 char2comp(m_char2comp),
216 comp2char(m_comp2char),
217 C(m_C),
218 sigma(m_sigma),
219 m_char2comp(bas.m_char2comp),
220 m_comp2char(bas.m_comp2char),
221 m_C(bas.m_C),
222 m_sigma(bas.m_sigma)
223 {}
224
226 char2comp(m_char2comp),
227 comp2char(m_comp2char),
228 C(m_C),
229 sigma(m_sigma),
230 m_char2comp(std::move(bas.m_char2comp)),
231 m_comp2char(std::move(bas.m_comp2char)),
232 m_C(std::move(bas.m_C)),
233 m_sigma(bas.m_sigma)
234 {}
235
237 {
238 if (this != &bas)
239 {
240 byte_alphabet tmp(bas);
241 *this = std::move(tmp);
242 }
243 return *this;
244 }
245
247 {
248 if (this != &bas)
249 {
250 m_char2comp = std::move(bas.m_char2comp);
251 m_comp2char = std::move(bas.m_comp2char);
252 m_C = std::move(bas.m_C);
253 m_sigma = std::move(bas.m_sigma);
254 }
255 return *this;
256 }
257
258 size_type serialize(std::ostream & out, structure_tree_node * v, std::string name = "") const
259 {
260 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
261 size_type written_bytes = 0;
262 written_bytes += m_char2comp.serialize(out, child, "m_char2comp");
263 written_bytes += m_comp2char.serialize(out, child, "m_comp2char");
264 written_bytes += m_C.serialize(out, child, "m_C");
265 written_bytes += write_member(m_sigma, out, child, "m_sigma");
266 structure_tree::add_size(child, written_bytes);
267 return written_bytes;
268 }
269
270 void load(std::istream & in)
271 {
272 m_char2comp.load(in);
273 m_comp2char.load(in);
274 m_C.load(in);
275 read_member(m_sigma, in);
276 }
277
279 bool operator==(byte_alphabet const & other) const noexcept
280 {
281 return (m_char2comp == other.m_char2comp) && (m_comp2char == other.m_comp2char) && (m_C == other.m_C)
282 && (m_sigma == other.m_sigma);
283 }
284
286 bool operator!=(byte_alphabet const & other) const noexcept
287 {
288 return !(*this == other);
289 }
290
291 template <typename archive_t>
292 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
293 {
294 ar(CEREAL_NVP(m_char2comp));
295 ar(CEREAL_NVP(m_comp2char));
296 ar(CEREAL_NVP(m_C));
297 ar(CEREAL_NVP(m_sigma));
298 }
299
300 template <typename archive_t>
301 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
302 {
303 ar(CEREAL_NVP(m_char2comp));
304 ar(CEREAL_NVP(m_comp2char));
305 ar(CEREAL_NVP(m_C));
306 ar(CEREAL_NVP(m_sigma));
307 }
308};
309
311
320template <class bit_vector_type, class rank_support_type, class select_support_type, class C_array_type>
322{
323public:
324 class char2comp_wrapper;
325 class comp2char_wrapper;
326
327 friend class char2comp_wrapper;
328 friend class comp2char_wrapper;
329
333 typedef C_array_type C_type;
334 typedef uint16_t sigma_type;
335 typedef uint8_t char_type;
336 typedef uint8_t comp_char_type;
337 typedef std::string string_type;
339 enum
340 {
342 };
343
346 {
347 private:
348 succinct_byte_alphabet const * m_strat;
349
350 public:
351 char2comp_wrapper(succinct_byte_alphabet const * strat) : m_strat(strat)
352 {}
354 {
355 if (c >= m_strat->m_char.size() or !m_strat->m_char[c])
356 return (comp_char_type)0;
357 return (comp_char_type)m_strat->m_char_rank((size_type)c);
358 }
359 };
360
363 {
364 private:
365 succinct_byte_alphabet const * m_strat;
366
367 public:
368 comp2char_wrapper(succinct_byte_alphabet const * strat) : m_strat(strat)
369 {}
371 {
372 return (char_type)m_strat->m_char_select(((size_type)c) + 1);
373 }
374 };
375
378 C_type const & C;
380
381private:
382 bit_vector_type m_char; // `m_char[i]` indicates if character with code i is present or not
383 rank_support_type m_char_rank; // rank data structure for `m_char` to answer char2comp
384 select_support_type m_char_select; // select data structure for `m_char` to answer comp2char
385 C_type m_C; // cumulative counts for the compact alphabet [0..sigma]
386 sigma_type m_sigma; // effective size of the alphabet
387
388public:
390 succinct_byte_alphabet() : char2comp(this), comp2char(this), C(m_C), sigma(m_sigma), m_sigma(0)
391 {}
392
394
399 char2comp(this),
400 comp2char(this),
401 C(m_C),
402 sigma(m_sigma)
403 {
404 m_sigma = 0;
405 if (0 == len or 0 == text_buf.size())
406 return;
407 assert(len <= text_buf.size());
408 // initialize vectors
409 int_vector<64> D(257, 0);
410 bit_vector tmp_char(256, 0);
411 // count occurrences of each symbol
412 for (size_type i = 0; i < len; ++i)
413 {
414 ++D[text_buf[i]];
415 }
416 assert(1 == D[0]); // null-byte should occur exactly once
417 m_sigma = 0;
418 for (int i = 0; i < 256; ++i)
419 if (D[i])
420 {
421 tmp_char[i] = 1; // mark occurring character
422 D[m_sigma] = D[i]; // compactify m_C
423 ++m_sigma;
424 }
425 // resize to sigma+1, since CSAs also need the sum of all elements
426 m_C = C_type(m_sigma + 1, 0, bits::hi(len) + 1);
427
428 for (int i = (int)m_sigma; i > 0; --i)
429 m_C[i] = D[i - 1];
430 m_C[0] = 0;
431 for (int i = 1; i <= (int)m_sigma; ++i)
432 m_C[i] = m_C[i] + m_C[i - 1];
433 assert(m_C[sigma] == len);
434 m_char = tmp_char;
435 util::init_support(m_char_rank, &m_char);
436 util::init_support(m_char_select, &m_char);
437 }
438
441 char2comp(this),
442 comp2char(this),
443 C(m_C),
444 sigma(m_sigma),
445 m_char(strat.m_char),
446 m_char_rank(strat.m_char_rank),
447 m_char_select(strat.m_char_select),
448 m_C(strat.m_C),
449 m_sigma(strat.m_sigma)
450 {
451 m_char_rank.set_vector(&m_char);
452 m_char_select.set_vector(&m_char);
453 }
454
457 char2comp(this),
458 comp2char(this),
459 C(m_C),
460 sigma(m_sigma),
461 m_char(std::move(strat.m_char)),
462 m_char_rank(std::move(strat.m_char_rank)),
463 m_char_select(std::move(strat.m_char_select)),
464 m_C(std::move(strat.m_C)),
465 m_sigma(std::move(strat.m_sigma))
466 {
467 m_char_rank.set_vector(&m_char);
468 m_char_select.set_vector(&m_char);
469 }
470
472 {
473 if (this != &strat)
474 {
475 succinct_byte_alphabet tmp(strat);
476 *this = std::move(tmp);
477 }
478 return *this;
479 }
480
482 {
483 if (this != &strat)
484 {
485 m_char = std::move(strat.m_char);
486 m_char_rank = std::move(strat.m_char_rank);
487 m_char_rank.set_vector(&m_char);
488 m_char_select = std::move(strat.m_char_select);
489 m_char_select.set_vector(&m_char);
490 m_C = std::move(strat.m_C);
491 m_sigma = std::move(strat.m_sigma);
492 }
493 return *this;
494 }
495
497 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
498 {
499 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
500 size_type written_bytes = 0;
501 written_bytes += m_char.serialize(out, child, "m_char");
502 written_bytes += m_char_rank.serialize(out, child, "m_char_rank");
503 written_bytes += m_char_select.serialize(out, child, "m_char_select");
504 written_bytes += m_C.serialize(out, child, "m_C");
505 written_bytes += write_member(m_sigma, out, child, "m_sigma");
506 structure_tree::add_size(child, written_bytes);
507 return written_bytes;
508 }
509
511 void load(std::istream & in)
512 {
513 m_char.load(in);
514 m_char_rank.load(in);
515 m_char_rank.set_vector(&m_char);
516 m_char_select.load(in);
517 m_char_select.set_vector(&m_char);
518 m_C.load(in);
519 read_member(m_sigma, in);
520 }
521
523 bool operator==(succinct_byte_alphabet const & other) const noexcept
524 {
525 return (m_char == other.m_char) && (m_char_rank == other.m_char_rank) && (m_char_select == other.m_char_select)
526 && (m_C == other.m_C) && (m_sigma == other.m_sigma);
527 }
528
530 bool operator!=(succinct_byte_alphabet const & other) const noexcept
531 {
532 return !(*this == other);
533 }
534
535 template <typename archive_t>
536 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
537 {
538 ar(CEREAL_NVP(m_char));
539 ar(CEREAL_NVP(m_char_rank));
540 ar(CEREAL_NVP(m_char_select));
541 ar(CEREAL_NVP(m_C));
542 ar(CEREAL_NVP(m_sigma));
543 }
544
545 template <typename archive_t>
546 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
547 {
548 ar(CEREAL_NVP(m_char));
549 ar(CEREAL_NVP(m_char_rank));
550 m_char_rank.set_vector(&m_char);
551 ar(CEREAL_NVP(m_char_select));
552 m_char_select.set_vector(&m_char);
553 ar(CEREAL_NVP(m_C));
554 ar(CEREAL_NVP(m_sigma));
555 }
556};
557
558template <typename bit_vector_type, typename size_type>
559void init_char_bitvector(bit_vector_type & char_bv, std::map<size_type, size_type> const & D)
560{
561 // note: the alphabet has at least size 1, so the following is safe:
562 auto largest_symbol = (--D.end())->first;
563 bit_vector tmp_char(largest_symbol + 1, 0);
564 for (auto const & x : D)
565 {
566 tmp_char[x.first] = 1;
567 }
568 char_bv = tmp_char;
569}
570
571template <typename t_hi_bit_vector, typename t_select_1, typename t_select_0, typename size_type>
573 std::map<size_type, size_type> const & D)
574{
575 auto largest_symbol = (--D.end())->first;
576 sd_vector_builder builder(largest_symbol + 1, D.size());
577 for (auto const & x : D)
578 {
579 builder.set(x.first);
580 }
581 char_bv = std::move(sd_vector<t_hi_bit_vector, t_select_1, t_select_0>(builder));
582}
583
590{
591public:
593 class mapping_wrapper;
594
599 typedef uint16_t sigma_type;
600 typedef uint8_t char_type;
601 typedef uint8_t comp_char_type;
602 typedef std::string string_type;
604 enum
605 {
607 };
608
611 {
612 public:
614 mapping_wrapper() = default;
615
617 constexpr char_type operator[](char_type const c) const noexcept
618 {
619 return c;
620 }
621 };
622
625 C_type const & C;
627
628private:
629 C_type m_C; // Cumulative counts for the compact alphabet [0..sigma].
630 sigma_type m_sigma; // Effective size of the alphabet.
631
632public:
634 plain_byte_alphabet() : C(m_C), sigma(m_sigma), m_sigma(0)
635 {}
636
642 {
643 m_sigma = 0;
644 if (0 == len || 0 == text_buf.size())
645 return;
646
647 assert(len <= text_buf.size());
648
649 // initialize vectors
650 m_C = int_vector<64>(257, 0);
651 // count occurrences of each symbol
652 for (size_type i = 0; i < len; ++i)
653 ++m_C[text_buf[i]];
654
655 assert(1 == m_C[0]); // null-byte should occur exactly once
656
657 m_sigma = 255;
658 for (int i = 0; i < 256; ++i)
659 {
660 if (m_C[i])
661 {
662 m_sigma = i + 1;
663 // m_C[m_sigma] = m_C[i];
664 // ++m_sigma;
665 }
666 }
667 // m_C.resize(m_sigma + 1);
668 for (int i = (int)256; i > 0; --i)
669 m_C[i] = m_C[i - 1];
670 m_C[0] = 0;
671 for (int i = 1; i <= (int)256; ++i)
672 m_C[i] += m_C[i - 1];
673
674 assert(C[sigma] == len);
675 }
676
679 C(m_C),
680 sigma(m_sigma),
681 m_C(strat.m_C),
682 m_sigma(strat.m_sigma)
683 {}
684
687 C(m_C),
688 sigma(m_sigma),
689 m_C(std::move(strat.m_C)),
690 m_sigma(strat.m_sigma)
691 {}
692
695 {
696 if (this != &strat)
697 {
698 plain_byte_alphabet tmp(strat);
699 *this = std::move(tmp);
700 }
701 return *this;
702 }
703
706 {
707 if (this != &strat)
708 {
709 m_C = std::move(strat.m_C);
710 m_sigma = strat.m_sigma;
711 }
712 return *this;
713 }
714
716 size_type serialize(std::ostream & out, structure_tree_node * v, std::string const & name = "") const
717 {
718 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
719 size_type written_bytes = 0;
720 written_bytes += m_C.serialize(out, child, "m_C");
721 written_bytes += write_member(m_sigma, out, child, "m_sigma");
722 structure_tree::add_size(child, written_bytes);
723 return written_bytes;
724 }
725
726 void load(std::istream & in)
727 {
728 m_C.load(in);
729 read_member(m_sigma, in);
730 }
731
732 template <typename archive_t>
733 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
734 {
735 ar(CEREAL_NVP(m_C));
736 ar(CEREAL_NVP(m_sigma));
737 }
738
739 template <typename archive_t>
740 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
741 {
742 ar(CEREAL_NVP(m_C));
743 ar(CEREAL_NVP(m_sigma));
744 }
745
746 bool operator==(plain_byte_alphabet const & other) const noexcept
747 {
748 return (m_C == other.m_C) && (m_sigma == other.m_sigma);
749 }
750
751 bool operator!=(plain_byte_alphabet const & other) const noexcept
752 {
753 return !(*this == other);
754 }
756};
757
759
769template <class bit_vector_type, class rank_support_type, class select_support_type, class C_array_type>
771{
772public:
773 class char2comp_wrapper;
774 class comp2char_wrapper;
775
776 friend class char2comp_wrapper;
777 friend class comp2char_wrapper;
778
782 typedef C_array_type C_type;
783 typedef uint64_t sigma_type;
784 typedef uint64_t char_type;
785 typedef uint64_t comp_char_type;
786 typedef std::vector<char_type> string_type;
788 enum
789 {
791 };
792
795 {
796 private:
797 int_alphabet const * m_strat;
798
799 public:
800 char2comp_wrapper(int_alphabet const * strat) : m_strat(strat)
801 {}
803 {
804 if (m_strat->m_char.size() > 0)
805 { // if alphabet is not continuous
806 if (c >= m_strat->m_char.size() or !m_strat->m_char[c])
807 return (comp_char_type)0;
808 return (comp_char_type)m_strat->m_char_rank((size_type)c);
809 }
810 else
811 { // direct map if it is continuous
812 if (c >= m_strat->m_sigma)
813 return 0;
814 return (comp_char_type)c;
815 }
816 return 0;
817 }
818 };
819
822 {
823 private:
824 int_alphabet const * m_strat;
825
826 public:
827 comp2char_wrapper(int_alphabet const * strat) : m_strat(strat)
828 {}
830 {
831 if (m_strat->m_char.size() > 0)
832 { // if alphabet is not continuous
833 return (char_type)m_strat->m_char_select(((size_type)c) + 1);
834 }
835 else
836 { // direct map if it is continuous
837 return (char_type)c;
838 }
839 }
840 };
841
844 C_type const & C;
846
847private:
848 bit_vector_type m_char; // `m_char[i]` indicates if character with code i is present or not
849 rank_support_type m_char_rank; // rank data structure for `m_char` to answer char2comp
850 select_support_type m_char_select; // select data structure for `m_char` to answer comp2char
851 C_type m_C; // cumulative counts for the compact alphabet [0..sigma]
852 sigma_type m_sigma; // effective size of the alphabet
853
855 bool is_continuous_alphabet(std::map<size_type, size_type> & D)
856 {
857 if (D.size() == 0)
858 { // an empty alphabet is continuous
859 return true;
860 }
861 else
862 {
863 // max key + 1 == size of map
864 return ((--D.end())->first + 1) == D.size();
865 }
866 }
867
868public:
870 int_alphabet() : char2comp(this), comp2char(this), C(m_C), sigma(m_sigma), m_sigma(0)
871 {}
872
874
879 char2comp(this),
880 comp2char(this),
881 C(m_C),
882 sigma(m_sigma)
883 {
884 m_sigma = 0;
885 if (0 == len or 0 == text_buf.size())
886 return;
887 assert(len <= text_buf.size());
888 // initialize vectors
889 std::map<size_type, size_type> D;
890 // count occurrences of each symbol
891 for (size_type i = 0; i < len; ++i)
892 {
893 D[text_buf[i]]++;
894 }
895 m_sigma = D.size();
896 if (is_continuous_alphabet(D))
897 {
898 // do not initialize m_char, m_char_rank and m_char_select since we can map directly
899 }
900 else
901 {
902 init_char_bitvector(m_char, D);
903 }
904 assert(D.find(0) != D.end() and 1 == D[0]); // null-byte should occur exactly once
905
906 // resize to sigma+1, since CSAs also need the sum of all elements
907 m_C = C_type(m_sigma + 1, 0, bits::hi(len) + 1);
908 size_type sum = 0, idx = 0;
909 for (std::map<size_type, size_type>::const_iterator it = D.begin(), end = D.end(); it != end; ++it)
910 {
911 m_C[idx++] = sum;
912 sum += it->second;
913 }
914 m_C[idx] = sum; // insert sum of all elements
915 }
916
918 int_alphabet(int_alphabet const & strat) :
919 char2comp(this),
920 comp2char(this),
921 C(m_C),
922 sigma(m_sigma),
923 m_char(strat.m_char),
924 m_char_rank(strat.m_char_rank),
925 m_char_select(strat.m_char_select),
926 m_C(strat.m_C),
927 m_sigma(strat.m_sigma)
928 {
929 m_char_rank.set_vector(&m_char);
930 m_char_select.set_vector(&m_char);
931 }
932
935 char2comp(this),
936 comp2char(this),
937 C(m_C),
938 sigma(m_sigma),
939 m_char(std::move(strat.m_char)),
940 m_char_rank(std::move(strat.m_char_rank)),
941 m_char_select(std::move(strat.m_char_select)),
942 m_C(std::move(strat.m_C)),
943 m_sigma(std::move(strat.m_sigma))
944 {
945 m_char_rank.set_vector(&m_char);
946 m_char_select.set_vector(&m_char);
947 }
948
950 {
951 if (this != &strat)
952 {
953 int_alphabet tmp(strat);
954 *this = std::move(tmp);
955 }
956 return *this;
957 }
958
960 {
961 if (this != &strat)
962 {
963 m_char = std::move(strat.m_char);
964 m_char_rank = std::move(strat.m_char_rank);
965 m_char_rank.set_vector(&m_char);
966 m_char_select = std::move(strat.m_char_select);
967 m_char_select.set_vector(&m_char);
968 m_C = std::move(strat.m_C);
969 m_sigma = std::move(strat.m_sigma);
970 }
971 return *this;
972 }
973
975 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
976 {
977 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
978 size_type written_bytes = 0;
979 written_bytes += m_char.serialize(out, child, "m_char");
980 written_bytes += m_char_rank.serialize(out, child, "m_char_rank");
981 written_bytes += m_char_select.serialize(out, child, "m_char_select");
982 written_bytes += m_C.serialize(out, child, "m_C");
983 written_bytes += write_member(m_sigma, out, child, "m_sigma");
984 structure_tree::add_size(child, written_bytes);
985 return written_bytes;
986 }
987
989 void load(std::istream & in)
990 {
991 m_char.load(in);
992 m_char_rank.load(in);
993 m_char_rank.set_vector(&m_char);
994 m_char_select.load(in);
995 m_char_select.set_vector(&m_char);
996 m_C.load(in);
997 read_member(m_sigma, in);
998 }
999
1001 bool operator==(int_alphabet const & other) const noexcept
1002 {
1003 return (m_char == other.m_char) && (m_char_rank == other.m_char_rank) && (m_char_select == other.m_char_select)
1004 && (m_C == other.m_C) && (m_sigma == other.m_sigma);
1005 }
1006
1008 bool operator!=(int_alphabet const & other) const noexcept
1009 {
1010 return !(*this == other);
1011 }
1012
1013 template <typename archive_t>
1014 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
1015 {
1016 ar(CEREAL_NVP(m_char));
1017 ar(CEREAL_NVP(m_char_rank));
1018 ar(CEREAL_NVP(m_char_select));
1019 ar(CEREAL_NVP(m_C));
1020 ar(CEREAL_NVP(m_sigma));
1021 }
1022
1023 template <typename archive_t>
1024 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
1025 {
1026 ar(CEREAL_NVP(m_char));
1027 ar(CEREAL_NVP(m_char_rank));
1028 m_char_rank.set_vector(&m_char);
1029 ar(CEREAL_NVP(m_char_select));
1030 m_char_select.set_vector(&m_char);
1031 ar(CEREAL_NVP(m_C));
1032 ar(CEREAL_NVP(m_sigma));
1033 }
1034};
1035
1036} // end namespace sdsl
1037
1038#endif
bits.hpp contains the sdsl::bits class.
cereal.hpp offers cereal support
#define CEREAL_NVP(X)
Definition cereal.hpp:31
#define CEREAL_LOAD_FUNCTION_NAME
Definition cereal.hpp:34
#define CEREAL_SAVE_FUNCTION_NAME
Definition cereal.hpp:35
A simple space greedy representation for byte alphabets.
byte_alphabet_tag alphabet_category
bool operator!=(byte_alphabet const &other) const noexcept
Inequality operator.
bool operator==(byte_alphabet const &other) const noexcept
Equality operator.
byte_alphabet & operator=(byte_alphabet &&bas)
char2comp_type const & char2comp
void load(std::istream &in)
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
comp2char_type const & comp2char
byte_alphabet(int_vector_buffer< 8 > &text_buf, int_vector_size_type len)
Construct from a byte-stream.
byte_alphabet()
Default constructor.
int_vector ::size_type size_type
byte_alphabet(byte_alphabet const &bas)
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
size_type serialize(std::ostream &out, structure_tree_node *v, std::string name="") const
byte_alphabet(byte_alphabet &&bas)
byte_alphabet & operator=(byte_alphabet const &bas)
Helper class for the char2comp mapping.
comp_char_type operator[](char_type c) const
Helper class for the comp2char mapping.
char_type operator[](comp_char_type c) const
A space-efficient representation for byte alphabets.
int_alphabet & operator=(int_alphabet &&strat)
char2comp_wrapper char2comp_type
comp2char_wrapper comp2char_type
int_alphabet & operator=(int_alphabet const &strat)
int_alphabet(int_vector_buffer< 0 > &text_buf, int_vector_size_type len)
Construct from a byte-stream.
int_alphabet(int_alphabet const &strat)
Copy constructor.
bool operator==(int_alphabet const &other) const noexcept
Equality operator.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
int_alphabet(int_alphabet &&strat)
Copy constructor.
int_alphabet_tag alphabet_category
int_vector ::size_type size_type
std::vector< char_type > string_type
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serialize method.
int_alphabet()
Default constructor.
void load(std::istream &in)
Load method.
const comp2char_type comp2char
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
const char2comp_type char2comp
bool operator!=(int_alphabet const &other) const noexcept
Inequality operator.
uint64_t size() const
Returns the number of elements currently stored.
int_vector_size_type size_type
void load(std::istream &in)
Load the int_vector for a stream.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the int_vector to a stream.
Helper class for the char2comp and comp2char mapping.
mapping_wrapper()=default
Default constructor.
constexpr char_type operator[](char_type const c) const noexcept
Random access operator.
plain_byte_alphabet & operator=(plain_byte_alphabet &&strat) noexcept
Move assignment.
plain_byte_alphabet(plain_byte_alphabet const &strat)
Copy constructor.
plain_byte_alphabet & operator=(plain_byte_alphabet const &strat)
Copy assignment.
plain_byte_alphabet(plain_byte_alphabet &&strat) noexcept
Move constructor.
plain_byte_alphabet()
Default constructor.
plain_byte_alphabet(int_vector_buffer< 8 > &text_buf, int_vector_size_type len)
Construct from a byte-stream.
A class supporting rank queries in linear time.
Class for in-place construction of sd_vector from a strictly increasing sequence.
Definition sd_vector.hpp:51
void set(size_type i)
Set a bit to 1.
Definition sd_vector.hpp:97
A bit vector which compresses very sparse populated bit vectors by.
A class supporting linear time select queries.
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)
char2comp_wrapper(succinct_byte_alphabet const *strat)
comp2char_wrapper(succinct_byte_alphabet const *strat)
A space-efficient representation for byte alphabets.
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
succinct_byte_alphabet(succinct_byte_alphabet &&strat)
Move constructor.
bool operator==(succinct_byte_alphabet const &other) const noexcept
Equality operator.
succinct_byte_alphabet()
Default constructor.
bool operator!=(succinct_byte_alphabet const &other) const noexcept
Inequality operator.
void load(std::istream &in)
Load method.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
succinct_byte_alphabet(int_vector_buffer< 8 > &text_buf, int_vector_size_type len)
Construct from a byte-stream.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serialize method.
succinct_byte_alphabet & operator=(succinct_byte_alphabet &&strat)
succinct_byte_alphabet & operator=(succinct_byte_alphabet const &strat)
succinct_byte_alphabet(succinct_byte_alphabet const &strat)
Copy constructor.
int_vector.hpp contains the sdsl::int_vector class.
int_vector_buffer.hpp contains the sdsl::int_vector_buffer class.
io.hpp contains some methods for reading/writing sdsl structures.
constexpr char KEY_BWT_INT[]
Definition config.hpp:35
constexpr char KEY_TEXT[]
Definition config.hpp:40
constexpr char KEY_TEXT_INT[]
Definition config.hpp:41
constexpr char KEY_BWT[]
Definition config.hpp:34
Namespace for the succinct data structure library.
constexpr char const * key_bwt< 8 >()
size_t write_member(T const &t, std::ostream &out, sdsl::structure_tree_node *v=nullptr, std::string name="")
Definition io.hpp:94
void read_member(T &t, std::istream &in)
Definition io.hpp:119
constexpr char const * key_text< 8 >()
std::enable_if< has_load< X >::value, void >::type load(X &x, std::istream &in)
Definition io.hpp:160
std::enable_if< has_serialize< X >::value, typenameX::size_type >::type serialize(X const &x, std::ostream &out, structure_tree_node *v=nullptr, std::string name="")
Definition io.hpp:139
int_vector< 1 > bit_vector
bit_vector is a specialization of the int_vector.
constexpr char const * key_bwt()
bool operator==(track_allocator< T > const &, track_allocator< U > const &)
uint64_t int_vector_size_type
Definition config.hpp:47
bool operator!=(track_allocator< T > const &a, track_allocator< U > const &b)
void init_char_bitvector(bit_vector_type &char_bv, std::map< size_type, size_type > const &D)
constexpr char const * key_text()
rank_support_scan.hpp contains rank_support_scan that support a sdsl::bit_vector with linear time ran...
sd_vector.hpp contains the sdsl::sd_vector class, and classes which support rank and select for sd_ve...
Contains declarations and definitions of data structure concepts.
select_support_scan.hpp contains classes that support a sdsl::bit_vector with linear time select.
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Definition bits.hpp:653
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.