Iterator.hpp

Go to the documentation of this file.

//
//  CeresEngine - A game development framework
//
//  Created by Rogiel Sulzbach.
//  Copyright (c) 2018-2022 Rogiel Sulzbach. All rights reserved.
//
 
#pragma once
 
#include "CeresEngine/DataTypes.hpp"
#include "CeresEngine/Macros.hpp"
 
#include "CeresEngine/Foundation/Container/Pair.hpp"
 
#include <algorithm>
#include <exception>
#include <functional>
#include <iterator>
#include <tuple>
#include <type_traits>
#include <utility>
 
namespace CeresEngine {
 
    struct IterationEnd {
        const IterationEnd& operator*() const { return *this; }
    };
 
    namespace impl {
        namespace compare {
            struct ByValue {
                template<class T> CE_FORCE_INLINE bool operator()(const T& a, const T& b) const { return a == b; }
            };
 
            struct ByValueGTE {
                template<class T> CE_FORCE_INLINE bool operator()(const T& a, const T& b) const { return a >= b; }
            };
 
            struct ByAddress {
                template<class T> CE_FORCE_INLINE bool operator()(const T& a, const T& b) const { return &a == &b; }
            };
 
            struct ByLastTupleElementMatch {
                template<typename... ArgsA, typename... ArgsB> bool operator()(const std::tuple<ArgsA...>& a, const std::tuple<ArgsB...>& b) const {
                    static_assert(sizeof...(ArgsA) == sizeof...(ArgsB), "comparing invalid tuples");
                    return std::get<sizeof...(ArgsA) - 1>(a) == std::get<sizeof...(ArgsB) - 1>(b);
                }
            };
 
            struct Never {
                template<class A, class B> bool operator()(const A&, const B&) const { return false; }
            };
        } // namespace compare
 
        namespace increment {
            template<int A> struct ByValue {
                template<class T> CE_FORCE_INLINE void operator()(T& v) const { v = v + A; }
            };
 
            struct ByPrefixIncrement {
                template<class T> CE_FORCE_INLINE void operator()(T& v) const { ++v; }
            };
 
            struct ByPostfixIncrement {
                template<class T> CE_FORCE_INLINE void operator()(T& v) const { v++; }
            };
 
            template<typename Callback> struct ByCallback {
                mutable Callback callback;
                explicit ByCallback(Callback callback) : callback(std::move(callback)) {}
                template<typename T> void operator()(T& v) const { callback(v); }
            };
 
            struct ByTupleIncrement {
                template<typename... Args> void dummy(Args&&...) {}
                template<class T, size_t... Idx> void updateValues(T& v, std::index_sequence<Idx...>) { dummy(++std::get<Idx>(v)...); }
                template<typename... Args> void operator()(std::tuple<Args...>& v) { updateValues(v, std::make_index_sequence<sizeof...(Args)>()); }
            };
 
            template<typename T, typename M, M Method> struct ByMemberCall {
                using R = decltype((std::declval<T&>().*Method)());
                R operator()(T& v) const { return (v.*Method)(); }
            };
 
        } // namespace increment
 
        namespace dereference {
            struct ByValue {
                template<class T> CE_FORCE_INLINE T operator()(T& v) const { return v; }
            };
 
            struct ByConstValueReference {
                template<class T> CE_FORCE_INLINE const T& operator()(T& v) const { return v; }
            };
 
            struct ByValueReference {
                template<class T> CE_FORCE_INLINE T& operator()(T& v) const { return v; }
            };
 
            struct ByValueDereference {
                template<class T> CE_FORCE_INLINE decltype(auto) operator()(T& v) const { return *v; }
            };
 
            struct ByPointerReference {
                template<class T> CE_FORCE_INLINE auto& operator()(T& v) const {
                    CE_ASSERT(*v != nullptr);
                    return **v;
                }
            };
 
            template<typename Callback> struct ByCallback {
                mutable Callback callback;
                explicit ByCallback(Callback callback) : callback(std::move(callback)) {}
                template<typename T> decltype(auto) operator()(T& v) const { return callback(*v); }
            };
 
            struct ByTupleDereference {
                template<size_t Idx, class T> auto constexpr getElement(T& v) const {
                    if constexpr(std::is_reference<decltype(*std::get<Idx>(v))>::value) {
                        return std::reference_wrapper(*std::get<Idx>(v));
                    } else {
                        return *std::get<Idx>(v);
                    }
                }
 
