A library for working with phylogenetic data.
v0.25.0
transform_iterator.hpp
Go to the documentation of this file.
1 #ifndef GENESIS_UTILS_CONTAINERS_TRANSFORM_ITERATOR_H_
2 #define GENESIS_UTILS_CONTAINERS_TRANSFORM_ITERATOR_H_
3 
4 /*
5  Genesis - A toolkit for working with phylogenetic data.
6  Copyright (C) 2014-2020 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 
35 
36 #include <cstddef>
37 #include <iterator>
38 #include <type_traits>
39 
40 namespace genesis {
41 namespace utils {
42 
43 // =================================================================================================
44 // Transforming Iterator
45 // =================================================================================================
46 
103 template< typename TransformFunctor, typename BaseIterator >
105 {
106 public:
107 
108  // -------------------------------------------------------------------------
109  // Member Types
110  // -------------------------------------------------------------------------
111 
112  // Get the type that the TransformFunctor returns
113  using result_type = typename std::result_of<
114  TransformFunctor( typename std::iterator_traits<BaseIterator>::reference )
115  >::type;
116 
117  // We want to cache the transformed values if the transform functor returns a valy by copy
118  // (that is, for example, the result of some computation that is simply returned by the functor).
119  // However, when the functor returns a reference instead (for example, it just selects a certain
120  // element from an underlying base iterator over vectors of elements), we do not want to cache,
121  // as that would make an unnecessary copy of the element (and would require that the element
122  // type is copyable). So in that case, we deactivate caching. We could use SFINAE and some class
123  // derivation to disable the cache member variable (see https://stackoverflow.com/a/25497790 for
124  // example), but we keep it simple here and instead just use a dummy bool variable in that case.
125  using cache_type = typename std::conditional<
126  std::is_reference<result_type>::value, bool, result_type
127  >::type;
128 
129  // Furthermore, the operator*(), operator->(), and operator[]() need to return the proper type:
130  // If the TransformFunctor returns a reference, we return a reference as well. If not, that is,
131  // if the functor returns a value by copy, we still return a reference here, but this time,
132  // referencing the cache! So, we need to remove the reference type trait first in case that it
133  // is present, and then can have these operators add the correct reference trait again.
134  using return_type = typename std::remove_reference<result_type>::type;
135 
136  // For the standard iterator types, we also want to use the types of the TransformFunctor,
137  // so that whatever that one does is the basis for our types here. We could instead also use the
138  // (commented out) types based on the BaseIterator here as well, which in many cases will be
139  // identical to what the transform functor returns. But by not doing so, and using a return
140  // type based on the transform functor, we allow that the TransformFunctor can perform implicit
141  // type conversions from the BaseIterator type to its input argument!
142  // Bit more flexibility this way, and helpful at times.
146  // using value_type = typename std::iterator_traits<BaseIterator>::value_type;
147  // using pointer = typename std::iterator_traits<BaseIterator>::pointer;
148  // using reference = typename std::iterator_traits<BaseIterator>::reference;
149 
150  // using reference = result_type;
151  // using iterator_category = typename std::random_access_iterator_tag;
152  using iterator_category = typename std::iterator_traits<BaseIterator>::iterator_category;
153  using difference_type = typename std::iterator_traits<BaseIterator>::difference_type;
154 
155  // -------------------------------------------------------------------------
156  // Constructor and Rule of Five
157  // -------------------------------------------------------------------------
158 
167  TransformIterator( TransformFunctor unary_func, BaseIterator iterator )
168  : functor_( unary_func )
169  , current_( iterator )
170  {
171  // We allow also non-random-access-iterators! No need for the following assertion.
172  // static_assert(
173  // (
174  // std::is_same<
175  // typename std::iterator_traits<BaseIterator>::iterator_category,
176  // std::random_access_iterator_tag
177  // >::value
178  // ),
179  // "TransformIterator requires underlying BaseIterator to be a random access iterator"
180  // );
181  }
182 
183  ~TransformIterator() = default;
184 
185  TransformIterator( TransformIterator const& ) = default;
186  TransformIterator( TransformIterator&& ) = default;
187 
188  TransformIterator& operator= ( TransformIterator const& ) = default;
190 
191  // Explicit copy constructor and assignment. Not needed.
192  // TransformIterator( TransformIterator const& input )
193  // : functor_( input.functor_ )
194  // , current_( input.current_ )
195  // {}
196  //
197  // TransformIterator& operator=( TransformIterator const& input )
198  // {
199  // current_ = input.current_;
200  // return *this;
201  // }
202 
203  // -------------------------------------------------------------------------
204  // Basic Iterator Operators
205  // -------------------------------------------------------------------------
206 
208  {
209  return get_value_<result_type>();
210  }
211 
213  {
214  return &get_value_<result_type>();
215  }
216 
218  {
219  return *(*this + i);
220  }
221 
222  BaseIterator base() const
223  {
224  return current_;
225  }
226 
227  // -------------------------------------------------------------------------
228  // Iterator Navigation
229  // -------------------------------------------------------------------------
230 
232  {
233  ++current_;
234  cache_valid_ = false;
235  return *this;
236  }
237 
239  {
240  --current_;
241  cache_valid_ = false;
242  return *this;
243  }
244 
246  {
247  TransformIterator it(*this);
248  ++(*this);
249  return it;
250  }
251 
253  {
254  TransformIterator it(*this);
255  --(*this);
256  return it;
257  }
258 
260  {
261  return { current_ + n, functor_ };
262  }
263 
265  {
266  return { current_ - n, functor_ };
267  }
268 
270  {
271  current_ += n;
272  cache_valid_ = false;
273  return *this;
274  }
275 
277  {
278  current_ -= n;
279  cache_valid_ = false;
280  return *this;
281  }
282 
283  // -------------------------------------------------------------------------
284  // Iterator Interaction
285  // -------------------------------------------------------------------------
286 
288  {
289  return it + n;
290  }
291 
293  {
294  return current_ - it.current_;
295  }
296 
297  // -------------------------------------------------------------------------
298  // Iterator Comparison
299  // -------------------------------------------------------------------------
300 
301  bool operator==( TransformIterator const& it ) const
302  {
303  return current_ == it.current_;
304  }
305 
306  bool operator!=( TransformIterator const& it ) const
307  {
308  return !(*this == it);
309  }
310 
311  bool operator<( TransformIterator const& it ) const
312  {
313  return *this - it < 0;
314  }
315 
316  bool operator>( TransformIterator const& it ) const
317  {
318  return it < *this;
319  }
320 
321  bool operator<=( TransformIterator const& it ) const
322  {
323  return !(*this > it);
324  }
325 
326  bool operator>=( TransformIterator const& it ) const
327  {
328  return !(*this < it);
329  }
330 
331  // -------------------------------------------------------------------------
332  // Internal Functions
333  // -------------------------------------------------------------------------
334 
335 private:
336 
340  template<typename T, typename std::enable_if< std::is_reference<T>::value >::type* = nullptr>
341  return_type& get_value_() const
342  {
343  // Internal check: This function needs type T only for the SFINAE of std::enable_if to work.
344  // But we only want this for the result_type that we are actually using here!
345  static_assert(
346  std::is_same<T, result_type>::value, "Function has to be called using T=result_type"
347  );
348 
349  // More internal checks, just to make sure that the SFINAE works correctly.
350  static_assert(
351  std::is_reference<result_type>::value,
352  "Function SFINAE is activated although result_type is not a reference type"
353  );
354  static_assert(
355  std::is_same<cache_type, bool>::value,
356  "cache_type is not bool although result_type is a reference type"
357  );
358 
359  // Return the result immediately. This returns by reference, so that no copy is made.
360  return functor_( *current_ );
361  }
362 
366  template<typename T, typename std::enable_if< !std::is_reference<T>::value >::type* = nullptr>
367  return_type& get_value_() const
368  {
369  // Internal check: This function needs type T only for the SFINAE of std::enable_if to work.
370  // But we only want this for the result_type that we are actually using here!
371  static_assert(
372  std::is_same<T, result_type>::value, "Function has to be called using T=result_type"
373  );
374 
375  // Another internal check, just to make sure that the SFINAE works correctly.
376  static_assert(
377  ! std::is_reference<result_type>::value,
378  "Function SFINAE is activated although result_type is a reference type"
379  );
380  static_assert(
381  std::is_same<cache_type, result_type>::value,
382  "cache_type is not the same as result_type although result_type is a not reference type"
383  );
384 
385  // Fill the cache as needed, and return a reference to the cached object.
386  if( ! cache_valid_ ) {
387  cache_ = functor_( *current_ );
388  cache_valid_ = true;
389  }
390  return cache_;
391  }
392 
393  // -------------------------------------------------------------------------
394  // Internal Members
395  // -------------------------------------------------------------------------
396 
397 private:
398 
399  TransformFunctor functor_;
400  BaseIterator current_;
401 
402  // Store the cached value, if needed. In cases where the TransformFunctor returns by reference,
403  // we do not want to use a cache, to avoid unnecessary copies. In that case, cache_type is
404  // simply set to bool as a dummy type, and never used.
405  // Furthermore, the cache_valid_ check is used by some of the iteration functions even if
406  // we do not have a valid cache (that is, for references). That is okay, as this is simply
407  // an overhead of setting one bool value that is not used. We can live with that.
408  mutable cache_type cache_;
409  mutable bool cache_valid_ = false;
410 
411 };
412 
413 // =================================================================================================
414 // Make Transforming Iterator
415 // =================================================================================================
416 
425 template<typename TransformFunctor, typename BaseIterator>
427  TransformFunctor unary_func,
428  BaseIterator iterator
429 ) {
430  return TransformIterator<TransformFunctor, BaseIterator>( unary_func, iterator );
431 }
432 
437 template<typename TransformFunctor, typename BaseIterator>
439  TransformFunctor unary_func,
440  BaseIterator begin,
441  BaseIterator end
442 ) {
446  );
447 }
448 
453 template<typename TransformFunctor, typename Container>
455  TransformFunctor unary_func,
456  Container& container
457 ) {
460  unary_func, container.begin()
461  ),
463  unary_func, container.end()
464  )
465  );
466 }
467 
472 template<typename TransformFunctor, typename Container>
474  TransformFunctor unary_func,
475  Container const& container
476 ) {
479  unary_func, container.begin()
480  ),
482  unary_func, container.end()
483  )
484  );
485 }
486 
487 } // namespace utils
488 } // namespace genesis
489 
490 #endif // include guard
genesis::utils::TransformIterator::operator*
return_type & operator*() const
Definition: transform_iterator.hpp:207
genesis::utils::TransformIterator::operator-
difference_type operator-(TransformIterator const &it) const
Definition: transform_iterator.hpp:292
genesis::utils::TransformIterator::operator=
TransformIterator & operator=(TransformIterator const &)=default
genesis::utils::TransformIterator::operator==
bool operator==(TransformIterator const &it) const
Definition: transform_iterator.hpp:301
genesis::utils::TransformIterator::operator->
return_type * operator->() const
Definition: transform_iterator.hpp:212
genesis::utils::TransformIterator::operator!=
bool operator!=(TransformIterator const &it) const
Definition: transform_iterator.hpp:306
genesis::utils::TransformIterator::operator-
TransformIterator operator-(difference_type n) const
Definition: transform_iterator.hpp:264
genesis::utils::TransformIterator::operator>
bool operator>(TransformIterator const &it) const
Definition: transform_iterator.hpp:316
genesis::utils::TransformIterator::TransformIterator
TransformIterator(TransformFunctor unary_func, BaseIterator iterator)
Construct a transforming iterator, given the underlying base iterator and the transformation function...
Definition: transform_iterator.hpp:167
genesis::utils::TransformIterator::operator--
TransformIterator operator--(int)
Definition: transform_iterator.hpp:252
genesis::utils::TransformIterator::result_type
typename std::result_of< TransformFunctor(typename std::iterator_traits< BaseIterator >::reference) >::type result_type
Definition: transform_iterator.hpp:115
genesis::utils::TransformIterator::operator>=
bool operator>=(TransformIterator const &it) const
Definition: transform_iterator.hpp:326
genesis::utils::TransformIterator::value_type
return_type value_type
Definition: transform_iterator.hpp:143
genesis::utils::TransformIterator::operator<
bool operator<(TransformIterator const &it) const
Definition: transform_iterator.hpp:311
genesis::utils::TransformIterator::operator++
TransformIterator & operator++()
Definition: transform_iterator.hpp:231
genesis::utils::TransformIterator::return_type
typename std::remove_reference< result_type >::type return_type
Definition: transform_iterator.hpp:134
genesis::utils::TransformIterator::difference_type
typename std::iterator_traits< BaseIterator >::difference_type difference_type
Definition: transform_iterator.hpp:153
range.hpp
genesis::utils::make_transform_iterator
TransformIterator< TransformFunctor, BaseIterator > make_transform_iterator(TransformFunctor unary_func, BaseIterator iterator)
Construct a transforming iterator, given the underlying base iterator and the transformation function...
Definition: transform_iterator.hpp:426
genesis::utils::TransformIterator::operator+=
TransformIterator & operator+=(difference_type n)
Definition: transform_iterator.hpp:269
genesis::utils::Range
Simple wrapper for typical begin() and end() iterators, to be used in range-based for loops.
Definition: range.hpp:46
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::TransformIterator::base
BaseIterator base() const
Definition: transform_iterator.hpp:222
genesis::utils::TransformIterator::reference
return_type & reference
Definition: transform_iterator.hpp:145
genesis::utils::TransformIterator::operator<=
bool operator<=(TransformIterator const &it) const
Definition: transform_iterator.hpp:321
genesis::utils::TransformIterator::operator+
friend TransformIterator operator+(difference_type n, TransformIterator const &it)
Definition: transform_iterator.hpp:287
genesis::utils::TransformIterator
Iterator class that allows to transform an underlying iterator by applying a function to each element...
Definition: transform_iterator.hpp:104
genesis::utils::TransformIterator::~TransformIterator
~TransformIterator()=default
genesis::utils::TransformIterator::operator--
TransformIterator & operator--()
Definition: transform_iterator.hpp:238
genesis::utils::TransformIterator::operator[]
return_type & operator[](difference_type i) const
Definition: transform_iterator.hpp:217
genesis::utils::make_transform_range
Range< TransformIterator< TransformFunctor, BaseIterator > > make_transform_range(TransformFunctor unary_func, BaseIterator begin, BaseIterator end)
Construct a transforming range, given the transformation function as well as the underlying base iter...
Definition: transform_iterator.hpp:438
genesis::utils::TransformIterator::operator+
TransformIterator operator+(difference_type n) const
Definition: transform_iterator.hpp:259
genesis::utils::TransformIterator::pointer
return_type * pointer
Definition: transform_iterator.hpp:144
genesis::utils::TransformIterator::operator-=
TransformIterator & operator-=(difference_type n)
Definition: transform_iterator.hpp:276
genesis::utils::TransformIterator::operator++
TransformIterator operator++(int)
Definition: transform_iterator.hpp:245
genesis::utils::TransformIterator::cache_type
typename std::conditional< std::is_reference< result_type >::value, bool, result_type >::type cache_type
Definition: transform_iterator.hpp:127
genesis::utils::TransformIterator::iterator_category
typename std::iterator_traits< BaseIterator >::iterator_category iterator_category
Definition: transform_iterator.hpp:152