_avl_iterator.hpp

Go to the documentation of this file.

 
 
#pragma once
 
#include <memory>
 
namespace datastructures {
 
template <class TKey, class TValue, class TKeyComp, class TAlloc>
class map;
 
namespace detail {
 
template <class TTree, bool is_const>
class avl_iterator {
  private:
    using tree_type = TTree;
 
    using alloc_traits = typename std::allocator_traits<
        typename std::allocator_traits<typename tree_type::allocator_type>::
            template rebind_alloc<typename tree_type::item_type>>;
 
  public:
    using iterator_category = std::bidirectional_iterator_tag;
 
    using value_type = typename tree_type::item_type;
 
    using difference_type = typename alloc_traits::difference_type;
 
    using pointer =
        std::conditional_t<is_const, typename alloc_traits::const_pointer,
                           typename alloc_traits::pointer>;
 
    using reference =
        std::conditional_t<is_const, const value_type &, value_type &>;
 
    using iterator_concept = std::bidirectional_iterator_tag;
 
  private:
    friend class avl_iterator<tree_type, true>;
 
    template <class, class, class, class>
    friend class ::datastructures::map;
 
    using node_ptr = tree_type::node_ptr;
 
    using tree_ptr = const tree_type *;
 
    tree_ptr tree;
    node_ptr node;
 
  public:
    // ==== Constructors & Assignments ====
 
    avl_iterator(tree_ptr tree, node_ptr node) noexcept
        : tree(tree), node(node) {}
 
    avl_iterator() noexcept : avl_iterator(nullptr, nullptr) {}
 
    avl_iterator(const avl_iterator &other) noexcept {
        tree = other.tree;
        node = other.node;
    }
 
    avl_iterator &operator=(const avl_iterator &other) noexcept {
        tree = other.tree;
        node = other.node;
 
        return *this;
    }
 
    ~avl_iterator() noexcept = default;
 
    avl_iterator(const avl_iterator<tree_type, false> &other) noexcept
        requires(is_const)
        : node(other.node) {}
 
    reference operator*() const noexcept {
        return node->item;
    }
    pointer operator->() const noexcept {
        return &node->item;
    }
 
    avl_iterator &operator++() noexcept {
        node = tree->successor(node);
        return *this;
    }
 
    avl_iterator operator++(int) noexcept {
        avl_iterator tmp(*this);
        ++(*this);
        return tmp;
    }
 
    avl_iterator &operator--() noexcept {
        node = (node == nullptr) ? tree->max_from(tree->get_root())
                                 : tree->predecessor(node);
        return *this;
    }
 
    avl_iterator operator--(int) noexcept {
        avl_iterator tmp(*this);
        --(*this);
        return tmp;
    }
 
    bool operator==(const avl_iterator &other) const noexcept {
        return tree == other.tree && node == other.node;
    }
 
    bool operator!=(const avl_iterator &other) const noexcept {
        return !(*this == other);
    }
};
 
} // namespace detail
} // namespace datastructures