enumerator.h

/*
 * SPDX-FileCopyrightText: 2013 Barefoot Networks, Inc.
 * Copyright 2013-present Barefoot Networks, Inc.
 *
 * SPDX-License-Identifier: Apache-2.0
 */
 
/* -*-c++-*-
   C#-like enumerator interface */
 
#ifndef LIB_ENUMERATOR_H_
#define LIB_ENUMERATOR_H_
 
#include <cstdint>
#include <functional>
#include <initializer_list>
#include <iterator>
#include <stdexcept>
#include <string>
#include <type_traits>
#include <vector>
 
#include "iterator_range.h"
 
namespace P4::Util {
enum class EnumeratorState { NotStarted, Valid, PastEnd };
 
template <typename T>
class Enumerator;

// FIXME: It is not a proper iterator (see reference type above) and should be removed
// in favor of more standard approach. Note that Enumerator<T>::getCurrent() always
// returns element by value, so more or less suitable only for copyable types that are cheap
// to copy.
template <typename T>
class EnumeratorHandle {
 private:
    Enumerator<T> *enumerator = nullptr;  // when nullptr it represents end()
    explicit EnumeratorHandle(Enumerator<T> *enumerator) : enumerator(enumerator) {}
    friend class Enumerator<T>;
 
 public:
    using iterator_category = std::input_iterator_tag;
    using difference_type = std::ptrdiff_t;
    using value_type = T;
    using reference = T;
    using pointer = void;
 
    reference operator*() const;
    const EnumeratorHandle<T> &operator++();
    bool operator==(const EnumeratorHandle<T> &other) const;
    bool operator!=(const EnumeratorHandle<T> &other) const;
};

template <class T>
class Enumerator {
 protected:
    EnumeratorState state = EnumeratorState::NotStarted;
 
    // This is a weird oddity of C++: this class is a friend of itself with different templates
    template <class S>
    friend class Enumerator;
    static std::vector<T> emptyVector;
    template <typename S>
    friend class EnumeratorHandle;
 
 public:
    using value_type = T;
 
    Enumerator() { this->reset(); }
 
    virtual ~Enumerator() = default;

    virtual bool moveNext() = 0;
    virtual T getCurrent() const = 0;
    virtual void reset() { this->state = EnumeratorState::NotStarted; }
 
    EnumeratorHandle<T> begin() {
        this->moveNext();
        return EnumeratorHandle<T>(this);
    }
    EnumeratorHandle<T> end() { return EnumeratorHandle<T>(nullptr); }
 
    const char *stateName() const {
        switch (this->state) {
            case EnumeratorState::NotStarted:
                return "NotStarted";
            case EnumeratorState::Valid:
                return "Valid";
            case EnumeratorState::PastEnd:
                return "PastEnd";
        }
        throw std::logic_error("Unexpected state " + std::to_string(static_cast<int>(this->state)));
    }

    template <typename Container>
    [[deprecated(
        "Use Util::enumerate() instead")]] static Enumerator<typename Container::value_type> *
    createEnumerator(const Container &data);
    static Enumerator<T> *emptyEnumerator();  // empty data
    template <typename Iter>
    [[deprecated("Use Util::enumerate() instead")]] static Enumerator<typename Iter::value_type> *
    createEnumerator(Iter begin, Iter end);
    template <typename Iter>
    [[deprecated("Use Util::enumerate() instead")]] static Enumerator<typename Iter::value_type> *
    createEnumerator(iterator_range<Iter> range);

    template <typename Filter>
    Enumerator<T> *where(Filter filter);
    template <typename Mapper>
    Enumerator<std::invoke_result_t<Mapper, T>> *map(Mapper map);
    template <typename S>
    Enumerator<S> *as();
    virtual Enumerator<T> *concat(Enumerator<T> *other);
    static Enumerator<T> *concatAll(Enumerator<Enumerator<T> *> *inputs);
 
