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