SDSL 3.0.1
Succinct Data Structure Library
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 <cassert>
12
13#include <sdsl/csa_sada.hpp> // for default template initialization
14#include <sdsl/int_vector.hpp>
15#include <sdsl/iterators.hpp>
16#include <sdsl/lcp.hpp>
17#include <sdsl/select_support.hpp> // for default template initialization
18
19namespace sdsl
20{
21
23
40template <class t_csa = csa_sada<>, class t_bitvec = bit_vector, class t_select = typename t_bitvec::select_1_type>
42{
43 public:
44 typedef typename t_csa::value_type value_type;
50 typedef const pointer const_pointer;
52 typedef ptrdiff_t difference_type;
53 typedef t_bitvec bit_vector_type;
54 typedef t_csa csa_type;
55 typedef t_select select_type;
56
58
59 enum
60 {
63 sa_order = 0
64 };
65 // inner class which is used in CSTs to parametrize lcp classes
66 // with information about the CST.
67 template <class Cst>
68 struct type
69 {
71 };
72
73 private:
74 const csa_type * m_csa = nullptr;
75 bit_vector_type m_data;
76 select_type m_select_support;
77
78 public:
79 const t_csa *& csa = m_csa;
82
85 : m_csa(lcp_c.m_csa)
86 , m_data(lcp_c.m_data)
87 , m_select_support(lcp_c.m_select_support)
88 {
89 m_select_support.set_vector(&m_data);
90 }
91
93 _lcp_support_sada(_lcp_support_sada && lcp_c) { *this = std::move(lcp_c); }
94
97 {
98 if (this != &lcp_c)
99 {
100 _lcp_support_sada tmp(lcp_c);
101 *this = std::move(tmp);
102 }
103 return *this;
104 }
105
108 {
109 if (this != &lcp_c)
110 {
111 m_csa = std::move(lcp_c.m_csa);
112 m_data = std::move(lcp_c.m_data);
113 m_select_support = std::move(lcp_c.m_select_support);
114 m_select_support.set_vector(&m_data);
115 }
116 return *this;
117 }
118
120 _lcp_support_sada(cache_config & config, const t_csa * f_csa)
121 {
122 typedef typename t_csa::size_type size_type;
123 set_csa(f_csa);
124 if (!cache_file_exists(conf::KEY_ISA, config)) { construct_isa(config); }
125 int_vector<> lcp;
127 std::string isa_file = cache_file_name(conf::KEY_ISA, config);
128 int_vector_buffer<> isa_buf(isa_file);
129 size_type n = lcp.size();
130 bit_vector data = bit_vector(2 * n, 0);
131 size_type data_cnt = 0;
132 for (size_type i = 0, l = 0, old_l = 1; i < n; ++i)
133 {
134 l = lcp[isa_buf[i]];
135 data_cnt += l + 1 - old_l;
136 data[data_cnt++] = 1;
137 old_l = l;
138 }
139 data.resize(data_cnt);
140 data.shrink_to_fit();
141 m_data = bit_vector_type(data);
142 util::init_support(m_select_support, &m_data);
143 }
144
145 void set_csa(const t_csa * f_csa) { m_csa = f_csa; }
146
148 size_type size() const { return m_csa->size(); }
149
151 static size_type max_size() { return t_csa::max_size(); }
152
154 bool empty() const { return m_csa->empty(); }
155
157 const_iterator begin() const { return const_iterator(this, 0); }
158
160 const_iterator end() const { return const_iterator(this, size()); }
161
163
167 {
168 size_type j = (*m_csa)[i];
169 size_type s = m_select_support.select(j + 1);
170 return s - (j << 1);
171 }
172
174 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
175 {
176 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
177 size_type written_bytes = 0;
178 written_bytes += m_data.serialize(out, child, "data");
179 written_bytes += m_select_support.serialize(out, child, "select_support");
180 structure_tree::add_size(child, written_bytes);
181 return written_bytes;
182 }
183
185 void load(std::istream & in, const t_csa * ccsa = nullptr)
186 {
187 m_csa = ccsa;
188 m_data.load(in);
189 m_select_support.load(in, &m_data);
190 }
191
192 template <typename archive_t>
193 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
194 {
195 ar(CEREAL_NVP(m_data));
196 ar(CEREAL_NVP(m_select_support));
197 }
198
199 template <typename archive_t>
200 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
201 {
202 ar(CEREAL_NVP(m_data));
203 ar(CEREAL_NVP(m_select_support));
204 m_select_support.set_vector(&m_data);
205 }
206
208 bool operator==(_lcp_support_sada const & other) const noexcept
209 {
210 return (m_data == other.m_data) && (m_select_support == other.m_select_support);
211 }
212
214 bool operator!=(_lcp_support_sada const & other) const noexcept { return !(*this == other); }
215};
216
218template <class t_bitvec = bit_vector, class t_select = typename t_bitvec::select_1_type>
220{
221 template <class t_cst>
223};
224
225} // end namespace sdsl
226#endif
#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 set_csa(const t_csa *f_csa)
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
random_access_const_iterator< _lcp_support_sada > const_iterator
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.
const_reference * pointer
lcp_permuted_tag lcp_category
void load(std::istream &in, const t_csa *ccsa=nullptr)
Load from a stream.
_lcp_support_sada & operator=(_lcp_support_sada &&lcp_c)
Assignment Move Operator.
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.
_lcp_support_sada(cache_config &config, const t_csa *f_csa)
Constructor.
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.
_lcp_support_sada(const _lcp_support_sada &lcp_c)
Copy constructor.
_lcp_support_sada & operator=(const _lcp_support_sada &lcp_c)
Assignment Operator.
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: int_vector.hpp:216
void shrink_to_fit()
Free unused allocated memory.
Definition: int_vector.hpp:506
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.
Definition: int_vector.hpp:521
Generic iterator for a random access container.
Definition: iterators.hpp:24
static structure_tree_node * add_child(structure_tree_node *v, const std::string &name, const std::string &type)
static void add_size(structure_tree_node *v, uint64_t value)
csa_sada.hpp contains an implementation of the compressed suffix array.
int_vector.hpp contains the sdsl::int_vector class.
iterators.hpp contains an generic iterator for random access containers.
lcp.hpp contains classes for lcp information.
constexpr char KEY_LCP[]
Definition: config.hpp:44
constexpr char KEY_ISA[]
Definition: config.hpp:40
int_vector ::size_type size_type
Namespace for the succinct data structure library.
std::string cache_file_name(const std::string &key, const cache_config &config)
Returns the file name of the resource.
Definition: io.hpp:630
int_vector< 1 > bit_vector
bit_vector is a specialization of the int_vector.
Definition: int_vector.hpp:53
void construct_isa(cache_config &config)
bool load_from_file(T &v, const std::string &file)
Load sdsl-object v from a file.
Definition: io.hpp:901
bool cache_file_exists(const std::string &key, const cache_config &config)
Checks if the resource specified by the key exists in the cache.
Definition: io.hpp:672
select_support.hpp contains classes that support a sdsl::bit_vector with constant time select informa...
Helper class for construction process.
Definition: config.hpp:67
Helper class which provides _lcp_support_sada the context of a CSA.