    std::vector<T> toVector() {
        std::vector<T> result;
        while (moveNext()) result.push_back(getCurrent());
        return result;
    }

    uint64_t count() {
        uint64_t found = 0;
        while (this->moveNext()) found++;
        return found;
    }

    bool any() { return this->moveNext(); }

    T single() {
        bool next = moveNext();
        if (!next) throw std::logic_error("There is no element for `single()'");
        T result = getCurrent();
        next = moveNext();
        if (next) throw std::logic_error("There are multiple elements when calling `single()'");
        return result;
    }

    T singleOrDefault() {
        bool next = moveNext();
        if (!next) return T{};
        T result = getCurrent();
        next = moveNext();
        if (next) throw std::logic_error("There are multiple elements when calling `single()'");
        return result;
    }

    T nextOrDefault() {
        bool next = moveNext();
        if (!next) return T{};
        return getCurrent();
    }

    T next() {
        bool next = moveNext();
        if (!next) throw std::logic_error("There is no element for `next()'");
        return getCurrent();
    }
};

// the implementation must be in the header file due to the templates


template <typename Iter>
class IteratorEnumerator : public Enumerator<typename std::iterator_traits<Iter>::value_type> {
 protected:
    Iter begin;
    Iter end;
    Iter current;
    const char *name;
    friend class Enumerator<typename std::iterator_traits<Iter>::value_type>;
 
 public:
    IteratorEnumerator(Iter begin, Iter end, const char *name)
        : Enumerator<typename std::iterator_traits<Iter>::value_type>(),
          begin(begin),
          end(end),
          current(begin),
          name(name) {}
 
    [[nodiscard]] std::string toString() const {
        return std::string(this->name) + ":" + this->stateName();
    }
 
    bool moveNext() override {
        switch (this->state) {
            case EnumeratorState::NotStarted:
                this->current = this->begin;
                if (this->current == this->end) {
                    this->state = EnumeratorState::PastEnd;
                    return false;
                } else {
                    this->state = EnumeratorState::Valid;
                }
                return true;
            case EnumeratorState::PastEnd:
                return false;
            case EnumeratorState::Valid:
                ++this->current;
                if (this->current == this->end) {
                    this->state = EnumeratorState::PastEnd;
                    return false;
                }
                return true;
        }
 
        throw std::runtime_error("Unexpected enumerator state");
    }
 
    typename std::iterator_traits<Iter>::value_type getCurrent() const override {
        switch (this->state) {
            case EnumeratorState::NotStarted:
                throw std::logic_error("You cannot call 'getCurrent' before 'moveNext'");
            case EnumeratorState::PastEnd:
                throw std::logic_error("You cannot call 'getCurrent' past the collection end");
            case EnumeratorState::Valid:
                return *this->current;
        }
        throw std::runtime_error("Unexpected enumerator state");
    }
};
 
template <typename Iter>
IteratorEnumerator(Iter begin, Iter end, const char *name) -> IteratorEnumerator<Iter>;

 
template <typename T>
class SingleEnumerator : public Enumerator<T> {
    T value;
 
 public:
    explicit SingleEnumerator(T v) : Enumerator<T>(), value(v) {}
    bool moveNext() {
        switch (this->state) {
            case EnumeratorState::NotStarted:
                this->state = EnumeratorState::Valid;
                return true;
            case EnumeratorState::PastEnd:
                return false;
            case EnumeratorState::Valid:
                this->state = EnumeratorState::PastEnd;
                return false;
        }
        throw std::runtime_error("Unexpected enumerator state");
    }
    T getCurrent() const {
        switch (this->state) {
            case EnumeratorState::NotStarted:
                throw std::logic_error("You cannot call 'getCurrent' before 'moveNext'");
            case EnumeratorState::PastEnd:
                throw std::logic_error("You cannot call 'getCurrent' past the collection end");
            case EnumeratorState::Valid:
                return this->value;
        }
        throw std::runtime_error("Unexpected enumerator state");
    }
};


template <typename T>
class EmptyEnumerator : public Enumerator<T> {
 public:
    [[nodiscard]] std::string toString() const { return "EmptyEnumerator"; }
    bool moveNext() override { return false; }
    T getCurrent() const override {
        throw std::logic_error("You cannot call 'getCurrent' on an EmptyEnumerator");
    }
};


template <typename T, typename Filter>
class FilterEnumerator final : public Enumerator<T> {
    Enumerator<T> *input;
    Filter filter;
    T current;  // must prevent repeated evaluation
 
