A toolkit for working with phylogenetic data.
v0.20.0
All
Classes
Namespaces
Files
Functions
Variables
Typedefs
Enumerations
Enumerator
Friends
Macros
Pages
inorder.hpp
Go to the documentation of this file.
1
#ifndef GENESIS_TREE_ITERATOR_INORDER_H_
2
#define GENESIS_TREE_ITERATOR_INORDER_H_
3
4
/*
5
Genesis - A toolkit for working with phylogenetic data.
6
Copyright (C) 2014-2017 Lucas Czech
7
8
This program is free software: you can redistribute it and/or modify
9
it under the terms of the GNU General Public License as published by
10
the Free Software Foundation, either version 3 of the License, or
11
(at your option) any later version.
12
13
This program is distributed in the hope that it will be useful,
14
but WITHOUT ANY WARRANTY; without even the implied warranty of
15
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16
GNU General Public License for more details.
17
18
You should have received a copy of the GNU General Public License
19
along with this program. If not, see <http://www.gnu.org/licenses/>.
20
21
Contact:
22
Lucas Czech <lucas.czech@h-its.org>
23
Exelixis Lab, Heidelberg Institute for Theoretical Studies
24
Schloss-Wolfsbrunnenweg 35, D-69118 Heidelberg, Germany
25
*/
26
34
#include <assert.h>
35
#include <deque>
36
#include <iterator>
37
38
namespace
genesis {
39
namespace
tree {
40
41
// =================================================================================================
42
// Inorder Iterator
43
// =================================================================================================
44
45
/* *
46
* @brief Iterates over a Tree in inorder manner.
47
*
48
* This iterator usually is used on binary trees and started at the root. As we are dealing with
49
* (possibly) multifurcating (non-binary) trees, and also might start this iterator on some inner
50
* node, it behaves a bit different from its standard mode of operation:
51
*
52
* * In multifurcating trees, inner nodes will be visited more than once, namely their number of
53
* neighbors - 2 many times. This is simply a consequence of the multifurcation. In a binary
54
* tree, each node has three neighbors, so is visited 3-2=1 many times, as usual, with notable
55
* exceptions:
56
* * In an unrooted binary tree, the "virtual root" (meaning, the node that is used as a starting
57
* point into the tree) usually has three children, as it actually is a normal inner node that
58
* just happened to be the first one in memory. Thus, when starting this iterator at this kind
59
* of root, the root node will be visited twice during the traversal. Again, this is a
60
* consequence of the mechanism of inorder traversal.
61
* * The same is true when the iterator is started on some other inner node (as they are
62
* topologically the same as the "unrooted" root node).
63
* * A special side-effect of this implementation: If the iterator is started on a leaf (unusual,
64
* but can be done), this node is visited as the very first one.
65
* %
66
* /
67
template <typename LinkPointerType, typename NodePointerType, typename EdgePointerType>
68
class IteratorInorder
69
{
70
71
public:
72
73
// -----------------------------------------------------
74
// Typedefs
75
// -----------------------------------------------------
76
77
typedef IteratorInorder<LinkPointerType, NodePointerType, EdgePointerType> self_type;
78
typedef std::forward_iterator_tag iterator_category;
79
80
// -----------------------------------------------------
81
// Constructors and Rule of Five
82
// -----------------------------------------------------
83
84
IteratorInorder (LinkPointerType link) : start_(link)
85
{
86
// the end iterator is created by handing over a nullptr to this constructor, so we first
87
// need to check for this:
88
if (link) {
89
link_ = link;
90
91
// if we start the iterator on an inner node, we actually need to add ALL children
92
// (which means all its neighbor nodes) of this node to the stack, not only the ones
93
// that point away from the given link of the node (which is what push_front_children
94
// does). this means, we also need to add the one link that is given as argument here.
95
if (link->outer() != link) {
96
// this loop just takes care to add the given node first, and then the other
97
// children. this is more or less beaty only, as it just makes sure that this link's
98
// path is taken first, instead of last.
99
while (link->next() != link_) {
100
link = link->next();
101
}
102
103
// now add the needed extra child
104
stack_.push_front(link->outer());
105
}
106
107
// in any case (no matter whether we start at the root or some other node), we run this
108
// loop. it goes down the tree until a leaf is encountered. this leaf will be the first
109
// node that the iterator points to. while going there, we add yet-to-be-visited nodes
110
// to the stack.
111
while (link->is_inner()) {
112
push_front_children(link);
113
link = link->next()->outer();
114
}
115
}
116
link_ = link;
117
}
118
119
~IteratorInorder() = default;
120
121
IteratorInorder( IteratorInorder const& ) = default;
122
IteratorInorder( IteratorInorder&& ) = default;
123
124
IteratorInorder& operator= ( IteratorInorder const& ) = default;
125
IteratorInorder& operator= ( IteratorInorder&& ) = default;
126
127
// -----------------------------------------------------
128
// Operators
129
// -----------------------------------------------------
130
131
// TODO Tree iterator inorder is NOT WORKING!!!
132
133
self_type operator ++ ()
134
{
135
std::string m = " ";
136
if (link_) {
137
m += "@" + link_->node()->name + " ";
138
}
139
for (LinkPointerType p : stack_) {
140
m += p->node()->name + " ";
141
}
142
LOG_DBG2 << m;
143
144
if (link_ == stack_.front()) {
145
while (!stack_.empty() && link_ == stack_.front()) {
146
link_ = link_->outer()->next();
147
stack_.pop_front();
148
}
149
while (link_->outer() == link_) {
150
link_ = link_->next();
151
}
152
if (stack_.empty()) {
153
link_ = nullptr;
154
}
155
} else {
156
assert(link_->outer() == stack_.front());
157
link_ = link_->outer();
158
while (link_->is_inner()) {
159
push_front_children(link_);
160
link_ = link_->next()->outer();
161
}
162
while (link_->outer() == link_) {
163
link_ = link_->next();
164
}
165
}
166
167
m = " ";
168
if (link_) {
169
m += "@" + link_->node()->name + " ";
170
}
171
for (LinkPointerType p : stack_) {
172
m += p->node()->name + " ";
173
}
174
LOG_DBG2 << m;
175
176
return *this;
177
}
178
179
self_type operator ++ (int)
180
{
181
self_type tmp = *this;
182
++(*this);
183
return tmp;
184
}
185
186
bool operator == (const self_type &other) const
187
{
188
return other.link_ == link_;
189
}
190
191
bool operator != (const self_type &other) const
192
{
193
return !(other == *this);
194
}
195
196
// -----------------------------------------------------
197
// Members
198
// -----------------------------------------------------
199
200
LinkPointerType link() const
201
{
202
return link_;
203
}
204
205
NodePointerType node() const
206
{
207
return link_->node();
208
}
209
210
EdgePointerType edge() const
211
{
212
return link_->edge();
213
}
214
215
LinkPointerType start_link() const
216
{
217
return start_;
218
}
219
220
NodePointerType start_node() const
221
{
222
return start_->node();
223
}
224
225
private:
226
227
void push_front_children(LinkPointerType link)
228
{
229
// we need to push to a tmp queue first, in order to get the order right.
230
// otherwise, we would still do a preorder traversal, but starting with
231
// the last child of each node instead of the first one.
232
std::deque<LinkPointerType> tmp;
233
LinkPointerType c = link->next();
234
while (c != link) {
235
tmp.push_front(c->outer());
236
c = c->next();
237
}
238
for (LinkPointerType l : tmp) {
239
stack_.push_front(l);
240
}
241
}
242
243
LinkPointerType link_;
244
LinkPointerType const start_;
245
std::deque<LinkPointerType> stack_;
246
};
247
248
*/
249
250
}
// namespace tree
251
}
// namespace genesis
252
253
#endif // include guard
lib
genesis
tree
iterator
inorder.hpp
Generated on Wed Oct 10 2018 23:08:40 for genesis by
1.8.6