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-2020 KiCad Developers, see AUTHORS.txt for contributors.
6  * @author Maciej Suminski <maciej.suminski@cern.ch>
7  * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
8  *
9  * This program is free software; you can redistribute it and/or
10  * modify it under the terms of the GNU General Public License
11  * as published by the Free Software Foundation; either version 2
12  * of the License, or (at your option) any later version.
13  *
14  * This program is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17  * GNU General Public License for more details.
18  *
19  * You should have received a copy of the GNU General Public License
20  * along with this program; if not, you may find one here:
21  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
22  * or you may search the http://www.gnu.org website for the version 2 license,
23  * or you may write to the Free Software Foundation, Inc.,
24  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
25  */
26 
27 // #define CONNECTIVITY_DEBUG
28 
29 #ifndef __CONNECTIVITY_ALGO_H
30 #define __CONNECTIVITY_ALGO_H
31 
32 #include <class_board.h>
33 #include <class_pad.h>
34 #include <class_module.h>
35 #include <class_zone.h>
36 
39 
40 #include <memory>
41 #include <algorithm>
42 #include <functional>
43 #include <vector>
44 #include <deque>
45 #include <intrusive_list.h>
46 
50 
51 class CN_CONNECTIVITY_ALGO_IMPL;
52 class CN_RATSNEST_NODES;
53 class BOARD;
55 class BOARD_ITEM;
56 class ZONE_CONTAINER;
57 class PROGRESS_REPORTER;
58 
59 class CN_EDGE
60 {
61 public:
63  : m_weight( 0 ), m_visible( true )
64  {}
65 
66  CN_EDGE( CN_ANCHOR_PTR aSource, CN_ANCHOR_PTR aTarget, unsigned aWeight = 0 )
67  : m_source( aSource ), m_target( aTarget ), m_weight( aWeight ), m_visible( true )
68  {}
69 
75  bool operator<( CN_EDGE aOther ) const
76  {
77  return m_weight < aOther.m_weight;
78  }
79 
80  CN_ANCHOR_PTR GetSourceNode() const { return m_source; }
81  CN_ANCHOR_PTR GetTargetNode() const { return m_target; }
82  unsigned GetWeight() const { return m_weight; }
83 
84  void SetSourceNode( const CN_ANCHOR_PTR& aNode ) { m_source = aNode; }
85  void SetTargetNode( const CN_ANCHOR_PTR& aNode ) { m_target = aNode; }
86  void SetWeight( unsigned weight ) { m_weight = weight; }
87 
88  void SetVisible( bool aVisible )
89  {
90  m_visible = aVisible;
91  }
92 
93  bool IsVisible() const
94  {
95  return m_visible;
96  }
97 
98  const VECTOR2I GetSourcePos() const
99  {
100  return m_source->Pos();
101  }
102 
103  const VECTOR2I GetTargetPos() const
104  {
105  return m_target->Pos();
106  }
107 
108 private:
111  unsigned m_weight;
112  bool m_visible;
113 };
114 
116 {
117 public:
119  {
123  };
124 
125  using CLUSTERS = std::vector<CN_CLUSTER_PTR>;
126 
128  {
129  public:
130  ITEM_MAP_ENTRY( CN_ITEM* aItem = nullptr )
131  {
132  if( aItem )
133  m_items.push_back( aItem );
134  }
135 
137  {
138  for( auto item : m_items )
139  {
140  item->SetValid( false );
141  }
142  }
143 
144  void Link( CN_ITEM* aItem )
145  {
146  m_items.push_back( aItem );
147  }
148 
149  const std::list<CN_ITEM*> GetItems() const
150  {
151  return m_items;
152  }
153 
154  std::list<CN_ITEM*> m_items;
155  };
156 
157 private:
158 
160 
161  std::unordered_map<const BOARD_ITEM*, ITEM_MAP_ENTRY> m_itemMap;
162 
165  std::vector<bool> m_dirtyNets;
167 
168  void searchConnections();
169 
170  void update();
171 
172  void propagateConnections( BOARD_COMMIT* aCommit = nullptr );
173 
174  template <class Container, class BItem>
175  void add( Container& c, BItem brditem )
176  {
177  auto item = c.Add( brditem );
178 
179  m_itemMap[ brditem ] = ITEM_MAP_ENTRY( item );
180  }
181 
182  void markItemNetAsDirty( const BOARD_ITEM* aItem );
183 
184 public:
185 
188 
189  bool ItemExists( const BOARD_CONNECTED_ITEM* aItem ) const
190  {
191  return m_itemMap.find( aItem ) != m_itemMap.end();
192  }
193 
195  {
196  return m_itemMap[ aItem ];
197  }
198 
199  bool IsNetDirty( int aNet ) const
200  {
201  if( aNet < 0 )
202  return false;
203 
204  return m_dirtyNets[ aNet ];
205  }
206 
208  {
209  for( auto i = m_dirtyNets.begin(); i != m_dirtyNets.end(); ++i )
210  *i = false;
211  }
212 
213  void GetDirtyClusters( CLUSTERS& aClusters ) const
214  {
215  for( const auto& cl : m_ratsnestClusters )
216  {
217  int net = cl->OriginNet();
218 
219  if( net >= 0 && m_dirtyNets[net] )
220  aClusters.push_back( cl );
221  }
222  }
223 
224  int NetCount() const
225  {
226  return m_dirtyNets.size();
227  }
228 
229  void Build( BOARD* aBoard );
230  void Build( const std::vector<BOARD_ITEM*>& aItems );
231 
232  void Clear();
233 
234  bool Remove( BOARD_ITEM* aItem );
235  bool Add( BOARD_ITEM* aItem );
236 
237  const CLUSTERS SearchClusters( CLUSTER_SEARCH_MODE aMode, const KICAD_T aTypes[], int aSingleNet );
239 
244  void PropagateNets( BOARD_COMMIT* aCommit = nullptr );
245 
247  std::vector<int>& aIslands );
248 
255  void FindIsolatedCopperIslands( std::vector<CN_ZONE_ISOLATED_ISLAND_LIST>& aZones );
256 
257  const CLUSTERS& GetClusters();
258 
259  const CN_LIST& ItemList() const
260  {
261  return m_itemList;
262  }
263 
264  template <typename Func>
265  void ForEachAnchor( Func&& aFunc ) const
266  {
267  for( auto&& item : m_itemList )
268  {
269  for( auto&& anchor : item->Anchors() )
270  aFunc( *anchor );
271  }
272  }
273 
274  template <typename Func>
275  void ForEachItem( Func&& aFunc ) const
276  {
277  for( auto&& item : m_itemList )
278  aFunc( *item );
279  }
280 
281 
282  void MarkNetAsDirty( int aNet );
283  void SetProgressReporter( PROGRESS_REPORTER* aReporter );
284 
285 };
286 
290 class CN_VISITOR {
291 
292 public:
293 
294  CN_VISITOR( CN_ITEM* aItem ) :
295  m_item( aItem )
296  {}
297 
298  bool operator()( CN_ITEM* aCandidate );
299 
300 protected:
301 
302  void checkZoneItemConnection( CN_ZONE* aZone, CN_ITEM* aItem );
303 
304  void checkZoneZoneConnection( CN_ZONE* aZoneA, CN_ZONE* aZoneB );
305 
308 };
309 
310 #endif
ZONE_CONTAINER handles a list of polygons defining a copper zone.
Definition: class_zone.h:61
void SetSourceNode(const CN_ANCHOR_PTR &aNode)
void propagateConnections(BOARD_COMMIT *aCommit=nullptr)
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)
void PropagateNets(BOARD_COMMIT *aCommit=nullptr)
Propagates nets from pads to other items in clusters.
BOARD_ITEM is a base class for any item which can be embedded within the BOARD container class,...
A progress reporter for use in multi-threaded environments.
CN_ANCHOR_PTR GetTargetNode() const
void checkZoneItemConnection(CN_ZONE *aZone, CN_ITEM *aItem)
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 add(Container &c, BItem brditem)
ITEM_MAP_ENTRY(CN_ITEM *aItem=nullptr)
BOARD_CONNECTED_ITEM is a base class derived from BOARD_ITEM for items that can be connected and have...
void GetDirtyClusters(CLUSTERS &aClusters) const
bool ItemExists(const BOARD_CONNECTED_ITEM *aItem) const
KICAD_T
Enum KICAD_T is the set of class identification values, stored in EDA_ITEM::m_StructType.
Definition: typeinfo.h:78
std::vector< bool > m_dirtyNets
const CLUSTERS SearchClusters(CLUSTER_SEARCH_MODE aMode, const KICAD_T aTypes[], int aSingleNet)
void MarkItemsAsInvalid()
PCB_LAYER_ID
A quick note on layer IDs:
void markItemNetAsDirty(const BOARD_ITEM *aItem)
void FindIsolatedCopperIslands(ZONE_CONTAINER *aZone, PCB_LAYER_ID aLayer, std::vector< int > &aIslands)
void ForEachItem(Func &&aFunc) const
std::list< CN_ITEM * > m_items
ITEM_MAP_ENTRY & ItemEntry(const BOARD_CONNECTED_ITEM *aItem)
const CN_LIST & ItemList() const
unsigned GetWeight() const
bool IsVisible() const
void SetTargetNode(const CN_ANCHOR_PTR &aNode)
void SetVisible(bool aVisible)
Pad object description.
CN_EDGE(CN_ANCHOR_PTR aSource, CN_ANCHOR_PTR aTarget, unsigned aWeight=0)
void SetWeight(unsigned weight)
void ForEachAnchor(Func &&aFunc) const
void Build(BOARD *aBoard)
bool operator()(CN_ITEM *aCandidate)
bool IsNetDirty(int aNet) const
const CLUSTERS & GetClusters()
void checkZoneZoneConnection(CN_ZONE *aZoneA, CN_ZONE *aZoneB)
BOARD holds information pertinent to a Pcbnew printed circuit board.
Definition: class_board.h:184
CN_ANCHOR_PTR m_source
Struct CN_VISTOR.
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