iterator.h

Go to the documentation of this file.

// SPDX-FileCopyrightText: Copyright (C) 2013 swift Project Community / Contributors
// SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-swift-pilot-client-1
 
 
#ifndef SWIFT_MISC_ITERATOR_H
#define SWIFT_MISC_ITERATOR_H
 
#include <algorithm>
#include <iterator>
#include <type_traits>
#include <utility>
 
#include "misc/optional.h"
#include "misc/typetraits.h"
 
namespace swift::misc::Iterators
{
    template <class F>
    class OutputIterator
    {
    public:
        using iterator_category = std::output_iterator_tag;
        using value_type = void;
        using difference_type = void;
        using pointer = void;
        using reference = void;
 
        explicit OutputIterator(const F &func) : m_func(func) {}
        explicit OutputIterator(F &&func) : m_func(std::move(func)) {}
        OutputIterator(const OutputIterator &other) : m_func(other.m_func) {}
 
        OutputIterator &operator++() { return *this; }
        OutputIterator operator++(int) { return *this; }
 
        OutputIterator &operator*() { return *this; }
 
        template <typename T, std::enable_if_t<!std::is_convertible_v<T, OutputIterator>, int> = 0>
        OutputIterator &operator=(T &&value)
        {
            m_func(std::forward<T>(value));
            return *this;
        }
 
        OutputIterator &operator=(const OutputIterator &other)
        {
            // Work around lambda's deleted copy assignment operator
            this->~OutputIterator();
            new (this) OutputIterator(other);
            return *this;
        }
 
        ~OutputIterator() = default;
 
    private:
        F m_func;
    };
 
    template <class F>
    auto makeOutputIterator(F &&func)
    {
        return OutputIterator<std::decay_t<F>>(std::forward<F>(func));
    }
 
    template <class T>
    auto makeInsertIterator(T &container)
    {
        if constexpr (THasPushBack<T>::value)
        {
            return makeOutputIterator([&container](auto &&v) { container.push_back(std::forward<decltype(v)>(v)); });
        }
        else
        {
            return makeOutputIterator([&container](auto &&v) { container.insert(std::forward<decltype(v)>(v)); });
        }
    }
 
    template <class I, class F>
    class TransformIterator
    {
    public:
        using iterator_category = std::forward_iterator_tag;
        using value_type =
            std::decay_t<decltype(std::declval<F>()(std::declval<typename std::iterator_traits<I>::value_type>()))>;
        using difference_type = typename std::iterator_traits<I>::difference_type;
        using reference = typename std::iterator_traits<I>::reference;
 
        using undecayed_type =
            decltype(std::declval<F>()(std::declval<typename std::iterator_traits<I>::value_type>()));
 
        struct PointerWrapper
        {
            PointerWrapper(std::decay_t<undecayed_type> *obj) : m_obj(std::move(*obj)) {}
            std::decay_t<undecayed_type> const *operator->() const { return &m_obj; }
            std::decay_t<undecayed_type> operator*() const & { return m_obj; }
            std::decay_t<undecayed_type> operator*() && { return std::move(m_obj); }
 
        private:
            const std::decay_t<undecayed_type> m_obj;
        };
 
        using pointer = typename std::conditional<std::is_reference_v<undecayed_type>,
                                                  std::remove_reference_t<undecayed_type> *, PointerWrapper>::type;
 
        TransformIterator(I iterator, F function) : m_iterator(iterator), m_function(function) {}
 
        TransformIterator(I end) : m_iterator(end) {}
 
        TransformIterator &operator++()
        {
            ++m_iterator;
            return *this;
        }
        TransformIterator operator++(int)
        {
            auto copy = *this;
            ++m_iterator;
            return copy;
        }
 
        undecayed_type operator*()
        {
            Q_ASSERT(m_function);
            return (*m_function)(*m_iterator);
        }
 
        pointer operator->()
        {
            Q_ASSERT(m_function);
            auto &&obj = (*m_function)(*m_iterator);
            return &obj;
        }
 
        bool operator==(const TransformIterator &other) const { return m_iterator == other.m_iterator; }
        bool operator!=(const TransformIterator &other) const { return m_iterator != other.m_iterator; }
        bool operator<(const TransformIterator &other) const { return m_iterator < other.m_iterator; }
        bool operator<=(const TransformIterator &other) const { return m_iterator <= other.m_iterator; }
        bool operator>(const TransformIterator &other) const { return m_iterator > other.m_iterator; }
        bool operator>=(const TransformIterator &other) const { return m_iterator >= other.m_iterator; }
 
    private:
        I m_iterator;
        Optional<F> m_function;
    };
 
