Horizon
shape_index_list.h
1/*
2 * This program source code file is part of KiCad, a free EDA CAD application.
3 *
4 * Copyright (C) 2013 CERN
5 * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
6 *
7 * This program is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License
9 * as published by the Free Software Foundation; either version 2
10 * of the License, or (at your option) any later version.
11 *
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, you may find one here:
19 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
20 * or you may search the http://www.gnu.org website for the version 2 license,
21 * or you may write to the Free Software Foundation, Inc.,
22 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
23 */
24
25#ifndef __SHAPE_INDEX_LIST_H
26#define __SHAPE_INDEX_LIST_H
27
28template <class T>
29const SHAPE* defaultShapeFunctor( const T aItem )
30{
31 return aItem->Shape();
32}
33
34template <class T, const SHAPE* (ShapeFunctor) (const T) = defaultShapeFunctor<T> >
36{
37 struct SHAPE_ENTRY
38 {
39 SHAPE_ENTRY( T aParent )
40 {
41 shape = ShapeFunctor( aParent );
42 bbox = shape->BBox( 0 );
43 parent = aParent;
44 }
45
46 ~SHAPE_ENTRY()
47 {
48 }
49
50 T parent;
51 const SHAPE* shape;
52 BOX2I bbox;
53 };
54
55 typedef std::vector<SHAPE_ENTRY> SHAPE_VEC;
56 typedef typename std::vector<SHAPE_ENTRY>::iterator SHAPE_VEC_ITER;
57
58public:
59 // "Normal" iterator interface, for STL algorithms.
61 {
62 public:
63 iterator()
64 {}
65
66 iterator( SHAPE_VEC_ITER aCurrent ) :
67 m_current( aCurrent )
68 {}
69
70 iterator( const iterator& aB ) :
71 m_current( aB.m_current )
72 {}
73
74 T operator*() const
75 {
76 return (*m_current).parent;
77 }
78
79 void operator++()
80 {
81 ++m_current;
82 }
83
84 iterator& operator++( int aDummy )
85 {
86 ++m_current;
87 return *this;
88 }
89
90 bool operator==( const iterator& aRhs ) const
91 {
92 return m_current == aRhs.m_current;
93 }
94
95 bool operator!=( const iterator& aRhs ) const
96 {
97 return m_current != aRhs.m_current;
98 }
99
100 const iterator& operator=( const iterator& aRhs )
101 {
102 m_current = aRhs.m_current;
103 return *this;
104 }
105
106 private:
107 SHAPE_VEC_ITER m_current;
108 };
109
110 // "Query" iterator, for iterating over a set of spatially matching shapes.
112 {
113 public:
115 {
116 }
117
118 query_iterator( SHAPE_VEC_ITER aCurrent, SHAPE_VEC_ITER aEnd, SHAPE* aShape,
119 int aMinDistance, bool aExact ) :
120 m_end( aEnd ),
121 m_current( aCurrent ),
122 m_shape( aShape ),
123 m_minDistance( aMinDistance ),
124 m_exact( aExact )
125 {
126 if( aShape )
127 {
128 m_refBBox = aShape->BBox();
129 next();
130 }
131 }
132
133 query_iterator( const query_iterator& aB ) :
134 m_end( aB.m_end ),
135 m_current( aB.m_current ),
136 m_shape( aB.m_shape ),
137 m_minDistance( aB.m_minDistance ),
138 m_exact( aB.m_exact ),
139 m_refBBox( aB.m_refBBox )
140 {
141 }
142
143 T operator*() const
144 {
145 return (*m_current).parent;
146 }
147
148 query_iterator& operator++()
149 {
150 ++m_current;
151 next();
152 return *this;
153 }
154
155 query_iterator& operator++( int aDummy )
156 {
157 ++m_current;
158 next();
159 return *this;
160 }
161
162 bool operator==( const query_iterator& aRhs ) const
163 {
164 return m_current == aRhs.m_current;
165 }
166
167 bool operator!=( const query_iterator& aRhs ) const
168 {
169 return m_current != aRhs.m_current;
170 }
171
172 const query_iterator& operator=( const query_iterator& aRhs )
173 {
174 m_end = aRhs.m_end;
175 m_current = aRhs.m_current;
176 m_shape = aRhs.m_shape;
177 m_minDistance = aRhs.m_minDistance;
178 m_exact = aRhs.m_exact;
179 m_refBBox = aRhs.m_refBBox;
180 return *this;
181 }
182
183 private:
184 void next()
185 {
186 while( m_current != m_end )
187 {
188 if( m_refBBox.Distance( m_current->bbox ) <= m_minDistance )
189 {
190 if( !m_exact || m_current->shape->Collide( m_shape, m_minDistance ) )
191 return;
192 }
193
194 ++m_current;
195 }
196 }
197
198 SHAPE_VEC_ITER m_end;
199 SHAPE_VEC_ITER m_current;
200 BOX2I m_refBBox;
201 bool m_exact;
202 SHAPE* m_shape;
203 int m_minDistance;
204 };
205
206 void Add( T aItem )
207 {
208 SHAPE_ENTRY s( aItem );
209
210 m_shapes.push_back( s );
211 }
212
213 void Remove( const T aItem )
214 {
215 SHAPE_VEC_ITER i;
216
217 for( i = m_shapes.begin(); i != m_shapes.end(); ++i )
218 {
219 if( i->parent == aItem )
220 break;
221 }
222
223 if( i == m_shapes.end() )
224 return;
225
226 m_shapes.erase( i );
227 }
228
229 int Size() const
230 {
231 return m_shapes.size();
232 }
233
234 template <class Visitor>
235 int Query( const SHAPE* aShape, int aMinDistance, Visitor& aV, bool aExact = true ) // const
236 {
237 SHAPE_VEC_ITER i;
238 int n = 0;
239 VECTOR2I::extended_type minDistSq = (VECTOR2I::extended_type) aMinDistance * aMinDistance;
240
241 BOX2I refBBox = aShape->BBox();
242
243 for( i = m_shapes.begin(); i != m_shapes.end(); ++i )
244 {
245 if( refBBox.SquaredDistance( i->bbox ) <= minDistSq )
246 {
247 if( !aExact || i->shape->Collide( aShape, aMinDistance ) )
248 {
249 n++;
250
251 if( !aV( i->parent ) )
252 return n;
253 }
254 }
255 }
256
257 return n;
258 }
259
260 void Clear()
261 {
262 m_shapes.clear();
263 }
264
265 query_iterator qbegin( SHAPE* aShape, int aMinDistance, bool aExact )
266 {
267 return query_iterator( m_shapes.begin(), m_shapes.end(), aShape, aMinDistance, aExact );
268 }
269
270 const query_iterator qend()
271 {
272 return query_iterator( m_shapes.end(), m_shapes.end(), NULL, 0, false );
273 }
274
275 iterator begin()
276 {
277 return iterator( m_shapes.begin() );
278 }
279
280 iterator end()
281 {
282 return iterator( m_shapes.end() );
283 }
284
285private:
286 SHAPE_VEC m_shapes;
287};
288
289#endif
Definition: shape_index_list.h:61
Definition: shape_index_list.h:112
Definition: shape_index_list.h:36
Class SHAPE.
Definition: shape.h:59
virtual const BOX2I BBox(int aClearance=0) const =0
Function BBox()