SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
cst_iterators.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_CST_ITERATORS
9#define INCLUDED_SDSL_CST_ITERATORS
10
11#include <cstdint>
12#include <iterator>
13#include <queue>
14
15namespace sdsl
16{
17
19
36// TODO: implement operator--
37template <class Cst, uint32_t cache_size = 128>
39{
40public:
41 using iterator_category = std::forward_iterator_tag;
42 using value_type = typename Cst::node_type;
43 using difference_type = std::ptrdiff_t;
46
48 typedef typename Cst::size_type size_type;
50 typedef typename Cst::node_type node_type;
51
52private:
53 Cst const * m_cst;
54 node_type m_v;
55 bool m_visited;
56 bool m_valid;
57 node_type * m_stack_cache;
58 uint32_t m_stack_size;
59
60 inline node_type parent()
61 {
62 --m_stack_size; // decrease stack size
63 if (m_stack_cache != nullptr and m_stack_size < cache_size)
64 {
65 return m_stack_cache[m_stack_size];
66 }
67 else
68 return m_cst->parent(m_v);
69 }
70
71 inline node_type first_child()
72 {
73 if (m_stack_cache != nullptr and m_stack_size < cache_size) // push node to the stack
74 m_stack_cache[m_stack_size] = m_v;
75 m_stack_size++;
76 return m_cst->select_child(m_v, 1);
77 }
78
80 cst_dfs_const_forward_iterator() : m_cst(nullptr), m_visited(false), m_valid(false), m_stack_cache(nullptr)
81 {}
82
83public:
85 cst_dfs_const_forward_iterator(Cst const * cst, const value_type node, bool visited = false, bool valid = true) :
86 m_visited(visited),
87 m_valid(valid),
88 m_stack_cache(nullptr)
89 {
90 m_cst = cst;
91 m_v = node;
92 if (m_cst == nullptr)
93 {
94 m_valid = false;
95 }
96 else if (m_v == m_cst->root() and !m_visited and m_valid)
97 { // if the iterator equal cst.begin()
98 m_stack_cache = new node_type[cache_size];
99 m_stack_size = 0;
100 // std::cerr<<"#creating stack "<<m_cst->lb(m_v)<<" "<<m_cst->rb(m_v)<<std::endl;
101 }
102 }
103
105 // cst_dfs_const_forward_iterator(const cst_dfs_const_forward_iterator
106 //&it):m_cst(it.cst),m_v(it.m_v),m_valid(m_valid), m_stack_cache(nullptr),m_stack_size(0){
107 // }
108
110 {
111 if (m_stack_cache != nullptr)
112 {
113 // std::cerr<<"#deleting stack "<<m_cst->lb(m_v)<<" "<<m_cst->rb(m_v)<<std::endl;
114 delete[] m_stack_cache;
115 }
116 }
117
119 uint8_t visit() const
120 {
121 return 1 + (uint8_t)m_visited;
122 }
123
125 {
126 if (m_valid)
127 {
128 if (!m_visited)
129 {
130 m_visited = true;
131 }
132 }
133 }
134
137 {
138 return m_v;
139 }
140
143 {
144 if (!m_valid)
145 return *this;
146 if (m_v == m_cst->root() and m_visited)
147 {
148 m_valid = false;
149 return *this;
150 }
151 value_type w;
152 if (!m_visited)
153 { // go down, if possible
154 if (m_cst->is_leaf(m_v))
155 {
156 w = m_cst->sibling(m_v); // determine sibling of leaf v
157 if (w == m_cst->root())
158 { // if there exists no right sibling of the leaf v
159 // w = m_cst->parent(m_v);
160 w = parent();
161 m_visited = true; // go up
162 }
163 }
164 else
165 { // v is not a leaf => go down the tree
166 w = first_child();
167 }
168 }
169 else
170 { //
171 w = m_cst->sibling(m_v);
172 if (w == m_cst->root())
173 { // if there exists no right sibling
174 w = parent();
175 }
176 else
177 {
178 m_visited = false;
179 }
180 }
181 m_v = w;
182 return *this;
183 }
184
186 void operator++(int)
187 {
188 ++(*this);
189 }
190
192 bool operator==(iterator const & it) const
193 {
194 return (it.m_visited == m_visited) // visited status is equal
195 and (it.m_valid == m_valid) // valid status is equal => for end() iterator
196 and (it.m_v == m_v) // nodes are equal
197 and (it.m_cst == m_cst); // iterator belongs to the same cst
198 }
199
201 bool operator!=(iterator const & it) const
202 {
203 return !(*this == it);
204 }
205};
206
208template <class Cst>
210{
211public:
212 using iterator_category = std::forward_iterator_tag;
213 using value_type = typename Cst::node_type;
214 using difference_type = std::ptrdiff_t;
217
219 typedef typename Cst::size_type size_type;
221
222private:
223 Cst const * m_cst;
224 typename Cst::node_type m_v;
225 bool m_valid;
226
227public:
229 cst_bottom_up_const_forward_iterator() : m_cst(nullptr), m_valid(false)
230 {}
231
233 cst_bottom_up_const_forward_iterator(Cst const * cst, const value_type node, bool valid = true) : m_valid(valid)
234 {
235 m_cst = cst;
236 m_v = node;
237 if (m_cst == nullptr)
238 m_valid = false;
239 }
240
243 {
244 return m_v;
245 }
246
249 {
250 if (!m_valid)
251 return *this;
252 if (m_v == m_cst->root())
253 {
254 m_valid = false;
255 return *this;
256 }
257 value_type w = m_cst->sibling(m_v);
258 if (w == m_cst->root())
259 { // if no next right sibling exist
260 m_v = m_cst->parent(m_v); // go to parent
261 }
262 else
263 { // if next right sibling exist
264 m_v = m_cst->leftmost_leaf(w); // go to leaftmost leaf in the subtree of w
265 }
266 return *this;
267 }
268
271 {
272 iterator it = *this;
273 ++(*this);
274 return it;
275 }
276
278 bool operator==(iterator const & it) const
279 {
280 return (it.m_valid == m_valid) // valid status is equal => for end() iterator
281 and (it.m_v == m_v) // nodes are equal
282 and (it.m_cst == m_cst); // iterator belongs to the same cst
283 }
284
286 bool operator!=(iterator const & it) const
287 {
288 return !(*this == it);
289 }
290};
291
293
298template <class Cst, class Queue = std::queue<typename Cst::node_type>>
300{
301public:
302 using iterator_category = std::forward_iterator_tag;
303 using value_type = typename Cst::node_type;
304 using difference_type = std::ptrdiff_t;
307
309 typedef typename Cst::size_type size_type;
311 typedef Queue queue_type;
312
313private:
314 Cst const * m_cst; // Pointer to the cst.
315 queue_type m_queue; //
316 bool m_valid; // State of the iterator.
317
318public:
320
326 cst_bfs_iterator(Cst const * cst, const value_type node, bool valid = true, bool end_it = false)
327 {
328 m_cst = cst;
329 m_valid = valid;
330 if (m_cst != nullptr and !end_it)
331 {
332 m_queue.push(node);
333 }
334 }
335
338 {
339 return m_queue.size();
340 }
341
344 {
345 return m_queue.front();
346 }
347
350 {
351 if (!m_valid)
352 return *this;
353 if (m_queue.empty())
354 {
355 m_valid = false;
356 return *this;
357 }
358 value_type v = m_queue.front();
359 m_queue.pop();
360 value_type child = m_cst->select_child(v, 1);
361 while (m_cst->root() != child)
362 {
363 m_queue.push(child);
364 child = m_cst->sibling(child);
365 }
366 return *this;
367 }
368
371 {
372 iterator it = *this;
373 ++(*this);
374 return it;
375 }
376
378 bool operator==(iterator const & it) const
379 {
380 if (m_queue.size() != it.m_queue.size())
381 { // if the queue size is different
382 return false; // the state of the to iterator are different
383 }
384 if (m_queue.empty())
385 { // if the queue is empty, we have to check if they are valid and
386 return it.m_valid == m_valid and it.m_cst == m_cst; // belong to the same cst
387 }
388 return (it.m_valid == m_valid) // valid status is equal => for end() iterator
389 and (it.m_cst == m_cst) // iterator belongs to the same cst
390 and (it.m_queue.front() == m_queue.front()) // front element and
391 and (it.m_queue.back() == m_queue.back()); // back element are the same.
392 }
393
395 bool operator!=(iterator const & it) const
396 {
397 return !(*this == it);
398 }
399};
400
401} // end namespace sdsl
402
403#endif
A forward iterator for a breath first traversal of a tree.
bool operator!=(iterator const &it) const
Inequality operator.
cst_bfs_iterator< Cst, Queue > iterator
std::forward_iterator_tag iterator_category
typename Cst::node_type value_type
const value_type const_reference
bool operator==(iterator const &it) const
Equality operator.
iterator operator++(int)
Postfix increment of the iterator.
cst_bfs_iterator(Cst const *cst, const value_type node, bool valid=true, bool end_it=false)
Constructor.
iterator & operator++()
Prefix increment of the iterator.
const_reference operator*() const
Method for dereferencing the iterator.
size_type size() const
Returns the current number of nodes in the queue.
std::ptrdiff_t difference_type
A forward iterator for a bottom up traversal of a suffix tree.
bool operator==(iterator const &it) const
Equality operator.
iterator operator++(int)
Postfix increment of the iterator.
iterator & operator++()
Prefix increment of the iterator.
cst_bottom_up_const_forward_iterator(Cst const *cst, const value_type node, bool valid=true)
Constructor.
cst_bottom_up_const_forward_iterator< Cst > iterator
bool operator!=(iterator const &it) const
Inequality operator.
cst_bottom_up_const_forward_iterator()
Default constructor.
const_reference operator*() const
Method for dereferencing the iterator.
An forward iterator for (compressed) suffix trees.
uint8_t visit() const
Returns how often the current node was already visited.
std::forward_iterator_tag iterator_category
bool operator!=(iterator const &it) const
Inequality operator.
void operator++(int)
Postfix increment of the iterator.
cst_dfs_const_forward_iterator(Cst const *cst, const value_type node, bool visited=false, bool valid=true)
Constructor.
iterator & operator++()
Prefix increment of the iterator.
cst_dfs_const_forward_iterator< Cst > iterator
bool operator==(iterator const &it) const
Equality operator.
~cst_dfs_const_forward_iterator()
Copy Constructor.
const_reference operator*() const
Method for dereferencing the iterator.
Namespace for the succinct data structure library.