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 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 <set>
29#include <unordered_map>
30
31#include <core/optional.h>
32
33#include <geometry/shape.h>
34#include <geometry/shape_line_chain.h>
35#include <geometry/shape_index.h>
36
37#include "pns_item.h"
38#include "pns_joint.h"
39#include "pns_itemset.h"
40
41namespace PNS {
42
43class SEGMENT;
44class LINE;
45class SOLID;
46class VIA;
47class INDEX;
48class ROUTER;
49class NODE;
50
58{
59public:
60 virtual ~RULE_RESOLVER() {}
61
62 virtual int Clearance( const ITEM* aA, const ITEM* aB ) const = 0;
63 virtual int Clearance( int aNetCode ) const = 0;
64 virtual int DpCoupledNet( int aNet ) = 0;
65 virtual int DpNetPolarity( int aNet ) = 0;
66 virtual bool DpNetPair( ITEM* aItem, int& aNetP, int& aNetN ) = 0;
67 virtual std::string NetName( int aNet ) = 0;
68};
69
77{
79 const ITEM* m_head;
80
83
86
90
92 int m_distFirst, m_distLast;
93};
94
99
100public:
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
108protected:
109
110 bool visit( ITEM* aCandidate );
111
113 const ITEM* m_item;
114
116 const NODE* m_node;
117
120
123};
124
137class NODE
138{
139public:
140 typedef OPT<OBSTACLE> OPT_OBSTACLE;
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
168 RULE_RESOLVER* GetRuleResolver()
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
278 bool Add( std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant = false );
279 void Add( std::unique_ptr< SOLID > aSolid );
280 void Add( std::unique_ptr< VIA > aVia );
281
282 void Add( LINE& aLine, bool aAllowRedundant = false );
283
284private:
285 void Add( std::unique_ptr< ITEM > aItem, bool aAllowRedundant = false );
286
287public:
293 void Remove( SOLID* aSolid );
294 void Remove( VIA* aVia );
295 void Remove( SEGMENT* aSegment );
296 void Remove( ITEM* aItem );
297
298public:
305 void Remove( LINE& aLine );
306
314 void Replace( ITEM* aOldItem, std::unique_ptr< ITEM > aNewItem );
315 void Replace( LINE& aOldLine, LINE& aNewLine );
316
325 NODE* Branch();
326
336 const LINE AssembleLine( SEGMENT* aSeg, int* aOriginSegmentIndex = NULL,
337 bool aStopAtLockedJoints = false );
338
340 void Dump( bool aLong = false );
341
350 void GetUpdatedItems( ITEM_VECTOR& aRemoved, ITEM_VECTOR& aAdded );
351
359 void Commit( NODE* aNode );
360
367 JOINT* FindJoint( const VECTOR2I& aPos, int aLayer, int aNet );
368
369 void LockJoint( const VECTOR2I& aPos, const ITEM* aItem, bool aLock );
370
377 JOINT* FindJoint( const VECTOR2I& aPos, const ITEM* aItem )
378 {
379 return FindJoint( aPos, aItem->Layers().Start(), aItem->Net() );
380 }
381
382#if 0
383 void MapConnectivity( JOINT* aStart, std::vector<JOINT*> & aFoundJoints );
384
385 ITEM* NearestUnconnectedItem( JOINT* aStart, int* aAnchor = NULL,
386 int aKindMask = ITEM::ANY_T);
387
388#endif
389
392 JOINT& aB,
393 std::vector<LINE>& aLines );
394
396 void FindLineEnds( const LINE& aLine, JOINT& aA, JOINT& aB );
397
399 void KillChildren();
400
401 void AllItemsInNet( int aNet, std::set<ITEM*>& aItems );
402
403 void ClearRanks( int aMarkerMask = MK_HEAD | MK_VIOLATION );
404
405 int FindByMarker( int aMarker, ITEM_SET& aItems );
406 int RemoveByMarker( int aMarker );
407
408 ITEM* FindItemByParent( const class PNS_HORIZON_PARENT_ITEM* aParent, int net);
409
410 bool HasChildren() const
411 {
412 return !m_children.empty();
413 }
414
417 bool Overrides( ITEM* aItem ) const
418 {
419 return m_override.find( aItem ) != m_override.end();
420 }
421
422private:
423 struct DEFAULT_OBSTACLE_VISITOR;
424 typedef std::unordered_multimap<JOINT::HASH_TAG, JOINT, JOINT::JOINT_TAG_HASH> JOINT_MAP;
425 typedef JOINT_MAP::value_type TagJointPair;
426
428 NODE( const NODE& aB );
429 NODE& operator=( const NODE& aB );
430
432 JOINT& touchJoint( const VECTOR2I& aPos,
433 const LAYER_RANGE& aLayers,
434 int aNet );
435
437 void linkJoint( const VECTOR2I& aPos, const LAYER_RANGE& aLayers, int aNet, ITEM* aWhere );
438
440 void unlinkJoint( const VECTOR2I& aPos, const LAYER_RANGE& aLayers, int aNet, ITEM* aWhere );
441
443 void addSolid( SOLID* aSeg );
444 void addSegment( SEGMENT* aSeg );
445 void addVia( VIA* aVia );
446
447 void removeLine( LINE& aLine );
448 void removeSolidIndex( SOLID* aSeg );
449 void removeSegmentIndex( SEGMENT* aSeg );
450 void removeViaIndex( VIA* aVia );
451
452 void doRemove( ITEM* aItem );
453 void unlinkParent();
454 void releaseChildren();
455 void releaseGarbage();
456
457 bool isRoot() const
458 {
459 return m_parent == NULL;
460 }
461
462 SEGMENT* findRedundantSegment( const VECTOR2I& A, const VECTOR2I& B,
463 const LAYER_RANGE & lr, int aNet );
464 SEGMENT* findRedundantSegment( SEGMENT* aSeg );
465
467 void followLine( SEGMENT* aCurrent,
468 bool aScanDirection,
469 int& aPos,
470 int aLimit,
471 VECTOR2I* aCorners,
472 SEGMENT** aSegments,
473 bool& aGuardHit,
474 bool aStopAtLockedJoints );
475
478 JOINT_MAP m_joints;
479
481 NODE* m_parent;
482
484 NODE* m_root;
485
487 std::set<NODE*> m_children;
488
490 std::unordered_set<ITEM*> m_override;
491
493 int m_maxClearance;
494
496 RULE_RESOLVER* m_ruleResolver;
497
499 INDEX* m_index;
500
502 int m_depth;
503
504 std::unordered_set<ITEM*> m_garbageItems;
505};
506
507}
508
509#endif
Class LAYER_RANGE.
Definition: pns_layerset.h:33
Definition: pns_itemset.h:40
Class ITEM.
Definition: pns_item.h:55
const LAYER_RANGE & Layers() const
Function Layers()
Definition: pns_item.h:215
int Net() const
Function Net()
Definition: pns_item.h:180
Class JOINT.
Definition: pns_joint.h:44
Definition: pns_line.h:61
Class NODE.
Definition: pns_node.h:138
NODE * Branch()
Function Branch()
Definition: pns_node.cpp:107
OPT_OBSTACLE NearestObstacle(const LINE *aItem, int aKindMask=ITEM::ANY_T, const std::set< ITEM * > *aRestrictedSet=NULL)
Function NearestObstacle()
Definition: pns_node.cpp:303
void Replace(ITEM *aOldItem, std::unique_ptr< ITEM > aNewItem)
Function Replace()
Definition: pns_node.cpp:720
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:277
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:417
int GetMaxClearance() const
‍Returns the pre-set worst case clearance between any pair of items
Definition: pns_node.h:151
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:937
void SetMaxClearance(int aClearance)
‍Sets the worst-case clerance between any pair of items
Definition: pns_node.h:157
void GetUpdatedItems(ITEM_VECTOR &aRemoved, ITEM_VECTOR &aAdded)
Function GetUpdatedItems()
Definition: pns_node.cpp:1166
const LINE AssembleLine(SEGMENT *aSeg, int *aOriginSegmentIndex=NULL, bool aStopAtLockedJoints=false)
Function AssembleLine()
Definition: pns_node.cpp:837
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Function CheckColliding()
Definition: pns_node.cpp:426
void Dump(bool aLong=false)
‍Prints the contents and joints structure
Definition: pns_node.cpp:1085
void Remove(SOLID *aSolid)
Function Remove()
Definition: pns_node.cpp:732
JOINT * FindJoint(const VECTOR2I &aPos, const ITEM *aItem)
Function FindJoint()
Definition: pns_node.h:377
int Depth() const
‍Returns the number of nodes in the inheritance chain (wrs to the root node)
Definition: pns_node.h:180
void FindLineEnds(const LINE &aLine, JOINT &aA, JOINT &aB)
‍finds the joints corresponding to the ends of line aLine
Definition: pns_node.cpp:892
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:597
void SetRuleResolver(RULE_RESOLVER *aFunc)
‍Assigns a clerance resolution function object
Definition: pns_node.h:163
int JointCount() const
‍Returns the number of joints
Definition: pns_node.h:174
void KillChildren()
‍Destroys all child nodes. Applicable only to the root node.
Definition: pns_node.cpp:1229
int GetClearance(const ITEM *aA, const ITEM *aB) const
‍Returns the expected clearance between items a and b.
Definition: pns_node.cpp:98
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:971
void Commit(NODE *aNode)
Function Commit()
Definition: pns_node.cpp:1209
const ITEM_SET HitTest(const VECTOR2I &aPoint) const
Function HitTest()
Definition: pns_node.cpp:505
Struct OBSTACLE_VISITOR.
Definition: pns_node.h:98
const NODE * m_node
‍node we are searching in (either root or a branch)
Definition: pns_node.h:116
const ITEM * m_item
‍the item we are looking for collisions with
Definition: pns_node.h:113
int m_extraClearance
‍additional clearance
Definition: pns_node.h:122
const NODE * m_override
‍node that overrides root entries
Definition: pns_node.h:119
Definition: pns_horizon_iface.hpp:29
Class RULE_RESOLVER.
Definition: pns_node.h:58
Definition: pns_segment.h:39
Definition: pns_solid.h:36
Definition: pns_via.h:38
Class SHAPE_LINE_CHAIN.
Definition: shape_line_chain.h:50
Struct OBSTACLE.
Definition: pns_node.h:77
int m_distFirst
‍... and the distance thereof
Definition: pns_node.h:92
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
ITEM * m_item
‍Item found to be colliding with m_head
Definition: pns_node.h:82
const ITEM * m_head
‍Item we search collisions with
Definition: pns_node.h:79
SHAPE_LINE_CHAIN m_hull
‍Hull of the colliding m_item
Definition: pns_node.h:85