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 
28 #include <boost/unordered_set.hpp>
29 #include <boost/unordered_map.hpp>
30 #include <boost/optional.hpp>
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 int Clearance( const ITEM* aA, const ITEM* aB ) const = 0;
62  virtual int Clearance( int aNetCode ) const = 0;
63  virtual void OverrideClearance( bool aEnable, int aNetA = 0, int aNetB = 0, int aClearance = 0 ) = 0;
64  virtual void UseDpGap( bool aUseDpGap ) = 0;
65  virtual int DpCoupledNet( int aNet ) = 0;
66  virtual int DpNetPolarity( int aNet ) = 0;
67  virtual bool DpNetPair( ITEM* aItem, int& aNetP, int& aNetN ) = 0;
68 };
69 
76 struct OBSTACLE
77 {
79  const ITEM* m_head;
80 
83 
86 
90 
93 };
94 
99 
100 public:
101 
102  OBSTACLE_VISITOR( const ITEM* aItem );
103 
104  void SetWorld( const NODE* aNode, const NODE* aOverride = NULL );
105 
106  virtual bool operator()( ITEM* aCandidate ) = 0;
107 
108 protected:
109 
110  bool visit( ITEM* aCandidate );
111 
113  const ITEM* m_item;
114 
116  const NODE* m_node;
117 
119  const NODE* m_override;
120 
123 };
124 
137 class NODE
138 {
139 public:
141  typedef std::vector<ITEM*> ITEM_VECTOR;
142  typedef std::vector<OBSTACLE> OBSTACLES;
143 
144  NODE();
145  ~NODE();
146 
148  int GetClearance( const ITEM* aA, const ITEM* aB ) const;
149 
151  int GetMaxClearance() const
152  {
153  return m_maxClearance;
154  }
155 
157  void SetMaxClearance( int aClearance )
158  {
159  m_maxClearance = aClearance;
160  }
161 
164  {
165  m_ruleResolver = aFunc;
166  }
167 
169  {
170  return m_ruleResolver;
171  }
172 
174  int JointCount() const
175  {
176  return m_joints.size();
177  }
178 
180  int Depth() const
181  {
182  return m_depth;
183  }
184 
195  int QueryColliding( const ITEM* aItem,
196  OBSTACLES& aObstacles,
197  int aKindMask = ITEM::ANY_T,
198  int aLimitCount = -1,
199  bool aDifferentNetsOnly = true,
200  int aForceClearance = -1 );
201 
202  int QueryColliding( const ITEM* aItem,
203  OBSTACLE_VISITOR& aVisitor
204  );
205 
215  OPT_OBSTACLE NearestObstacle( const LINE* aItem,
216  int aKindMask = ITEM::ANY_T,
217  const std::set<ITEM*>* aRestrictedSet = NULL );
218 
228  OPT_OBSTACLE CheckColliding( const ITEM* aItem,
229  int aKindMask = ITEM::ANY_T );
230 
231 
241  OPT_OBSTACLE CheckColliding( const ITEM_SET& aSet,
242  int aKindMask = ITEM::ANY_T );
243 
244 
255  bool CheckColliding( const ITEM* aItemA,
256  const ITEM* aItemB,
257  int aKindMask = ITEM::ANY_T,
258  int aForceClearance = -1 );
259 
267  const ITEM_SET HitTest( const VECTOR2I& aPoint ) const;
268 
277  void Add( std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant = false );
278  void Add( std::unique_ptr< SOLID > aSolid );
279  void Add( std::unique_ptr< VIA > aVia );
280 
281  void Add( LINE& aLine, bool aAllowRedundant = false );
282 
283 private:
284  void Add( std::unique_ptr< ITEM > aItem, bool aAllowRedundant = false );
285 
286 public:
292  void Remove( SOLID* aSolid );
293  void Remove( VIA* aVia );
294  void Remove( SEGMENT* aSegment );
295  void Remove( ITEM* aItem );
296 
297 public:
304  void Remove( LINE& aLine );
305 
313  void Replace( ITEM* aOldItem, std::unique_ptr< ITEM > aNewItem );
314  void Replace( LINE& aOldLine, LINE& aNewLine );
315 
324  NODE* Branch();
325 
335  const LINE AssembleLine( SEGMENT* aSeg, int* aOriginSegmentIndex = NULL,
336  bool aStopAtLockedJoints = false );
337 
339  void Dump( bool aLong = false );
340 
349  void GetUpdatedItems( ITEM_VECTOR& aRemoved, ITEM_VECTOR& aAdded );
350 
358  void Commit( NODE* aNode );
359 
366  JOINT* FindJoint( const VECTOR2I& aPos, int aLayer, int aNet );
367 
368  void LockJoint( const VECTOR2I& aPos, const ITEM* aItem, bool aLock );
369 
376  JOINT* FindJoint( const VECTOR2I& aPos, const ITEM* aItem )
377  {
378  return FindJoint( aPos, aItem->Layers().Start(), aItem->Net() );
379  }
380 
381 #if 0
382  void MapConnectivity( JOINT* aStart, std::vector<JOINT*> & aFoundJoints );
383 
384  ITEM* NearestUnconnectedItem( JOINT* aStart, int* aAnchor = NULL,
385  int aKindMask = ITEM::ANY_T);
386 
387 #endif
388 
390  int FindLinesBetweenJoints( JOINT& aA,
391  JOINT& aB,
392  std::vector<LINE>& aLines );
393 
395  void FindLineEnds( const LINE& aLine, JOINT& aA, JOINT& aB );
396 
398  void KillChildren();
399 
400  void AllItemsInNet( int aNet, std::set<ITEM*>& aItems );
401 
402  void ClearRanks( int aMarkerMask = MK_HEAD | MK_VIOLATION );
403 
404  int FindByMarker( int aMarker, ITEM_SET& aItems );
405  int RemoveByMarker( int aMarker );
406 
407  ITEM* FindItemByParent( const BOARD_CONNECTED_ITEM* aParent );
408 
409  bool HasChildren() const
410  {
411  return !m_children.empty();
412  }
413 
416  bool Overrides( ITEM* aItem ) const
417  {
418  return m_override.find( aItem ) != m_override.end();
419  }
420 
421 private:
423  typedef boost::unordered_multimap<JOINT::HASH_TAG, JOINT> JOINT_MAP;
424  typedef JOINT_MAP::value_type TagJointPair;
425 
427  NODE( const NODE& aB );
428  NODE& operator=( const NODE& aB );
429 
431  JOINT& touchJoint( const VECTOR2I& aPos,
432  const LAYER_RANGE& aLayers,
433  int aNet );
434 
436  void linkJoint( const VECTOR2I& aPos, const LAYER_RANGE& aLayers, int aNet, ITEM* aWhere );
437 
439  void unlinkJoint( const VECTOR2I& aPos, const LAYER_RANGE& aLayers, int aNet, ITEM* aWhere );
440 
442  void addSolid( SOLID* aSeg );
443  void addSegment( SEGMENT* aSeg );
444  void addVia( VIA* aVia );
445 
446  void removeLine( LINE& aLine );
447  void removeSolidIndex( SOLID* aSeg );
448  void removeSegmentIndex( SEGMENT* aSeg );
449  void removeViaIndex( VIA* aVia );
450 
451  void doRemove( ITEM* aItem );
452  void unlinkParent();
453  void releaseChildren();
454  void releaseGarbage();
455 
456  bool isRoot() const
457  {
458  return m_parent == NULL;
459  }
460 
461  SEGMENT* findRedundantSegment( const VECTOR2I& A, const VECTOR2I& B,
462  const LAYER_RANGE & lr, int aNet );
464 
466  void followLine( SEGMENT* aCurrent,
467  bool aScanDirection,
468  int& aPos,
469  int aLimit,
470  VECTOR2I* aCorners,
471  SEGMENT** aSegments,
472  bool& aGuardHit,
473  bool aStopAtLockedJoints );
474 
477  JOINT_MAP m_joints;
478 
481 
484 
486  std::set<NODE*> m_children;
487 
489  boost::unordered_set<ITEM*> m_override;
490 
493 
496 
499 
501  int m_depth;
502 
503  boost::unordered_set<ITEM*> m_garbageItems;
504 };
505 
506 }
507 
508 #endif
Class ITEM.
Definition: pns_item.h:53
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION)
Definition: pns_node.cpp:1256
std::set< NODE * > m_children
list of nodes branched from this one
Definition: pns_node.h:486
ITEM * m_item
Item found to be colliding with m_head
Definition: pns_node.h:82
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:794
int Depth() const
Returns the number of nodes in the inheritance chain (wrs to the root node)
Definition: pns_node.h:180
const NODE * m_node
node we are searching in (either root or a branch)
Definition: pns_node.h:116
VECTOR2I m_ipLast
Definition: pns_node.h:89
int GetMaxClearance() const
Returns the pre-set worst case clearance between any pair of items
Definition: pns_node.h:151
Class NODE.
Definition: pns_node.h:137
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 ~RULE_RESOLVER()
Definition: pns_node.h:59
const LAYER_RANGE & Layers() const
Function Layers()
Definition: pns_item.h:207
void removeLine(LINE &aLine)
boost::unordered_multimap< JOINT::HASH_TAG, JOINT > JOINT_MAP
Definition: pns_node.h:422
void releaseChildren()
Definition: pns_node.cpp:1178
virtual int DpCoupledNet(int aNet)=0
void unlinkParent()
Definition: pns_node.cpp:143
const LINE AssembleLine(SEGMENT *aSeg, int *aOriginSegmentIndex=NULL, bool aStopAtLockedJoints=false)
Function AssembleLine()
Definition: pns_node.cpp:834
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:934
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:416
int m_distFirst
... and the distance thereof
Definition: pns_node.h:92
void FindLineEnds(const LINE &aLine, JOINT &aA, JOINT &aB)
finds the joints corresponding to the ends of line aLine
Definition: pns_node.cpp:889
void AllItemsInNet(int aNet, std::set< ITEM * > &aItems)
Definition: pns_node.cpp:1234
void doRemove(ITEM *aItem)
Definition: pns_node.cpp:637
void removeSegmentIndex(SEGMENT *aSeg)
Definition: pns_node.cpp:658
int m_extraClearance
additional clearance
Definition: pns_node.h:122
Class RULE_RESOLVER.
Definition: pns_node.h:56
boost::optional< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:140
virtual bool operator()(ITEM *aCandidate)=0
void SetRuleResolver(RULE_RESOLVER *aFunc)
Assigns a clerance resolution function object
Definition: pns_node.h:163
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:1063
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:1206
NODE * Branch()
Function Branch()
Definition: pns_node.cpp:109
void unlinkJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
unlinks an item from a joint
Definition: pns_node.cpp:1072
const ITEM_SET HitTest(const VECTOR2I &aPoint) const
Function HitTest()
Definition: pns_node.cpp:506
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:498
void SetMaxClearance(int aClearance)
Sets the worst-case clerance between any pair of items
Definition: pns_node.h:157
void addSegment(SEGMENT *aSeg)
Definition: pns_node.cpp:588
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:483
int m_depth
depth of the node (number of parent nodes in the inheritance chain)
Definition: pns_node.h:501
Class JOINT.
Definition: pns_joint.h:44
RULE_RESOLVER * m_ruleResolver
Design rules resolver
Definition: pns_node.h:495
Struct OBSTACLE_VISITOR.
Definition: pns_node.h:98
void addSolid(SOLID *aSeg)
helpers for adding/removing items
Definition: pns_node.cpp:535
void KillChildren()
Destroys all child nodes. Applicable only to the root node.
Definition: pns_node.cpp:1227
JOINT * FindJoint(const VECTOR2I &aPos, const ITEM *aItem)
Function FindJoint()
Definition: pns_node.h:376
SEGMENT * findRedundantSegment(const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, int aNet)
Definition: pns_node.cpp:1298
virtual int Clearance(const ITEM *aA, const ITEM *aB) const =0
OBSTACLE_VISITOR(const ITEM *aItem)
Definition: pns_node.cpp:152
boost::unordered_set< ITEM * > m_override
hash of root's items that have been changed in this node
Definition: pns_node.h:489
bool visit(ITEM *aCandidate)
Definition: pns_node.cpp:169
void SetWorld(const NODE *aNode, const NODE *aOverride=NULL)
Definition: pns_node.cpp:162
const ITEM * m_item
the item we are looking for collisions with
Definition: pns_node.h:113
void releaseGarbage()
Definition: pns_node.cpp:1191
void addVia(VIA *aVia)
Definition: pns_node.cpp:547
int Start() const
Definition: pns_layerset.h:83
bool isRoot() const
Definition: pns_node.h:456
virtual bool DpNetPair(ITEM *aItem, int &aNetP, int &aNetN)=0
int m_distLast
Definition: pns_node.h:92
void Remove(SOLID *aSolid)
Function Remove()
Definition: pns_node.cpp:729
SHAPE_LINE_CHAIN m_hull
Hull of the colliding m_item
Definition: pns_node.h:85
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:968
void Replace(ITEM *aOldItem, std::unique_ptr< ITEM > aNewItem)
Function Replace()
Definition: pns_node.cpp:717
void removeSolidIndex(SOLID *aSeg)
Definition: pns_node.cpp:711
JOINT_MAP::value_type TagJointPair
Definition: pns_node.h:424
int GetClearance(const ITEM *aA, const ITEM *aB) const
Returns the expected clearance between items a and b.
Definition: pns_node.cpp:100
RULE_RESOLVER * GetRuleResolver()
Definition: pns_node.h:168
boost::unordered_set< ITEM * > m_garbageItems
Definition: pns_node.h:503
void Dump(bool aLong=false)
Prints the contents and joints structure
Definition: pns_node.cpp:1082
int JointCount() const
Returns the number of joints
Definition: pns_node.h:174
Class SHAPE_LINE_CHAIN.
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Function CheckColliding()
Definition: pns_node.cpp:427
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:1005
int FindByMarker(int aMarker, ITEM_SET &aItems)
Definition: pns_node.cpp:1266
void removeViaIndex(VIA *aVia)
Definition: pns_node.cpp:664
int Net() const
Function Net()
Definition: pns_item.h:177
const ITEM * m_head
Item we search collisions with
Definition: pns_node.h:79
ITEM * FindItemByParent(const BOARD_CONNECTED_ITEM *aParent)
Definition: pns_node.cpp:1330
void GetUpdatedItems(ITEM_VECTOR &aRemoved, ITEM_VECTOR &aAdded)
Function GetUpdatedItems()
Definition: pns_node.cpp:1163
Struct SEGMENT is a simple container used when filling areas with segments.
Definition: class_zone.h:57
virtual int DpNetPolarity(int aNet)=0
int m_maxClearance
worst case item-item clearance
Definition: pns_node.h:492
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:477
int RemoveByMarker(int aMarker)
Definition: pns_node.cpp:1278
VECTOR2I m_ipFirst
First and last intersection point between the head item and the hull of the colliding m_item ...
Definition: pns_node.h:89
bool HasChildren() const
Definition: pns_node.h:409
std::vector< OBSTACLE > OBSTACLES
Definition: pns_node.h:142
const NODE * m_override
node that overrides root entries
Definition: pns_node.h:119
virtual void OverrideClearance(bool aEnable, int aNetA=0, int aNetB=0, int aClearance=0)=0
Push and Shove diff pair dimensions (gap) settings dialog.
virtual void UseDpGap(bool aUseDpGap)=0
NODE * m_parent
node this node was branched from
Definition: pns_node.h:480
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)
void Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:596
Class INDEX.
Definition: pns_index.h:45
Class LAYER_RANGE.
Definition: pns_layerset.h:32
void LockJoint(const VECTOR2I &aPos, const ITEM *aItem, bool aLock)
Definition: pns_node.cpp:998
std::vector< ITEM * > ITEM_VECTOR
Definition: pns_node.h:141
Struct OBSTACLE.
Definition: pns_node.h:76