Horizon
pns_node.h
1 /*
2  * KiRouter - a push-and-(sometimes-)shove PCB router
3  *
4  * Copyright (C) 2013-2014 CERN
5  * Copyright (C) 2016-2021 KiCad Developers, see AUTHORS.txt for contributors.
6  *
7  * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
8  *
9  * This program is free software: you can redistribute it and/or modify it
10  * under the terms of the GNU General Public License as published by the
11  * Free Software Foundation, either version 3 of the License, or (at your
12  * option) any later version.
13  *
14  * This program is distributed in the hope that it will be useful, but
15  * WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17  * General Public License for more details.
18  *
19  * You should have received a copy of the GNU General Public License along
20  * with this program. If not, see <http://www.gnu.org/licenses/>.
21  */
22 
23 #ifndef __PNS_NODE_H
24 #define __PNS_NODE_H
25 
26 #include <vector>
27 #include <list>
28 #include <unordered_set>
29 #include <unordered_map>
30 #include <core/minoptmax.h>
31 
32 #include <geometry/shape_line_chain.h>
33 #include <geometry/shape_index.h>
34 
35 #include "pns_item.h"
36 #include "pns_joint.h"
37 #include "pns_itemset.h"
38 
39 namespace PNS {
40 
41 class ARC;
42 class SEGMENT;
43 class LINE;
44 class SOLID;
45 class VIA;
46 class INDEX;
47 class ROUTER;
48 class NODE;
49 
55 enum class CONSTRAINT_TYPE
56 {
57  CT_CLEARANCE = 1,
58  CT_DIFF_PAIR_GAP = 2,
59  CT_LENGTH = 3,
60  CT_WIDTH = 4,
61  CT_VIA_DIAMETER = 5,
62  CT_VIA_HOLE = 6,
63  CT_HOLE_CLEARANCE = 7,
64  CT_EDGE_CLEARANCE = 8,
65  CT_HOLE_TO_HOLE = 9
66 };
67 
68 struct CONSTRAINT
69 {
70  CONSTRAINT_TYPE m_Type;
71  MINOPTMAX<int> m_Value;
72  bool m_Allowed;
73  wxString m_RuleName;
74  wxString m_FromName;
75  wxString m_ToName;
76 };
77 
79 {
80 public:
81  virtual ~RULE_RESOLVER() {}
82 
83  virtual int Clearance( const ITEM* aA, const ITEM* aB ) = 0;
84  virtual int HoleClearance( const ITEM* aA, const ITEM* aB ) = 0;
85  virtual int HoleToHoleClearance( const ITEM* aA, const ITEM* aB ) = 0;
86 
87  virtual int DpCoupledNet( int aNet ) = 0;
88  virtual int DpNetPolarity( int aNet ) = 0;
89  virtual bool DpNetPair( const ITEM* aItem, int& aNetP, int& aNetN ) = 0;
90 
91  virtual bool IsDiffPair( const ITEM* aA, const ITEM* aB ) = 0;
92 
93  virtual bool QueryConstraint( CONSTRAINT_TYPE aType, const PNS::ITEM* aItemA,
94  const PNS::ITEM* aItemB, int aLayer,
95  PNS::CONSTRAINT* aConstraint ) = 0;
96 
97  virtual wxString NetName( int aNet ) = 0;
98 
99  virtual void ClearCacheForItem( const ITEM* aItem ) {}
100 };
101 
105 struct OBSTACLE
106 {
107  const ITEM* m_head;
108 
113 };
114 
116 {
117 public:
118  OBSTACLE_VISITOR( const ITEM* aItem );
119 
120  virtual ~OBSTACLE_VISITOR()
121  {
122  }
123 
124  void SetWorld( const NODE* aNode, const NODE* aOverride = nullptr );
125 
126  virtual bool operator()( ITEM* aCandidate ) = 0;
127 
128 protected:
129  bool visit( ITEM* aCandidate );
130 
131 protected:
132  const ITEM* m_item;
133 
134  const NODE* m_node;
135  const NODE* m_override;
136 };
137 
147 class NODE
148 {
149 public:
150  typedef OPT<OBSTACLE> OPT_OBSTACLE;
151  typedef std::vector<ITEM*> ITEM_VECTOR;
152  typedef std::vector<OBSTACLE> OBSTACLES;
153 
154  NODE();
155  ~NODE();
156 
158  int GetClearance( const ITEM* aA, const ITEM* aB ) const;
159  int GetHoleClearance( const ITEM* aA, const ITEM* aB ) const;
160  int GetHoleToHoleClearance( const ITEM* aA, const ITEM* aB ) const;
161 
163  int GetMaxClearance() const
164  {
165  return m_maxClearance;
166  }
167 
169  void SetMaxClearance( int aClearance )
170  {
171  m_maxClearance = aClearance;
172  }
173 
175  void SetRuleResolver( RULE_RESOLVER* aFunc )
176  {
177  m_ruleResolver = aFunc;
178  }
179 
181  {
182  return m_ruleResolver;
183  }
184 
186  int JointCount() const
187  {
188  return m_joints.size();
189  }
190 
192  int Depth() const
193  {
194  return m_depth;
195  }
196 
206  int QueryColliding( const ITEM* aItem, OBSTACLES& aObstacles, int aKindMask = ITEM::ANY_T,
207  int aLimitCount = -1, bool aDifferentNetsOnly = true );
208 
209  int QueryJoints( const BOX2I& aBox, std::vector<JOINT*>& aJoints,
210  LAYER_RANGE aLayerMask = LAYER_RANGE::All(), int aKindMask = ITEM::ANY_T );
211 
220  OPT_OBSTACLE NearestObstacle( const LINE* aLine, int aKindMask = ITEM::ANY_T,
221  const std::set<ITEM*>* aRestrictedSet = nullptr );
222 
231  OPT_OBSTACLE CheckColliding( const ITEM* aItem, int aKindMask = ITEM::ANY_T );
232 
233 
242  OPT_OBSTACLE CheckColliding( const ITEM_SET& aSet, int aKindMask = ITEM::ANY_T );
243 
250  const ITEM_SET HitTest( const VECTOR2I& aPoint ) const;
251 
260  bool Add( std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant = false );
261  void Add( std::unique_ptr< SOLID > aSolid );
262  void Add( std::unique_ptr< VIA > aVia );
263  bool Add( std::unique_ptr< ARC > aArc, bool aAllowRedundant = false );
264 
265  void Add( LINE& aLine, bool aAllowRedundant = false );
266 
270  void Remove( ARC* aArc );
271  void Remove( SOLID* aSolid );
272  void Remove( VIA* aVia );
273  void Remove( SEGMENT* aSegment );
274  void Remove( ITEM* aItem );
275 
281  void Remove( LINE& aLine );
282 
289  void Replace( ITEM* aOldItem, std::unique_ptr< ITEM > aNewItem );
290  void Replace( LINE& aOldLine, LINE& aNewLine );
291 
300  NODE* Branch();
301 
313  const LINE AssembleLine( LINKED_ITEM* aSeg, int* aOriginSegmentIndex = nullptr,
314  bool aStopAtLockedJoints = false,
315  bool aFollowLockedSegments = false );
316 
318  void Dump( bool aLong = false );
319 
326  void GetUpdatedItems( ITEM_VECTOR& aRemoved, ITEM_VECTOR& aAdded );
327 
336  void Commit( NODE* aNode );
337 
343  JOINT* FindJoint( const VECTOR2I& aPos, int aLayer, int aNet );
344 
345  void LockJoint( const VECTOR2I& aPos, const ITEM* aItem, bool aLock );
346 
352  JOINT* FindJoint( const VECTOR2I& aPos, const ITEM* aItem )
353  {
354  return FindJoint( aPos, aItem->Layers().Start(), aItem->Net() );
355  }
356 
358  int FindLinesBetweenJoints( const JOINT& aA, const JOINT& aB, std::vector<LINE>& aLines );
359 
361  void FindLineEnds( const LINE& aLine, JOINT& aA, JOINT& aB );
362 
364  void KillChildren();
365 
366  void AllItemsInNet( int aNet, std::set<ITEM*>& aItems, int aKindMask = -1 );
367 
368  void ClearRanks( int aMarkerMask = MK_HEAD | MK_VIOLATION | MK_HOLE );
369 
370  void RemoveByMarker( int aMarker );
371 
372  ITEM* FindItemByParent( const class PNS_HORIZON_PARENT_ITEM* aParent, int net);
373 
374  bool HasChildren() const
375  {
376  return !m_children.empty();
377  }
378 
379  NODE* GetParent() const
380  {
381  return m_parent;
382  }
383 
385  bool Overrides( ITEM* aItem ) const
386  {
387  return m_override.find( aItem ) != m_override.end();
388  }
389 
390  void FixupVirtualVias();
391 
392 private:
393  void Add( std::unique_ptr< ITEM > aItem, bool aAllowRedundant = false );
394 
396  NODE( const NODE& aB );
397  NODE& operator=( const NODE& aB );
398 
400  JOINT& touchJoint( const VECTOR2I& aPos, const LAYER_RANGE& aLayers, int aNet );
401 
403  void linkJoint( const VECTOR2I& aPos, const LAYER_RANGE& aLayers, int aNet, ITEM* aWhere );
404 
406  void unlinkJoint( const VECTOR2I& aPos, const LAYER_RANGE& aLayers, int aNet, ITEM* aWhere );
407 
409  void addSolid( SOLID* aSeg );
410  void addSegment( SEGMENT* aSeg );
411  void addVia( VIA* aVia );
412  void addArc( ARC* aVia );
413 
414  void removeSolidIndex( SOLID* aSeg );
415  void removeSegmentIndex( SEGMENT* aSeg );
416  void removeViaIndex( VIA* aVia );
417  void removeArcIndex( ARC* aVia );
418 
419  void doRemove( ITEM* aItem );
420  void unlinkParent();
421  void releaseChildren();
422  void releaseGarbage();
423  void rebuildJoint( JOINT* aJoint, ITEM* aItem );
424 
425  bool isRoot() const
426  {
427  return m_parent == nullptr;
428  }
429 
430  SEGMENT* findRedundantSegment( const VECTOR2I& A, const VECTOR2I& B, const LAYER_RANGE& lr,
431  int aNet );
432  SEGMENT* findRedundantSegment( SEGMENT* aSeg );
433 
434  ARC* findRedundantArc( const VECTOR2I& A, const VECTOR2I& B, const LAYER_RANGE& lr, int aNet );
435  ARC* findRedundantArc( ARC* aSeg );
436 
438  void followLine( LINKED_ITEM* aCurrent, bool aScanDirection, int& aPos, int aLimit,
439  VECTOR2I* aCorners, LINKED_ITEM** aSegments, bool* aArcReversed,
440  bool& aGuardHit, bool aStopAtLockedJoints, bool aFollowLockedSegments );
441 
442 private:
443  struct DEFAULT_OBSTACLE_VISITOR;
444  typedef std::unordered_multimap<JOINT::HASH_TAG, JOINT, JOINT::JOINT_TAG_HASH> JOINT_MAP;
445  typedef JOINT_MAP::value_type TagJointPair;
446 
447  JOINT_MAP m_joints;
449 
450  NODE* m_parent;
451  NODE* m_root;
452  std::set<NODE*> m_children;
453 
454  std::unordered_set<ITEM*> m_override;
456 
457  int m_maxClearance;
458  RULE_RESOLVER* m_ruleResolver;
459  INDEX* m_index;
460  int m_depth;
462 
463  std::unordered_set<ITEM*> m_garbageItems;
464 };
465 
466 }
467 
468 #endif
Represent a contiguous set of PCB layers.
Definition: pns_layerset.h:32
Base class for PNS router board items.
Definition: pns_item.h:57
A 2D point on a given set of layers and belonging to a certain net, that links together a number of b...
Definition: pns_joint.h:43
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition: pns_line.h:61
Keep the router "world" - i.e.
Definition: pns_node.h:148
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
Definition: pns_node.cpp:138
int FindLinesBetweenJoints(const JOINT &aA, const JOINT &aB, std::vector< LINE > &aLines)
Find the joints corresponding to the ends of line aLine.
Definition: pns_node.cpp:1037
JOINT * FindJoint(const VECTOR2I &aPos, const ITEM *aItem)
Search for a joint at a given position, linked to given item.
Definition: pns_node.h:352
void Replace(ITEM *aOldItem, std::unique_ptr< ITEM > aNewItem)
Replace an item with another one.
Definition: pns_node.cpp:803
int GetMaxClearance() const
Set the worst-case clearance between any pair of items.
Definition: pns_node.h:163
void SetMaxClearance(int aClearance)
Assign a clearance resolution function object.
Definition: pns_node.h:169
void GetUpdatedItems(ITEM_VECTOR &aRemoved, ITEM_VECTOR &aAdded)
Return the list of items removed and added in this branch with respect to the root branch.
Definition: pns_node.cpp:1345
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Check if the item collides with anything else in the world, and if found, returns the obstacle.
Definition: pns_node.cpp:451
NODE * GetParent() const
Check if this branch contains an updated version of the m_item from the root branch.
Definition: pns_node.h:379
int QueryColliding(const ITEM *aItem, OBSTACLES &aObstacles, int aKindMask=ITEM::ANY_T, int aLimitCount=-1, bool aDifferentNetsOnly=true)
Find items colliding (closer than clearance) with the item aItem.
Definition: pns_node.cpp:267
void FindLineEnds(const LINE &aLine, JOINT &aA, JOINT &aB)
Destroy all child nodes. Applicable only to the root node.
Definition: pns_node.cpp:1030
int GetHoleToHoleClearance(const ITEM *aA, const ITEM *aB) const
Return the pre-set worst case clearance between any pair of items.
Definition: pns_node.cpp:126
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:639
int JointCount() const
Return the number of nodes in the inheritance chain (wrs to the root node).
Definition: pns_node.h:186
OPT_OBSTACLE NearestObstacle(const LINE *aLine, int aKindMask=ITEM::ANY_T, const std::set< ITEM * > *aRestrictedSet=nullptr)
Follow the line in search of an obstacle that is nearest to the starting to the line's starting point...
Definition: pns_node.cpp:297
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Search for a joint at a given position, layer and belonging to given net.
Definition: pns_node.cpp:1142
RULE_RESOLVER * GetRuleResolver() const
Return the number of joints.
Definition: pns_node.h:180
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:838
void Commit(NODE *aNode)
Apply the changes from a given branch (aNode) to the root branch.
Definition: pns_node.cpp:1392
~NODE()
Return the expected clearance between items a and b.
Definition: pns_node.cpp:69
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=nullptr, bool aStopAtLockedJoints=false, bool aFollowLockedSegments=false)
Follow the joint map to assemble a line connecting two non-trivial joints starting from segment aSeg.
Definition: pns_node.cpp:948
const ITEM_SET HitTest(const VECTOR2I &aPoint) const
Find all items that contain the point aPoint.
Definition: pns_node.cpp:518
Definition: pns_node.h:116
const NODE * m_node
node we are searching in (either root or a branch)
Definition: pns_node.h:134
const ITEM * m_item
the item we are looking for collisions with
Definition: pns_node.h:132
const NODE * m_override
node that overrides root entries
Definition: pns_node.h:135
Definition: pns_horizon_iface.hpp:29
Definition: pns_node.h:79
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
Definition: shape_line_chain.h:81
Definition: wx_compat.h:13
Definition: pns_node.h:69
Hold an object colliding with another object, along with some useful data about the collision.
Definition: pns_node.h:106
int m_distFirst
... and the distance thereof
Definition: pns_node.h:112
VECTOR2I m_ipFirst
First intersection between m_head and m_hull.
Definition: pns_node.h:111
ITEM * m_item
Item found to be colliding with m_head.
Definition: pns_node.h:109
const ITEM * m_head
Item we search collisions with.
Definition: pns_node.h:107
SHAPE_LINE_CHAIN m_hull
Hull of the colliding m_item.
Definition: pns_node.h:110