                template<size_t... Idx, class T> auto getReferenceTuple(T& v, std::index_sequence<Idx...>) const {
                    return std::make_tuple(getElement<Idx>(v)...);
                }
 
                template<typename... Args> auto operator()(std::tuple<Args...>& v) const {
                    return getReferenceTuple(v, std::make_index_sequence<sizeof...(Args)>());
                }
            };
 
            template<typename T, typename M, M Method> struct ByMemberCall {
                using R = decltype((std::declval<T&>().*Method)());
                R operator()(T& v) const { return (v.*Method)(); }
            };
 
            template<typename M, M Member> struct ByMemberVariable {
                template<typename T> auto& operator()(T& v) const { return ((*v).*Member); }
            };
 
        } // namespace dereference
    } // namespace impl
 
    struct UndefinedIteratorException : public std::exception {
        [[nodiscard]] const char* what() const noexcept override { return "attempt to dereference an undefined iterator"; }
    };
 
    template<class T, typename D = impl::dereference::ByValueReference, typename C = impl::compare::ByValue> class IteratorPrototype {
    public:
        // iterator traits
        using iterator_category = std::input_iterator_tag;
        using reference = decltype(std::declval<D>()(std::declval<T&>()));
        using value_type = typename std::decay<reference>::type;
        using pointer = value_type*;
        using difference_type = std::ptrdiff_t;
 
    protected:
        D dereferencer;
        C compare;
 
    public:
        mutable T value;
        using DereferencedType = decltype(dereferencer(value));
 
        IteratorPrototype() = delete;
        explicit IteratorPrototype(T&& first, D&& _dereferencer = D(), C&& _compare = C())
                : dereferencer(std::forward<D>(_dereferencer)), compare(std::forward<C>(_compare)), value(std::forward<T>(first)) {}
 
        CE_FORCE_INLINE DereferencedType operator*() { return dereferencer(value); }
        CE_FORCE_INLINE auto* operator->() const { return &**this; }
 
        friend bool operator==(const IteratorPrototype& lhs, const IteratorPrototype& rhs) { return lhs.compare(lhs.value, rhs.value); }
        friend bool operator!=(const IteratorPrototype& lhs, const IteratorPrototype& rhs) { return !(lhs == rhs); }
    };
 
    template<class T> IteratorPrototype(const T&) -> IteratorPrototype<T>;
    template<class T, typename D> IteratorPrototype(const T&, const D&) -> IteratorPrototype<T, D>;
    template<class T, typename D, typename C> IteratorPrototype(const T&, const D&, const C&) -> IteratorPrototype<T, D, C>;
 
    namespace impl {
        struct WithState {
            constexpr static bool hasState = true;
            bool state = true;
        };
        struct WithoutState {
            constexpr static bool hasState = false;
        };
 
        template<class F, class T> static constexpr bool needsState = !std::is_same<void, decltype(std::declval<F>()(std::declval<T&>()))>::value;
    } // namespace impl
 
    template<class T, typename F = impl::increment::ByValue<1>, typename D = impl::dereference::ByValueReference, typename C = impl::compare::ByValue>
    class Iterator final : public IteratorPrototype<T, D, C>, public std::conditional<impl::needsState<F, T>, impl::WithState, impl::WithoutState>::type {
    protected:
        using Base = IteratorPrototype<T, D, C>;
        F callback;
 
    public:
        template<typename TF = F, typename TD = D, typename TC = C>
        explicit Iterator(T&& begin, F&& _callback = F(), D&& _dereferencer = D(), C&& _compare = C())
                : IteratorPrototype<T, D, C>(std::forward<T>(begin), std::forward<D>(_dereferencer), std::forward<C>(_compare)),
                  callback(std::forward<F>(_callback)) {}
 
        Iterator& operator++() {
            if constexpr(Iterator::hasState) {
                if(Iterator::state) {
                    Iterator::state = callback(Base::value);
                }
            } else {
                callback(Base::value);
            }
            return *this;
        }
 
        typename Base::DereferencedType operator*() const {
            if constexpr(Iterator::hasState) {
                if(!Iterator::state) {
                    throw UndefinedIteratorException();
                }
            }
            return Base::dereferencer(Base::value);
        }
 
        friend bool operator==(const Iterator& lhs, const IterationEnd& rhs) { return !(lhs != rhs); }
 
        friend bool operator!=(const Iterator& lhs, const IterationEnd& rhs) {
            if constexpr(Iterator::hasState) {
                return lhs.state;
            } else {
                return true;
            }
        }
 