 public:
    FilterEnumerator(Enumerator<T> *input, Filter filter)
        : input(input), filter(std::move(filter)) {}
 
 private:
    bool advance() {
        this->state = EnumeratorState::Valid;
        while (this->input->moveNext()) {
            this->current = this->input->getCurrent();
            bool match = this->filter(this->current);
            if (match) return true;
        }
        this->state = EnumeratorState::PastEnd;
        return false;
    }
 
 public:
    [[nodiscard]] std::string toString() const {
        return "FilterEnumerator(" + this->input->toString() + "):" + this->stateName();
    }
 
    void reset() {
        this->input->reset();
        Enumerator<T>::reset();
    }
 
    bool moveNext() {
        switch (this->state) {
            case EnumeratorState::NotStarted:
            case EnumeratorState::Valid:
                return this->advance();
            case EnumeratorState::PastEnd:
                return false;
        }
        throw std::runtime_error("Unexpected enumerator state");
    }
 
    T getCurrent() const {
        switch (this->state) {
            case EnumeratorState::NotStarted:
                throw std::logic_error("You cannot call 'getCurrent' before 'moveNext'");
            case EnumeratorState::PastEnd:
                throw std::logic_error("You cannot call 'getCurrent' past the collection end");
            case EnumeratorState::Valid:
                return this->current;
        }
        throw std::runtime_error("Unexpected enumerator state");
    }
};

 
namespace Detail {
// See if we can use ICastable interface to cast from T to S. This is only possible if:
// - Both T and S are pointer types (let's denote T = From* and S = To*)
// - Expression (From*)()->to<To>() is well-formed
// Essentially this means the following code is well-formed:
// From *current = input->getCurrent(); current->to<To>();
template <typename From, typename To, typename = void>
static constexpr bool can_be_casted = false;
 
template <typename From, typename To>
static constexpr bool
    can_be_casted<From *, To *, std::void_t<decltype(std::declval<From *>()->template to<To>())>> =
        true;
}  // namespace Detail

template <typename T, typename S>
class AsEnumerator final : public Enumerator<S> {
    template <typename U = S>
    typename std::enable_if_t<!Detail::can_be_casted<T, S>, U> getCurrentImpl() const {
        T current = input->getCurrent();
        return dynamic_cast<S>(current);
    }
 
    template <typename U = S>
    typename std::enable_if_t<Detail::can_be_casted<T, S>, U> getCurrentImpl() const {
        T current = input->getCurrent();
        return current->template to<std::remove_pointer_t<S>>();
    }
 
 protected:
    Enumerator<T> *input;
 
 public:
    explicit AsEnumerator(Enumerator<T> *input) : input(input) {}
 
    std::string toString() const {
        return "AsEnumerator(" + this->input->toString() + "):" + this->stateName();
    }
 
    void reset() override {
        Enumerator<S>::reset();
        this->input->reset();
    }
 
    bool moveNext() override {
        bool result = this->input->moveNext();
        if (result)
            this->state = EnumeratorState::Valid;
        else
            this->state = EnumeratorState::PastEnd;
        return result;
    }
 
    S getCurrent() const override { return getCurrentImpl(); }
};


template <typename T, typename S, typename Mapper>
class MapEnumerator final : public Enumerator<S> {
 protected:
    Enumerator<T> *input;
    Mapper map;
    S current;
 
 public:
    MapEnumerator(Enumerator<T> *input, Mapper map) : input(input), map(std::move(map)) {}
 
