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 SEGMENT;
43 class LINE;
44 class SOLID;
45 class VIA;
46 class INDEX;
47 class ROUTER;
48 class NODE;
49 
57 {
58 public:
59  virtual ~RULE_RESOLVER() {}
60 
61  virtual bool CollideHoles( const ITEM* aA, const ITEM* aB,
62  bool aNeedMTV, VECTOR2I* aMTV ) const = 0;
63 
64  virtual int Clearance( const ITEM* aA, const ITEM* aB ) const = 0;
65  virtual int Clearance( int aNetCode ) const = 0;
66  virtual int DpCoupledNet( int aNet ) = 0;
67  virtual int DpNetPolarity( int aNet ) = 0;
68  virtual bool DpNetPair( ITEM* aItem, int& aNetP, int& aNetN ) = 0;
69 
70  virtual wxString NetName( int aNet ) = 0;
71 };
72 
79 struct OBSTACLE
80 {
82  const ITEM* m_head;
83 
86 
89 
93 
96 };
97 
102 
103 public:
104 
105  OBSTACLE_VISITOR( const ITEM* aItem );
106 
107  void SetWorld( const NODE* aNode, const NODE* aOverride = NULL );
108 
109  virtual bool operator()( ITEM* aCandidate ) = 0;
110 
111 protected:
112 
113  bool visit( ITEM* aCandidate );
114 
116  const ITEM* m_item;
117 
119  const NODE* m_node;
120 
122  const NODE* m_override;
123 
126 };
127 
140 class NODE
141 {
142 public:
144  typedef std::vector<ITEM*> ITEM_VECTOR;
145  typedef std::vector<OBSTACLE> OBSTACLES;
146 
147  NODE();
148  ~NODE();
149 
151  int GetClearance( const ITEM* aA, const ITEM* aB ) const;
152 
154  int GetMaxClearance() const
155  {
156  return m_maxClearance;
157  }
158 
160  void SetMaxClearance( int aClearance )
161  {
162  m_maxClearance = aClearance;
163  }
164 
167  {
168  m_ruleResolver = aFunc;
169  }
170 
172  {
173  return m_ruleResolver;
174  }
175 
177  int JointCount() const
178  {
179  return m_joints.size();
180  }
181 
183  int Depth() const
184  {
185  return m_depth;
186  }
187 
198  int QueryColliding( const ITEM* aItem,
199  OBSTACLES& aObstacles,
200  int aKindMask = ITEM::ANY_T,
201  int aLimitCount = -1,
202  bool aDifferentNetsOnly = true,
203  int aForceClearance = -1 );
204 
205  int QueryColliding( const ITEM* aItem,
206  OBSTACLE_VISITOR& aVisitor
207  );
208 
218  OPT_OBSTACLE NearestObstacle( const LINE* aItem,
219  int aKindMask = ITEM::ANY_T,
220  const std::set<ITEM*>* aRestrictedSet = NULL );
221 
231  OPT_OBSTACLE CheckColliding( const ITEM* aItem,
232  int aKindMask = ITEM::ANY_T );
233 
234 
244  OPT_OBSTACLE CheckColliding( const ITEM_SET& aSet,
245  int aKindMask = ITEM::ANY_T );
246 
247 
258  bool CheckColliding( const ITEM* aItemA,
259  const ITEM* aItemB,
260  int aKindMask = ITEM::ANY_T,
261  int aForceClearance = -1 );
262 
270  const ITEM_SET HitTest( const VECTOR2I& aPoint ) const;
271 
281  bool Add( std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant = false );
282  void Add( std::unique_ptr< SOLID > aSolid );
283  void Add( std::unique_ptr< VIA > aVia );
284 
285  void Add( LINE& aLine, bool aAllowRedundant = false );
286 
287 private:
288  void Add( std::unique_ptr< ITEM > aItem, bool aAllowRedundant = false );
289 
290 public:
296  void Remove( SOLID* aSolid );
297  void Remove( VIA* aVia );
298  void Remove( SEGMENT* aSegment );
299  void Remove( ITEM* aItem );
300 
301 public:
308  void Remove( LINE& aLine );
309 
317  void Replace( ITEM* aOldItem, std::unique_ptr< ITEM > aNewItem );
318  void Replace( LINE& aOldLine, LINE& aNewLine );
319 
328  NODE* Branch();
329 
339  const LINE AssembleLine( SEGMENT* aSeg, int* aOriginSegmentIndex = NULL,
340  bool aStopAtLockedJoints = false );
341 
343  void Dump( bool aLong = false );
344 
353  void GetUpdatedItems( ITEM_VECTOR& aRemoved, ITEM_VECTOR& aAdded );
354 
362  void Commit( NODE* aNode );
363 
370  JOINT* FindJoint( const VECTOR2I& aPos, int aLayer, int aNet );
371 
372  void LockJoint( const VECTOR2I& aPos, const ITEM* aItem, bool aLock );
373 
380  JOINT* FindJoint( const VECTOR2I& aPos, const ITEM* aItem )
381  {
382  return FindJoint( aPos, aItem->Layers().Start(), aItem->Net() );
383  }
384 
385 #if 0
386  void MapConnectivity( JOINT* aStart, std::vector<JOINT*> & aFoundJoints );
387 
388  ITEM* NearestUnconnectedItem( JOINT* aStart, int* aAnchor = NULL,
389  int aKindMask = ITEM::ANY_T);
390 
391 #endif
392 
394  int FindLinesBetweenJoints( JOINT& aA,
395  JOINT& aB,
396  std::vector<LINE>& aLines );
397 
399  void FindLineEnds( const LINE& aLine, JOINT& aA, JOINT& aB );
400 
402  void KillChildren();
403 
404  void AllItemsInNet( int aNet, std::set<ITEM*>& aItems );
405 
406  void ClearRanks( int aMarkerMask = MK_HEAD | MK_VIOLATION );
407 
408  void RemoveByMarker( int aMarker );
409 
410  ITEM* FindItemByParent( const BOARD_CONNECTED_ITEM* aParent );
411 
412  bool HasChildren() const
413  {
414  return !m_children.empty();
415  }
416 
419  bool Overrides( ITEM* aItem ) const
420  {
421  return m_override.find( aItem ) != m_override.end();
422  }
423 
424 private:
426  typedef std::unordered_multimap<JOINT::HASH_TAG, JOINT, JOINT::JOINT_TAG_HASH> JOINT_MAP;
427  typedef JOINT_MAP::value_type TagJointPair;
428 
430  NODE( const NODE& aB );
431  NODE& operator=( const NODE& aB );
432 
434  JOINT& touchJoint( const VECTOR2I& aPos,
435  const LAYER_RANGE& aLayers,
436  int aNet );
437 
439  void linkJoint( const VECTOR2I& aPos, const LAYER_RANGE& aLayers, int aNet, ITEM* aWhere );
440 
442  void unlinkJoint( const VECTOR2I& aPos, const LAYER_RANGE& aLayers, int aNet, ITEM* aWhere );
443 
445  void addSolid( SOLID* aSeg );
446  void addSegment( SEGMENT* aSeg );
447  void addVia( VIA* aVia );
448 
449  void removeLine( LINE& aLine );
450  void removeSolidIndex( SOLID* aSeg );
451  void removeSegmentIndex( SEGMENT* aSeg );
452  void removeViaIndex( VIA* aVia );
453 
454  void doRemove( ITEM* aItem );
455  void unlinkParent();
456  void releaseChildren();
457  void releaseGarbage();
458 
459  bool isRoot() const
460  {
461  return m_parent == NULL;
462  }
463 
464  SEGMENT* findRedundantSegment( const VECTOR2I& A, const VECTOR2I& B,
465  const LAYER_RANGE & lr, int aNet );
467 
469  void followLine( SEGMENT* aCurrent,
470  bool aScanDirection,
471  int& aPos,
472  int aLimit,
473  VECTOR2I* aCorners,
474  SEGMENT** aSegments,
475  bool& aGuardHit,
476  bool aStopAtLockedJoints );
477 
481 
484 
487 
489  std::set<NODE*> m_children;
490 
492  std::unordered_set<ITEM*> m_override;
493 
496 
499 
502 
504  int m_depth;
505 
506  std::unordered_set<ITEM*> m_garbageItems;
507 };
508 
509 }
510 
511 #endif
Class ITEM.
Definition: pns_item.h:53
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION)
Definition: pns_node.cpp:1241
std::set< NODE * > m_children
list of nodes branched from this one
Definition: pns_node.h:489
ITEM * m_item
Item found to be colliding with m_head
Definition: pns_node.h:85
void followLine(SEGMENT *aCurrent, bool aScanDirection, int &aPos, int aLimit, VECTOR2I *aCorners, SEGMENT **aSegments, bool &aGuardHit, bool aStopAtLockedJoints)
scans the joint map, forming a line starting from segment (current).
Definition: pns_node.cpp:780
const NODE * m_node
node we are searching in (either root or a branch)
Definition: pns_node.h:119
VECTOR2I m_ipLast
Definition: pns_node.h:92
Class NODE.
Definition: pns_node.h:140
OPT_OBSTACLE NearestObstacle(const LINE *aItem, int aKindMask=ITEM::ANY_T, const std::set< ITEM * > *aRestrictedSet=NULL)
Function NearestObstacle()
Definition: pns_node.cpp:298
virtual bool CollideHoles(const ITEM *aA, const ITEM *aB, bool aNeedMTV, VECTOR2I *aMTV) const =0
virtual ~RULE_RESOLVER()
Definition: pns_node.h:59
void removeLine(LINE &aLine)
void releaseChildren()
Definition: pns_node.cpp:1164
virtual int DpCoupledNet(int aNet)=0
void unlinkParent()
Definition: pns_node.cpp:138
const LINE AssembleLine(SEGMENT *aSeg, int *aOriginSegmentIndex=NULL, bool aStopAtLockedJoints=false)
Function AssembleLine()
Definition: pns_node.cpp:820
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:920
int m_distFirst
... and the distance thereof
Definition: pns_node.h:95
void FindLineEnds(const LINE &aLine, JOINT &aA, JOINT &aB)
finds the joints corresponding to the ends of line aLine
Definition: pns_node.cpp:875
void AllItemsInNet(int aNet, std::set< ITEM * > &aItems)
Definition: pns_node.cpp:1219
void doRemove(ITEM *aItem)
Definition: pns_node.cpp:622
void removeSegmentIndex(SEGMENT *aSeg)
Definition: pns_node.cpp:643
int m_extraClearance
additional clearance
Definition: pns_node.h:125
bool HasChildren() const
Definition: pns_node.h:412
int JointCount() const
Returns the number of joints
Definition: pns_node.h:177
Class RULE_RESOLVER.
Definition: pns_node.h:56
int Depth() const
Returns the number of nodes in the inheritance chain (wrs to the root node)
Definition: pns_node.h:183
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:419
virtual bool operator()(ITEM *aCandidate)=0
void SetRuleResolver(RULE_RESOLVER *aFunc)
Assigns a clerance resolution function object
Definition: pns_node.h:166
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:1049
Class BOARD_CONNECTED_ITEM is a base class derived from BOARD_ITEM for items that can be connected an...
void Commit(NODE *aNode)
Function Commit()
Definition: pns_node.cpp:1192
NODE * Branch()
Function Branch()
Definition: pns_node.cpp:104
void unlinkJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
unlinks an item from a joint
Definition: pns_node.cpp:1058
bool isRoot() const
Definition: pns_node.h:459
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:501
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:160
void addSegment(SEGMENT *aSeg)
Definition: pns_node.cpp:582
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:486
int m_depth
depth of the node (number of parent nodes in the inheritance chain)
Definition: pns_node.h:504
Class JOINT.
Definition: pns_joint.h:43
RULE_RESOLVER * m_ruleResolver
Design rules resolver
Definition: pns_node.h:498
Struct OBSTACLE_VISITOR.
Definition: pns_node.h:101
void addSolid(SOLID *aSeg)
helpers for adding/removing items
Definition: pns_node.cpp:529
int GetClearance(const ITEM *aA, const ITEM *aB) const
Returns the expected clearance between items a and b.
Definition: pns_node.cpp:95
void KillChildren()
Destroys all child nodes. Applicable only to the root node.
Definition: pns_node.cpp:1212
std::unordered_multimap< JOINT::HASH_TAG, JOINT, JOINT::JOINT_TAG_HASH > JOINT_MAP
Definition: pns_node.h:425
int Net() const
Definition: pns_item.h:148
JOINT * FindJoint(const VECTOR2I &aPos, const ITEM *aItem)
Function FindJoint()
Definition: pns_node.h:380
SEGMENT * findRedundantSegment(const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, int aNet)
Definition: pns_node.cpp:1265
virtual int Clearance(const ITEM *aA, const ITEM *aB) const =0
OBSTACLE_VISITOR(const ITEM *aItem)
Definition: pns_node.cpp:147
bool visit(ITEM *aCandidate)
Definition: pns_node.cpp:163
std::unordered_set< ITEM * > m_override
hash of root's items that have been changed in this node
Definition: pns_node.h:492
void SetWorld(const NODE *aNode, const NODE *aOverride=NULL)
Definition: pns_node.cpp:156
const ITEM * m_item
the item we are looking for collisions with
Definition: pns_node.h:116
void releaseGarbage()
Definition: pns_node.cpp:1177
void addVia(VIA *aVia)
Definition: pns_node.cpp:541
virtual bool DpNetPair(ITEM *aItem, int &aNetP, int &aNetN)=0
int m_distLast
Definition: pns_node.h:95
const ITEM_SET HitTest(const VECTOR2I &aPoint) const
Function HitTest()
Definition: pns_node.cpp:500
void Remove(SOLID *aSolid)
Function Remove()
Definition: pns_node.cpp:715
SHAPE_LINE_CHAIN m_hull
Hull of the colliding m_item
Definition: pns_node.h:88
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:954
RULE_RESOLVER * GetRuleResolver() const
Definition: pns_node.h:171
void Replace(ITEM *aOldItem, std::unique_ptr< ITEM > aNewItem)
Function Replace()
Definition: pns_node.cpp:703
void RemoveByMarker(int aMarker)
Definition: pns_node.cpp:1251
void removeSolidIndex(SOLID *aSeg)
Definition: pns_node.cpp:697
JOINT_MAP::value_type TagJointPair
Definition: pns_node.h:427
void Dump(bool aLong=false)
Prints the contents and joints structure
Definition: pns_node.cpp:1068
Class SHAPE_LINE_CHAIN.
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Function CheckColliding()
Definition: pns_node.cpp:421
int GetMaxClearance() const
Returns the pre-set worst case clearance between any pair of items
Definition: pns_node.h:154
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:991
std::unordered_set< ITEM * > m_garbageItems
Definition: pns_node.h:506
void removeViaIndex(VIA *aVia)
Definition: pns_node.cpp:649
const ITEM * m_head
Item we search collisions with
Definition: pns_node.h:82
ITEM * FindItemByParent(const BOARD_CONNECTED_ITEM *aParent)
Definition: pns_node.cpp:1297
boost::optional< T > OPT
Definition: optional.h:7
void GetUpdatedItems(ITEM_VECTOR &aRemoved, ITEM_VECTOR &aAdded)
Function GetUpdatedItems()
Definition: pns_node.cpp:1149
OPT< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:143
virtual int DpNetPolarity(int aNet)=0
virtual wxString NetName(int aNet)=0
int m_maxClearance
worst case item-item clearance
Definition: pns_node.h:495
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:480
VECTOR2I m_ipFirst
First and last intersection point between the head item and the hull of the colliding m_item
Definition: pns_node.h:92
std::vector< OBSTACLE > OBSTACLES
Definition: pns_node.h:145
const NODE * m_override
node that overrides root entries
Definition: pns_node.h:122
Push and Shove diff pair dimensions (gap) settings dialog.
NODE * m_parent
node this node was branched from
Definition: pns_node.h:483
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:272
NODE & operator=(const NODE &aB)
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:590
Class INDEX.
Definition: pns_index.h:46
Class LAYER_RANGE.
Definition: pns_layerset.h:32
const LAYER_RANGE & Layers() const
Definition: pns_item.h:150
void LockJoint(const VECTOR2I &aPos, const ITEM *aItem, bool aLock)
Definition: pns_node.cpp:984
std::vector< ITEM * > ITEM_VECTOR
Definition: pns_node.h:144
Struct OBSTACLE.
Definition: pns_node.h:79