SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
lcp_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.
8#ifndef INCLUDED_SDSL_LCP_SUPPORT_SADA
9#define INCLUDED_SDSL_LCP_SUPPORT_SADA
10
11#include <iosfwd>
12#include <stddef.h>
13#include <string>
14
15#include <sdsl/cereal.hpp>
16#include <sdsl/config.hpp>
18#include <sdsl/csa_sada.hpp> // for default template initialization
19#include <sdsl/int_vector.hpp>
21#include <sdsl/io.hpp>
22#include <sdsl/iterators.hpp>
25#include <sdsl/util.hpp>
26
27namespace sdsl
28{
29
31
48template <class t_csa = csa_sada<>, class t_bitvec = bit_vector, class t_select = typename t_bitvec::select_1_type>
50{
51public:
52 typedef typename t_csa::value_type value_type;
58 typedef const pointer const_pointer;
60 typedef ptrdiff_t difference_type;
61 typedef t_bitvec bit_vector_type;
62 typedef t_csa csa_type;
63 typedef t_select select_type;
64
66
67 enum
68 {
71 sa_order = 0
72 };
73 // inner class which is used in CSTs to parametrize lcp classes
74 // with information about the CST.
75 template <class Cst>
76 struct type
77 {
79 };
80
81private:
82 csa_type const * m_csa = nullptr;
83 bit_vector_type m_data;
84 select_type m_select_support;
85
86public:
87 t_csa const *& csa = m_csa;
91
94 m_csa(lcp_c.m_csa),
95 m_data(lcp_c.m_data),
96 m_select_support(lcp_c.m_select_support)
97 {
98 m_select_support.set_vector(&m_data);
99 }
100
103 {
104 *this = std::move(lcp_c);
105 }
106
109 {
110 if (this != &lcp_c)
111 {
112 _lcp_support_sada tmp(lcp_c);
113 *this = std::move(tmp);
114 }
115 return *this;
116 }
117
120 {
121 if (this != &lcp_c)
122 {
123 m_csa = std::move(lcp_c.m_csa);
124 m_data = std::move(lcp_c.m_data);
125 m_select_support = std::move(lcp_c.m_select_support);
126 m_select_support.set_vector(&m_data);
127 }
128 return *this;
129 }
130
132 _lcp_support_sada(cache_config & config, t_csa const * f_csa)
133 {
134 typedef typename t_csa::size_type size_type;
135 set_csa(f_csa);
136 if (!cache_file_exists(conf::KEY_ISA, config))
137 {
138 construct_isa(config);
139 }
140 int_vector<> lcp;
142 std::string isa_file = cache_file_name(conf::KEY_ISA, config);
143 int_vector_buffer<> isa_buf(isa_file);
144 size_type n = lcp.size();
145 bit_vector data = bit_vector(2 * n, 0);
146 size_type data_cnt = 0;
147 for (size_type i = 0, l = 0, old_l = 1; i < n; ++i)
148 {
149 l = lcp[isa_buf[i]];
150 data_cnt += l + 1 - old_l;
151 data[data_cnt++] = 1;
152 old_l = l;
153 }
154 data.resize(data_cnt);
155 data.shrink_to_fit();
156 m_data = bit_vector_type(data);
157 util::init_support(m_select_support, &m_data);
158 }
159
160 void set_csa(t_csa const * f_csa)
161 {
162 m_csa = f_csa;
163 }
164
167 {
168 return m_csa->size();
169 }
170
173 {
174 return t_csa::max_size();
175 }
176
178 bool empty() const
179 {
180 return m_csa->empty();
181 }
182
185 {
186 return const_iterator(this, 0);
187 }
188
191 {
192 return const_iterator(this, size());
193 }
194
196
200 {
201 size_type j = (*m_csa)[i];
202 size_type s = m_select_support.select(j + 1);
203 return s - (j << 1);
204 }
205
207 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
208 {
209 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
210 size_type written_bytes = 0;
211 written_bytes += m_data.serialize(out, child, "data");
212 written_bytes += m_select_support.serialize(out, child, "select_support");
213 structure_tree::add_size(child, written_bytes);
214 return written_bytes;
215 }
216
218 void load(std::istream & in, t_csa const * ccsa = nullptr)
219 {
220 m_csa = ccsa;
221 m_data.load(in);
222 m_select_support.load(in, &m_data);
223 }
224
225 template <typename archive_t>
226 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
227 {
228 ar(CEREAL_NVP(m_data));
229 ar(CEREAL_NVP(m_select_support));
230 }
231
232 template <typename archive_t>
233 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
234 {
235 ar(CEREAL_NVP(m_data));
236 ar(CEREAL_NVP(m_select_support));
237 m_select_support.set_vector(&m_data);
238 }
239
241 bool operator==(_lcp_support_sada const & other) const noexcept
242 {
243 return (m_data == other.m_data) && (m_select_support == other.m_select_support);
244 }
245
247 bool operator!=(_lcp_support_sada const & other) const noexcept
248 {
249 return !(*this == other);
250 }
251};
252
254template <class t_bitvec = bit_vector, class t_select = typename t_bitvec::select_1_type>
260
261} // end namespace sdsl
262#endif
cereal.hpp offers cereal support
#define CEREAL_NVP(X)
Definition cereal.hpp:31
A class to represent the LCP array in compressed form.
static size_type max_size()
Returns the largest size that _lcp_support_sada can ever have.
const_iterator begin() const
Returns a const_iterator to the first element.
_lcp_support_sada(_lcp_support_sada &&lcp_c)
Move constructor.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serialize to a stream.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
random_access_const_iterator< _lcp_support_sada > const_iterator
_lcp_support_sada(_lcp_support_sada const &lcp_c)
Copy constructor.
_lcp_support_sada & operator=(_lcp_support_sada const &lcp_c)
Assignment Operator.
const_iterator end() const
Returns a const_iterator to the element after the last element.
bool operator!=(_lcp_support_sada const &other) const noexcept
Inequality operator.
lcp_permuted_tag lcp_category
_lcp_support_sada(cache_config &config, t_csa const *f_csa)
Constructor.
_lcp_support_sada & operator=(_lcp_support_sada &&lcp_c)
Assignment Move Operator.
void set_csa(t_csa const *f_csa)
int_vector ::size_type size_type
const value_type const_reference
_lcp_support_sada()
Default Constructor.
size_type size() const
Number of elements in the instance.
value_type operator[](size_type i) const
[]-operator
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
bool operator==(_lcp_support_sada const &other) const noexcept
Equality operator.
void load(std::istream &in, t_csa const *ccsa=nullptr)
Load from a stream.
t_csa::value_type value_type
bool empty() const
Returns if the data structure is empty.
A generic vector class for integers of width .
Definition io.hpp:36
int_vector_size_type size_type
size_type size() const noexcept
The number of elements in the int_vector.
void shrink_to_fit()
Free unused allocated memory.
void resize(const size_type size)
Resize the int_vector in terms of elements.
Generic iterator for a random access container.
Definition iterators.hpp:24
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)
construct_isa.hpp contains a space and time efficient construction method for the inverse suffix arra...
csa_sada.hpp contains an implementation of the compressed suffix array.
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.
iterators.hpp contains an generic iterator for random access containers.
constexpr char KEY_LCP[]
Definition config.hpp:43
constexpr char KEY_ISA[]
Definition config.hpp:39
Namespace for the succinct data structure library.
bool cache_file_exists(std::string const &key, cache_config const &config)
Checks if the resource specified by the key exists in the cache.
Definition io.hpp:733
std::string cache_file_name(std::string const &key, cache_config const &config)
Returns the file name of the resource.
Definition io.hpp:688
bool load_from_file(T &v, std::string const &file)
Load sdsl-object v from a file.
Definition io.hpp:989
int_vector< 1 > bit_vector
bit_vector is a specialization of the int_vector.
void construct_isa(cache_config &config)
Contains declarations and definitions of data structure concepts.
Helper class for construction process.
Definition config.hpp:66
Helper class which provides _lcp_support_sada the context of a CSA.
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.