iterator.hpp

 
#ifndef UFO_CONTAINER_DETAIL_TREE_MAP_ITERATOR_HPP
#define UFO_CONTAINER_DETAIL_TREE_MAP_ITERATOR_HPP
 
// UFO
#include <ufo/container/tree/index.hpp>
 
// STL
#include <cassert>
#include <cstddef>
#include <iterator>
#include <type_traits>
 
namespace ufo
{
// Forward declare
template <std::size_t Dim, class T>
class TreeMap;
 
template <bool Const, std::size_t Dim, class T>
class TreeMapIterator
{
 private:
    //
    // Friends
    //
 
    friend class TreeMapIterator<!Const, Dim, T>;
 
    friend class TreeMap<Dim, T>;
 
 private:
    static constexpr std::size_t const BF = TreeMap<Dim, T>::branchingFactor();
 
    using RawIterator =
        std::conditional_t<Const, typename TreeMap<Dim, T>::container_type::const_iterator,
                           typename TreeMap<Dim, T>::container_type::iterator>;
 
 public:
    //
    // Tags
    //
 
    using iterator_category = std::forward_iterator_tag;
    using difference_type   = std::ptrdiff_t;
    using value_type        = typename std::iterator_traits<RawIterator>::value_type;
    using reference         = typename std::iterator_traits<RawIterator>::reference;
    using pointer           = typename std::iterator_traits<RawIterator>::pointer;
 
    TreeMapIterator() = default;
 
    TreeMapIterator(TreeMapIterator const&) = default;
 
    // From non-const to const
    template <bool Const2, std::enable_if_t<Const && !Const2, bool> = true>
    TreeMapIterator(TreeMapIterator<Const2, Dim, T> const& other)
        : tm_(other.tm_)
        , root_(other.root_)
        , cur_(other.cur_)
        , it_(other.it_)
        , last_(other.last_)
    {
    }
 
    TreeMapIterator& operator++()
    {
        if (++it_ == last_) {
            nextNode();
        }
        return *this;
    }
 
    TreeMapIterator operator++(int)
    {
        TreeMapIterator tmp(*this);
        ++*this;
        return tmp;
    }
 
    reference operator*() const { return *it_; }
 
    pointer operator->() const { return &*it_; }
 
    template <bool Const2>
    bool operator==(TreeMapIterator<Const2, Dim, T> const& other)
    {
        return it_ == other.it_;
    }
 
    template <bool Const2>
    bool operator!=(TreeMapIterator<Const2, Dim, T> const& other)
    {
        return !(*this == other);
    }
 
 private:
    [[nodiscard]] bool returnable(TreeIndex node) const
    {
        return tm_->isPureLeaf(node) && !tm_->empty(node);
    }
 
    [[nodiscard]] bool traversable(TreeIndex node) const { return tm_->isParent(node); }
 
    void nextNode()
    {
        while (root_ != cur_) {
            if (BF - 1 == cur_.offset) {
                cur_ = tm_->parent(cur_);
                continue;
            }
 
            ++cur_.offset;
 
            if (nextNodeDownwards()) {
                return;
            }
        }
 
        // We have visited all nodes
        it_   = {};
        last_ = {};
    }
 
    bool nextNodeDownwards()
    {
        while (true) {
            if (returnable(cur_)) {
                it_   = tm_->values(cur_).begin();
                last_ = tm_->values(cur_).end();
                return true;
            } else if (traversable(cur_)) {
                cur_ = tm_->child(cur_, 0);
            } else {
                break;
            }
        }
        return false;
    }
 
    [[nodiscard]] RawIterator iterator() { return it_; }
 
 private:
    TreeMapIterator(TreeMap<Dim, T>* tm, TreeIndex node) : tm_(tm), root_(node), cur_(node)
    {
        if (nextNodeDownwards()) {
            return;
        }
 
        nextNode();
    }
 
    // From const to non-const
    template <bool Const2, std::enable_if_t<!Const && Const2, bool> = true>
    TreeMapIterator(TreeMapIterator<Const2, Dim, T> const& other)
        : tm_(other.tm_), root_(other.root_), cur_(other.cur_)
    {
        // Remove const from other.it_ and other.last_
        it_   = tm_->values(cur_).erase(other.it_, other.it_);
        last_ = tm_->values(cur_).erase(other.last_, other.last_);
    }
 
 private:
    TreeMap<Dim, T>* tm_ = nullptr;
 
    TreeIndex root_{};
    TreeIndex cur_{};
 
    RawIterator it_{};
    RawIterator last_{};
};
}  // namespace ufo
 
#endif  // UFO_CONTAINER_DETAIL_TREE_MAP_ITERATOR_HPP