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