Iterator.h

#ifndef theplu_yat_utility_ranking_iterator
#define theplu_yat_utility_ranking_iterator

// $Id: Iterator.h 4072 2021-08-20 05:40:18Z peter $

/*
  Copyright (C) 2021 Peter Johansson

  This file is part of the yat library, http://dev.thep.lu.se/yat

  The yat library is free software; you can redistribute it and/or
  modify it under the terms of the GNU General Public License as
  published by the Free Software Foundation; either version 3 of the
  License, or (at your option) any later version.

  The yat library is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with yat. If not, see <http://www.gnu.org/licenses/>.
*/

// This is a private file used by yat/utility/Ranking.h

#include "NodeBase.h"
#include "NodeValue.h"

#include <yat/utility/yat_assert.h>
#include <boost/iterator/iterator_facade.hpp>

#include <cstddef>
#include <iterator>

#include <iostream> // debug
namespace theplu {
namespace yat {
namespace utility {


  // namespace for internal classes used in class Ranking
  namespace ranking {

    template<typename T>
    class Iterator
      : public boost::iterator_facade<
      Iterator<T>, const T, std::bidirectional_iterator_tag
      >
    {
    public:
      Iterator(void);
      explicit Iterator(const NodeBase* node);
      const NodeBase* node_;
    private:
      friend class boost::iterator_core_access;
      const T& dereference(void) const;
      bool equal(Iterator other) const;
      void increment(void);
      void decrement(void);
    };

    template<typename T>
    Iterator<T>::Iterator(void)
      : node_(nullptr)
    {
    }


    template<typename T>
    Iterator<T>::Iterator(const NodeBase* node)
      : node_(node)
    {
      YAT_ASSERT(node);
    }


    template<typename T>
    const T& Iterator<T>::dereference(void) const
    {
      YAT_ASSERT(node_);
      YAT_ASSERT(node_->is_head_node()==false);
      // All nodes are NodeValue except head which is pointee of end
      // iterator and not dereferencable
      return static_cast<const NodeValue<T>*>(node_)->value();
    }


    template<typename T>
    bool Iterator<T>::equal(Iterator<T> other) const
    {
      return node_ == other.node_;
    }


    template<typename T>
    void Iterator<T>::increment(void)
    {
      YAT_ASSERT(node_);
      YAT_ASSERT(!node_->is_head_node());
      YAT_ASSERT(node_->validate());

      // If we have a right branch, go to the leftmost leaf in it.
      if (node_->right_) {
        node_ = node_->right_->left_most();
        YAT_ASSERT(node_);
        return;
      }

      // traverse up through ancestors until we are coming from left
      const NodeBase* child = node_;
      YAT_ASSERT(child->parent_);
      while (child->is_right_node()) {
        child = child->parent_; // traverse up
        YAT_ASSERT(child->parent_);
        YAT_ASSERT(child->validate());
      }

      node_ = child->parent_;
      YAT_ASSERT(node_);
    }


    template<typename T>
    void Iterator<T>::decrement(void)
    {
      YAT_ASSERT(node_);

      if (node_->is_head_node()) {
        node_ = node_->left_->right_most();
        return;
      }

      if (node_->left_) {
        node_ = node_->left_->right_most();
        YAT_ASSERT(node_);
        return;
      }

      // traverse up through ancestors until we are coming from right
      const NodeBase* child = node_;
      YAT_ASSERT(child->parent_);
      while (child->is_left_node()) {
        child = child->parent_;
        YAT_ASSERT(child->parent_);
      }

      node_ = child->parent_;
      YAT_ASSERT(node_);
    }
  } // end of namespace ranking


}}} // of namespace utility, yat, and theplu
#endif