#include <iostream>
#include <vector>
#include <stdexcept>

// Abstract iterator: defines the interface for traversing elements
template <typename T>
class Iterator {
public:
    virtual ~Iterator() = default;
    virtual void first() = 0;          // Move to the first element
    virtual void next() = 0;           // Move to the next element
    virtual bool isDone() const = 0;   // Is traversal finished
    virtual T currentItem() const = 0; // Get current element
};

// Abstract aggregate: defines the interface to create iterators
template <typename T>
class Aggregate {
public:
    virtual ~Aggregate() = default;
    virtual Iterator<T>* createIterator() = 0; // Factory method
};

// Concrete aggregate: stores data internally using std::vector
template <typename T>
class ConcreteAggregate : public Aggregate<T> {
public:
    void addItem(const T& item) {
        items_.push_back(item);
    }

    size_t size() const {
        return items_.size();
    }

    T getItem(size_t index) const {
        if (index >= items_.size())
            throw std::out_of_range("Index out of range");
        return items_[index];
    }

    Iterator<T>* createIterator() override;

private:
    std::vector<T> items_;
};

// Concrete iterator: associated with a ConcreteAggregate and traverses elements sequentially
template <typename T>
class ConcreteIterator : public Iterator<T> {
public:
    explicit ConcreteIterator(ConcreteAggregate<T>* aggregate)
        : aggregate_(aggregate), current_(0) {}

    void first() override {
        current_ = 0;
    }

    void next() override {
        if (!isDone())
            ++current_;
    }

    bool isDone() const override {
        return current_ >= aggregate_->size();
    }

    T currentItem() const override {
        if (isDone())
            throw std::out_of_range("Iterator out of range");
        return aggregate_->getItem(current_);
    }

private:
    ConcreteAggregate<T>* aggregate_;
    size_t current_;
};

// Implement createIterator here (requires full definition of ConcreteIterator)
template <typename T>
Iterator<T>* ConcreteAggregate<T>::createIterator() {
    return new ConcreteIterator<T>(this);
}

// Demo program
int main() {
    // Create a concrete aggregate and add some integer elements
    ConcreteAggregate<int> numbers;
    numbers.addItem(10);
    numbers.addItem(20);
    numbers.addItem(30);
    numbers.addItem(40);
    numbers.addItem(50);

    // Create an iterator from the aggregate
    Iterator<int>* it = numbers.createIterator();

    // Traverse the aggregate using the iterator without depending on internal storage
    std::cout << "Traversing elements using Iterator:\n";
    for (it->first(); !it->isDone(); it->next()) {
        std::cout << it->currentItem() << " ";
    }
    std::cout << std::endl;

    // Clean up resources
    delete it;

    return 0;
}