SDSL  3.0.0
Succinct Data Structure Library
lcp_support_tree.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.
4 #ifndef INCLUDED_SDSL_SUPPORT_LCP_TREE
5 #define INCLUDED_SDSL_SUPPORT_LCP_TREE
6 
7 #include <iostream>
8 #include <string>
9 
10 #include <sdsl/lcp.hpp>
11 #include <sdsl/lcp_wt.hpp>
13 #include <sdsl/util.hpp>
14 
15 namespace sdsl
16 {
17 
19 {
21  size_type n = lcp_buf.size();
22  if (n == 0)
23  { // if n == 0 we are done
24  fc_lcp = int_vector<>(0);
25  return;
26  }
27  fc_lcp = int_vector<>(n, 0, bits::hi(n) + 1);
28  size_type fc_cnt = 0; // first child counter
29  sorted_multi_stack_support vec_stack(n);
30  size_type y;
31  for (size_type i = 0, x; i < n; ++i)
32  {
33  x = lcp_buf[i];
34  while (!vec_stack.empty() and x < vec_stack.top())
35  {
36  y = vec_stack.top();
37  if (vec_stack.pop()) { fc_lcp[fc_cnt++] = y; }
38  }
39  vec_stack.push(x);
40  }
41 
42  while (!vec_stack.empty())
43  {
44  y = vec_stack.top();
45  if (vec_stack.pop()) { fc_lcp[fc_cnt++] = y; }
46  }
47  if (fc_cnt < fc_lcp.size())
48  {
49  fc_lcp.resize(fc_cnt);
50  fc_lcp.shrink_to_fit();
51  }
52 }
53 
63 template <class t_lcp, class t_cst>
65 {
66  public:
67  typedef typename t_lcp::value_type value_type;
70  typedef const value_type const_reference;
73  typedef const pointer const_pointer;
74  typedef typename t_lcp::size_type size_type;
75  typedef typename t_lcp::difference_type difference_type;
76 
78 
79  enum
80  {
82  text_order = t_lcp::text_order,
83  sa_order = t_lcp::sa_order
84  };
85 
86  template <class CST>
87  struct type
88  {
90  };
91 
92  private:
93  const t_cst * m_cst;
94  t_lcp m_lcp;
95 
96  public:
98  _lcp_support_tree() = default;
99 
100  // Destructor
101  ~_lcp_support_tree() = default;
102 
108 
110 
114  _lcp_support_tree(cache_config & config, const t_cst * cst = nullptr)
115  {
116  m_cst = cst;
117  std::string fc_lcp_key = "fc_lcp_" + util::to_string(util::id());
118  std::string tmp_file = cache_file_name(fc_lcp_key, config);
119  {
120  int_vector<0> temp_lcp;
122  construct_first_child_lcp(lcp_buf, temp_lcp);
123  // TODO: store LCP values directly
124  store_to_file(temp_lcp, tmp_file);
125  }
126  {
127  {
128  m_lcp = t_lcp(config, fc_lcp_key); // works for lcp_kurtz, lcp_wt and lcp_bitcompressed
129  }
130  }
132  }
133 
134  size_type size() const { return m_cst->size(); }
135 
136  void set_cst(const t_cst * cst) { m_cst = cst; }
137 
138  static size_type max_size() { return t_lcp::max_size(); }
139 
140  size_type empty() const { return m_lcp.empty(); }
141 
143  const_iterator begin() const { return const_iterator(this, 0); }
144 
146  const_iterator end() const { return const_iterator(this, size()); }
147 
149 
153  inline value_type operator[](size_type i) const { return m_lcp[m_cst->tlcp_idx(i)]; }
154 
156  size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
157  {
158  size_type written_bytes = 0;
159  structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
160  written_bytes += m_lcp.serialize(out, child, "lcp");
161  structure_tree::add_size(child, written_bytes);
162  return written_bytes;
163  }
164 
166  void load(std::istream & in, const t_cst * cst = nullptr)
167  {
168  m_lcp.load(in); // works for lcp_byte and lcp_bitcompressed
169  m_cst = cst;
170  }
171 
172  template <typename archive_t>
173  void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
174  {
175  ar(CEREAL_NVP(m_lcp));
176  }
177 
178  template <typename archive_t>
179  void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
180  {
181  ar(CEREAL_NVP(m_lcp));
182  }
183 
185  bool operator==(_lcp_support_tree const & other) const noexcept { return (m_lcp == other.m_lcp); }
186 
188  bool operator!=(_lcp_support_tree const & other) const noexcept { return !(*this == other); }
189 };
190 
192 template <class t_lcp = lcp_wt<>>
194 {
195  template <class t_cst>
197 };
198 
199 } // namespace sdsl
200 #endif
#define CEREAL_NVP(X)
Definition: cereal.hpp:30
This class composes a virtual LCP array from a LCP arrays which is in suffix array order (e....
const_iterator begin() const
Returns a const_iterator to the first element.
_lcp_support_tree(const _lcp_support_tree &)=default
Copy/Move constructor.
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
_lcp_support_tree & operator=(const _lcp_support_tree &)=default
_lcp_support_tree(cache_config &config, const t_cst *cst=nullptr)
Constructor.
bool operator==(_lcp_support_tree const &other) const noexcept
Equality operator.
const_reference * pointer
value_type operator[](size_type i) const
[]-operator
const value_type const_reference
_lcp_support_tree & operator=(_lcp_support_tree &&)=default
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serialize to a stream.
t_lcp::difference_type difference_type
t_lcp::size_type size_type
void load(std::istream &in, const t_cst *cst=nullptr)
Load from a stream.
bool operator!=(_lcp_support_tree const &other) const noexcept
Inequality operator.
random_access_const_iterator< _lcp_support_tree > const_iterator
static size_type max_size()
void set_cst(const t_cst *cst)
_lcp_support_tree()=default
Default constructor.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
t_lcp::value_type value_type
const_iterator end() const
Returns a const_iterator to the element after the last element.
lcp_tree_compressed_tag lcp_category
_lcp_support_tree(_lcp_support_tree &&)=default
uint64_t size() const
Returns the number of elements currently stored.
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
Stack which contains elements from [0..n] in sorted order. Duplicates are possible.
bool empty() const
Returns if the stack is empty.
size_type top() const
Returns the topmost index on the stack.
bool pop()
Pop the topmost index of the stack.
bool push(size_type x)
Push the index x of vector vec onto the stack.
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)
lcp.hpp contains classes for lcp information.
lcp_wt.hpp contains a (compressed) LCP array based on a WT.
constexpr char KEY_LCP[]
Definition: config.hpp:44
int_vector ::size_type size_type
uint64_t id()
std::string to_string(const T &t, int w=1)
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
std::string tmp_file(const cache_config &config, std::string name_part="")
Returns a name for a temporary file. I.e. the name was not used before.
Definition: io.hpp:698
uint64_t int_vector_size_type
Definition: config.hpp:48
bool store_to_file(const T &v, const std::string &file)
Store a data structure to a file.
Definition: io.hpp:798
int remove(const std::string &)
Remove a file.
Definition: ram_fs.hpp:194
void construct_first_child_lcp(int_vector_buffer<> &lcp_buf, int_vector<> &fc_lcp)
sorted_multi_stack_support.hpp contains a data structure for a stack which contains elements from [0....
static SDSL_CONSTEXPR uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Definition: bits.hpp:661
Helper class for construction process.
Definition: config.hpp:67
Helper class which provides _lcp_support_tree the context of a CST.
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.