    void reset() {
        this->input->reset();
        Enumerator<S>::reset();
    }
 
    [[nodiscard]] std::string toString() const {
        return "MapEnumerator(" + this->input->toString() + "):" + this->stateName();
    }
 
    bool moveNext() {
        switch (this->state) {
            case EnumeratorState::NotStarted:
            case EnumeratorState::Valid: {
                bool success = input->moveNext();
                if (success) {
                    T currentInput = this->input->getCurrent();
                    this->current = this->map(currentInput);
                    this->state = EnumeratorState::Valid;
                    return true;
                } else {
                    this->state = EnumeratorState::PastEnd;
                    return false;
                }
            }
            case EnumeratorState::PastEnd:
                return false;
        }
        throw std::runtime_error("Unexpected enumerator state");
    }
 
    S getCurrent() const {
        switch (this->state) {
            case EnumeratorState::NotStarted:
                throw std::logic_error("You cannot call 'getCurrent' before 'moveNext'");
            case EnumeratorState::PastEnd:
                throw std::logic_error("You cannot call 'getCurrent' past the collection end");
            case EnumeratorState::Valid:
                return this->current;
        }
        throw std::runtime_error("Unexpected enumerator state");
    }
};
 
template <typename T, typename Mapper>
MapEnumerator(Enumerator<T> *,
              Mapper) -> MapEnumerator<T, typename std::invoke_result_t<Mapper, T>, Mapper>;


template <typename T>
class ConcatEnumerator final : public Enumerator<T> {
    std::vector<Enumerator<T> *> inputs;
    T currentResult;
 
 public:
    ConcatEnumerator() = default;
    // We take ownership of the vector
    explicit ConcatEnumerator(std::vector<Enumerator<T> *> &&inputs) : inputs(std::move(inputs)) {
        for (auto *currentInput : inputs)
            if (currentInput == nullptr) throw std::logic_error("Null iterator in concatenation");
    }
 
    ConcatEnumerator(std::initializer_list<Enumerator<T> *> inputs) : inputs(inputs) {
        for (auto *currentInput : inputs)
            if (currentInput == nullptr) throw std::logic_error("Null iterator in concatenation");
    }
    explicit ConcatEnumerator(Enumerator<Enumerator<T> *> *inputs)
        : ConcatEnumerator(inputs->toVector()) {}
 
    [[nodiscard]] std::string toString() const { return "ConcatEnumerator:" + this->stateName(); }
 
 private:
    bool advance() {
        this->state = EnumeratorState::Valid;
        for (auto *currentInput : inputs) {
            if (currentInput->moveNext()) {
                this->currentResult = currentInput->getCurrent();
                return true;
            }
        }
 
        this->state = EnumeratorState::PastEnd;
        return false;
    }
 
 public:
    Enumerator<T> *concat(Enumerator<T> *other) override {
        // Too late to add
        if (this->state == EnumeratorState::PastEnd)
            throw std::runtime_error("Invalid enumerator state to concatenate");
 
        inputs.push_back(other);
 
        return this;
    }
 
    void reset() override {
        for (auto *currentInput : inputs) currentInput->reset();
        Enumerator<T>::reset();
    }
 
    bool moveNext() override {
        switch (this->state) {
            case EnumeratorState::NotStarted:
            case EnumeratorState::Valid:
                return this->advance();
            case EnumeratorState::PastEnd:
                return false;
        }
        throw std::runtime_error("Unexpected enumerator state");
    }
 
