A library for working with phylogenetic and population genetic data.
v0.32.0
containers/interval_tree/iterator.hpp
Go to the documentation of this file.
1 #ifndef GENESIS_UTILS_CONTAINERS_INTERVAL_TREE_ITERATOR_H_
2 #define GENESIS_UTILS_CONTAINERS_INTERVAL_TREE_ITERATOR_H_
3 
4 /*
5  Genesis - A toolkit for working with phylogenetic data.
6  Copyright (C) 2014-2022 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 <lczech@carnegiescience.edu>
23  Department of Plant Biology, Carnegie Institution For Science
24  260 Panama Street, Stanford, CA 94305, USA
25 */
26 
27 /*
28  The code below is adapted from https://github.com/5cript/interval-tree
29  which was published under the CC0-1.0 License (Creative Commons Zero v1.0 Universal).
30  We modified the code to fit our needs and formatting, but the functionality is the same.
31  */
32 
40 #include <cassert>
41 #include <cstdio>
42 #include <iostream>
43 #include <iterator>
44 #include <memory>
45 #include <stdexcept>
46 #include <string>
47 #include <type_traits>
48 
53 
54 namespace genesis {
55 namespace utils {
56 
57 // =================================================================================================
58 // Interval Iterator
59 // =================================================================================================
60 
70 template< typename NodeType, bool is_const = true >
71 class IntervalTreeIterator
72  : public std::forward_iterator_tag
73 {
74 public:
75 
76  // -------------------------------------------------------------------------
77  // Typedefs
78  // -------------------------------------------------------------------------
79 
80  using data_type = typename NodeType::data_type;
81  using numerical_type = typename NodeType::numerical_type;
82  using interval_kind = typename NodeType::interval_kind;
83  using interval_type = typename NodeType::interval_type;
84 
85  using node_type = NodeType;
87 
89  using value_type = NodeType;
90 
91  using node_ptr_t = typename std::conditional< is_const, node_type const*, node_type* >::type;
92  using owner_type = typename std::conditional< is_const, tree_type const*, tree_type* >::type;
93 
95 
96  // -------------------------------------------------------------------------
97  // Constructors and Rule of Five
98  // -------------------------------------------------------------------------
99 
100 private:
101 
103  : node_{node}
104  , owner_{owner}
105  {}
106 
107 public:
108 
109  ~IntervalTreeIterator() = default;
110 
111  IntervalTreeIterator( IntervalTreeIterator const& ) = default;
112  IntervalTreeIterator( IntervalTreeIterator&& ) = default;
113 
114  IntervalTreeIterator& operator= ( IntervalTreeIterator const& ) = default;
115  IntervalTreeIterator& operator= ( IntervalTreeIterator&& ) = default;
116 
117  // -------------------------------------------------------------------------
118  // Operators
119  // -------------------------------------------------------------------------
120 
121 public:
122 
123  bool operator!=(IntervalTreeIterator const& other) const
124  {
125  return node_ != other.node_;
126  }
127 
128  bool operator==(IntervalTreeIterator const& other) const
129  {
130  return node_ == other.node_;
131  }
132 
134  {
135  if( !node_ ) {
136  node_ = owner_->root_;
137  if( !node_ ) {
138  return *this;
139  }
140  while( node_->left_ ){
141  node_ = node_->left_;
142  }
143  }
144 
145  if( node_->right_ ) {
146  node_ = node_->right_;
147  while( node_->left_ ){
148  node_ = node_->left_;
149  }
150  } else {
151  auto* parent = node_->parent_;
152  while( parent != nullptr && node_ == parent->right_ ) {
153  node_ = parent;
154  parent = parent->parent_;
155  }
156  node_ = parent;
157  }
158 
159  return *this;
160  }
161 
163  {
164  auto cpy = *this;
165  operator++();
166  return cpy;
167  }
168 
169  interval_type const& operator*() const
170  {
171  if( node_ ) {
172  return node_->interval();
173  } else {
174  throw std::out_of_range("Dereferencing IntervalTreeIterator out of bounds.");
175  }
176  }
177 
178  value_type const* operator->() const
179  {
180  return node_;
181  }
182 
183  // -------------------------------------------------------------------------
184  // Member Functions
185  // -------------------------------------------------------------------------
186 
193  {
194  if (node_)
195  return {node_->parent_, owner_};
196  else
197  throw std::out_of_range("interval_tree_iterator out of bounds");
198  }
199 
205  self_type left() const
206  {
207  if (node_)
208  return {node_->left_, owner_};
209  else
210  throw std::out_of_range("interval_tree_iterator out of bounds");
211  }
212 
218  self_type right() const
219  {
220  if (node_)
221  return {node_->right_, owner_};
222  else
223  throw std::out_of_range("interval_tree_iterator out of bounds");
224  }
225 
230  {
231  return node_->max();
232  }
233 
238  {
239  return node_->color();
240  }
241 
242  interval_type const& interval() const
243  {
244  return node_->interval();
245  }
246 
247  // -------------------------------------------------------------------------
248  // Member Variables
249  // -------------------------------------------------------------------------
250 
251 private:
252 
253  node_ptr_t node_;
254  owner_type owner_;
255 
256 };
257 
258 } // namespace utils
259 } // namespace genesis
260 
261 #endif // include guard
genesis::utils::IntervalTreeIterator::value_type
NodeType value_type
Definition: containers/interval_tree/iterator.hpp:89
genesis::utils::IntervalTreeIterator::interval_type
typename NodeType::interval_type interval_type
Definition: containers/interval_tree/iterator.hpp:83
genesis::utils::IntervalTreeIterator::operator->
value_type const * operator->() const
Definition: containers/interval_tree/iterator.hpp:178
genesis::utils::IntervalTreeIterator::max
numerical_type max() const
Return the max property of the node.
Definition: containers/interval_tree/iterator.hpp:229
functions.hpp
genesis::utils::IntervalTreeIterator::node_type
NodeType node_type
Definition: containers/interval_tree/iterator.hpp:85
fwd.hpp
genesis::utils::IntervalTreeIterator::parent
self_type parent() const
Return an iterator to the parent of this node.
Definition: containers/interval_tree/iterator.hpp:192
genesis::utils::IntervalTreeIterator::interval_kind
typename NodeType::interval_kind interval_kind
Definition: containers/interval_tree/iterator.hpp:82
genesis::utils::IntervalTreeIterator::~IntervalTreeIterator
~IntervalTreeIterator()=default
genesis::utils::IntervalTreeIterator
Iterate the Intervals stored in an IntervalTree.
Definition: fwd.hpp:51
node.hpp
genesis::utils::IntervalTreeIterator::owner_type
typename std::conditional< is_const, tree_type const *, tree_type * >::type owner_type
Definition: containers/interval_tree/iterator.hpp:92
genesis
Container namespace for all symbols of genesis in order to keep them separate when used as a library.
Definition: placement/formats/edge_color.cpp:42
genesis::utils::IntervalTreeIterator::data_type
typename NodeType::data_type data_type
Definition: containers/interval_tree/iterator.hpp:80
genesis::utils::RedBackColor
RedBackColor
Definition for Red-Black Tree coloring.
Definition: utils/containers/interval_tree/node.hpp:65
genesis::utils::IntervalTreeIterator::operator++
self_type operator++(int)
Definition: containers/interval_tree/iterator.hpp:162
genesis::utils::IntervalTreeIterator::operator!=
bool operator!=(IntervalTreeIterator const &other) const
Definition: containers/interval_tree/iterator.hpp:123
genesis::utils::IntervalTreeIterator::numerical_type
typename NodeType::numerical_type numerical_type
Definition: containers/interval_tree/iterator.hpp:81
interval.hpp
genesis::utils::IntervalTreeIterator::interval
interval_type const & interval() const
Definition: containers/interval_tree/iterator.hpp:242
genesis::utils::IntervalTreeIterator::right
self_type right() const
Continue down the right side of this node.
Definition: containers/interval_tree/iterator.hpp:218
genesis::utils::IntervalTreeIterator::operator==
bool operator==(IntervalTreeIterator const &other) const
Definition: containers/interval_tree/iterator.hpp:128
genesis::utils::IntervalTreeIterator::operator=
IntervalTreeIterator & operator=(IntervalTreeIterator const &)=default
genesis::utils::IntervalTreeIterator::left
self_type left() const
Continue down the left side of this node.
Definition: containers/interval_tree/iterator.hpp:205
genesis::utils::IntervalTree
Interval tree that enables storing and querying intervals, each containing some data.
Definition: fwd.hpp:45
genesis::utils::IntervalTreeIterator::operator*
interval_type const & operator*() const
Definition: containers/interval_tree/iterator.hpp:169
genesis::utils::IntervalTreeIterator::color
RedBackColor color() const
Return the color of the node.
Definition: containers/interval_tree/iterator.hpp:237
genesis::utils::IntervalTreeIterator::operator++
self_type & operator++()
Definition: containers/interval_tree/iterator.hpp:133
genesis::utils::IntervalTreeIterator::node_ptr_t
typename std::conditional< is_const, node_type const *, node_type * >::type node_ptr_t
Definition: containers/interval_tree/iterator.hpp:91