SDSL 3.0.1
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 <queue>
13
14namespace sdsl
15{
16
18
35// TODO: implement operator--
36template <class Cst, uint32_t cache_size = 128>
38{
39 public:
40 using iterator_category = std::forward_iterator_tag;
41 using value_type = typename Cst::node_type;
42 using difference_type = std::ptrdiff_t;
45
47 typedef typename Cst::size_type size_type;
49 typedef typename Cst::node_type node_type;
50
51 private:
52 const Cst * m_cst;
53 node_type m_v;
54 bool m_visited;
55 bool m_valid;
56 node_type * m_stack_cache;
57 uint32_t m_stack_size;
58
59 inline node_type parent()
60 {
61 --m_stack_size; // decrease stack size
62 if (m_stack_cache != nullptr and m_stack_size < cache_size) { return m_stack_cache[m_stack_size]; }
63 else
64 return m_cst->parent(m_v);
65 }
66
67 inline node_type first_child()
68 {
69 if (m_stack_cache != nullptr and m_stack_size < cache_size) // push node to the stack
70 m_stack_cache[m_stack_size] = m_v;
71 m_stack_size++;
72 return m_cst->select_child(m_v, 1);
73 }
74
76 cst_dfs_const_forward_iterator()
77 : m_cst(nullptr)
78 , m_visited(false)
79 , m_valid(false)
80 , m_stack_cache(nullptr)
81 {}
82
83 public:
85 cst_dfs_const_forward_iterator(const Cst * 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) { m_valid = false; }
93 else if (m_v == m_cst->root() and !m_visited and m_valid)
94 { // if the iterator equal cst.begin()
95 m_stack_cache = new node_type[cache_size];
96 m_stack_size = 0;
97 // std::cerr<<"#creating stack "<<m_cst->lb(m_v)<<" "<<m_cst->rb(m_v)<<std::endl;
98 }
99 }
100
102 // cst_dfs_const_forward_iterator(const cst_dfs_const_forward_iterator
103 //&it):m_cst(it.cst),m_v(it.m_v),m_valid(m_valid), m_stack_cache(nullptr),m_stack_size(0){
104 // }
105
107 {
108 if (m_stack_cache != nullptr)
109 {
110 // std::cerr<<"#deleting stack "<<m_cst->lb(m_v)<<" "<<m_cst->rb(m_v)<<std::endl;
111 delete[] m_stack_cache;
112 }
113 }
114
116 uint8_t visit() const { return 1 + (uint8_t)m_visited; }
117
119 {
120 if (m_valid)
121 {
122 if (!m_visited) { m_visited = true; }
123 }
124 }
125
127 const_reference operator*() const { return m_v; }
128
131 {
132 if (!m_valid) return *this;
133 if (m_v == m_cst->root() and m_visited)
134 {
135 m_valid = false;
136 return *this;
137 }
138 value_type w;
139 if (!m_visited)
140 { // go down, if possible
141 if (m_cst->is_leaf(m_v))
142 {
143 w = m_cst->sibling(m_v); // determine sibling of leaf v
144 if (w == m_cst->root())
145 { // if there exists no right sibling of the leaf v
146 // w = m_cst->parent(m_v);
147 w = parent();
148 m_visited = true; // go up
149 }
150 }
151 else
152 { // v is not a leaf => go down the tree
153 w = first_child();
154 }
155 }
156 else
157 { //
158 w = m_cst->sibling(m_v);
159 if (w == m_cst->root())
160 { // if there exists no right sibling
161 w = parent();
162 }
163 else
164 {
165 m_visited = false;
166 }
167 }
168 m_v = w;
169 return *this;
170 }
171
173 void operator++(int) { ++(*this); }
174
176 bool operator==(const iterator & it) const
177 {
178 return (it.m_visited == m_visited) // visited status is equal
179 and (it.m_valid == m_valid) // valid status is equal => for end() iterator
180 and (it.m_v == m_v) // nodes are equal
181 and (it.m_cst == m_cst); // iterator belongs to the same cst
182 }
183
185 bool operator!=(const iterator & it) const { return !(*this == it); }
186};
187
189template <class Cst>
191{
192 public:
193 using iterator_category = std::forward_iterator_tag;
194 using value_type = typename Cst::node_type;
195 using difference_type = std::ptrdiff_t;
198
200 typedef typename Cst::size_type size_type;
202
203 private:
204 const Cst * m_cst;
205 typename Cst::node_type m_v;
206 bool m_valid;
207
208 public:
211 : m_cst(nullptr)
212 , m_valid(false)
213 {}
214
216 cst_bottom_up_const_forward_iterator(const Cst * cst, const value_type node, bool valid = true)
217 : m_valid(valid)
218 {
219 m_cst = cst;
220 m_v = node;
221 if (m_cst == nullptr) m_valid = false;
222 }
223
225 const_reference operator*() const { return m_v; }
226
229 {
230 if (!m_valid) return *this;
231 if (m_v == m_cst->root())
232 {
233 m_valid = false;
234 return *this;
235 }
236 value_type w = m_cst->sibling(m_v);
237 if (w == m_cst->root())
238 { // if no next right sibling exist
239 m_v = m_cst->parent(m_v); // go to parent
240 }
241 else
242 { // if next right sibling exist
243 m_v = m_cst->leftmost_leaf(w); // go to leaftmost leaf in the subtree of w
244 }
245 return *this;
246 }
247
250 {
251 iterator it = *this;
252 ++(*this);
253 return it;
254 }
255
257 bool operator==(const iterator & it) const
258 {
259 return (it.m_valid == m_valid) // valid status is equal => for end() iterator
260 and (it.m_v == m_v) // nodes are equal
261 and (it.m_cst == m_cst); // iterator belongs to the same cst
262 }
263
265 bool operator!=(const iterator & it) const { return !(*this == it); }
266};
267
269
274template <class Cst, class Queue = std::queue<typename Cst::node_type>>
276{
277 public:
278 using iterator_category = std::forward_iterator_tag;
279 using value_type = typename Cst::node_type;
280 using difference_type = std::ptrdiff_t;
283
285 typedef typename Cst::size_type size_type;
287 typedef Queue queue_type;
288
289 private:
290 const Cst * m_cst; // Pointer to the cst.
291 queue_type m_queue; //
292 bool m_valid; // State of the iterator.
293
294 public:
296
302 cst_bfs_iterator(const Cst * cst, const value_type node, bool valid = true, bool end_it = false)
303 {
304 m_cst = cst;
305 m_valid = valid;
306 if (m_cst != nullptr and !end_it) { m_queue.push(node); }
307 }
308
310 size_type size() const { return m_queue.size(); }
311
313 const_reference operator*() const { return m_queue.front(); }
314
317 {
318 if (!m_valid) return *this;
319 if (m_queue.empty())
320 {
321 m_valid = false;
322 return *this;
323 }
324 value_type v = m_queue.front();
325 m_queue.pop();
326 value_type child = m_cst->select_child(v, 1);
327 while (m_cst->root() != child)
328 {
329 m_queue.push(child);
330 child = m_cst->sibling(child);
331 }
332 return *this;
333 }
334
337 {
338 iterator it = *this;
339 ++(*this);
340 return it;
341 }
342
344 bool operator==(const iterator & it) const
345 {
346 if (m_queue.size() != it.m_queue.size())
347 { // if the queue size is different
348 return false; // the state of the to iterator are different
349 }
350 if (m_queue.empty())
351 { // if the queue is empty, we have to check if they are valid and
352 return it.m_valid == m_valid and it.m_cst == m_cst; // belong to the same cst
353 }
354 return (it.m_valid == m_valid) // valid status is equal => for end() iterator
355 and (it.m_cst == m_cst) // iterator belongs to the same cst
356 and (it.m_queue.front() == m_queue.front()) // front element and
357 and (it.m_queue.back() == m_queue.back()); // back element are the same.
358 }
359
361 bool operator!=(const iterator & it) const { return !(*this == it); }
362};
363
364} // end namespace sdsl
365
366#endif
A forward iterator for a breath first traversal of a tree.
std::forward_iterator_tag iterator_category
typename Cst::node_type value_type
const value_type const_reference
iterator operator++(int)
Postfix increment of the iterator.
cst_bfs_iterator(const Cst *cst, const value_type node, bool valid=true, bool end_it=false)
Constructor.
bool operator==(const iterator &it) const
Equality operator.
iterator & operator++()
Prefix increment of the iterator.
const_reference operator*() const
Method for dereferencing the iterator.
cst_bfs_iterator< Cst, Queue > iterator
bool operator!=(const iterator &it) const
Inequality operator.
size_type size() const
Returns the current number of nodes in the queue.
std::ptrdiff_t difference_type
Cst::size_type size_type
A forward iterator for a bottom up traversal of a suffix tree.
cst_bottom_up_const_forward_iterator(const Cst *cst, const value_type node, bool valid=true)
Constructor.
iterator operator++(int)
Postfix increment of the iterator.
iterator & operator++()
Prefix increment of the iterator.
bool operator!=(const iterator &it) const
Inequality operator.
bool operator==(const iterator &it) const
Equality operator.
cst_bottom_up_const_forward_iterator()
Default constructor.
cst_bottom_up_const_forward_iterator< Cst > iterator
const_reference operator*() const
Method for dereferencing the iterator.
std::forward_iterator_tag iterator_category
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
void operator++(int)
Postfix increment of the iterator.
iterator & operator++()
Prefix increment of the iterator.
cst_dfs_const_forward_iterator< Cst > iterator
cst_dfs_const_forward_iterator(const Cst *cst, const value_type node, bool visited=false, bool valid=true)
Constructor.
~cst_dfs_const_forward_iterator()
Copy Constructor.
bool operator==(const iterator &it) const
Equality operator.
bool operator!=(const iterator &it) const
Inequality operator.
typename Cst::node_type value_type
const_reference operator*() const
Method for dereferencing the iterator.
Namespace for the succinct data structure library.