/**
 * @file avltree_iterator.hpp
 *
 * CopyRight F. J. Madrid-Cuevas <fjmadrid@uco.es>
 *
 * Sólo se permite el uso de este código en la docencia de las asignaturas sobre
 * Estructuras de Datos de la Universidad de Córdoba.
 *
 * Está prohibido su uso para cualquier otro objetivo.
 */
#pragma once
#include <iterator>
#include <cstddef>
#include <avltree_node.hpp>

template <class T>
class AVLTree; // Forward declaration

/**
 * @brief An iterator for a AVLTree.
 *
 * This iterator allows to traverse the nodes of a AVLTree in order.
 * This iterator is a bidirectional iterator, so it allows to traverse the
 * tree in both directions (in order and reverse order).
 * This iterator is a const iterator, so it does not allow to modify the
 * items stored in the tree.
 *
 * @tparam T
 */
template <class T>
class AVLTreeIterator
{

public:
    /** @name Types */
    /** @{*/
    using iterator_category = std::bidirectional_iterator_tag;
    using value_type = T;
    using difference_type = std::ptrdiff_t;
    using pointer = const T *;
    using reference = const T &;
    /** @}*/
    /** @name Life cicle.*/
    /** @{*/

    /**
     * @brief Construct a new AVLTreeIterator object
     *
     */
    AVLTreeIterator() = default;

    /** @} */

    /** @name Observers*/

    /** @{*/
    /**
     * @brief Is this iterator valid?
     *
     * @return true if this iterator is valid (pointing to a node in the tree).
     */
    bool is_valid() const;

    /**
     * @brief Equality operator.
     *
     * @param other is a AVLTreeIterator to be compared.
     * @return true if this iterator is equal to other (pointing to the same node).
     */
    bool operator==(AVLTreeIterator<T> const &other) const;

    /**
     * @brief Inequality operator.
     *
     * @param other is a AVLTreeIterator to be compared.
     * @return true if this iterator is different to other (pointing to different nodes).
     */
    bool operator!=(AVLTreeIterator<T> const &other) const;

    /**
     * @brief Dereference operator.
     *
     * @return the item stored in the node pointed by this iterator.
     * @pre is_valid()
     */
    reference operator*() const;

    /**
     * @brief Dereference operator.
     *
     * @return the item stored in the node pointed by this iterator.
     * @pre is_valid()
     */
    pointer operator->() const;

    /** @{*/

    /** @name Modifiers */
    /** @{*/
    /**
     * @brief Increment operator.
     *
     * @return AVLTreeIterator<T>&
     * @pre is_valid()
     * @post Time analysis: O(H) where H is the height of the tree.
     */
    AVLTreeIterator<T> &operator++();

    /**
     * @brief Increment operator (postfix).
     *
     * @return AVLTreeIterator<T>
     * @pre is_valid()
     * @post Time analysis: O(H) where H is the height of the tree.
     */
    AVLTreeIterator<T> operator++(int);

    /**
     * @brief Decrement operator.
     *
     * @return AVLTreeIterator<T>&
     * @pre is_valid()
     * @post Time analysis: O(H) where H is the height of the tree.
     */
    AVLTreeIterator<T> &operator--();

    /**
     * @brief Decrement operator (postfix).
     *
     * @return AVLTreeIterator<T>
     * @pre is_valid()
     * @post Time analysis: O(H) where H is the height of the tree.
     */
    AVLTreeIterator<T> operator--(int);
    /** @} */
protected:
    // Allow AVLTree to create iterators to traverse the tree.
    friend class AVLTree<T>;

    /**
     * @brief Construct a new AVLTreeIterator object
     *
     * @param node is the node to be pointed by this iterator.
     */
    AVLTreeIterator(const typename AVLTNode<T>::Ref &node);

    // TODO: give a representatiion.
    AVLTree<T> tree_;
    typename AVLTNode<T>::Ref node_;
};

#include <avltree_iterator_imp.hpp>