KiCad PCB EDA Suite
connectivity_items.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-2017 CERN
5  * Copyright (C) 2018 KiCad Developers, see AUTHORS.txt for contributors.
6  *
7  * @author Maciej Suminski <maciej.suminski@cern.ch>
8  * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
9  *
10  * This program is free software; you can redistribute it and/or
11  * modify it under the terms of the GNU General Public License
12  * as published by the Free Software Foundation; either version 2
13  * of the License, or (at your option) any later version.
14  *
15  * This program is distributed in the hope that it will be useful,
16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18  * GNU General Public License for more details.
19  *
20  * You should have received a copy of the GNU General Public License
21  * along with this program; if not, you may find one here:
22  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
23  * or you may search the http://www.gnu.org website for the version 2 license,
24  * or you may write to the Free Software Foundation, Inc.,
25  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
26  */
27 
28 
29 #ifndef PCBNEW_CONNECTIVITY_CONNECTIVITY_ITEMS_H_
30 #define PCBNEW_CONNECTIVITY_CONNECTIVITY_ITEMS_H_
31 
32 #include <class_board.h>
33 #include <class_pad.h>
34 #include <class_module.h>
35 #include <class_track.h>
36 #include <class_zone.h>
37 
40 
41 #include <memory>
42 #include <algorithm>
43 #include <functional>
44 #include <vector>
45 #include <deque>
46 #include <intrusive_list.h>
47 
50 
51 class CN_ITEM;
52 class CN_CLUSTER;
53 
54 class CN_ANCHOR
55 {
56 public:
58  {
59  m_item = nullptr;
60  }
61 
62  CN_ANCHOR( const VECTOR2I& aPos, CN_ITEM* aItem )
63  {
64  m_pos = aPos;
65  m_item = aItem;
66  assert( m_item );
67  }
68 
69  bool Valid() const;
70 
71 
72  CN_ITEM* Item() const
73  {
74  return m_item;
75  }
76 
78 
79  const VECTOR2I& Pos() const
80  {
81  return m_pos;
82  }
83 
85  inline int GetTag() const
86  {
87  return m_tag;
88  }
89 
91  inline void SetTag( int aTag )
92  {
93  m_tag = aTag;
94  }
95 
97  inline void SetNoLine( bool aEnable )
98  {
99  m_noline = aEnable;
100  }
101 
103  inline const bool& GetNoLine() const
104  {
105  return m_noline;
106  }
107 
108  inline void SetCluster( std::shared_ptr<CN_CLUSTER> aCluster )
109  {
110  m_cluster = aCluster;
111  }
112 
113  inline const std::shared_ptr<CN_CLUSTER>& GetCluster() const
114  {
115  return m_cluster;
116  }
117 
126  bool IsDangling() const;
127 
132  int ConnectedItemsCount() const;
133 
134  // Tag used for unconnected items.
135  static const int TAG_UNCONNECTED = -1;
136 
137 private:
140 
142  CN_ITEM* m_item = nullptr;
143 
145  int m_tag = -1;
146 
148  bool m_noline = false;
149 
151  std::shared_ptr<CN_CLUSTER> m_cluster;
152 };
153 
154 
155 typedef std::shared_ptr<CN_ANCHOR> CN_ANCHOR_PTR;
156 typedef std::vector<CN_ANCHOR_PTR> CN_ANCHORS;
157 
158 
159 // basic connectivity item
160 class CN_ITEM : public INTRUSIVE_LIST<CN_ITEM>
161 {
162 public:
163  using CONNECTED_ITEMS = std::vector<CN_ITEM*>;
164 
165 private:
167 
170 
172 
174  bool m_visited;
175 
178 
180  bool m_valid;
181 
183  std::mutex m_listLock;
184 
185 protected:
187  bool m_dirty;
188 
191 
194 
195 public:
196  void Dump();
197 
198  CN_ITEM( BOARD_CONNECTED_ITEM* aParent, bool aCanChangeNet, int aAnchorCount = 2 )
199  {
200  m_parent = aParent;
201  m_canChangeNet = aCanChangeNet;
202  m_visited = false;
203  m_valid = true;
204  m_dirty = true;
205  m_anchors.reserve( std::max( 6, aAnchorCount ) );
207  m_connected.reserve( 8 );
208  }
209 
210  virtual ~CN_ITEM() {};
211 
212  void AddAnchor( const VECTOR2I& aPos )
213  {
214  m_anchors.emplace_back( std::make_shared<CN_ANCHOR>( aPos, this ) );
215  }
216 
218  {
219  return m_anchors;
220  }
221 
222  void SetValid( bool aValid )
223  {
224  m_valid = aValid;
225  }
226 
227  bool Valid() const
228  {
229  return m_valid;
230  }
231 
232  void SetDirty( bool aDirty )
233  {
234  m_dirty = aDirty;
235  }
236 
237  bool Dirty() const
238  {
239  return m_dirty;
240  }
241 
247  void SetLayers( const LAYER_RANGE& aLayers )
248  {
249  m_layers = aLayers;
250  }
251 
257  void SetLayer( int aLayer )
258  {
259  m_layers = LAYER_RANGE( aLayer, aLayer );
260  }
261 
267  const LAYER_RANGE& Layers() const
268  {
269  return m_layers;
270  }
271 
277  virtual int Layer() const
278  {
279  return Layers().Start();
280  }
281 
282  const BOX2I& BBox()
283  {
284  if( m_dirty && m_valid )
285  {
287  m_bbox = BOX2I( box.GetPosition(), box.GetSize() );
288  }
289  return m_bbox;
290  }
291 
293  {
294  return m_parent;
295  }
296 
298  {
299  return m_connected;
300  }
301 
303  {
304  m_connected.clear();
305  }
306 
307  void SetVisited( bool aVisited )
308  {
309  m_visited = aVisited;
310  }
311 
312  bool Visited() const
313  {
314  return m_visited;
315  }
316 
317  bool CanChangeNet() const
318  {
319  return m_canChangeNet;
320  }
321 
322  void Connect( CN_ITEM* b )
323  {
324  std::lock_guard<std::mutex> lock( m_listLock );
325 
326  auto i = std::lower_bound( m_connected.begin(), m_connected.end(), b );
327 
328  if( i != m_connected.end() && *i == b )
329  return;
330 
331  m_connected.insert( i, b );
332  }
333 
334  void RemoveInvalidRefs();
335 
336  virtual int AnchorCount() const;
337  virtual const VECTOR2I GetAnchor( int n ) const;
338 
339  int Net() const;
340 };
341 
342 typedef std::shared_ptr<CN_ITEM> CN_ITEM_PTR;
343 
344 class CN_ZONE : public CN_ITEM
345 {
346 public:
347  CN_ZONE( ZONE_CONTAINER* aParent, bool aCanChangeNet, int aSubpolyIndex ) :
348  CN_ITEM( aParent, aCanChangeNet ),
349  m_subpolyIndex( aSubpolyIndex )
350  {
351  SHAPE_LINE_CHAIN outline = aParent->GetFilledPolysList().COutline( aSubpolyIndex );
352 
353  outline.SetClosed( true );
354  outline.Simplify();
355 
356  m_cachedPoly = std::make_unique<POLY_GRID_PARTITION>( outline, 16 );
357  }
358 
359  int SubpolyIndex() const
360  {
361  return m_subpolyIndex;
362  }
363 
364  bool ContainsAnchor( const CN_ANCHOR_PTR anchor ) const
365  {
366  return ContainsPoint( anchor->Pos() );
367  }
368 
369  bool ContainsPoint( const VECTOR2I p ) const
370  {
371  auto zone = static_cast<ZONE_CONTAINER*> ( Parent() );
372  int clearance = zone->GetFilledPolysUseThickness() ? zone->GetMinThickness() / 2 : 0;
373  return m_cachedPoly->ContainsPoint( p, clearance );
374  }
375 
376  const BOX2I& BBox()
377  {
378  if( m_dirty )
379  m_bbox = m_cachedPoly->BBox();
380 
381  return m_bbox;
382  }
383 
384  virtual int AnchorCount() const override;
385  virtual const VECTOR2I GetAnchor( int n ) const override;
386 
387 private:
388  std::vector<VECTOR2I> m_testOutlinePoints;
389  std::unique_ptr<POLY_GRID_PARTITION> m_cachedPoly;
391 };
392 
393 class CN_LIST
394 {
395 private:
396  bool m_dirty;
398 
400 
401 protected:
402  std::vector<CN_ITEM*> m_items;
403 
404  void addItemtoTree( CN_ITEM* item )
405  {
406  m_index.Insert( item );
407  }
408 
409 public:
411  {
412  m_dirty = false;
413  m_hasInvalid = false;
414  }
415 
416  void Clear()
417  {
418  for( auto item : m_items )
419  delete item;
420 
421  m_items.clear();
422  m_index.RemoveAll();
423  }
424 
425  using ITER = decltype(m_items)::iterator;
426 
427  ITER begin() { return m_items.begin(); };
428  ITER end() { return m_items.end(); };
429 
430  CN_ITEM* operator[] ( int aIndex ) { return m_items[aIndex]; }
431 
432  template <class T>
433  void FindNearby( CN_ITEM *aItem, T aFunc )
434  {
435  m_index.Query( aItem->BBox(), aItem->Layers(), aFunc );
436  }
437 
438  void SetHasInvalid( bool aInvalid = true )
439  {
440  m_hasInvalid = aInvalid;
441  }
442 
443  void SetDirty( bool aDirty = true )
444  {
445  m_dirty = aDirty;
446  }
447 
448  bool IsDirty() const
449  {
450  return m_dirty;
451  }
452 
453  void RemoveInvalidItems( std::vector<CN_ITEM*>& aGarbage );
454 
456  {
457  for( auto item : m_items )
458  item->SetDirty( false );
459 
460  SetDirty( false );
461  }
462 
464  {
465  for( auto item : m_items )
466  item->SetDirty( true );
467 
468  SetDirty( true );
469  }
470 
471  int Size() const
472  {
473  return m_items.size();
474  }
475 
476  CN_ITEM* Add( D_PAD* pad );
477 
478  CN_ITEM* Add( TRACK* track );
479 
480  CN_ITEM* Add( ARC* track );
481 
482  CN_ITEM* Add( VIA* via );
483 
484  const std::vector<CN_ITEM*> Add( ZONE_CONTAINER* zone );
485 };
486 
488 {
489 private:
490 
491  bool m_conflicting = false;
492  int m_originNet = 0;
493  CN_ITEM* m_originPad = nullptr;
494  std::vector<CN_ITEM*> m_items;
495 
496 public:
497  CN_CLUSTER();
498  ~CN_CLUSTER();
499 
500  bool HasValidNet() const
501  {
502  return m_originNet > 0;
503  }
504 
505  int OriginNet() const
506  {
507  return m_originNet;
508  }
509 
510  wxString OriginNetName() const;
511 
512  bool Contains( const CN_ITEM* aItem );
513  bool Contains( const BOARD_CONNECTED_ITEM* aItem );
514  void Dump();
515 
516  int Size() const
517  {
518  return m_items.size();
519  }
520 
521  bool HasNet() const
522  {
523  return m_originNet > 0;
524  }
525 
526  bool IsOrphaned() const
527  {
528  return m_originPad == nullptr;
529  }
530 
531  bool IsConflicting() const
532  {
533  return m_conflicting;
534  }
535 
536  void Add( CN_ITEM* item );
537 
538  using ITER = decltype(m_items)::iterator;
539 
540  ITER begin() { return m_items.begin(); };
541  ITER end() { return m_items.end(); };
542 };
543 
544 typedef std::shared_ptr<CN_CLUSTER> CN_CLUSTER_PTR;
545 
546 
547 #endif /* PCBNEW_CONNECTIVITY_CONNECTIVITY_ITEMS_H_ */
std::vector< CN_ITEM * > CONNECTED_ITEMS
void RemoveInvalidItems(std::vector< CN_ITEM * > &aGarbage)
const CONNECTED_ITEMS & ConnectedItems() const
bool Contains(const CN_ITEM *aItem)
int GetTag() const
Returns tag, common identifier for connected nodes.
virtual int AnchorCount() const override
std::vector< CN_ITEM * > m_items
ZONE_CONTAINER handles a list of polygons defining a copper zone.
Definition: class_zone.h:60
BOX2< VECTOR2I > BOX2I
Definition: box2.h:521
decltype(m_items)::iterator ITER
BOARD_CONNECTED_ITEM * m_parent
int Size() const
void SetHasInvalid(bool aInvalid=true)
std::shared_ptr< CN_CLUSTER > m_cluster
Cluster to which the anchor belongs.
int SubpolyIndex() const
std::vector< VECTOR2I > m_testOutlinePoints
void addItemtoTree(CN_ITEM *item)
bool m_valid
valid flag, used to identify garbage items (we use lazy removal)
A lightweight intrusive list container
CN_ITEM * Add(D_PAD *pad)
void ClearDirtyFlags()
const bool & GetNoLine() const
Returns true if this node can be a target for ratsnest lines.
void ClearConnections()
CN_ITEM * operator[](int aIndex)
LAYER_RANGE m_layers
layer range over which the item exists
const BOX2I & BBox()
void SetVisited(bool aVisited)
bool IsDirty() const
bool Dirty() const
BOARD_CONNECTED_ITEM * Parent() const
static const int TAG_UNCONNECTED
CN_ITEM * Item() const
bool HasNet() const
void SetCluster(std::shared_ptr< CN_CLUSTER > aCluster)
bool IsDangling() const
has meaning only for tracks and vias.
CN_ANCHORS & Anchors()
void Insert(T aItem)
Function Insert() Inserts an item into the tree.
BOARD_CONNECTED_ITEM is a base class derived from BOARD_ITEM for items that can be connected and have...
void SetDirty(bool aDirty=true)
void RemoveAll()
Function RemoveAll() Removes all items from the RTree.
int ConnectedItemsCount() const
has meaning only for tracks and vias.
int Net() const
bool Visited() const
Definitions for tracks, vias and zones.
void MarkAllAsDirty()
VECTOR2I m_pos
Position of the anchor.
virtual int AnchorCount() const
int Start() const
Definition: pns_layerset.h:83
void SetValid(bool aValid)
SHAPE_LINE_CHAIN & Simplify()
Function Simplify()
std::vector< CN_ITEM * > m_items
void SetClosed(bool aClosed)
Function SetClosed()
bool m_visited
visited flag for the BFS scan
std::vector< CN_ANCHOR_PTR > CN_ANCHORS
int OriginNet() const
CN_ANCHOR(const VECTOR2I &aPos, CN_ITEM *aItem)
const wxPoint GetPosition() const
Definition: eda_rect.h:115
int Size() const
bool m_dirty
dirty flag, used to identify recently added item not yet scanned into the connectivity search
decltype(m_items)::iterator ITER
void SetLayers(const LAYER_RANGE &aLayers)
Function SetLayers()
std::mutex m_listLock
mutex protecting this item's connected_items set to allow parallel connection threads
virtual ~CN_ITEM()
BOX2I m_bbox
bounding box for the item
void SetTag(int aTag)
Sets tag, common identifier for connected nodes.
void Add(CN_ITEM *item)
bool m_canChangeNet
can the net propagator modify the netcode?
void Query(const BOX2I &aBounds, const LAYER_RANGE &aRange, Visitor &aVisitor)
Function Query() Executes a function object aVisitor for each item whose bounding box intersects with...
const std::shared_ptr< CN_CLUSTER > & GetCluster() const
bool ContainsPoint(const VECTOR2I p) const
bool Valid() const
Pad object description.
bool IsConflicting() const
virtual const VECTOR2I GetAnchor(int n) const
void SetDirty(bool aDirty)
int m_tag
Tag for quick connection resolution.
std::unique_ptr< POLY_GRID_PARTITION > m_cachedPoly
bool CanChangeNet() const
wxString OriginNetName() const
bool HasValidNet() const
void AddAnchor(const VECTOR2I &aPos)
void FindNearby(CN_ITEM *aItem, T aFunc)
CN_ZONE(ZONE_CONTAINER *aParent, bool aCanChangeNet, int aSubpolyIndex)
virtual const VECTOR2I GetAnchor(int n) const override
CN_ITEM * m_item
Item owning the anchor.
SHAPE_LINE_CHAIN.
void SetLayer(int aLayer)
Function SetLayer()
CN_ITEM * m_originPad
const SHAPE_LINE_CHAIN & COutline(int aIndex) const
const LAYER_RANGE & Layers() const
Function Layers()
EDA_RECT handles the component boundary box.
Definition: eda_rect.h:44
BOARD_CONNECTED_ITEM * Parent() const
std::shared_ptr< CN_CLUSTER > CN_CLUSTER_PTR
std::shared_ptr< CN_ANCHOR > CN_ANCHOR_PTR
CN_ITEM(BOARD_CONNECTED_ITEM *aParent, bool aCanChangeNet, int aAnchorCount=2)
virtual int Layer() const
Function Layer()
std::shared_ptr< CN_ITEM > CN_ITEM_PTR
void SetNoLine(bool aEnable)
Decides whether this node can be a ratsnest line target.
const VECTOR2I & Pos() const
CONNECTED_ITEMS m_connected
list of items physically connected (touching)
bool ContainsAnchor(const CN_ANCHOR_PTR anchor) const
void Connect(CN_ITEM *b)
Module description (excepted pads)
virtual const EDA_RECT GetBoundingBox() const
Function GetBoundingBox returns the orthogonal, bounding box of this object for display purposes.
bool IsOrphaned() const
LAYER_RANGE.
Definition: pns_layerset.h:32
const BOX2I & BBox()
void RemoveInvalidRefs()
bool m_noline
Whether it the node can be a target for ratsnest lines.
const wxSize GetSize() const
Definition: eda_rect.h:103
bool Valid() const
CN_RTREE< CN_ITEM * > m_index
CN_ANCHORS m_anchors
const SHAPE_POLY_SET & GetFilledPolysList() const
Function GetFilledPolysList returns a reference to the list of filled polygons.
Definition: class_zone.h:571