1 // Boost.Geometry Index
2 //
3 // R-tree iterator visitor implementation
4 //
5 // Copyright (c) 2011-2015 Adam Wulkiewicz, Lodz, Poland.
6 //
7 // Use, modification and distribution is subject to the Boost Software License,
8 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
9 // http://www.boost.org/LICENSE_1_0.txt)
10 
11 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_ITERATOR_HPP
12 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_ITERATOR_HPP
13 
14 namespace boost { namespace geometry { namespace index {
15 
16 namespace detail { namespace rtree { namespace visitors {
17 
18 template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
19 class iterator
20     : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, true>::type
21 {
22 public:
23     typedef typename rtree::node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type node;
24     typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
25     typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
26 
27     typedef typename Allocators::size_type size_type;
28     typedef typename Allocators::const_reference const_reference;
29     typedef typename Allocators::node_pointer node_pointer;
30 
31     typedef typename rtree::elements_type<internal_node>::type::const_iterator internal_iterator;
32     typedef typename rtree::elements_type<leaf>::type leaf_elements;
33     typedef typename rtree::elements_type<leaf>::type::const_iterator leaf_iterator;
34 
iterator()35     inline iterator()
36         : m_values(NULL)
37         , m_current()
38     {}
39 
operator ()(internal_node const & n)40     inline void operator()(internal_node const& n)
41     {
42         typedef typename rtree::elements_type<internal_node>::type elements_type;
43         elements_type const& elements = rtree::elements(n);
44 
45         m_internal_stack.push_back(std::make_pair(elements.begin(), elements.end()));
46     }
47 
operator ()(leaf const & n)48     inline void operator()(leaf const& n)
49     {
50         m_values = ::boost::addressof(rtree::elements(n));
51         m_current = rtree::elements(n).begin();
52     }
53 
dereference() const54     const_reference dereference() const
55     {
56         BOOST_GEOMETRY_INDEX_ASSERT(m_values, "not dereferencable");
57         return *m_current;
58     }
59 
initialize(node_pointer root)60     void initialize(node_pointer root)
61     {
62         rtree::apply_visitor(*this, *root);
63         search_value();
64     }
65 
increment()66     void increment()
67     {
68         ++m_current;
69         search_value();
70     }
71 
search_value()72     void search_value()
73     {
74         for (;;)
75         {
76             // if leaf is choosen, move to the next value in leaf
77             if ( m_values )
78             {
79                 // there are more values in the current leaf
80                 if ( m_current != m_values->end() )
81                 {
82                     return;
83                 }
84                 // no more values, clear current leaf
85                 else
86                 {
87                     m_values = 0;
88                 }
89             }
90             // if leaf isn't choosen, move to the next leaf
91             else
92             {
93                 // return if there is no more nodes to traverse
94                 if ( m_internal_stack.empty() )
95                     return;
96 
97                 // no more children in current node, remove it from stack
98                 if ( m_internal_stack.back().first == m_internal_stack.back().second )
99                 {
100                     m_internal_stack.pop_back();
101                     continue;
102                 }
103 
104                 internal_iterator it = m_internal_stack.back().first;
105                 ++m_internal_stack.back().first;
106 
107                 // push the next node to the stack
108                 rtree::apply_visitor(*this, *(it->second));
109             }
110         }
111     }
112 
is_end() const113     bool is_end() const
114     {
115         return 0 == m_values;
116     }
117 
operator ==(iterator const & l,iterator const & r)118     friend bool operator==(iterator const& l, iterator const& r)
119     {
120         return (l.m_values == r.m_values) && (0 == l.m_values || l.m_current == r.m_current );
121     }
122 
123 private:
124 
125     std::vector< std::pair<internal_iterator, internal_iterator> > m_internal_stack;
126     const leaf_elements * m_values;
127     leaf_iterator m_current;
128 };
129 
130 }}} // namespace detail::rtree::visitors
131 
132 }}} // namespace boost::geometry::index
133 
134 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_ITERATOR_HPP
135