        explicit operator bool() const {
            if constexpr(Iterator::hasState) {
                return Iterator::state;
            } else {
                return true;
            }
        }
    };
 
    template<class T> Iterator(const T&) -> Iterator<T>;
    template<class T, typename F> Iterator(const T&, const F&) -> Iterator<T, F>;
    template<class T, typename F, typename D> Iterator(const T&, const F&, const D&) -> Iterator<T, F, D>;
    template<class T, typename F, typename D, typename C> Iterator(const T&, const F&, const D&, const C&) -> Iterator<T, F, D, C>;
 
    template<class T, typename F = impl::increment::ByValue<1>, typename D = impl::dereference::ByValueReference, typename C = impl::compare::ByValue>
    Iterator<T, F, D, C> makeIterator(T&& t, F f = F(), D&& d = D(), C&& c = C()) {
        return Iterator<T, F, D, C>(std::forward<T>(t), std::forward<F>(f), std::forward<D>(d), std::forward<C>(c));
    }
 
    template<class T, class A = impl::increment::ByValue<1>> using ReferenceIterator = Iterator<T*, A, impl::dereference::ByValueDereference>;
 
    template<class IB, class IE = IB, class Context = void> struct WrappedIterator {
        Context mContext;
        mutable IB beginIterator;
        mutable IE endIterator;
        IB&& begin() const { return std::move(beginIterator); }
        IE&& end() const { return std::move(endIterator); }
        WrappedIterator(IB&& begin, IE&& end, Context&& context) : mContext(std::move(context)), beginIterator(std::move(begin)), endIterator(std::move(end)) {}
    };
 
    template<class IB, class IE> struct WrappedIterator<IB, IE> {
        mutable IB beginIterator;
        mutable IE endIterator;
        IB&& begin() const { return std::move(beginIterator); }
        IE&& end() const { return std::move(endIterator); }
        WrappedIterator(IB&& begin, IE&& end) : beginIterator(std::move(begin)), endIterator(std::move(end)) {}
    };
 
    template<class IB, class IE, class Context> auto wrap(IB&& a, IE&& b, Context&& context) {
        return WrappedIterator<IB, IE, Context>(std::forward<IB>(a), std::forward<IE>(b), std::forward<Context>(context));
    }
 
    template<class IB, class IE, class Context> auto wrap(Pair<IB, IE>&& pair, Context&& context) {
        return wrap(std::forward<IB>(pair.first), std::forward<IE>(pair.second), std::forward<Context>(context));
    }
 
    template<class IB, class IE> auto wrap(IB&& a, IE&& b) { return WrappedIterator<IB, IE>(std::forward<IB>(a), std::forward<IE>(b)); }
 
    template<class IB, class IE> auto wrap(Pair<IB, IE>&& pair) { return wrap(std::forward<IB>(pair.first), std::forward<IE>(pair.second)); }
 
    template<class T> struct RangeIterator : public IteratorPrototype<T, impl::dereference::ByValue, impl::compare::ByValueGTE> {
        T increment;
 
        RangeIterator(const T& start, const T& _increment = 1)
                : IteratorPrototype<T, impl::dereference::ByValue, impl::compare::ByValueGTE>(T(start)), increment(_increment) {}
 
        RangeIterator& operator++() {
            RangeIterator::value += increment;
            return *this;
        }
    };
 
    template<class T> RangeIterator<T> rangeValue(T v, T i = 1) { return RangeIterator<T>(v, i); }
 
    template<class T> auto range(T begin, T end, T increment) {
        if constexpr(std::is_floating_point_v<T>) {
            return wrap(rangeValue(end, increment), rangeValue(end, increment));
        } else {
            const T actualEnd = end - ((end - begin) % increment);
            return wrap(rangeValue(begin, increment), rangeValue(actualEnd, increment));
        }
    }
 
    template<class T> auto range(T begin, T end) { return range<T>(begin, end, 1); }
 
    template<class T> auto range(T end) { return range<T>(0, end, 1); }
 
    template<class T = UInt64> auto range() { return range<T>(std::numeric_limits<T>::max()); }
 
    template<typename T = UInt64, typename Container> auto indices(const Container& container) { return range<T>(T(0), T(container.size())); }
 
    template<typename Container> auto indices(const Container& container) {
        using T = decltype(container.size());
        return indices<T>(container);
    }
 
    template<class T> auto reverse(T& v) { return wrap(v.rbegin(), v.rend()); }
 
