FPrePostOrderNodeIterator.hpp 5.58 KB
Newer Older
1 2 3 4 5
#ifndef _SCALFMM____ORDER_NODE_ITERATOR_HPP_
#define _SCALFMM____ORDER_NODE_ITERATOR_HPP_

#include "FNodeIterator.hpp"

6 7 8
#define NAMESPACE_START namespace scalfmm { namespace details { namespace adaptive_iterator
#define NAMESPACE_END } }

9 10 11 12 13 14 15
namespace scalfmm {
    namespace tests {
        struct test_PostOrderNodeIterator;
        struct test_PreOrderNodeIterator;
    }
}

16
NAMESPACE_START {
17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162

    enum class NodeIteratorOrder {preorder, postorder};

    template<class Node, NodeIteratorOrder it_type>
    class __OrderNodeIterator : public FNodeIterator<__OrderNodeIterator<Node, it_type>, Node> {

        friend scalfmm::tests::test_PostOrderNodeIterator;
        friend scalfmm::tests::test_PreOrderNodeIterator;

        using base_t = FNodeIterator<__OrderNodeIterator<Node, it_type>, Node>;
        using Direction = typename base_t::Direction;

    public:

        friend base_t;
        using base_t::base_t;
        using base_t::operator++;
        using base_t::operator--;

        __OrderNodeIterator& operator++() {
            if(it_type == NodeIteratorOrder::preorder) {
                return move_iterator_prefix<Direction::forwards>();
            } else {
                return move_iterator_postfix<Direction::forwards>();
            }
        }

        __OrderNodeIterator& operator--() {
            if(it_type == NodeIteratorOrder::preorder) {
                return move_iterator_postfix<Direction::backwards>();
            } else {
                return move_iterator_prefix<Direction::backwards>();
            }
        }


    protected:


        /** Moves the cursor to the first node
         *
         * Resets the iterator to a valid state.
         */
        template<Direction dir>
        __OrderNodeIterator& move_to_boundary() {

            base_t::template goto_root<dir>();

            if( (it_type == NodeIteratorOrder::preorder
                 && dir == Direction::backwards)
                || (it_type == NodeIteratorOrder::postorder
                    && dir == Direction::forwards) )
            {
                while(! this->_cur->is_leaf()) {
                    base_t::template move_down<dir>();
                }
            }
            return *this;
        }


        ////////////// POSTORDER TRAVERSAL /////////////////
        template<Direction dir>
        __OrderNodeIterator& move_iterator_postfix() {
            if(base_t::template is_other_end<dir>()) {
                return move_to_boundary<dir>();
            }
            if(base_t::template is_end<dir>()) {
                return *this;
            }
            return next_postfix<dir>();
        }

        template<Direction dir>
        __OrderNodeIterator& next_postfix() {
            // Leave current leaf
            if(!this->_cur_state.empty()) {
                base_t::move_up();
            }
            // If we visited all the children of the node, we move up
            if(!this->_cur_state.empty() && base_t::template at_last_child<dir>()) {
                if(dir == Direction::backwards) {
                    --(this->_cur_state.back());
                } else {
                    ++(this->_cur_state.back());
                }
                return *this;
            }
            // Moving too far up means we got to the end of the tree
            if(this->_cur_state.empty()) {
                base_t::template set_end<dir>();
                return *this;
            }
            // Once we moved up enough, we move down to the next node
            while(! this->_cur->is_leaf()) {
                base_t::template move_down<dir>();
            }
            return *this;
        }

        ////////////// PREORDER TRAVERSAL //////////////////
        template<Direction dir>
        __OrderNodeIterator& move_iterator_prefix() {
            if(base_t::template is_other_end<dir>()) {
                return move_to_boundary<dir>();
            }
            if(base_t::template is_end<dir>()) {
                return *this;
            }
            if(this->_cur->is_leaf()) {
                return leaf_next_prefix<dir>();
            } else {
                return node_next_prefix<dir>();
            }
        }

        template<Direction dir>
        __OrderNodeIterator& leaf_next_prefix() {
            // Leave current leaf
            if(!this->_cur_state.empty()) {
                base_t::move_up();
            }
            // If we visited all the children of the node, we move up
            while(!this->_cur_state.empty() && base_t::template at_last_child<dir>()) {
                base_t::move_up();
            }
            // Moving too far up means we got to the end of the tree
            if(this->_cur_state.empty()) {
                base_t::template set_end<dir>();
                return *this;
            }
            // Once we moved up enough, we move down to the next node
            base_t::template move_down<dir>();
            return *this;
        }

        template<Direction dir>
        __OrderNodeIterator& node_next_prefix() {
            base_t::template move_down<dir>();
            return *this;
        }


        ////////////////////////////////////////////////////////////
    };

163 164 165 166 167 168 169
} NAMESPACE_END


#undef NAMESPACE_START
#undef NAMESPACE_END


170
template<class Node>
171 172
using FPreOrderNodeIterator = scalfmm::details::adaptive_iterator::
    __OrderNodeIterator<Node,scalfmm::details::adaptive_iterator::
173 174
                        NodeIteratorOrder::preorder>;
template<class Node>
175 176
using FPostOrderNodeIterator = scalfmm::details::adaptive_iterator::
    __OrderNodeIterator<Node,scalfmm::details::adaptive_iterator::
177 178 179 180
                        NodeIteratorOrder::postorder>;


#endif