#pragma once

template <typename T>
class Iterator {
protected:
	T* current;
public:
	explicit Iterator(T* ptr) : current(ptr) {}

	T& operator*() const { return *current; }
	T* operator->() const { return current; }

	bool operator!=(const Iterator& other) const {
		return current != other.current;
	}

	virtual Iterator& operator++() = 0;
};

template<typename T, typename Policy>
class Traversal {
	T* start;

public:
	explicit Traversal(T* start) : start(start) {}

	Policy begin() const { return Policy(start); }
	Policy end() const { return Policy(nullptr); }
};

template <typename T>
struct IteratorForward : public Iterator<T> {
	explicit IteratorForward(T* ptr) : Iterator<T>(first(ptr)) {}

	static T* first(T* node) {
		return node;
	}

	static T* next(T* node) {
		return node ? node->get_next() : nullptr;
	}

	Iterator<T>& operator++() override {
		this->current = next(this->current);
		return *this;
	}
};

template <typename T>
struct IteratorBackward : public Iterator<T> {
	explicit IteratorBackward(T* ptr) : Iterator<T>(first(ptr)) {}

	static T* first(T* node) {
		if (!node) return nullptr;
		while (node->get_next()) node = node->get_next();
		return node;
	}

	static T* next(T* node) {
		return node ? node->get_prev() : nullptr;
	}

	Iterator<T>& operator++() override {
		this->current = next(this->current);
		return *this;
	}
};