    template<typename... Args> auto zip(Args&&... args) {
        auto begin = Iterator(std::make_tuple(args.begin()...), impl::increment::ByTupleIncrement(), impl::dereference::ByTupleDereference(),
            impl::compare::ByLastTupleElementMatch());
        auto end = Iterator(std::make_tuple(args.end()...), impl::increment::ByTupleIncrement(), impl::dereference::ByTupleDereference(),
            impl::compare::ByLastTupleElementMatch());
        return wrap(std::move(begin), std::move(end));
    }
 
    template<typename Container> auto keys(Container& container) {
        using PairType = std::decay_t<decltype(*container.begin())>;
        using Dereference = impl::dereference::ByMemberVariable<decltype(&PairType::first), &PairType::first>;
 
        return wrap(makeIterator(container.begin(), impl::increment::ByPrefixIncrement(), Dereference()),
            makeIterator(container.end(), impl::increment::ByPrefixIncrement(), Dereference()));
    }
 
    template<typename Container> auto keys(Container&& container) {
        using PairType = std::decay_t<decltype(*container.begin())>;
        using Dereference = impl::dereference::ByMemberVariable<decltype(&PairType::first), &PairType::first>;
 
        return wrap(makeIterator(container.begin(), impl::increment::ByPrefixIncrement(), Dereference()),
            makeIterator(container.end(), impl::increment::ByPrefixIncrement(), Dereference()), std::forward<Container>(container));
    }
 
    template<typename Container> auto values(Container& container) {
        using PairType = std::decay_t<decltype(*container.begin())>;
        using Dereference = impl::dereference::ByMemberVariable<decltype(&PairType::second), &PairType::second>;
 
        return wrap(makeIterator(container.begin(), impl::increment::ByPrefixIncrement(), Dereference()),
            makeIterator(container.end(), impl::increment::ByPrefixIncrement(), Dereference()));
    }
 
    template<typename Container> auto values(Container&& container) {
        using PairType = std::decay_t<decltype(*container.begin())>;
        using Dereference = impl::dereference::ByMemberVariable<decltype(&PairType::second), &PairType::second>;
 
        return wrap(makeIterator(container.begin(), impl::increment::ByPrefixIncrement(), Dereference()),
            makeIterator(container.end(), impl::increment::ByPrefixIncrement(), Dereference()), std::forward<Container>(container));
    }
 
    template<typename Container> auto dereference(Container& container) {
        return wrap(makeIterator(container.begin(), impl::increment::ByPrefixIncrement(), impl::dereference::ByPointerReference()),
            makeIterator(container.end(), impl::increment::ByPrefixIncrement(), impl::dereference::ByPointerReference()));
    }
 
    template<typename Container> auto dereference(Container&& container) {
        return wrap(makeIterator(container.begin(), impl::increment::ByPrefixIncrement(), impl::dereference::ByPointerReference()),
            makeIterator(container.end(), impl::increment::ByPrefixIncrement(), impl::dereference::ByPointerReference()), std::forward<Container>(container));
    }
 
    template<typename Container, typename Transform> auto transform(Container& container, Transform&& transform) {
        return wrap(makeIterator(container.begin(), impl::increment::ByPrefixIncrement(), impl::dereference::ByCallback(transform)),
            makeIterator(container.end(), impl::increment::ByPrefixIncrement(), impl::dereference::ByCallback(transform)));
    }
 
    template<typename Container, typename Transform> auto transform(Container&& container, Transform&& transform) {
        return wrap(makeIterator(container.begin(), impl::increment::ByPrefixIncrement(), impl::dereference::ByCallback(transform)),
            makeIterator(container.end(), impl::increment::ByPrefixIncrement(), impl::dereference::ByCallback(transform)), std::forward<Container>(container));
    }
 
    template<typename Container, typename Predicate> auto filter(Container& container, Predicate&& predicate) {
        auto begin = std::find_if(container.begin(), container.end(), predicate);
        const auto filter = [end = container.end(), predicate = std::forward<Predicate>(predicate)](auto& iterator) mutable {
            iterator = std::find_if(++iterator, end, predicate);
        };
        return wrap(makeIterator(decltype(begin)(begin), impl::increment::ByCallback(filter), impl::dereference::ByValueDereference()),
            makeIterator(container.end(), impl::increment::ByCallback(filter), impl::dereference::ByValueDereference()));
    }
 
