You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 
 

206 lines
6.9 KiB

/**
* Copyright (c) 2018 Niklas Rosenstein
* MIT licensed.
*
* @description This header provides base class for implementing stateful
* iterators that are simple to implement. We call these iterators
* "new-style".
*/
#pragma once
#include <cassert>
#include <iterator>
#include <memory>
#include "macros.h"
/**
* @macro NR_ITERATOR_NOTYPETRAITS
*
* If this macro is defined, #<type_traits> will not but used. This requires
* the implementor of the #niklasrosenstein::iterator interface to manually
* specify the datatype that the `operator * ()` (dereference operator) will
* return as `yield_type`.
*/
#ifndef NR_ITERATOR_NOTYPETRAITS
#include <type_traits>
#endif
namespace niklasrosenstein {
namespace detail {
namespace iterator {
template <typename T, typename = int>
struct yield_type {
#ifdef NR_ITERATOR_NOTYPETRAITS
static_assert(false, "no type traits available, specify T::yield_type");
#else
using type = typename std::result_of<decltype(&T::next)(T)>::type;
#endif
};
template <typename T>
struct yield_type <T, decltype(T::yield_type)> {
using type = typename T::yield_type;
};
template <typename T>
using yield_type_t = typename yield_type<T>::type;
template <typename Y, bool is_reference, bool move_value>
struct _holder_type { };
template <typename Y>
struct _holder_type<Y, false, false> {
// This struct holds a reference type and the internal value will not
// be moved when dereferenced.
Y value;
_holder_type() : value() {}
_holder_type(Y&& value_) : value(std::forward<Y>(value_)) { }
void emplace(Y&& value_) { value = std::forward<Y>(value_); }
Y get() { return value; }
};
template <typename Y>
struct _holder_type<Y, false, true> : _holder_type<Y, false, false> {
// This struct holds a reference type and the internal value WILL be
// moved when dereferenced.
using _holder_type<Y, false, false>::_holder_type;
// TODO: In debug mode, track if the value was already moved.
Y get() { return std::move(_holder_type<Y, false, false>::value); }
};
template <typename Y, bool move_value>
struct _holder_type<Y, true, move_value> {
static_assert(std::is_reference<Y>::value, "not a reference type");
std::add_pointer_t<std::remove_reference_t<Y>> value;
_holder_type() : value(nullptr) { }
_holder_type(Y value_) : value(value_) { }
void emplace(Y value_) { value = &value_; }
Y get() { assert(value != nullptr && "reference holder type holds a nullptr"); return *value; }
};
template <typename T, bool move_value>
using holder_type = _holder_type<T, std::is_reference<T>::value, move_value>;
} // namespace iterator
} // namespace detail
/**
* This class is an adapter of the C++ iterator interface for new style
* iterator classes. Note that if the *move_value* argument is #true,
* the iterator adapter must not be dereferenced more than once (unless
* #yield_type is a reference type, in which case the *move_value*
* argument doesn't matter).
*/
template <typename T, bool move_value=true>
class iterator_adapter {
public:
using yield_type = typename detail::iterator::yield_type_t<T>;
static_assert(!std::is_same<yield_type, void>::value, "T::next() can not return void");
using holder_type = detail::iterator::holder_type<yield_type, move_value>;
/**
* Passing nullptr to this constructor represents creates a sentinel
* iterator that marks the end of the iteration.
*
* You can only create a C++ iterator adapter when the iterator object
* is new, ie. it is currently situated at the beginning at NOT the
* first element. This constructor will call #has_next() and #next().
*/
inline iterator_adapter(T* itimpl) : _itimpl(nullptr) {
if (itimpl && itimpl->has_next()) {
_itimpl = itimpl;
_holder = std::make_shared<holder_type>();
_holder->emplace(itimpl->next());
}
}
/**
* Calls `next()` and `has_next()` on the iterator implementation to advance
* to the next item and check if the end of the iteration has been reached.
*/
inline iterator_adapter& operator ++ () {
assert(_itimpl != nullptr);
if (_itimpl->has_next()) {
_holder->emplace(_itimpl->next());
}
else {
_itimpl = nullptr;
_holder = nullptr;
}
return *this;
}
inline bool operator != (iterator_adapter const& other) const {
return _itimpl != other._itimpl;
}
inline yield_type operator * () {
assert(_itimpl != nullptr);
return _holder->get();
}
private:
T* _itimpl;
std::shared_ptr<holder_type> _holder;
};
/**
* This is the base class for new-style iterators. A subclass must specify
* itself as the template parameter #T and implement the following functions:
*
* + yield_type next()
* + bool has_next() [const]
*
* Instances of this class are intended to be used either directly by this
* interface or by using a range-based for loop. In case of the range-based
* for loop, the object returns an #iterator_adapter<> which is not supposed
* to be accessed more than it would be by the expansion of the for loop as
* specified in the C++ standard.
*/
template <class T, bool move_value=true>
class iterator {
public:
/**
* Returns the #iterator_adapter for this iterator implementation. It does
* not really mark the begin of the iteration, rather the current state of
* the iterator.
*/
inline iterator_adapter<T, move_value> begin() { return iterator_adapter<T, move_value>(static_cast<T*>(this)); }
/**
* Returns the sentinel #iterator_adapter that marks the end of the
* iteration.
*/
inline iterator_adapter<T, move_value> end() const { return iterator_adapter<T, move_value>(nullptr); }
};
/**
* A wrapper for iterators that can be used to make your iterator compatible
* if the input iterator is not movable. This class simply wraps the non-movable
* iterator and is itself movable.
*
* template <typename Iterable>
* auto enumerate(Iterable& iter) -> _enumerator<movable_iterator_wrapper<Iterable>> {
* return {movable_iterator_wrapper<Iterable>(iter)};
* }
*/
template <typename Iterable>
class movable_iterator_wrapper {
Iterable& _iter;
public:
inline movable_iterator_wrapper(Iterable& iter) : _iter(iter) {}
inline movable_iterator_wrapper(movable_iterator_wrapper&& other)
: _iter(other._iter) {}
inline auto begin() -> decltype(std::begin(_iter)) { return std::begin(_iter); }
inline auto end() -> decltype(std::end(_iter)) { return std::end(_iter); }
inline auto begin() const -> decltype(std::begin(_iter)) { return std::begin(_iter); }
inline auto end() const -> decltype(std::end(_iter)) { return std::end(_iter); }
};
} // namespace niklasrosenstein