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  * @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 
28 #include <vector>
29 
30 #include <geometry/shape.h>
31 #include <math/box2.h>
32 #include <math/vector2d.h>
33 
34 template <class T>
35 const SHAPE* defaultShapeFunctor( const T aItem )
36 {
37  return aItem->Shape();
38 }
39 
40 template <class T, const SHAPE* (ShapeFunctor) (const T) = defaultShapeFunctor<T> >
42 {
43  struct SHAPE_ENTRY
44  {
45  SHAPE_ENTRY( T aParent )
46  {
47  shape = ShapeFunctor( aParent );
48  bbox = shape->BBox( 0 );
49  parent = aParent;
50  }
51 
53  {
54  }
55 
56  T parent;
57  const SHAPE* shape;
59  };
60 
61  typedef std::vector<SHAPE_ENTRY> SHAPE_VEC;
62  typedef typename std::vector<SHAPE_ENTRY>::iterator SHAPE_VEC_ITER;
63 
64 public:
65  // "Normal" iterator interface, for STL algorithms.
66  class iterator
67  {
68  public:
70  {}
71 
72  iterator( SHAPE_VEC_ITER aCurrent ) :
73  m_current( aCurrent )
74  {}
75 
76  iterator( const iterator& aB ) :
77  m_current( aB.m_current )
78  {}
79 
80  T operator*() const
81  {
82  return (*m_current).parent;
83  }
84 
85  void operator++()
86  {
87  ++m_current;
88  }
89 
90  iterator& operator++( int aDummy )
91  {
92  ++m_current;
93  return *this;
94  }
95 
96  bool operator==( const iterator& aRhs ) const
97  {
98  return m_current == aRhs.m_current;
99  }
100 
101  bool operator!=( const iterator& aRhs ) const
102  {
103  return m_current != aRhs.m_current;
104  }
105 
106  const iterator& operator=( const iterator& aRhs )
107  {
108  m_current = aRhs.m_current;
109  return *this;
110  }
111 
112  private:
114  };
115 
116  // "Query" iterator, for iterating over a set of spatially matching shapes.
118  {
119  public:
121  {
122  }
123 
125  int aMinDistance, bool aExact ) :
126  m_end( aEnd ),
127  m_current( aCurrent ),
128  m_shape( aShape ),
129  m_minDistance( aMinDistance ),
130  m_exact( aExact )
131  {
132  if( aShape )
133  {
134  m_refBBox = aShape->BBox();
135  next();
136  }
137  }
138 
140  m_end( aB.m_end ),
141  m_current( aB.m_current ),
142  m_shape( aB.m_shape ),
144  m_exact( aB.m_exact ),
145  m_refBBox( aB.m_refBBox )
146  {
147  }
148 
149  T operator*() const
150  {
151  return (*m_current).parent;
152  }
153 
155  {
156  ++m_current;
157  next();
158  return *this;
159  }
160 
161  query_iterator& operator++( int aDummy )
162  {
163  ++m_current;
164  next();
165  return *this;
166  }
167 
168  bool operator==( const query_iterator& aRhs ) const
169  {
170  return m_current == aRhs.m_current;
171  }
172 
173  bool operator!=( const query_iterator& aRhs ) const
174  {
175  return m_current != aRhs.m_current;
176  }
177 
179  {
180  m_end = aRhs.m_end;
181  m_current = aRhs.m_current;
182  m_shape = aRhs.m_shape;
184  m_exact = aRhs.m_exact;
185  m_refBBox = aRhs.m_refBBox;
186  return *this;
187  }
188 
189  private:
190  void next()
191  {
192  while( m_current != m_end )
193  {
194  if( m_refBBox.Distance( m_current->bbox ) <= m_minDistance )
195  {
196  if( !m_exact || m_current->shape->Collide( m_shape, m_minDistance ) )
197  return;
198  }
199 
200  ++m_current;
201  }
202  }
203 
207  bool m_exact;
210  };
211 
212  void Add( T aItem )
213  {
214  SHAPE_ENTRY s( aItem );
215 
216  m_shapes.push_back( s );
217  }
218 
219  void Remove( const T aItem )
220  {
221  SHAPE_VEC_ITER i;
222 
223  for( i = m_shapes.begin(); i != m_shapes.end(); ++i )
224  {
225  if( i->parent == aItem )
226  break;
227  }
228 
229  if( i == m_shapes.end() )
230  return;
231 
232  m_shapes.erase( i );
233  }
234 
235  int Size() const
236  {
237  return m_shapes.size();
238  }
239 
240  template <class Visitor>
241  int Query( const SHAPE* aShape, int aMinDistance, Visitor& aV, bool aExact = true ) // const
242  {
243  SHAPE_VEC_ITER i;
244  int n = 0;
245  VECTOR2I::extended_type minDistSq = (VECTOR2I::extended_type) aMinDistance * aMinDistance;
246 
247  BOX2I refBBox = aShape->BBox();
248 
249  for( i = m_shapes.begin(); i != m_shapes.end(); ++i )
250  {
251  if( refBBox.SquaredDistance( i->bbox ) <= minDistSq )
252  {
253  if( !aExact || i->shape->Collide( aShape, aMinDistance ) )
254  {
255  n++;
256 
257  if( !aV( i->parent ) )
258  return n;
259  }
260  }
261  }
262 
263  return n;
264  }
265 
266  void Clear()
267  {
268  m_shapes.clear();
269  }
270 
271  query_iterator qbegin( SHAPE* aShape, int aMinDistance, bool aExact )
272  {
273  return query_iterator( m_shapes.begin(), m_shapes.end(), aShape, aMinDistance, aExact );
274  }
275 
276  const query_iterator qend()
277  {
278  return query_iterator( m_shapes.end(), m_shapes.end(), NULL, 0, false );
279  }
280 
281  iterator begin()
282  {
283  return iterator( m_shapes.begin() );
284  }
285 
286  iterator end()
287  {
288  return iterator( m_shapes.end() );
289  }
290 
291 private:
293 };
294 
295 #endif
~SHAPE_ENTRY()
VECTOR2_TRAITS< int >::extended_type extended_type
Definition: vector2d.h:77
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:441
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
Function BBox()
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)
#define NULL
iterator(SHAPE_VEC_ITER aCurrent)
bool operator!=(const iterator &aRhs) const
SHAPE.
Definition: shape.h:60
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:450
T parent