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 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  virtual wxString NetName( int aNet ) = 0;
69 };
70 
77 struct OBSTACLE
78 {
80  const ITEM* m_head;
81 
84 
87 
90  VECTOR2I m_ipFirst, m_ipLast;
91 
93  int m_distFirst, m_distLast;
94 };
95 
100 
101 public:
102 
103  OBSTACLE_VISITOR( const ITEM* aItem );
104 
105  void SetWorld( const NODE* aNode, const NODE* aOverride = NULL );
106 
107  virtual bool operator()( ITEM* aCandidate ) = 0;
108 
109 protected:
110 
111  bool visit( ITEM* aCandidate );
112 
114  const ITEM* m_item;
115 
117  const NODE* m_node;
118 
120  const NODE* m_override;
121 
124 };
125 
138 class NODE
139 {
140 public:
142  typedef std::vector<ITEM*> ITEM_VECTOR;
143  typedef std::vector<OBSTACLE> OBSTACLES;
144 
145  NODE();
146  ~NODE();
147 
149  int GetClearance( const ITEM* aA, const ITEM* aB ) const;
150 
152  int GetMaxClearance() const
153  {
154  return m_maxClearance;
155  }
156 
158  void SetMaxClearance( int aClearance )
159  {
160  m_maxClearance = aClearance;
161  }
162 
165  {
166  m_ruleResolver = aFunc;
167  }
168 
170  {
171  return m_ruleResolver;
172  }
173 
175  int JointCount() const
176  {
177  return m_joints.size();
178  }
179 
181  int Depth() const
182  {
183  return m_depth;
184  }
185 
196  int QueryColliding( const ITEM* aItem,
197  OBSTACLES& aObstacles,
198  int aKindMask = ITEM::ANY_T,
199  int aLimitCount = -1,
200  bool aDifferentNetsOnly = true,
201  int aForceClearance = -1 );
202 
203  int QueryColliding( const ITEM* aItem,
204  OBSTACLE_VISITOR& aVisitor
205  );
206 
216  OPT_OBSTACLE NearestObstacle( const LINE* aItem,
217  int aKindMask = ITEM::ANY_T,
218  const std::set<ITEM*>* aRestrictedSet = NULL );
219 
229  OPT_OBSTACLE CheckColliding( const ITEM* aItem,
230  int aKindMask = ITEM::ANY_T );
231 
232 
242  OPT_OBSTACLE CheckColliding( const ITEM_SET& aSet,
243  int aKindMask = ITEM::ANY_T );
244 
245 
256  bool CheckColliding( const ITEM* aItemA,
257  const ITEM* aItemB,
258  int aKindMask = ITEM::ANY_T,
259  int aForceClearance = -1 );
260 
268  const ITEM_SET HitTest( const VECTOR2I& aPoint ) const;
269 
279  bool Add( std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant = false );
280  void Add( std::unique_ptr< SOLID > aSolid );
281  void Add( std::unique_ptr< VIA > aVia );
282 
283  void Add( LINE& aLine, bool aAllowRedundant = false );
284 
285 private:
286  void Add( std::unique_ptr< ITEM > aItem, bool aAllowRedundant = false );
287 
288 public:
294  void Remove( SOLID* aSolid );
295  void Remove( VIA* aVia );
296  void Remove( SEGMENT* aSegment );
297  void Remove( ITEM* aItem );
298 
299 public:
306  void Remove( LINE& aLine );
307 
315  void Replace( ITEM* aOldItem, std::unique_ptr< ITEM > aNewItem );
316  void Replace( LINE& aOldLine, LINE& aNewLine );
317 
326  NODE* Branch();
327 
337  const LINE AssembleLine( SEGMENT* aSeg, int* aOriginSegmentIndex = NULL,
338  bool aStopAtLockedJoints = false );
339 
341  void Dump( bool aLong = false );
342 
351  void GetUpdatedItems( ITEM_VECTOR& aRemoved, ITEM_VECTOR& aAdded );
352 
360  void Commit( NODE* aNode );
361 
368  JOINT* FindJoint( const VECTOR2I& aPos, int aLayer, int aNet );
369 
370  void LockJoint( const VECTOR2I& aPos, const ITEM* aItem, bool aLock );
371 
378  JOINT* FindJoint( const VECTOR2I& aPos, const ITEM* aItem )
379  {
380  return FindJoint( aPos, aItem->Layers().Start(), aItem->Net() );
381  }
382 
383 #if 0
384  void MapConnectivity( JOINT* aStart, std::vector<JOINT*> & aFoundJoints );
385 
386  ITEM* NearestUnconnectedItem( JOINT* aStart, int* aAnchor = NULL,
387  int aKindMask = ITEM::ANY_T);
388 
389 #endif
390 
392  int FindLinesBetweenJoints( JOINT& aA,
393  JOINT& aB,
394  std::vector<LINE>& aLines );
395 
397  void FindLineEnds( const LINE& aLine, JOINT& aA, JOINT& aB );
398 
400  void KillChildren();
401 
402  void AllItemsInNet( int aNet, std::set<ITEM*>& aItems );
403 
404  void ClearRanks( int aMarkerMask = MK_HEAD | MK_VIOLATION );
405 
406  int FindByMarker( int aMarker, ITEM_SET& aItems );
407  int RemoveByMarker( int aMarker );
408 
409  ITEM* FindItemByParent( const BOARD_CONNECTED_ITEM* aParent );
410 
411  bool HasChildren() const
412  {
413  return !m_children.empty();
414  }
415 
418  bool Overrides( ITEM* aItem ) const
419  {
420  return m_override.find( aItem ) != m_override.end();
421  }
422 
423 private:
425  typedef std::unordered_multimap<JOINT::HASH_TAG, JOINT, JOINT::JOINT_TAG_HASH> JOINT_MAP;
426  typedef JOINT_MAP::value_type TagJointPair;
427 
429  NODE( const NODE& aB );
430  NODE& operator=( const NODE& aB );
431 
433  JOINT& touchJoint( const VECTOR2I& aPos,
434  const LAYER_RANGE& aLayers,
435  int aNet );
436 
438  void linkJoint( const VECTOR2I& aPos, const LAYER_RANGE& aLayers, int aNet, ITEM* aWhere );
439 
441  void unlinkJoint( const VECTOR2I& aPos, const LAYER_RANGE& aLayers, int aNet, ITEM* aWhere );
442 
444  void addSolid( SOLID* aSeg );
445  void addSegment( SEGMENT* aSeg );
446  void addVia( VIA* aVia );
447 
448  void removeLine( LINE& aLine );
449  void removeSolidIndex( SOLID* aSeg );
450  void removeSegmentIndex( SEGMENT* aSeg );
451  void removeViaIndex( VIA* aVia );
452 
453  void doRemove( ITEM* aItem );
454  void unlinkParent();
455  void releaseChildren();
456  void releaseGarbage();
457 
458  bool isRoot() const
459  {
460  return m_parent == NULL;
461  }
462 
463  SEGMENT* findRedundantSegment( const VECTOR2I& A, const VECTOR2I& B,
464  const LAYER_RANGE & lr, int aNet );
465  SEGMENT* findRedundantSegment( SEGMENT* aSeg );
466 
468  void followLine( SEGMENT* aCurrent,
469  bool aScanDirection,
470  int& aPos,
471  int aLimit,
472  VECTOR2I* aCorners,
473  SEGMENT** aSegments,
474  bool& aGuardHit,
475  bool aStopAtLockedJoints );
476 
479  JOINT_MAP m_joints;
480 
483 
486 
488  std::set<NODE*> m_children;
489 
491  std::unordered_set<ITEM*> m_override;
492 
495 
498 
501 
503  int m_depth;
504 
505  std::unordered_set<ITEM*> m_garbageItems;
506 };
507 
508 }
509 
510 #endif
Class ITEM.
Definition: pns_item.h:53
std::set< NODE * > m_children
list of nodes branched from this one
Definition: pns_node.h:488
ITEM * m_item
Item found to be colliding with m_head
Definition: pns_node.h:83
int Depth() const
Returns the number of nodes in the inheritance chain (wrs to the root node)
Definition: pns_node.h:181
const NODE * m_node
node we are searching in (either root or a branch)
Definition: pns_node.h:117
VECTOR2I m_ipLast
Definition: pns_node.h:90
int GetMaxClearance() const
Returns the pre-set worst case clearance between any pair of items
Definition: pns_node.h:152
Class NODE.
Definition: pns_node.h:138
virtual ~RULE_RESOLVER()
Definition: pns_node.h:59
const LAYER_RANGE & Layers() const
Function Layers()
Definition: pns_item.h:209
virtual int DpCoupledNet(int aNet)=0
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:418
int m_extraClearance
additional clearance
Definition: pns_node.h:123
Class RULE_RESOLVER.
Definition: pns_node.h:56
void SetRuleResolver(RULE_RESOLVER *aFunc)
Assigns a clerance resolution function object
Definition: pns_node.h:164
Class BOARD_CONNECTED_ITEM is a base class derived from BOARD_ITEM for items that can be connected an...
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:500
void SetMaxClearance(int aClearance)
Sets the worst-case clerance between any pair of items
Definition: pns_node.h:158
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:485
int m_depth
depth of the node (number of parent nodes in the inheritance chain)
Definition: pns_node.h:503
Class JOINT.
Definition: pns_joint.h:43
RULE_RESOLVER * m_ruleResolver
Design rules resolver
Definition: pns_node.h:497
Struct OBSTACLE_VISITOR.
Definition: pns_node.h:99
std::unordered_multimap< JOINT::HASH_TAG, JOINT, JOINT::JOINT_TAG_HASH > JOINT_MAP
Definition: pns_node.h:424
JOINT * FindJoint(const VECTOR2I &aPos, const ITEM *aItem)
Function FindJoint()
Definition: pns_node.h:378
virtual int Clearance(const ITEM *aA, const ITEM *aB) const =0
std::unordered_set< ITEM * > m_override
hash of root&#39;s items that have been changed in this node
Definition: pns_node.h:491
const ITEM * m_item
the item we are looking for collisions with
Definition: pns_node.h:114
int Start() const
Definition: pns_layerset.h:83
bool isRoot() const
Definition: pns_node.h:458
virtual bool DpNetPair(ITEM *aItem, int &aNetP, int &aNetN)=0
int m_distLast
Definition: pns_node.h:93
SHAPE_LINE_CHAIN m_hull
Hull of the colliding m_item
Definition: pns_node.h:86
JOINT_MAP::value_type TagJointPair
Definition: pns_node.h:426
RULE_RESOLVER * GetRuleResolver()
Definition: pns_node.h:169
int JointCount() const
Returns the number of joints
Definition: pns_node.h:175
Class SHAPE_LINE_CHAIN.
std::unordered_set< ITEM * > m_garbageItems
Definition: pns_node.h:505
int Net() const
Function Net()
Definition: pns_item.h:179
const ITEM * m_head
Item we search collisions with
Definition: pns_node.h:80
boost::optional< T > OPT
Definition: optional.h:7
OPT< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:141
virtual int DpNetPolarity(int aNet)=0
virtual wxString NetName(int aNet)=0
int m_maxClearance
worst case item-item clearance
Definition: pns_node.h:494
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:479
bool HasChildren() const
Definition: pns_node.h:411
std::vector< OBSTACLE > OBSTACLES
Definition: pns_node.h:143
const NODE * m_override
node that overrides root entries
Definition: pns_node.h:120
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:482
Class INDEX.
Definition: pns_index.h:46
Class LAYER_RANGE.
Definition: pns_layerset.h:32
std::vector< ITEM * > ITEM_VECTOR
Definition: pns_node.h:142
Struct OBSTACLE.
Definition: pns_node.h:77