yat/utility/ranking/Iterator.h

Code
Comments
Other
Rev Date Author Line
4064 05 Aug 21 peter 1 #ifndef theplu_yat_utility_ranking_iterator
4064 05 Aug 21 peter 2 #define theplu_yat_utility_ranking_iterator
4064 05 Aug 21 peter 3
4064 05 Aug 21 peter 4 // $Id$
4064 05 Aug 21 peter 5
4064 05 Aug 21 peter 6 /*
4064 05 Aug 21 peter 7   Copyright (C) 2021 Peter Johansson
4064 05 Aug 21 peter 8
4064 05 Aug 21 peter 9   This file is part of the yat library, http://dev.thep.lu.se/yat
4064 05 Aug 21 peter 10
4064 05 Aug 21 peter 11   The yat library is free software; you can redistribute it and/or
4064 05 Aug 21 peter 12   modify it under the terms of the GNU General Public License as
4064 05 Aug 21 peter 13   published by the Free Software Foundation; either version 3 of the
4064 05 Aug 21 peter 14   License, or (at your option) any later version.
4064 05 Aug 21 peter 15
4064 05 Aug 21 peter 16   The yat library is distributed in the hope that it will be useful,
4064 05 Aug 21 peter 17   but WITHOUT ANY WARRANTY; without even the implied warranty of
4064 05 Aug 21 peter 18   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
4064 05 Aug 21 peter 19   General Public License for more details.
4064 05 Aug 21 peter 20
4064 05 Aug 21 peter 21   You should have received a copy of the GNU General Public License
4064 05 Aug 21 peter 22   along with yat. If not, see <http://www.gnu.org/licenses/>.
4064 05 Aug 21 peter 23 */
4064 05 Aug 21 peter 24
4065 05 Aug 21 peter 25 // This is a private file used by yat/utility/Ranking.h
4065 05 Aug 21 peter 26
4064 05 Aug 21 peter 27 #include "NodeBase.h"
4064 05 Aug 21 peter 28 #include "NodeValue.h"
4064 05 Aug 21 peter 29
4064 05 Aug 21 peter 30 #include <yat/utility/yat_assert.h>
4064 05 Aug 21 peter 31 #include <boost/iterator/iterator_facade.hpp>
4064 05 Aug 21 peter 32
4064 05 Aug 21 peter 33 #include <cstddef>
4064 05 Aug 21 peter 34 #include <iterator>
4064 05 Aug 21 peter 35
4069 06 Aug 21 peter 36 #include <iostream> // debug
4064 05 Aug 21 peter 37 namespace theplu {
4064 05 Aug 21 peter 38 namespace yat {
4064 05 Aug 21 peter 39 namespace utility {
4064 05 Aug 21 peter 40
4065 05 Aug 21 peter 41   /// \cond IGNORE_DOXYGEN
4065 05 Aug 21 peter 42
4064 05 Aug 21 peter 43   // namespace for internal classes used in class Ranking
4064 05 Aug 21 peter 44   namespace ranking {
4064 05 Aug 21 peter 45
4064 05 Aug 21 peter 46     template<typename T>
4064 05 Aug 21 peter 47     class Iterator
4064 05 Aug 21 peter 48       : public boost::iterator_facade<
4064 05 Aug 21 peter 49       Iterator<T>, const T, std::bidirectional_iterator_tag
4064 05 Aug 21 peter 50       >
4064 05 Aug 21 peter 51     {
4064 05 Aug 21 peter 52     public:
4072 20 Aug 21 peter 53       Iterator(void);
4072 20 Aug 21 peter 54       explicit Iterator(const NodeBase* node);
4070 09 Aug 21 peter 55       const NodeBase* node_;
4064 05 Aug 21 peter 56     private:
4064 05 Aug 21 peter 57       friend class boost::iterator_core_access;
4064 05 Aug 21 peter 58       const T& dereference(void) const;
4064 05 Aug 21 peter 59       bool equal(Iterator other) const;
4064 05 Aug 21 peter 60       void increment(void);
4064 05 Aug 21 peter 61       void decrement(void);
4064 05 Aug 21 peter 62     };
4064 05 Aug 21 peter 63
4064 05 Aug 21 peter 64     /// Implementations
4064 05 Aug 21 peter 65     template<typename T>
4072 20 Aug 21 peter 66     Iterator<T>::Iterator(void)
4072 20 Aug 21 peter 67       : node_(nullptr)
4072 20 Aug 21 peter 68     {
4072 20 Aug 21 peter 69     }
4072 20 Aug 21 peter 70
4072 20 Aug 21 peter 71
4072 20 Aug 21 peter 72     template<typename T>
4064 05 Aug 21 peter 73     Iterator<T>::Iterator(const NodeBase* node)
4064 05 Aug 21 peter 74       : node_(node)
4069 06 Aug 21 peter 75     {
4072 20 Aug 21 peter 76       YAT_ASSERT(node);
4069 06 Aug 21 peter 77     }
4064 05 Aug 21 peter 78
4064 05 Aug 21 peter 79
4064 05 Aug 21 peter 80     template<typename T>
4064 05 Aug 21 peter 81     const T& Iterator<T>::dereference(void) const
4064 05 Aug 21 peter 82     {
4064 05 Aug 21 peter 83       YAT_ASSERT(node_);
4070 09 Aug 21 peter 84       YAT_ASSERT(node_->is_head_node()==false);
4064 05 Aug 21 peter 85       // All nodes are NodeValue except head which is pointee of end
4064 05 Aug 21 peter 86       // iterator and not dereferencable
4064 05 Aug 21 peter 87       return static_cast<const NodeValue<T>*>(node_)->value();
4064 05 Aug 21 peter 88     }
4064 05 Aug 21 peter 89
4064 05 Aug 21 peter 90
4064 05 Aug 21 peter 91     template<typename T>
4064 05 Aug 21 peter 92     bool Iterator<T>::equal(Iterator<T> other) const
4064 05 Aug 21 peter 93     {
4064 05 Aug 21 peter 94       return node_ == other.node_;
4064 05 Aug 21 peter 95     }
4064 05 Aug 21 peter 96
4064 05 Aug 21 peter 97
4064 05 Aug 21 peter 98     template<typename T>
4064 05 Aug 21 peter 99     void Iterator<T>::increment(void)
4064 05 Aug 21 peter 100     {
4064 05 Aug 21 peter 101       YAT_ASSERT(node_);
4064 05 Aug 21 peter 102       YAT_ASSERT(!node_->is_head_node());
4072 20 Aug 21 peter 103       YAT_ASSERT(node_->validate());
4064 05 Aug 21 peter 104
4064 05 Aug 21 peter 105       // If we have a right branch, go to the leftmost leaf in it.
4064 05 Aug 21 peter 106       if (node_->right_) {
4064 05 Aug 21 peter 107         node_ = node_->right_->left_most();
4064 05 Aug 21 peter 108         YAT_ASSERT(node_);
4064 05 Aug 21 peter 109         return;
4064 05 Aug 21 peter 110       }
4064 05 Aug 21 peter 111
4064 05 Aug 21 peter 112       // traverse up through ancestors until we are coming from left
4064 05 Aug 21 peter 113       const NodeBase* child = node_;
4064 05 Aug 21 peter 114       YAT_ASSERT(child->parent_);
4064 05 Aug 21 peter 115       while (child->is_right_node()) {
4072 20 Aug 21 peter 116         child = child->parent_; // traverse up
4072 20 Aug 21 peter 117         YAT_ASSERT(child->parent_);
4072 20 Aug 21 peter 118         YAT_ASSERT(child->validate());
4064 05 Aug 21 peter 119       }
4064 05 Aug 21 peter 120
4064 05 Aug 21 peter 121       node_ = child->parent_;
4064 05 Aug 21 peter 122       YAT_ASSERT(node_);
4064 05 Aug 21 peter 123     }
4064 05 Aug 21 peter 124
4064 05 Aug 21 peter 125
4064 05 Aug 21 peter 126     template<typename T>
4064 05 Aug 21 peter 127     void Iterator<T>::decrement(void)
4064 05 Aug 21 peter 128     {
4064 05 Aug 21 peter 129       YAT_ASSERT(node_);
4064 05 Aug 21 peter 130
4064 05 Aug 21 peter 131       if (node_->is_head_node()) {
4072 20 Aug 21 peter 132         node_ = node_->left_->right_most();
4064 05 Aug 21 peter 133         return;
4064 05 Aug 21 peter 134       }
4064 05 Aug 21 peter 135
4064 05 Aug 21 peter 136       if (node_->left_) {
4064 05 Aug 21 peter 137         node_ = node_->left_->right_most();
4064 05 Aug 21 peter 138         YAT_ASSERT(node_);
4064 05 Aug 21 peter 139         return;
4064 05 Aug 21 peter 140       }
4064 05 Aug 21 peter 141
4064 05 Aug 21 peter 142       // traverse up through ancestors until we are coming from right
4064 05 Aug 21 peter 143       const NodeBase* child = node_;
4064 05 Aug 21 peter 144       YAT_ASSERT(child->parent_);
4064 05 Aug 21 peter 145       while (child->is_left_node()) {
4064 05 Aug 21 peter 146         child = child->parent_;
4072 20 Aug 21 peter 147         YAT_ASSERT(child->parent_);
4064 05 Aug 21 peter 148       }
4064 05 Aug 21 peter 149
4064 05 Aug 21 peter 150       node_ = child->parent_;
4064 05 Aug 21 peter 151       YAT_ASSERT(node_);
4064 05 Aug 21 peter 152     }
4064 05 Aug 21 peter 153   } // end of namespace ranking
4064 05 Aug 21 peter 154
4065 05 Aug 21 peter 155   /// \endcond
4065 05 Aug 21 peter 156
4064 05 Aug 21 peter 157 }}} // of namespace utility, yat, and theplu
4064 05 Aug 21 peter 158 #endif

Generated on Sat Oct 14 02:24:15 2023 (UTC) by svndigest 0.11.2pre (dev build 1672)