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