KiCad PCB EDA Suite
pns_node.h
Go to the documentation of this file.
1 /*
2  * KiRouter - a push-and-(sometimes-)shove PCB router
3  *
4  * Copyright (C) 2013-2014 CERN
5  * Copyright (C) 2016 KiCad Developers, see AUTHORS.txt for contributors.
6  * Author: Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
7  *
8  * This program is free software: you can redistribute it and/or modify it
9  * under the terms of the GNU General Public License as published by the
10  * Free Software Foundation, either version 3 of the License, or (at your
11  * option) any later version.
12  *
13  * This program is distributed in the hope that it will be useful, but
14  * WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16  * General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License along
19  * with this program. If not, see <http://www.gnu.org/licenses/>.
20  */
21 
22 #ifndef __PNS_NODE_H
23 #define __PNS_NODE_H
24 
25 #include <vector>
26 #include <list>
27 #include <unordered_set>
28 #include <unordered_map>
29 
30 #include <core/optional.h>
31 
32 #include <geometry/shape.h>
34 #include <geometry/shape_index.h>
35 
36 #include "pns_item.h"
37 #include "pns_joint.h"
38 #include "pns_itemset.h"
39 
40 namespace PNS {
41 
42 class ARC;
43 class SEGMENT;
44 class LINE;
45 class SOLID;
46 class VIA;
47 class INDEX;
48 class ROUTER;
49 class NODE;
50 
58 {
59 public:
60  virtual ~RULE_RESOLVER() {}
61 
62  virtual bool CollideHoles( const ITEM* aA, const ITEM* aB,
63  bool aNeedMTV, VECTOR2I* aMTV ) const = 0;
64 
65  virtual int Clearance( const ITEM* aA, const ITEM* aB ) const = 0;
66  virtual int Clearance( int aNetCode ) const = 0;
67  virtual int DpCoupledNet( int aNet ) = 0;
68  virtual int DpNetPolarity( int aNet ) = 0;
69  virtual bool DpNetPair( ITEM* aItem, int& aNetP, int& aNetN ) = 0;
70 
71  virtual wxString NetName( int aNet ) = 0;
72 };
73 
80 struct OBSTACLE
81 {
83  const ITEM* m_head;
84 
87 
90 
94 
97 };
98 
103 
104 public:
105 
106  OBSTACLE_VISITOR( const ITEM* aItem );
107 
109  {
110  }
111 
112  void SetWorld( const NODE* aNode, const NODE* aOverride = NULL );
113 
114  virtual bool operator()( ITEM* aCandidate ) = 0;
115 
116 protected:
117 
118  bool visit( ITEM* aCandidate );
119 
121  const ITEM* m_item;
122 
124  const NODE* m_node;
125 
127  const NODE* m_override;
128 
131 };
132 
145 class NODE
146 {
147 public:
149  typedef std::vector<ITEM*> ITEM_VECTOR;
150  typedef std::vector<OBSTACLE> OBSTACLES;
151 
152  NODE();
153  ~NODE();
154 
156  int GetClearance( const ITEM* aA, const ITEM* aB ) const;
157 
159  int GetMaxClearance() const
160  {
161  return m_maxClearance;
162  }
163 
165  void SetMaxClearance( int aClearance )
166  {
167  m_maxClearance = aClearance;
168  }
169 
172  {
173  m_ruleResolver = aFunc;
174  }
175 
177  {
178  return m_ruleResolver;
179  }
180 
182  int JointCount() const
183  {
184  return m_joints.size();
185  }
186 
188  int Depth() const
189  {
190  return m_depth;
191  }
192 
203  int QueryColliding( const ITEM* aItem,
204  OBSTACLES& aObstacles,
205  int aKindMask = ITEM::ANY_T,
206  int aLimitCount = -1,
207  bool aDifferentNetsOnly = true,
208  int aForceClearance = -1 );
209 
210  int QueryJoints( const BOX2I& aBox, std::vector<JOINT*> & aJoints, int aLayerMask = -1, int aKindMask = ITEM::ANY_T);
211 
212  int QueryColliding( const ITEM* aItem,
213  OBSTACLE_VISITOR& aVisitor
214  );
215 
225  OPT_OBSTACLE NearestObstacle( const LINE* aItem,
226  int aKindMask = ITEM::ANY_T,
227  const std::set<ITEM*>* aRestrictedSet = NULL );
228 
238  OPT_OBSTACLE CheckColliding( const ITEM* aItem,
239  int aKindMask = ITEM::ANY_T );
240 
241 
251  OPT_OBSTACLE CheckColliding( const ITEM_SET& aSet,
252  int aKindMask = ITEM::ANY_T );
253 
254 
265  bool CheckColliding( const ITEM* aItemA,
266  const ITEM* aItemB,
267  int aKindMask = ITEM::ANY_T,
268  int aForceClearance = -1 );
269 
277  const ITEM_SET HitTest( const VECTOR2I& aPoint ) const;
278 
288  bool Add( std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant = false );
289  void Add( std::unique_ptr< SOLID > aSolid );
290  void Add( std::unique_ptr< VIA > aVia );
291  void Add( std::unique_ptr< ARC > aArc );
292 
293  void Add( LINE& aLine, bool aAllowRedundant = false );
294 
295 private:
296  void Add( std::unique_ptr< ITEM > aItem, bool aAllowRedundant = false );
297 
298 public:
304  void Remove( ARC* aArc );
305  void Remove( SOLID* aSolid );
306  void Remove( VIA* aVia );
307  void Remove( SEGMENT* aSegment );
308  void Remove( ITEM* aItem );
309 
310 public:
317  void Remove( LINE& aLine );
318 
326  void Replace( ITEM* aOldItem, std::unique_ptr< ITEM > aNewItem );
327  void Replace( LINE& aOldLine, LINE& aNewLine );
328 
337  NODE* Branch();
338 
348  const LINE AssembleLine( LINKED_ITEM* aSeg, int* aOriginSegmentIndex = NULL,
349  bool aStopAtLockedJoints = false );
350 
352  void Dump( bool aLong = false );
353 
362  void GetUpdatedItems( ITEM_VECTOR& aRemoved, ITEM_VECTOR& aAdded );
363 
371  void Commit( NODE* aNode );
372 
379  JOINT* FindJoint( const VECTOR2I& aPos, int aLayer, int aNet );
380 
381  void LockJoint( const VECTOR2I& aPos, const ITEM* aItem, bool aLock );
382 
389  JOINT* FindJoint( const VECTOR2I& aPos, const ITEM* aItem )
390  {
391  return FindJoint( aPos, aItem->Layers().Start(), aItem->Net() );
392  }
393 
394 #if 0
395  void MapConnectivity( JOINT* aStart, std::vector<JOINT*> & aFoundJoints );
396 
397  ITEM* NearestUnconnectedItem( JOINT* aStart, int* aAnchor = NULL,
398  int aKindMask = ITEM::ANY_T);
399 
400 #endif
401 
403  int FindLinesBetweenJoints( JOINT& aA,
404  JOINT& aB,
405  std::vector<LINE>& aLines );
406 
408  void FindLineEnds( const LINE& aLine, JOINT& aA, JOINT& aB );
409 
411  void KillChildren();
412 
413  void AllItemsInNet( int aNet, std::set<ITEM*>& aItems );
414 
415  void ClearRanks( int aMarkerMask = MK_HEAD | MK_VIOLATION );
416 
417  void RemoveByMarker( int aMarker );
418 
419  const ITEM_SET FindItemsByParent( const BOARD_CONNECTED_ITEM* aParent );
420  ITEM* FindItemByParent( const BOARD_CONNECTED_ITEM* aParent );
421 
422  bool HasChildren() const
423  {
424  return !m_children.empty();
425  }
426 
427  NODE* GetParent() const
428  {
429  return m_parent;
430  }
431 
434  bool Overrides( ITEM* aItem ) const
435  {
436  return m_override.find( aItem ) != m_override.end();
437  }
438 
439 private:
441  typedef std::unordered_multimap<JOINT::HASH_TAG, JOINT, JOINT::JOINT_TAG_HASH> JOINT_MAP;
442  typedef JOINT_MAP::value_type TagJointPair;
443 
445  NODE( const NODE& aB );
446  NODE& operator=( const NODE& aB );
447 
449  JOINT& touchJoint( const VECTOR2I& aPos,
450  const LAYER_RANGE& aLayers,
451  int aNet );
452 
454  void linkJoint( const VECTOR2I& aPos, const LAYER_RANGE& aLayers, int aNet, ITEM* aWhere );
455 
457  void unlinkJoint( const VECTOR2I& aPos, const LAYER_RANGE& aLayers, int aNet, ITEM* aWhere );
458 
460  void addSolid( SOLID* aSeg );
461  void addSegment( SEGMENT* aSeg );
462  void addVia( VIA* aVia );
463  void addArc( ARC* aVia );
464 
465  void removeLine( LINE& aLine );
466  void removeSolidIndex( SOLID* aSeg );
467  void removeSegmentIndex( SEGMENT* aSeg );
468  void removeViaIndex( VIA* aVia );
469  void removeArcIndex( ARC* aVia );
470 
471  void doRemove( ITEM* aItem );
472  void unlinkParent();
473  void releaseChildren();
474  void releaseGarbage();
475  void rebuildJoint( JOINT* aJoint, ITEM* aItem );
476 
477  bool isRoot() const
478  {
479  return m_parent == NULL;
480  }
481 
482  SEGMENT* findRedundantSegment( const VECTOR2I& A, const VECTOR2I& B,
483  const LAYER_RANGE & lr, int aNet );
485 
486  ARC* findRedundantArc( const VECTOR2I& A, const VECTOR2I& B,
487  const LAYER_RANGE & lr, int aNet );
488  ARC* findRedundantArc( ARC* aSeg );
489 
491  void followLine( LINKED_ITEM* aCurrent, int aScanDirection, int& aPos, int aLimit, VECTOR2I* aCorners,
492  LINKED_ITEM** aSegments, bool& aGuardHit, bool aStopAtLockedJoints );
493 
497 
500 
503 
505  std::set<NODE*> m_children;
506 
508  std::unordered_set<ITEM*> m_override;
509 
512 
515 
518 
520  int m_depth;
521 
522  std::unordered_set<ITEM*> m_garbageItems;
523 };
524 
525 }
526 
527 #endif
ITEM.
Definition: pns_item.h:53
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION)
Definition: pns_node.cpp:1316
std::set< NODE * > m_children
list of nodes branched from this one
Definition: pns_node.h:505
ITEM * m_item
Item found to be colliding with m_head
Definition: pns_node.h:86
const NODE * m_node
node we are searching in (either root or a branch)
Definition: pns_node.h:124
VECTOR2I m_ipLast
Definition: pns_node.h:93
NODE.
Definition: pns_node.h:145
OPT_OBSTACLE NearestObstacle(const LINE *aItem, int aKindMask=ITEM::ANY_T, const std::set< ITEM * > *aRestrictedSet=NULL)
Function NearestObstacle()
Definition: pns_node.cpp:304
virtual bool CollideHoles(const ITEM *aA, const ITEM *aB, bool aNeedMTV, VECTOR2I *aMTV) const =0
virtual ~RULE_RESOLVER()
Definition: pns_node.h:60
void removeLine(LINE &aLine)
void releaseChildren()
Definition: pns_node.cpp:1240
virtual int DpCoupledNet(int aNet)=0
void unlinkParent()
Definition: pns_node.cpp:140
int FindLinesBetweenJoints(JOINT &aA, JOINT &aB, std::vector< LINE > &aLines)
finds all lines between a pair of joints. Used by the loop removal procedure.
Definition: pns_node.cpp:993
int m_distFirst
... and the distance thereof
Definition: pns_node.h:96
void FindLineEnds(const LINE &aLine, JOINT &aA, JOINT &aB)
finds the joints corresponding to the ends of line aLine
Definition: pns_node.cpp:948
void AllItemsInNet(int aNet, std::set< ITEM * > &aItems)
Definition: pns_node.cpp:1294
void doRemove(ITEM *aItem)
Definition: pns_node.cpp:671
void removeSegmentIndex(SEGMENT *aSeg)
Definition: pns_node.cpp:692
int m_extraClearance
additional clearance
Definition: pns_node.h:130
bool HasChildren() const
Definition: pns_node.h:422
int JointCount() const
Returns the number of joints
Definition: pns_node.h:182
int QueryJoints(const BOX2I &aBox, std::vector< JOINT * > &aJoints, int aLayerMask=-1, int aKindMask=ITEM::ANY_T)
Definition: pns_node.cpp:1403
RULE_RESOLVER.
Definition: pns_node.h:57
int Depth() const
Returns the number of nodes in the inheritance chain (wrs to the root node)
Definition: pns_node.h:188
bool Overrides(ITEM *aItem) const
checks if this branch contains an updated version of the m_item from the root branch.
Definition: pns_node.h:434
virtual bool operator()(ITEM *aCandidate)=0
void SetRuleResolver(RULE_RESOLVER *aFunc)
Assigns a clerance resolution function object
Definition: pns_node.h:171
void linkJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
touches a joint and links it to an m_item
Definition: pns_node.cpp:1122
BOARD_CONNECTED_ITEM is a base class derived from BOARD_ITEM for items that can be connected and have...
void Commit(NODE *aNode)
Function Commit()
Definition: pns_node.cpp:1268
NODE * Branch()
Function Branch()
Definition: pns_node.cpp:106
void unlinkJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
unlinks an item from a joint
Definition: pns_node.cpp:1131
bool isRoot() const
Definition: pns_node.h:477
virtual ~OBSTACLE_VISITOR()
Definition: pns_node.h:108
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:517
void Remove(ARC *aArc)
Function Remove()
Definition: pns_node.cpp:796
int Start() const
Definition: pns_layerset.h:83
void SetMaxClearance(int aClearance)
Sets the worst-case clerance between any pair of items
Definition: pns_node.h:165
void addSegment(SEGMENT *aSeg)
Definition: pns_node.cpp:612
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:502
int m_depth
depth of the node (number of parent nodes in the inheritance chain)
Definition: pns_node.h:520
JOINT.
Definition: pns_joint.h:43
RULE_RESOLVER * m_ruleResolver
Design rules resolver
Definition: pns_node.h:514
Struct OBSTACLE_VISITOR.
Definition: pns_node.h:102
void addSolid(SOLID *aSeg)
helpers for adding/removing items
Definition: pns_node.cpp:539
int GetClearance(const ITEM *aA, const ITEM *aB) const
Returns the expected clearance between items a and b.
Definition: pns_node.cpp:97
void KillChildren()
Destroys all child nodes. Applicable only to the root node.
Definition: pns_node.cpp:1288
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=NULL, bool aStopAtLockedJoints=false)
Function AssembleLine()
Definition: pns_node.cpp:893
#define NULL
void rebuildJoint(JOINT *aJoint, ITEM *aItem)
Definition: pns_node.cpp:706
std::unordered_multimap< JOINT::HASH_TAG, JOINT, JOINT::JOINT_TAG_HASH > JOINT_MAP
Definition: pns_node.h:440
int Net() const
Definition: pns_item.h:149
JOINT * FindJoint(const VECTOR2I &aPos, const ITEM *aItem)
Function FindJoint()
Definition: pns_node.h:389
SEGMENT * findRedundantSegment(const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, int aNet)
Definition: pns_node.cpp:1340
virtual int Clearance(const ITEM *aA, const ITEM *aB) const =0
OBSTACLE_VISITOR(const ITEM *aItem)
Definition: pns_node.cpp:149
bool visit(ITEM *aCandidate)
Definition: pns_node.cpp:165
std::unordered_set< ITEM * > m_override
hash of root's items that have been changed in this node
Definition: pns_node.h:508
void SetWorld(const NODE *aNode, const NODE *aOverride=NULL)
Definition: pns_node.cpp:158
const ITEM * m_item
the item we are looking for collisions with
Definition: pns_node.h:121
void releaseGarbage()
Definition: pns_node.cpp:1253
void addVia(VIA *aVia)
Definition: pns_node.cpp:553
virtual bool DpNetPair(ITEM *aItem, int &aNetP, int &aNetN)=0
int m_distLast
Definition: pns_node.h:96
ARC * findRedundantArc(const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, int aNet)
Definition: pns_node.cpp:1371
const ITEM_SET HitTest(const VECTOR2I &aPoint) const
Function HitTest()
Definition: pns_node.cpp:510
void addArc(ARC *aVia)
Definition: pns_node.cpp:637
SHAPE_LINE_CHAIN m_hull
Hull of the colliding m_item
Definition: pns_node.h:89
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:1027
RULE_RESOLVER * GetRuleResolver() const
Definition: pns_node.h:176
const ITEM_SET FindItemsByParent(const BOARD_CONNECTED_ITEM *aParent)
void Replace(ITEM *aOldItem, std::unique_ptr< ITEM > aNewItem)
Function Replace()
Definition: pns_node.cpp:766
void RemoveByMarker(int aMarker)
Definition: pns_node.cpp:1326
void removeSolidIndex(SOLID *aSeg)
Definition: pns_node.cpp:757
JOINT_MAP::value_type TagJointPair
Definition: pns_node.h:442
void Dump(bool aLong=false)
Prints the contents and joints structure
Definition: pns_node.cpp:1141
NODE * GetParent() const
Definition: pns_node.h:427
SHAPE_LINE_CHAIN.
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Function CheckColliding()
Definition: pns_node.cpp:427
int GetMaxClearance() const
Returns the pre-set worst case clearance between any pair of items
Definition: pns_node.h:159
JOINT & touchJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet)
tries to find matching joint and creates a new one if not found
Definition: pns_node.cpp:1064
std::unordered_set< ITEM * > m_garbageItems
Definition: pns_node.h:522
void removeViaIndex(VIA *aVia)
Definition: pns_node.cpp:749
const ITEM * m_head
Item we search collisions with
Definition: pns_node.h:83
ITEM * FindItemByParent(const BOARD_CONNECTED_ITEM *aParent)
Definition: pns_node.cpp:1443
boost::optional< T > OPT
Definition: optional.h:7
void GetUpdatedItems(ITEM_VECTOR &aRemoved, ITEM_VECTOR &aAdded)
Function GetUpdatedItems()
Definition: pns_node.cpp:1222
void removeArcIndex(ARC *aVia)
Definition: pns_node.cpp:699
OPT< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:148
virtual int DpNetPolarity(int aNet)=0
virtual wxString NetName(int aNet)=0
int m_maxClearance
worst case item-item clearance
Definition: pns_node.h:511
void followLine(LINKED_ITEM *aCurrent, int aScanDirection, int &aPos, int aLimit, VECTOR2I *aCorners, LINKED_ITEM **aSegments, bool &aGuardHit, bool aStopAtLockedJoints)
scans the joint map, forming a line starting from segment (current).
Definition: pns_node.cpp:856
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:496
VECTOR2I m_ipFirst
First and last intersection point between the head item and the hull of the colliding m_item
Definition: pns_node.h:93
std::vector< OBSTACLE > OBSTACLES
Definition: pns_node.h:150
const NODE * m_override
node that overrides root entries
Definition: pns_node.h:127
Push and Shove diff pair dimensions (gap) settings dialog.
NODE * m_parent
node this node was branched from
Definition: pns_node.h:499
int QueryColliding(const ITEM *aItem, OBSTACLES &aObstacles, int aKindMask=ITEM::ANY_T, int aLimitCount=-1, bool aDifferentNetsOnly=true, int aForceClearance=-1)
Function QueryColliding()
Definition: pns_node.cpp:278
NODE & operator=(const NODE &aB)
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:620
INDEX.
Definition: pns_index.h:45
LAYER_RANGE.
Definition: pns_layerset.h:32
const LAYER_RANGE & Layers() const
Definition: pns_item.h:151
void LockJoint(const VECTOR2I &aPos, const ITEM *aItem, bool aLock)
Definition: pns_node.cpp:1057
std::vector< ITEM * > ITEM_VECTOR
Definition: pns_node.h:149
Struct OBSTACLE.
Definition: pns_node.h:80