    template<typename Container, typename Predicate> auto filter(Container&& container, Predicate&& predicate) {
        auto begin = std::find_if(container.begin(), container.end(), predicate);
        const auto filter = [end = container.end(), predicate = std::forward<Predicate>(predicate)](auto& iterator) mutable {
            iterator = std::find_if(++iterator, end, predicate);
        };
        return wrap(makeIterator(decltype(begin)(begin), impl::increment::ByCallback(filter), impl::dereference::ByValueDereference()),
            makeIterator(container.end(), impl::increment::ByCallback(filter), impl::dereference::ByValueDereference()), std::forward<Container>(container));
    }
 
    template<typename Container> auto unique(Container& container) {
        const auto callback = [end = container.end(), current = container.begin()](auto& iterator) mutable {
            current = iterator = std::find_if_not(++iterator, end, [&](auto& candidate) {
                return candidate == *current;
            });
        };
        return wrap(makeIterator(container.begin(), impl::increment::ByCallback(callback), impl::dereference::ByValueDereference()),
            makeIterator(container.end(), impl::increment::ByCallback(callback), impl::dereference::ByValueDereference()));
    }
 
    template<typename Container> auto unique(Container&& container) {
        const auto callback = [end = container.end(), current = container.begin()](auto& iterator) mutable {
            current = iterator = std::find_if_not(++iterator, end, [&](auto& candidate) {
                return candidate == *current;
            });
        };
        return wrap(makeIterator(container.begin(), impl::increment::ByCallback(callback), impl::dereference::ByValueDereference()),
                    makeIterator(container.end(), impl::increment::ByCallback(callback), impl::dereference::ByValueDereference()), std::forward<Container>(container));
    }
 
    template<typename Container> auto skipNull(Container& container) {
        return filter(container, [](const auto& v) { return v != nullptr; });
    }
 
    template<typename Container> auto skipNull(Container&& container) {
        return filter(std::forward<Container>(container), [](const auto& v) { return v != nullptr; });
    }
 
    template<typename Container> auto weakLock(Container& container) {
        return transform(container, [](const auto& value) { return value.lock(); });
    }
 
    template<typename Container> auto weakLock(Container&& container) {
        return transform(std::forward<Container>(container), [](const auto& value) { return value.lock(); });
    }
 
    struct InitializedIterable {};
 
    template<class T> struct MakeIterable {
        mutable Iterator<T, impl::increment::ByMemberCall<T, decltype(&T::advance), &T::advance>,
            impl::dereference::ByMemberCall<T, decltype(&T::value), &T::value>, impl::compare::ByValue>
            start;
 
        auto&& begin() const {
            if constexpr(std::is_base_of<InitializedIterable, T>::value) {
                start.state = start.value.init();
            }
            return std::move(start);
        }
        auto end() const { return IterationEnd(); }
 
        explicit MakeIterable(T&& value) : start(std::move(value)) {}
        template<typename... Args> explicit MakeIterable(Args&&... args) : start(T(std::forward<Args>(args)...)) {}
    };
 
    template<class T, class I = impl::increment::ByValue<1>> auto valuesBetween(T* begin, T* end) {
        return wrap(ReferenceIterator<T, I>(begin), Iterator(end));
    }
 
    template<class T, class A> void fill(A& arr, const T& value) {
        for(auto& v : arr) {
            v = value;
        }
    }
 
    template<class A, class B, class T = impl::dereference::ByValueReference> void copy(const A& a, B& b, T&& t = T()) {
        for(auto [v1, v2] : zip(a, b)) {
            v2 = t(v1);
        }
    }
 
    template<class I, class C> decltype(&*std::declval<I>()) found(const I& it, C& container) {
        if(it != container.end()) {
            return &*it;
        }
        return nullptr;
    }
 
    template<class I, class C> bool eraseIfFound(const I& it, C& container) {
        if(it != container.end()) {
            container.erase(it);
            return true;
        }
        return false;
    }
 
    //    /// Returns a pointer to the value if found, otherwise `nullptr`.
    //    /// Usage: `if(auto v = find(map, key)) { do_something(v); }`
    //    template<class C, class V> auto find(C& c, V&& v) {
    //        auto it = c.find(v);
    //        return found(it, c);
    //    }
 
} // namespace CeresEngine
 
template<class T, typename F, typename D, typename C> struct std::iterator_traits<CeresEngine::Iterator<T, F, D, C>> {
    using Iterator = CeresEngine::Iterator<T, F, D, C>;
 
    using difference_type = typename Iterator::difference_type;
    using value_type = typename Iterator::value_type;
    using pointer = typename Iterator::pointer;
    using reference = typename Iterator::reference;
    using iterator_category = typename Iterator::iterator_category;
};