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  * @author Maciej Suminski <maciej.suminski@cern.ch>
6  * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
7  *
8  * This program is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU General Public License
10  * as published by the Free Software Foundation; either version 2
11  * of the License, or (at your option) any later version.
12  *
13  * This program is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16  * GNU General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License
19  * along with this program; if not, you may find one here:
20  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
21  * or you may search the http://www.gnu.org website for the version 2 license,
22  * or you may write to the Free Software Foundation, Inc.,
23  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
24  */
25 
26 // #define CONNECTIVITY_DEBUG
27 
28 #ifndef __CONNECTIVITY_ALGO_H
29 #define __CONNECTIVITY_ALGO_H
30 
31 #include <class_board.h>
32 #include <class_pad.h>
33 #include <class_module.h>
34 #include <class_zone.h>
35 
38 
39 #include <memory>
40 #include <algorithm>
41 #include <functional>
42 #include <vector>
43 #include <deque>
44 #include <intrusive_list.h>
45 
49 
50 class CN_CONNECTIVITY_ALGO_IMPL;
51 class CN_RATSNEST_NODES;
52 class BOARD;
54 class BOARD_ITEM;
55 class ZONE_CONTAINER;
56 class PROGRESS_REPORTER;
57 
58 class CN_EDGE
59 {
60 public:
61  CN_EDGE() {};
62  CN_EDGE( CN_ANCHOR_PTR aSource, CN_ANCHOR_PTR aTarget, int aWeight = 0 ) :
63  m_source( aSource ),
64  m_target( aTarget ),
65  m_weight( aWeight ) {}
66 
67  CN_ANCHOR_PTR GetSourceNode() const { return m_source; }
68  CN_ANCHOR_PTR GetTargetNode() const { return m_target; }
69  int GetWeight() const { return m_weight; }
70 
71  void SetSourceNode( const CN_ANCHOR_PTR& aNode ) { m_source = aNode; }
72  void SetTargetNode( const CN_ANCHOR_PTR& aNode ) { m_target = aNode; }
73  void SetWeight( unsigned int weight ) { m_weight = weight; }
74 
75  void SetVisible( bool aVisible )
76  {
77  m_visible = aVisible;
78  }
79 
80  bool IsVisible() const
81  {
82  return m_visible;
83  }
84 
85  const VECTOR2I GetSourcePos() const
86  {
87  return m_source->Pos();
88  }
89 
90  const VECTOR2I GetTargetPos() const
91  {
92  return m_target->Pos();
93  }
94 
95 private:
98  unsigned int m_weight = 0;
99  bool m_visible = true;
100 };
101 
103 {
104 public:
106  {
110  };
111 
112  using CLUSTERS = std::vector<CN_CLUSTER_PTR>;
113 
114 private:
115 
117  {
118  public:
119  ITEM_MAP_ENTRY( CN_ITEM* aItem = nullptr )
120  {
121  if( aItem )
122  m_items.push_back( aItem );
123  }
124 
126  {
127  for( auto item : m_items )
128  {
129  item->SetValid( false );
130  }
131  }
132 
133  void Link( CN_ITEM* aItem )
134  {
135  m_items.push_back( aItem );
136  }
137 
138  const std::list<CN_ITEM*> GetItems() const
139  {
140  return m_items;
141  }
142 
143  std::list<CN_ITEM*> m_items;
144  };
145 
147 
148  std::unordered_map<const BOARD_CONNECTED_ITEM*, ITEM_MAP_ENTRY> m_itemMap;
149 
152  std::vector<bool> m_dirtyNets;
154 
155  void searchConnections();
156 
157  void update();
158 
159  void propagateConnections( BOARD_COMMIT* aCommit = nullptr );
160 
161  template <class Container, class BItem>
162  void add( Container& c, BItem brditem )
163  {
164  auto item = c.Add( brditem );
165 
166  m_itemMap[ brditem ] = ITEM_MAP_ENTRY( item );
167  }
168 
169  void markItemNetAsDirty( const BOARD_ITEM* aItem );
170 
171 public:
172 
175 
176  bool ItemExists( const BOARD_CONNECTED_ITEM* aItem )
177  {
178  return m_itemMap.find( aItem ) != m_itemMap.end();
179  }
180 
182  {
183  return m_itemMap[ aItem ];
184  }
185 
186  bool IsNetDirty( int aNet ) const
187  {
188  if( aNet < 0 )
189  return false;
190 
191  return m_dirtyNets[ aNet ];
192  }
193 
195  {
196  for( auto i = m_dirtyNets.begin(); i != m_dirtyNets.end(); ++i )
197  *i = false;
198  }
199 
200  void GetDirtyClusters( CLUSTERS& aClusters )
201  {
202  for( auto cl : m_ratsnestClusters )
203  {
204  int net = cl->OriginNet();
205 
206  if( net >= 0 && m_dirtyNets[net] )
207  aClusters.push_back( cl );
208  }
209  }
210 
211  int NetCount() const
212  {
213  return m_dirtyNets.size();
214  }
215 
216  void Build( BOARD* aBoard );
217  void Build( const std::vector<BOARD_ITEM*>& aItems );
218 
219  void Clear();
220 
221  bool Remove( BOARD_ITEM* aItem );
222  bool Add( BOARD_ITEM* aItem );
223 
224  const CLUSTERS SearchClusters( CLUSTER_SEARCH_MODE aMode, const KICAD_T aTypes[], int aSingleNet );
226 
231  void PropagateNets( BOARD_COMMIT* aCommit = nullptr );
232 
233  void FindIsolatedCopperIslands( ZONE_CONTAINER* aZone, std::vector<int>& aIslands );
234 
241  void FindIsolatedCopperIslands( std::vector<CN_ZONE_ISOLATED_ISLAND_LIST>& aZones );
242 
243  bool CheckConnectivity( std::vector<CN_DISJOINT_NET_ENTRY>& aReport );
244 
245  const CLUSTERS& GetClusters();
246  int GetUnconnectedCount();
247 
248  CN_LIST& ItemList() { return m_itemList; }
249 
250  void ForEachAnchor( const std::function<void( CN_ANCHOR& )>& aFunc );
251  void ForEachItem( const std::function<void( CN_ITEM& )>& aFunc );
252 
253  void MarkNetAsDirty( int aNet );
254  void SetProgressReporter( PROGRESS_REPORTER* aReporter );
255 
256 };
257 
261 class CN_VISITOR {
262 
263 public:
264 
265  CN_VISITOR( CN_ITEM* aItem ) :
266  m_item( aItem )
267  {}
268 
269  bool operator()( CN_ITEM* aCandidate );
270 
271 protected:
272 
273  void checkZoneItemConnection( CN_ZONE* aZone, CN_ITEM* aItem );
274 
275  void checkZoneZoneConnection( CN_ZONE* aZoneA, CN_ZONE* aZoneB );
276 
279 };
280 
281 #endif
bool CheckConnectivity(std::vector< CN_DISJOINT_NET_ENTRY > &aReport)
Class ZONE_CONTAINER handles a list of polygons defining a copper zone.
Definition: class_zone.h:57
void SetSourceNode(const CN_ANCHOR_PTR &aNode)
void propagateConnections(BOARD_COMMIT *aCommit=nullptr)
CN_EDGE(CN_ANCHOR_PTR aSource, CN_ANCHOR_PTR aTarget, int aWeight=0)
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.
Class 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
int GetWeight() const
void checkZoneItemConnection(CN_ZONE *aZone, CN_ITEM *aItem)
const std::list< CN_ITEM * > GetItems() const
void ForEachAnchor(const std::function< void(CN_ANCHOR &)> &aFunc)
CN_ANCHOR_PTR m_target
void MarkNetAsDirty(int aNet)
unsigned int m_weight
bool Add(BOARD_ITEM *aItem)
void add(Container &c, BItem brditem)
ITEM_MAP_ENTRY(CN_ITEM *aItem=nullptr)
Class BOARD_CONNECTED_ITEM is a base class derived from BOARD_ITEM for items that can be connected an...
std::unordered_map< const BOARD_CONNECTED_ITEM *, ITEM_MAP_ENTRY > m_itemMap
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()
void markItemNetAsDirty(const BOARD_ITEM *aItem)
std::list< CN_ITEM * > m_items
ITEM_MAP_ENTRY & ItemEntry(const BOARD_CONNECTED_ITEM *aItem)
void ForEachItem(const std::function< void(CN_ITEM &)> &aFunc)
bool ItemExists(const BOARD_CONNECTED_ITEM *aItem)
bool IsVisible() const
void SetTargetNode(const CN_ANCHOR_PTR &aNode)
void SetVisible(bool aVisible)
Pad object description.
void FindIsolatedCopperIslands(ZONE_CONTAINER *aZone, std::vector< int > &aIslands)
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)
Class BOARD holds information pertinent to a Pcbnew printed circuit board.
Definition: class_board.h:161
CN_ANCHOR_PTR m_source
Struct CN_VISTOR.
void SetWeight(unsigned int weight)
size_t i
Definition: json11.cpp:597
std::shared_ptr< CN_ANCHOR > CN_ANCHOR_PTR
const VECTOR2I GetSourcePos() const
const VECTOR2I GetTargetPos() const
void GetDirtyClusters(CLUSTERS &aClusters)
Module description (excepted pads)
CN_ITEM * m_item
the item we are looking for connections to
CN_VISITOR(CN_ITEM *aItem)
std::vector< CN_CLUSTER_PTR > CLUSTERS
CN_ANCHOR_PTR GetSourceNode() const
void SetProgressReporter(PROGRESS_REPORTER *aReporter)
PROGRESS_REPORTER * m_progressReporter