SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
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/bits.hpp>
11#include <sdsl/cereal.hpp>
12#include <sdsl/config.hpp>
13#include <sdsl/int_vector.hpp>
15#include <sdsl/io.hpp>
16#include <sdsl/iterators.hpp>
17#include <sdsl/lcp_wt.hpp>
18#include <sdsl/ram_fs.hpp>
22#include <sdsl/util.hpp>
23
24namespace sdsl
25{
26
28{
30 size_type n = lcp_buf.size();
31 if (n == 0)
32 { // if n == 0 we are done
33 fc_lcp = int_vector<>(0);
34 return;
35 }
36 fc_lcp = int_vector<>(n, 0, bits::hi(n) + 1);
37 size_type fc_cnt = 0; // first child counter
38 sorted_multi_stack_support vec_stack(n);
39 size_type y;
40 for (size_type i = 0, x; i < n; ++i)
41 {
42 x = lcp_buf[i];
43 while (!vec_stack.empty() and x < vec_stack.top())
44 {
45 y = vec_stack.top();
46 if (vec_stack.pop())
47 {
48 fc_lcp[fc_cnt++] = y;
49 }
50 }
51 vec_stack.push(x);
52 }
53
54 while (!vec_stack.empty())
55 {
56 y = vec_stack.top();
57 if (vec_stack.pop())
58 {
59 fc_lcp[fc_cnt++] = y;
60 }
61 }
62 if (fc_cnt < fc_lcp.size())
63 {
64 fc_lcp.resize(fc_cnt);
65 fc_lcp.shrink_to_fit();
66 }
67}
68
78template <class t_lcp, class t_cst>
80{
81public:
82 typedef typename t_lcp::value_type value_type;
88 typedef const pointer const_pointer;
89 typedef typename t_lcp::size_type size_type;
90 typedef typename t_lcp::difference_type difference_type;
91
93
94 enum
95 {
97 text_order = t_lcp::text_order,
98 sa_order = t_lcp::sa_order
99 };
100
101 template <class CST>
102 struct type
103 {
105 };
106
107private:
108 t_cst const * m_cst;
109 t_lcp m_lcp;
110
111public:
113 _lcp_support_tree() = default;
114
115 // Destructor
117
123
125
129 _lcp_support_tree(cache_config & config, t_cst const * cst = nullptr)
130 {
131 m_cst = cst;
132 std::string fc_lcp_key = "fc_lcp_" + util::to_string(util::id());
133 std::string tmp_file = cache_file_name(fc_lcp_key, config);
134 {
135 int_vector<0> temp_lcp;
137 construct_first_child_lcp(lcp_buf, temp_lcp);
138 // TODO: store LCP values directly
139 store_to_file(temp_lcp, tmp_file);
140 }
141 {
142 {
143 m_lcp = t_lcp(config, fc_lcp_key); // works for lcp_kurtz, lcp_wt and lcp_bitcompressed
144 }
145 }
147 }
148
150 {
151 return m_cst->size();
152 }
153
154 void set_cst(t_cst const * cst)
155 {
156 m_cst = cst;
157 }
158
160 {
161 return t_lcp::max_size();
162 }
163
165 {
166 return m_lcp.empty();
167 }
168
171 {
172 return const_iterator(this, 0);
173 }
174
177 {
178 return const_iterator(this, size());
179 }
180
182
187 {
188 return m_lcp[m_cst->tlcp_idx(i)];
189 }
190
192 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
193 {
194 size_type written_bytes = 0;
195 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
196 written_bytes += m_lcp.serialize(out, child, "lcp");
197 structure_tree::add_size(child, written_bytes);
198 return written_bytes;
199 }
200
202 void load(std::istream & in, t_cst const * cst = nullptr)
203 {
204 m_lcp.load(in); // works for lcp_byte and lcp_bitcompressed
205 m_cst = cst;
206 }
207
208 template <typename archive_t>
209 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
210 {
211 ar(CEREAL_NVP(m_lcp));
212 }
213
214 template <typename archive_t>
215 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
216 {
217 ar(CEREAL_NVP(m_lcp));
218 }
219
221 bool operator==(_lcp_support_tree const & other) const noexcept
222 {
223 return (m_lcp == other.m_lcp);
224 }
225
227 bool operator!=(_lcp_support_tree const & other) const noexcept
228 {
229 return !(*this == other);
230 }
231};
232
234template <class t_lcp = lcp_wt<>>
236{
237 template <class t_cst>
239};
240
241} // namespace sdsl
242#endif
bits.hpp contains the sdsl::bits class.
cereal.hpp offers cereal support
#define CEREAL_NVP(X)
Definition cereal.hpp:31
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.
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
bool operator==(_lcp_support_tree const &other) const noexcept
Equality operator.
value_type operator[](size_type i) const
[]-operator
const value_type const_reference
_lcp_support_tree & operator=(_lcp_support_tree const &)=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
void set_cst(t_cst const *cst)
_lcp_support_tree(cache_config &config, t_cst const *cst=nullptr)
Constructor.
bool operator!=(_lcp_support_tree const &other) const noexcept
Inequality operator.
random_access_const_iterator< _lcp_support_tree > const_iterator
_lcp_support_tree(_lcp_support_tree const &)=default
Copy/Move constructor.
void load(std::istream &in, t_cst const *cst=nullptr)
Load from a stream.
static size_type max_size()
_lcp_support_tree()=default
Default constructor.
_lcp_support_tree & operator=(_lcp_support_tree &&)=default
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.
int_vector< 64 >::size_type size() const noexcept
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
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 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)
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.
lcp_wt.hpp contains a (compressed) LCP array based on a WT.
constexpr char KEY_LCP[]
Definition config.hpp:43
uint64_t id()
std::string to_string(T const &t, int w=1)
Namespace for the succinct data structure library.
int remove(std::string const &)
Remove a file.
Definition ram_fs.hpp:221
std::string tmp_file(cache_config const &config, std::string name_part="")
Returns a name for a temporary file. I.e. the name was not used before.
Definition io.hpp:759
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 store_to_file(T const &v, std::string const &file)
Store a data structure to a file.
Definition io.hpp:874
uint64_t int_vector_size_type
Definition config.hpp:47
void construct_first_child_lcp(int_vector_buffer<> &lcp_buf, int_vector<> &fc_lcp)
ram_fs.hpp
Contains declarations and definitions of data structure concepts.
sorted_multi_stack_support.hpp contains a data structure for a stack which contains elements from [0....
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Definition bits.hpp:653
Helper class for construction process.
Definition config.hpp:66
Helper class which provides _lcp_support_tree the context of a CST.
_lcp_support_tree< t_lcp, t_cst > type
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.