Branch data Line data Source code
1 : : /* Copyright 2003-2005 Daniel F. Savarese
2 : : * Copyright 2006-2009 Savarese Software Research Corporation
3 : : *
4 : : * Licensed under the Apache License, Version 2.0 (the "License");
5 : : * you may not use this file except in compliance with the License.
6 : : * You may obtain a copy of the License at
7 : : *
8 : : * https://www.savarese.com/software/ApacheLicense-2.0
9 : : *
10 : : * Unless required by applicable law or agreed to in writing, software
11 : : * distributed under the License is distributed on an "AS IS" BASIS,
12 : : * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 : : * See the License for the specific language governing permissions and
14 : : * limitations under the License.
15 : : */
16 : :
17 : : #ifndef __SSRC_SPATIAL_DETAIL_KDTREE_RANGE_SEARCH_ITERATOR_H
18 : : #define __SSRC_SPATIAL_DETAIL_KDTREE_RANGE_SEARCH_ITERATOR_H
19 : :
20 : : #include <ssrc/libssrckdtree-packages.h>
21 : :
22 : : #include <iterator>
23 : : #include <stack>
24 : : #include <array>
25 : :
26 : : __BEGIN_NS_SSRC_SPATIAL
27 : :
28 : : namespace detail {
29 : :
30 : : template<typename TreeTraits, typename Region>
31 : 1032784 : class kd_tree_range_search_iterator :
32 : : public
33 : : std::iterator<std::forward_iterator_tag,typename TreeTraits::value_type>
34 : : {
35 : : public:
36 : : typedef TreeTraits traits;
37 : : typedef typename traits::node_type node_type;
38 : : typedef typename traits::key_type key_type;
39 : : typedef typename traits::value_type value_type;
40 : : typedef typename traits::pointer pointer;
41 : : typedef typename traits::const_pointer const_pointer;
42 : : typedef typename traits::reference reference;
43 : : typedef typename traits::const_reference const_reference;
44 : : typedef typename traits::discriminator_type discriminator_type;
45 : : typedef Region region_type;
46 : :
47 : : private:
48 : : #ifdef LIBSSRCKDTREE_HAVE_EXTENDED_FRIEND_DECLARATIONS
49 : : friend traits::const_iterator;
50 : : friend traits::tree_type;
51 : : #else
52 : : friend class traits::const_iterator;
53 : : friend class traits::tree_type;
54 : : #endif
55 : : typedef std::stack<node_type *> stack_type;
56 : :
57 : : node_type *_node;
58 : : stack_type _stack;
59 : : discriminator_type _discriminator;
60 : : region_type _region;
61 : :
62 : 688161 : void advance() {
63 [ + + ][ + + ]: 995796 : while(!_stack.empty()) {
[ + + ][ + + ]
[ + + ][ + + ]
64 : 995454 : node_type *node = _stack.top();
65 : 995454 : _stack.pop();
66 : :
67 : 995454 : _discriminator = node->discriminator;
68 : :
69 : : // <= instead of < because values >= are in right subtree.
70 [ + - ][ + + ]: 995454 : if(node->point()[_discriminator] <= _region.upper[_discriminator] &&
[ + + + - ]
[ + + ]
[ + + + - ]
[ + + ]
[ + + + - ]
[ + + ]
[ + + + - ]
[ + + ]
[ + + + - ]
[ + + ][ + + ]
71 : : node->child_high != 0)
72 : 617536 : _stack.push(node->child_high);
73 : :
74 : : // Push left subtree last so that it will be searched first
75 [ + + ][ + + ]: 995454 : if(node->point()[_discriminator] > _region.lower[_discriminator] &&
[ + + ][ + - ]
[ + + ][ + + ]
[ + - ][ + + ]
[ + + ][ + + ]
[ + + ][ + + ]
[ + + ][ + + ]
[ + + ][ + + ]
[ + + ][ + + ]
76 : : node->child_low != 0)
77 : 418591 : _stack.push(node->child_low);
78 : :
79 [ + - ][ + - ]: 995454 : if(_region.contains(node->point())) {
[ + - ][ + + ]
[ + + ][ + + ]
80 : 687819 : _node = node;
81 : 688161 : return;
82 : : }
83 : : }
84 : 342 : _node = 0;
85 : : }
86 : :
87 : 344067 : void advance_to_lower() {
88 [ + - ][ + - ]: 5374887 : while(!_stack.empty()) {
[ + - ][ + - ]
[ + - ][ + - ]
89 : 5374887 : node_type *node = _stack.top();
90 : 5374887 : _stack.pop();
91 : :
92 : 5374887 : _discriminator = node->discriminator;
93 : :
94 : : // <= instead of < because values >= are in right subtree.
95 [ + - ][ + + ]: 5374887 : if(node->point()[_discriminator] <= _region.upper[_discriminator] &&
[ + + + - ]
[ + + ]
[ + + + - ]
[ + + ]
[ + + + - ]
[ + + ]
[ + + + - ]
[ + + ]
[ + + + - ]
[ + + ][ + + ]
96 : : node->child_high != 0)
97 : 5063064 : _stack.push(node->child_high);
98 : :
99 : : // Push left subtree last so that it will be searched first.
100 [ + + ][ + - ]: 5374887 : if(node->point()[_discriminator] > _region.lower[_discriminator] &&
[ + + ][ + + ]
[ + - ][ + + ]
[ + + ][ + - ]
[ + + ][ + + ]
[ + - ][ + + ]
[ + + ][ + - ]
[ + + ][ + + ]
[ + - ][ + + ]
101 : : node->child_low != 0)
102 : 2544315 : _stack.push(node->child_low);
103 : :
104 [ + + ][ + + ]: 5374887 : if(node->point() == _region.lower) {
[ + + ][ + + ]
[ + + ][ + + ]
105 : 344067 : _node = node;
106 : 344067 : return;
107 : : }
108 : : }
109 : 0 : _node = 0;
110 : : }
111 : :
112 : : public:
113 : : // For now, we rely on default assignment operator and for
114 : : // const_iterator the default copy constructor. They are
115 : : // unacceptable only if Discriminator, Point, or Region types allocate and
116 : : // destroy memory referenced by pointers, which for now we forbid.
117 : :
118 : 128 : explicit kd_tree_range_search_iterator(node_type * const node = 0) :
119 [ + - ][ + - ]: 128 : _node(node), _stack(), _discriminator(), _region()
[ + - ][ + - ]
[ + - ][ + - ]
120 : 128 : { }
121 : :
122 : : // Copy constructor to allow const_iterator to be created from iterator
123 : 540937 : kd_tree_range_search_iterator(const typename traits::iterator & rsi) :
124 : : _node(rsi._node), _stack(rsi._stack), _discriminator(rsi._discriminator),
125 : 540937 : _region(rsi._region)
126 : 540937 : { }
127 : :
128 : 344121 : kd_tree_range_search_iterator(const region_type & region,
129 : : node_type* const root,
130 : : bool find = false) :
131 [ + - ][ + - ]: 344121 : _node(root), _stack(), _discriminator(), _region(region)
[ + - ][ + - ]
[ + - ][ + - ]
132 : : {
133 [ + - + + : 344121 : if(_node != 0) {
+ - + + +
- + + ]
134 [ + - ][ + - ]: 344112 : _stack.push(_node);
[ + - ][ + - ]
[ + - ][ + - ]
135 [ + + ][ + + ]: 344112 : if(!find)
[ + + ][ + + ]
[ + + ][ + + ]
136 [ + - ][ + - ]: 45 : advance();
[ + - ][ + - ]
[ + - ][ + - ]
137 : : else
138 [ + - ][ + - ]: 344067 : advance_to_lower();
[ + - ][ + - ]
[ + - ][ + - ]
139 : : }
140 : 344121 : }
141 : :
142 : 491660 : bool end_of_range() const {
143 : 491660 : return (_node == 0);
144 : : }
145 : :
146 : 196608 : reference operator*() {
147 : 196608 : return _node->pair();
148 : : }
149 : :
150 : : const_reference operator*() const {
151 : : return _node->pair();
152 : : }
153 : :
154 : 1130661 : pointer operator->() {
155 : 1130661 : return &(_node->pair());
156 : : }
157 : :
158 : : const_pointer operator->() const {
159 : : return &(_node->pair());
160 : : }
161 : :
162 : 442243 : kd_tree_range_search_iterator & operator++() {
163 : 442243 : advance();
164 : 442243 : return *this;
165 : : }
166 : :
167 : : kd_tree_range_search_iterator operator++(int) {
168 : : kd_tree_range_search_iterator old(*this);
169 : : advance();
170 : : return old;
171 : : }
172 : :
173 : 15 : bool operator==(const kd_tree_range_search_iterator & rsi) const {
174 : 15 : return (_node == rsi._node);
175 : : }
176 : :
177 : 540713 : bool operator!=(const kd_tree_range_search_iterator & rsi) const {
178 : 540713 : return (_node != rsi._node);
179 : : }
180 : : };
181 : :
182 : : }
183 : :
184 : : __END_NS_SSRC_SPATIAL
185 : :
186 : : #endif
|
