KiCad PCB EDA Suite
connectivity_algo.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) 2019-2021 KiCad Developers, see AUTHORS.txt for contributors.
6  *
7  * @author Maciej Suminski <[email protected]>
8  * @author Tomasz Wlostowski <[email protected]>
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 // #define CONNECTIVITY_DEBUG
29 
30 #ifndef __CONNECTIVITY_ALGO_H
31 #define __CONNECTIVITY_ALGO_H
32 
33 #include <board.h>
34 #include <pad.h>
35 #include <footprint.h>
36 #include <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 
51 
52 class CN_CONNECTIVITY_ALGO_IMPL;
53 class CN_RATSNEST_NODES;
54 class BOARD;
56 class BOARD_ITEM;
57 class ZONE;
58 class PROGRESS_REPORTER;
59 
60 
65 class CN_EDGE
66 {
67 public:
69  : m_weight( 0 ), m_visible( true )
70  {}
71 
72  CN_EDGE( CN_ANCHOR_PTR aSource, CN_ANCHOR_PTR aTarget, unsigned aWeight = 0 )
73  : m_source( aSource ), m_target( aTarget ), m_weight( aWeight ), m_visible( true )
74  {}
75 
82  bool operator<( CN_EDGE aOther ) const
83  {
84  return m_weight < aOther.m_weight;
85  }
86 
87  CN_ANCHOR_PTR GetSourceNode() const { return m_source; }
88  CN_ANCHOR_PTR GetTargetNode() const { return m_target; }
89  unsigned GetWeight() const { return m_weight; }
90 
91  void SetSourceNode( const CN_ANCHOR_PTR& aNode ) { m_source = aNode; }
92  void SetTargetNode( const CN_ANCHOR_PTR& aNode ) { m_target = aNode; }
93  void SetWeight( unsigned weight ) { m_weight = weight; }
94 
95  void SetVisible( bool aVisible )
96  {
97  m_visible = aVisible;
98  }
99 
100  bool IsVisible() const
101  {
102  return m_visible;
103  }
104 
105  const VECTOR2I GetSourcePos() const
106  {
107  return m_source->Pos();
108  }
109 
110  const VECTOR2I GetTargetPos() const
111  {
112  return m_target->Pos();
113  }
114 
115 private:
118  unsigned m_weight;
119  bool m_visible;
120 };
121 
122 
124 {
125 public:
127  {
131  };
132 
133  using CLUSTERS = std::vector<CN_CLUSTER_PTR>;
134 
136  {
137  public:
138  ITEM_MAP_ENTRY( CN_ITEM* aItem = nullptr )
139  {
140  if( aItem )
141  m_items.push_back( aItem );
142  }
143 
145  {
146  for( auto item : m_items )
147  {
148  item->SetValid( false );
149  }
150  }
151 
152  void Link( CN_ITEM* aItem )
153  {
154  m_items.push_back( aItem );
155  }
156 
157  const std::list<CN_ITEM*> GetItems() const
158  {
159  return m_items;
160  }
161 
162  std::list<CN_ITEM*> m_items;
163  };
164 
167 
168  bool ItemExists( const BOARD_CONNECTED_ITEM* aItem ) const
169  {
170  return m_itemMap.find( aItem ) != m_itemMap.end();
171  }
172 
174  {
175  return m_itemMap[ aItem ];
176  }
177 
178  bool IsNetDirty( int aNet ) const
179  {
180  if( aNet < 0 )
181  return false;
182 
183  return m_dirtyNets[ aNet ];
184  }
185 
187  {
188  for( auto i = m_dirtyNets.begin(); i != m_dirtyNets.end(); ++i )
189  *i = false;
190  }
191 
192  void GetDirtyClusters( CLUSTERS& aClusters ) const
193  {
194  for( const auto& cl : m_ratsnestClusters )
195  {
196  int net = cl->OriginNet();
197 
198  if( net >= 0 && m_dirtyNets[net] )
199  aClusters.push_back( cl );
200  }
201  }
202 
203  int NetCount() const
204  {
205  return m_dirtyNets.size();
206  }
207 
208  void Build( BOARD* aBoard, PROGRESS_REPORTER* aReporter = nullptr );
209  void Build( const std::vector<BOARD_ITEM*>& aItems );
210 
211  void Clear();
212 
213  bool Remove( BOARD_ITEM* aItem );
214  bool Add( BOARD_ITEM* aItem );
215 
216  const CLUSTERS SearchClusters( CLUSTER_SEARCH_MODE aMode, const KICAD_T aTypes[],
217  int aSingleNet );
219 
225  void PropagateNets( BOARD_COMMIT* aCommit = nullptr,
227 
228  void FindIsolatedCopperIslands( ZONE* aZone, PCB_LAYER_ID aLayer, std::vector<int>& aIslands );
229 
238  void FindIsolatedCopperIslands( std::vector<CN_ZONE_ISOLATED_ISLAND_LIST>& aZones );
239 
240  const CLUSTERS& GetClusters();
241 
242  const CN_LIST& ItemList() const
243  {
244  return m_itemList;
245  }
246 
247  template <typename Func>
248  void ForEachAnchor( Func&& aFunc ) const
249  {
250  for( auto&& item : m_itemList )
251  {
252  for( auto&& anchor : item->Anchors() )
253  aFunc( *anchor );
254  }
255  }
256 
257  template <typename Func>
258  void ForEachItem( Func&& aFunc ) const
259  {
260  for( auto&& item : m_itemList )
261  aFunc( *item );
262  }
263 
264  void MarkNetAsDirty( int aNet );
265  void SetProgressReporter( PROGRESS_REPORTER* aReporter );
266 
267 private:
268  void searchConnections();
269 
270  void propagateConnections( BOARD_COMMIT* aCommit = nullptr,
272 
273  template <class Container, class BItem>
274  void add( Container& c, BItem brditem )
275  {
276  auto item = c.Add( brditem );
277 
278  m_itemMap[ brditem ] = ITEM_MAP_ENTRY( item );
279  }
280 
281  void markItemNetAsDirty( const BOARD_ITEM* aItem );
282 
283 private:
285  std::unordered_map<const BOARD_ITEM*, ITEM_MAP_ENTRY> m_itemMap;
286 
289  std::vector<bool> m_dirtyNets;
290 
292 };
293 
294 
296 {
297 public:
298  CN_VISITOR( CN_ITEM* aItem ) :
299  m_item( aItem )
300  {}
301 
302  bool operator()( CN_ITEM* aCandidate );
303 
304 protected:
305  void checkZoneItemConnection( CN_ZONE_LAYER* aZoneLayer, CN_ITEM* aItem );
306 
307  void checkZoneZoneConnection( CN_ZONE_LAYER* aZoneLayerA, CN_ZONE_LAYER* aZoneLayerB );
308 
309 protected:
311 };
312 
313 #endif
void SetSourceNode(const CN_ANCHOR_PTR &aNode)
bool operator<(CN_EDGE aOther) const
This sort operator provides a sort-by-weight for the ratsnest operation.
void Link(CN_ITEM *aItem)
bool Remove(BOARD_ITEM *aItem)
PROPAGATE_MODE
Controls how nets are propagated through clusters.
A base class for any item which can be embedded within the BOARD container class, and therefore insta...
Definition: board_item.h:49
void checkZoneItemConnection(CN_ZONE_LAYER *aZoneLayer, CN_ITEM *aItem)
A progress reporter interface for use in multi-threaded environments.
CN_ANCHOR_PTR GetTargetNode() const
const std::list< CN_ITEM * > GetItems() const
CN_ANCHOR_PTR m_target
unsigned m_weight
void MarkNetAsDirty(int aNet)
bool Add(BOARD_ITEM *aItem)
void FindIsolatedCopperIslands(ZONE *aZone, PCB_LAYER_ID aLayer, std::vector< int > &aIslands)
void add(Container &c, BItem brditem)
ITEM_MAP_ENTRY(CN_ITEM *aItem=nullptr)
A base class derived from BOARD_ITEM for items that can be connected and have a net,...
void GetDirtyClusters(CLUSTERS &aClusters) const
bool ItemExists(const BOARD_CONNECTED_ITEM *aItem) const
KICAD_T
The set of class identification values stored in EDA_ITEM::m_structType.
Definition: typeinfo.h:77
std::vector< bool > m_dirtyNets
void PropagateNets(BOARD_COMMIT *aCommit=nullptr, PROPAGATE_MODE aMode=PROPAGATE_MODE::SKIP_CONFLICTS)
Propagate nets from pads to other items in clusters.
const CLUSTERS SearchClusters(CLUSTER_SEARCH_MODE aMode, const KICAD_T aTypes[], int aSingleNet)
void MarkItemsAsInvalid()
void markItemNetAsDirty(const BOARD_ITEM *aItem)
void ForEachItem(Func &&aFunc) const
std::list< CN_ITEM * > m_items
ITEM_MAP_ENTRY & ItemEntry(const BOARD_CONNECTED_ITEM *aItem)
void propagateConnections(BOARD_COMMIT *aCommit=nullptr, PROPAGATE_MODE aMode=PROPAGATE_MODE::SKIP_CONFLICTS)
const CN_LIST & ItemList() const
unsigned GetWeight() const
bool IsVisible() const
void SetTargetNode(const CN_ANCHOR_PTR &aNode)
void checkZoneZoneConnection(CN_ZONE_LAYER *aZoneLayerA, CN_ZONE_LAYER *aZoneLayerB)
Handle a list of polygons defining a copper zone.
Definition: zone.h:56
void SetVisible(bool aVisible)
CN_EDGE(CN_ANCHOR_PTR aSource, CN_ANCHOR_PTR aTarget, unsigned aWeight=0)
void SetWeight(unsigned weight)
void ForEachAnchor(Func &&aFunc) const
bool operator()(CN_ITEM *aCandidate)
bool IsNetDirty(int aNet) const
const CLUSTERS & GetClusters()
void Build(BOARD *aBoard, PROGRESS_REPORTER *aReporter=nullptr)
CN_EDGE represents a point-to-point connection, whether realized or unrealized (ie: tracks etc.
Information pertinent to a Pcbnew printed circuit board.
Definition: board.h:191
CN_ANCHOR_PTR m_source
PCB_LAYER_ID
A quick note on layer IDs:
Definition: layer_ids.h:65
CN_ITEM represents a BOARD_CONNETED_ITEM in the connectivity system (ie: a pad, track/arc/via,...
std::shared_ptr< CN_ANCHOR > CN_ANCHOR_PTR
const VECTOR2I GetSourcePos() const
const VECTOR2I GetTargetPos() const
CN_ITEM * m_item
The item we are looking for connections to.
CN_VISITOR(CN_ITEM *aItem)
std::vector< CN_CLUSTER_PTR > CLUSTERS
std::unordered_map< const BOARD_ITEM *, ITEM_MAP_ENTRY > m_itemMap
CN_ANCHOR_PTR GetSourceNode() const
void SetProgressReporter(PROGRESS_REPORTER *aReporter)
PROGRESS_REPORTER * m_progressReporter