A toolkit for working with phylogenetic data.
v0.18.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