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  {
109  CSM_RATSNEST
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;
153  PROGRESS_REPORTER* m_progressReporter = nullptr;
154 
155  void searchConnections();
156 
157  void update();
158  void propagateConnections();
159 
160  template <class Container, class BItem>
161  void add( Container& c, BItem brditem )
162  {
163  auto item = c.Add( brditem );
164 
165  m_itemMap[ brditem ] = ITEM_MAP_ENTRY( item );
166  }
167 
168  void markItemNetAsDirty( const BOARD_ITEM* aItem );
169 
170 public:
171 
173  ~CN_CONNECTIVITY_ALGO() { Clear(); }
174 
175  bool ItemExists( const BOARD_CONNECTED_ITEM* aItem )
176  {
177  return m_itemMap.find( aItem ) != m_itemMap.end();
178  }
179 
181  {
182  return m_itemMap[ aItem ];
183  }
184 
185  bool IsNetDirty( int aNet ) const
186  {
187  if( aNet < 0 )
188  return false;
189 
190  return m_dirtyNets[ aNet ];
191  }
192 
194  {
195  for( auto i = m_dirtyNets.begin(); i != m_dirtyNets.end(); ++i )
196  *i = false;
197  }
198 
199  void GetDirtyClusters( CLUSTERS& aClusters )
200  {
201  for( auto cl : m_ratsnestClusters )
202  {
203  int net = cl->OriginNet();
204 
205  if( net >= 0 && m_dirtyNets[net] )
206  aClusters.push_back( cl );
207  }
208  }
209 
210  int NetCount() const
211  {
212  return m_dirtyNets.size();
213  }
214 
215  void Build( BOARD* aBoard );
216  void Build( const std::vector<BOARD_ITEM*>& aItems );
217 
218  void Clear();
219 
220  bool Remove( BOARD_ITEM* aItem );
221  bool Add( BOARD_ITEM* aItem );
222 
223  const CLUSTERS SearchClusters( CLUSTER_SEARCH_MODE aMode, const KICAD_T aTypes[], int aSingleNet );
224  const CLUSTERS SearchClusters( CLUSTER_SEARCH_MODE aMode );
225 
226  void PropagateNets();
227  void FindIsolatedCopperIslands( ZONE_CONTAINER* aZone, std::vector<int>& aIslands );
228 
235  void FindIsolatedCopperIslands( std::vector<CN_ZONE_ISOLATED_ISLAND_LIST>& aZones );
236 
237  bool CheckConnectivity( std::vector<CN_DISJOINT_NET_ENTRY>& aReport );
238 
239  const CLUSTERS& GetClusters();
240  int GetUnconnectedCount();
241 
242  CN_LIST& ItemList() { return m_itemList; }
243 
244  void ForEachAnchor( const std::function<void( CN_ANCHOR& )>& aFunc );
245  void ForEachItem( const std::function<void( CN_ITEM& )>& aFunc );
246 
247  void MarkNetAsDirty( int aNet );
248  void SetProgressReporter( PROGRESS_REPORTER* aReporter );
249 
250 };
251 
255 class CN_VISITOR {
256 
257 public:
258 
259  CN_VISITOR( CN_ITEM* aItem ) :
260  m_item( aItem )
261  {}
262 
263  bool operator()( CN_ITEM* aCandidate );
264 
265 protected:
266 
267  void checkZoneItemConnection( CN_ZONE* aZone, CN_ITEM* aItem );
268 
269  void checkZoneZoneConnection( CN_ZONE* aZoneA, CN_ZONE* aZoneB );
270 
273 };
274 
275 #endif
Class ZONE_CONTAINER handles a list of polygons defining a copper zone.
Definition: class_zone.h:60
void SetSourceNode(const CN_ANCHOR_PTR &aNode)
CN_EDGE(CN_ANCHOR_PTR aSource, CN_ANCHOR_PTR aTarget, int aWeight=0)
void Link(CN_ITEM *aItem)
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.
Class BOARD to handle a board.
CN_ANCHOR_PTR m_target
unsigned int m_weight
Classes to handle copper zones.
CN_ANCHOR_PTR GetTargetNode() const
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
void MarkItemsAsInvalid()
std::list< CN_ITEM * > m_items
ITEM_MAP_ENTRY & ItemEntry(const BOARD_CONNECTED_ITEM *aItem)
bool IsNetDirty(int aNet) const
bool ItemExists(const BOARD_CONNECTED_ITEM *aItem)
bool IsVisible() const
const std::list< CN_ITEM * > GetItems() const
void SetTargetNode(const CN_ANCHOR_PTR &aNode)
const VECTOR2I GetTargetPos() const
void SetVisible(bool aVisible)
Pad object description.
Class BOARD holds information pertinent to a Pcbnew printed circuit board.
Definition: class_board.h:170
CN_ANCHOR_PTR m_source
Struct CN_VISTOR.
int GetWeight() const
void SetWeight(unsigned int weight)
size_t i
Definition: json11.cpp:597
std::shared_ptr< CN_ANCHOR > CN_ANCHOR_PTR
void GetDirtyClusters(CLUSTERS &aClusters)
Module description (excepted pads)
CN_ANCHOR_PTR GetSourceNode() const
CN_ITEM * m_item
the item we are looking for connections to
CN_VISITOR(CN_ITEM *aItem)
std::vector< CN_CLUSTER_PTR > CLUSTERS
const VECTOR2I GetSourcePos() const