    template <class I, class F>
    class ConditionalIterator
    {
    public:
        using iterator_category = std::forward_iterator_tag;
        using value_type = typename std::iterator_traits<I>::value_type;
        using difference_type = typename std::iterator_traits<I>::difference_type;
        using pointer = typename std::iterator_traits<I>::pointer;
        using reference = typename std::iterator_traits<I>::reference;
 
        ConditionalIterator(I iterator, I end, F predicate) : m_iterator(iterator), m_end(end), m_predicate(predicate)
        {
            while (m_iterator != m_end && !(*m_predicate)(*m_iterator)) { ++m_iterator; }
        }
 
        ConditionalIterator(I end) : m_iterator(end), m_end(end) {}
 
        ConditionalIterator &operator++()
        {
            Q_ASSERT(m_predicate);
            do {
                ++m_iterator;
            }
            while (m_iterator != m_end && !(*m_predicate)(*m_iterator));
            return *this;
        }
        ConditionalIterator operator++(int)
        {
            auto copy = *this;
            ++(*this);
            return copy;
        }
 
        I operator->() { return m_iterator; }
 
        typename std::iterator_traits<I>::reference operator*() { return *m_iterator; }
 
        bool operator==(const ConditionalIterator &other) const { return m_iterator == other.m_iterator; }
        bool operator!=(const ConditionalIterator &other) const { return m_iterator != other.m_iterator; }
        bool operator<(const ConditionalIterator &other) const { return m_iterator < other.m_iterator; }
        bool operator<=(const ConditionalIterator &other) const { return m_iterator <= other.m_iterator; }
        bool operator>(const ConditionalIterator &other) const { return m_iterator > other.m_iterator; }
        bool operator>=(const ConditionalIterator &other) const { return m_iterator >= other.m_iterator; }
 
        void checkEnd(const ConditionalIterator &other) // debugging
        {
            Q_ASSERT(m_end == other.m_end && m_end == other.m_iterator);
            Q_UNUSED(other);
        }
 
    private:
        I m_iterator;
        I m_end;
        Optional<F> m_predicate;
    };
 
    template <class I>
    class ConcatIterator
    {
    public:
        using iterator_category = std::forward_iterator_tag;
        using value_type = typename std::iterator_traits<I>::value_type;
        using difference_type = typename std::iterator_traits<I>::difference_type;
        using pointer = typename std::iterator_traits<I>::pointer;
        using reference = typename std::iterator_traits<I>::reference;
 
        ConcatIterator(QVector<I> iterators) : m_iterators(std::move(iterators))
        {
            Q_ASSERT(m_iterators.size() % 2 == 0);
            while (!m_iterators.empty() && m_iterators[0] == m_iterators[1]) { m_iterators.remove(0, 2); }
        }
 
        ConcatIterator(I end) { Q_UNUSED(end); }
 
        ConcatIterator &operator++()
        {
            ++(m_iterators[0]);
            while (!m_iterators.empty() && m_iterators[0] == m_iterators[1]) { m_iterators.remove(0, 2); }
            return *this;
        }
        ConcatIterator operator++(int)
        {
            auto copy = *this;
            ++(*this);
            return copy;
        }
 
        I operator->() { return m_iterators[0]; }
 
        typename std::iterator_traits<I>::reference operator*() { return *(m_iterators[0]); }
 
        bool operator==(const ConcatIterator &other) const { return m_iterators == other.m_iterators; }
        bool operator!=(const ConcatIterator &other) const { return m_iterators != other.m_iterators; }
        bool operator<(const ConcatIterator &other) const { return m_iterators < other.m_iterators; }
        bool operator<=(const ConcatIterator &other) const { return m_iterators <= other.m_iterators; }
        bool operator>(const ConcatIterator &other) const { return m_iterators > other.m_iterators; }
        bool operator>=(const ConcatIterator &other) const { return m_iterators >= other.m_iterators; }
 
    private:
        QVector<I> m_iterators;
    };
 
    template <class I, class F>
    auto makeTransformIterator(I iterator, F function) -> TransformIterator<I, F>
    {
        return { iterator, function };
    }
 
    template <class I, class F>
    auto makeConditionalIterator(I iterator, I end, F predicate) -> ConditionalIterator<I, F>
    {
        return { iterator, end, predicate };
    }
 
    template <class I>
    auto makeConcatIterator(QVector<I> iterators) -> ConcatIterator<I>
    {
        return { std::move(iterators) };
    }
 
} // namespace swift::misc::Iterators
 
#endif // SWIFT_MISC_ITERATOR_H