SDSL  3.0.0
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 
19 namespace sdsl
20 {
21 
23 
40 template <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;
47  typedef const value_type const_reference;
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 
218 template <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:30
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=(const _lcp_support_sada &lcp_c)
Assignment 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.
t_csa::value_type value_type
_lcp_support_sada & operator=(_lcp_support_sada &&lcp_c)
Assignment Move Operator.
bool empty() const
Returns if the data structure is empty.
A generic vector class for integers of width .
Definition: int_vector.hpp:253
void shrink_to_fit()
Free unused allocated memory.
Definition: int_vector.hpp:530
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:545
Generic iterator for a random access container.
Definition: iterators.hpp:24
static void add_size(structure_tree_node *v, uint64_t value)
static structure_tree_node * add_child(structure_tree_node *v, const std::string &name, const std::string &type)
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:51
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.