rtree/visitors/iterator.hpp

0001 // Boost.Geometry Index
0002 //
0003 // R-tree iterator visitor implementation
0004 //
0005 // Copyright (c) 2011-2015 Adam Wulkiewicz, Lodz, Poland.
0006 //
0007 // This file was modified by Oracle on 2021-2023.
0008 // Modifications copyright (c) 2021-2023 Oracle and/or its affiliates.
0009 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0010 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0011 //
0012 // Use, modification and distribution is subject to the Boost Software License,
0013 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0014 // http://www.boost.org/LICENSE_1_0.txt)
0015
0016 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_ITERATOR_HPP
0017 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_ITERATOR_HPP
0018
0019 #include <boost/geometry/index/detail/rtree/node/concept.hpp>
0020 #include <boost/geometry/index/detail/rtree/node/node_elements.hpp>
0021 #include <boost/geometry/index/detail/rtree/node/variant_visitor.hpp>
0022
0023 namespace boost { namespace geometry { namespace index {
0024
0025 namespace detail { namespace rtree { namespace visitors {
0026
0027 template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
0028 class iterator
0029     : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, true>::type
0030 {
0031 public:
0032     typedef typename rtree::node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type node;
0033     typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
0034     typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
0035
0036     typedef typename Allocators::size_type size_type;
0037     typedef typename Allocators::const_reference const_reference;
0038     typedef typename Allocators::node_pointer node_pointer;
0039
0040     typedef typename rtree::elements_type<internal_node>::type::const_iterator internal_iterator;
0041     typedef typename rtree::elements_type<leaf>::type leaf_elements;
0042     typedef typename rtree::elements_type<leaf>::type::const_iterator leaf_iterator;
0043
0044     inline iterator()
0045         : m_values(NULL)
0046         , m_current()
0047     {}
0048
0049     inline void operator()(internal_node const& n)
0050     {
0051         typedef typename rtree::elements_type<internal_node>::type elements_type;
0052         elements_type const& elements = rtree::elements(n);
0053
0054         m_internal_stack.push_back(std::make_pair(elements.begin(), elements.end()));
0055     }
0056
0057     inline void operator()(leaf const& n)
0058     {
0059         m_values = ::boost::addressof(rtree::elements(n));
0060         m_current = rtree::elements(n).begin();
0061     }
0062
0063     const_reference dereference() const
0064     {
0065         BOOST_GEOMETRY_INDEX_ASSERT(m_values, "not dereferencable");
0066         return *m_current;
0067     }
0068
0069     void initialize(node_pointer root)
0070     {
0071         rtree::apply_visitor(*this, *root);
0072         search_value();
0073     }
0074
0075     void increment()
0076     {
0077         ++m_current;
0078         search_value();
0079     }
0080
0081     void search_value()
0082     {
0083         for (;;)
0084         {
0085             // if leaf is choosen, move to the next value in leaf
0086             if ( m_values )
0087             {
0088                 // there are more values in the current leaf
0089                 if ( m_current != m_values->end() )
0090                 {
0091                     return;
0092                 }
0093                 // no more values, clear current leaf
0094                 else
0095                 {
0096                     m_values = 0;
0097                 }
0098             }
0099             // if leaf isn't choosen, move to the next leaf
0100             else
0101             {
0102                 // return if there is no more nodes to traverse
0103                 if ( m_internal_stack.empty() )
0104                     return;
0105
0106                 // no more children in current node, remove it from stack
0107                 if ( m_internal_stack.back().first == m_internal_stack.back().second )
0108                 {
0109                     m_internal_stack.pop_back();
0110                     continue;
0111                 }
0112
0113                 internal_iterator it = m_internal_stack.back().first;
0114                 ++m_internal_stack.back().first;
0115
0116                 // push the next node to the stack
0117                 rtree::apply_visitor(*this, *(it->second));
0118             }
0119         }
0120     }
0121
0122     bool is_end() const
0123     {
0124         return 0 == m_values;
0125     }
0126
0127     friend bool operator==(iterator const& l, iterator const& r)
0128     {
0129         return (l.m_values == r.m_values) && (0 == l.m_values || l.m_current == r.m_current );
0130     }
0131
0132 private:
0133
0134     std::vector< std::pair<internal_iterator, internal_iterator> > m_internal_stack;
0135     const leaf_elements * m_values;
0136     leaf_iterator m_current;
0137 };
0138
0139 }}} // namespace detail::rtree::visitors
0140
0141 }}} // namespace boost::geometry::index
0142
0143 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_ITERATOR_HPP