    T getCurrent() const override {
        switch (this->state) {
            case EnumeratorState::NotStarted:
                throw std::logic_error("You cannot call 'getCurrent' before 'moveNext'");
            case EnumeratorState::PastEnd:
                throw std::logic_error("You cannot call 'getCurrent' past the collection end");
            case EnumeratorState::Valid:
                return this->currentResult;
        }
        throw std::runtime_error("Unexpected enumerator state");
    }
};

 
template <typename T>
template <typename Mapper>
Enumerator<std::invoke_result_t<Mapper, T>> *Enumerator<T>::map(Mapper map) {
    return new MapEnumerator(this, std::move(map));
}
 
template <typename T>
template <typename S>
Enumerator<S> *Enumerator<T>::as() {
    return new AsEnumerator<T, S>(this);
}
 
template <typename T>
template <typename Filter>
Enumerator<T> *Enumerator<T>::where(Filter filter) {
    return new FilterEnumerator(this, std::move(filter));
}
 
template <typename T>
template <typename Container>
Enumerator<typename Container::value_type> *Enumerator<T>::createEnumerator(const Container &data) {
    return new IteratorEnumerator(data.begin(), data.end(), typeid(Container).name());
}
 
template <typename T>
Enumerator<T> *Enumerator<T>::emptyEnumerator() {
    return new EmptyEnumerator<T>();
}
 
template <typename T>
template <typename Iter>
Enumerator<typename Iter::value_type> *Enumerator<T>::createEnumerator(Iter begin, Iter end) {
    return new IteratorEnumerator(begin, end, "iterator");
}
 
template <typename T>
template <typename Iter>
Enumerator<typename Iter::value_type> *Enumerator<T>::createEnumerator(iterator_range<Iter> range) {
    return new IteratorEnumerator(range.begin(), range.end(), "range");
}
 
template <typename T>
Enumerator<T> *Enumerator<T>::concatAll(Enumerator<Enumerator<T> *> *inputs) {
    return new ConcatEnumerator<T>(inputs);
}
 
template <typename T>
Enumerator<T> *Enumerator<T>::concat(Enumerator<T> *other) {
    return new ConcatEnumerator<T>({this, other});
}

 
template <typename T>
T EnumeratorHandle<T>::operator*() const {
    if (enumerator == nullptr) throw std::logic_error("Dereferencing end() iterator");
    return enumerator->getCurrent();
}
 
template <typename T>
const EnumeratorHandle<T> &EnumeratorHandle<T>::operator++() {
    enumerator->moveNext();
    return *this;
}
 
template <typename T>
bool EnumeratorHandle<T>::operator==(const EnumeratorHandle<T> &other) const {
    return !(*this != other);
}
 
template <typename T>
bool EnumeratorHandle<T>::operator!=(const EnumeratorHandle<T> &other) const {
    if (this->enumerator == other.enumerator) return true;
    if (other.enumerator != nullptr) throw std::logic_error("Comparison with different iterator");
    return this->enumerator->state == EnumeratorState::Valid;
}
 
template <typename Iter>
Enumerator<typename std::iterator_traits<Iter>::value_type> *enumerate(Iter begin, Iter end) {
    return new IteratorEnumerator(begin, end, "iterator");
}
 
template <typename Iter>
Enumerator<typename std::iterator_traits<Iter>::value_type> *enumerate(iterator_range<Iter> range) {
    return new IteratorEnumerator(range.begin(), range.end(), "range");
}
 
template <typename Container>
Enumerator<typename Container::value_type> *enumerate(const Container &data) {
    using std::begin;
    using std::end;
    return new IteratorEnumerator(begin(data), end(data), typeid(data).name());
}
 
// TODO: Flatten ConcatEnumerator's during concatenation
template <typename T>
Enumerator<T> *concat(std::initializer_list<Enumerator<T> *> inputs) {
    return new ConcatEnumerator<T>(inputs);
}
 
template <typename... Args>
auto concat(Args &&...inputs) {
    using FirstEnumeratorTy =
        std::remove_pointer_t<std::decay_t<std::tuple_element_t<0, std::tuple<Args...>>>>;
    std::initializer_list<Enumerator<typename FirstEnumeratorTy::value_type> *> init{
        std::forward<Args>(inputs)...};
    return concat(init);
}
 
}  // namespace P4::Util
 
#endif /* LIB_ENUMERATOR_H_ */