KiCad PCB EDA Suite
PNS::NODE Class Reference

Class NODE. More...

#include <pns_node.h>

Classes

struct  DEFAULT_OBSTACLE_VISITOR
 

Public Types

typedef OPT< OBSTACLEOPT_OBSTACLE
 
typedef std::vector< ITEM * > ITEM_VECTOR
 
typedef std::vector< OBSTACLEOBSTACLES
 

Public Member Functions

 NODE ()
 
 ~NODE ()
 
int GetClearance (const ITEM *aA, const ITEM *aB) const
 

Returns the expected clearance between items a and b.

More...
 
int GetMaxClearance () const
 

Returns the pre-set worst case clearance between any pair of items

More...
 
void SetMaxClearance (int aClearance)
 

Sets the worst-case clerance between any pair of items

More...
 
void SetRuleResolver (RULE_RESOLVER *aFunc)
 

Assigns a clerance resolution function object

More...
 
RULE_RESOLVERGetRuleResolver () const
 
int JointCount () const
 

Returns the number of joints

More...
 
int Depth () const
 

Returns the number of nodes in the inheritance chain (wrs to the root node)

More...
 
int QueryColliding (const ITEM *aItem, OBSTACLES &aObstacles, int aKindMask=ITEM::ANY_T, int aLimitCount=-1, bool aDifferentNetsOnly=true, int aForceClearance=-1)
 Function QueryColliding() More...
 
int QueryColliding (const ITEM *aItem, OBSTACLE_VISITOR &aVisitor)
 
OPT_OBSTACLE NearestObstacle (const LINE *aItem, int aKindMask=ITEM::ANY_T, const std::set< ITEM * > *aRestrictedSet=NULL)
 Function NearestObstacle() More...
 
OPT_OBSTACLE CheckColliding (const ITEM *aItem, int aKindMask=ITEM::ANY_T)
 Function CheckColliding() More...
 
OPT_OBSTACLE CheckColliding (const ITEM_SET &aSet, int aKindMask=ITEM::ANY_T)
 Function CheckColliding() More...
 
bool CheckColliding (const ITEM *aItemA, const ITEM *aItemB, int aKindMask=ITEM::ANY_T, int aForceClearance=-1)
 Function CheckColliding() More...
 
const ITEM_SET HitTest (const VECTOR2I &aPoint) const
 Function HitTest() More...
 
bool Add (std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
 Function Add() More...
 
void Add (std::unique_ptr< SOLID > aSolid)
 
void Add (std::unique_ptr< VIA > aVia)
 
void Add (LINE &aLine, bool aAllowRedundant=false)
 
void Remove (SOLID *aSolid)
 Function Remove() More...
 
void Remove (VIA *aVia)
 
void Remove (SEGMENT *aSegment)
 
void Remove (ITEM *aItem)
 
void Remove (LINE &aLine)
 Function Remove() More...
 
void Replace (ITEM *aOldItem, std::unique_ptr< ITEM > aNewItem)
 Function Replace() More...
 
void Replace (LINE &aOldLine, LINE &aNewLine)
 
NODEBranch ()
 Function Branch() More...
 
const LINE AssembleLine (SEGMENT *aSeg, int *aOriginSegmentIndex=NULL, bool aStopAtLockedJoints=false)
 Function AssembleLine() More...
 
void Dump (bool aLong=false)
 

Prints the contents and joints structure

More...
 
void GetUpdatedItems (ITEM_VECTOR &aRemoved, ITEM_VECTOR &aAdded)
 Function GetUpdatedItems() More...
 
void Commit (NODE *aNode)
 Function Commit() More...
 
JOINTFindJoint (const VECTOR2I &aPos, int aLayer, int aNet)
 Function FindJoint() More...
 
void LockJoint (const VECTOR2I &aPos, const ITEM *aItem, bool aLock)
 
JOINTFindJoint (const VECTOR2I &aPos, const ITEM *aItem)
 Function FindJoint() More...
 
int FindLinesBetweenJoints (JOINT &aA, JOINT &aB, std::vector< LINE > &aLines)
 

finds all lines between a pair of joints. Used by the loop removal procedure.

More...
 
void FindLineEnds (const LINE &aLine, JOINT &aA, JOINT &aB)
 

finds the joints corresponding to the ends of line aLine

More...
 
void KillChildren ()
 

Destroys all child nodes. Applicable only to the root node.

More...
 
void AllItemsInNet (int aNet, std::set< ITEM * > &aItems)
 
void ClearRanks (int aMarkerMask=MK_HEAD|MK_VIOLATION)
 
void RemoveByMarker (int aMarker)
 
ITEMFindItemByParent (const BOARD_CONNECTED_ITEM *aParent)
 
bool HasChildren () const
 
bool Overrides (ITEM *aItem) const
 

checks if this branch contains an updated version of the m_item from the root branch.

More...
 

Private Types

typedef std::unordered_multimap< JOINT::HASH_TAG, JOINT, JOINT::JOINT_TAG_HASHJOINT_MAP
 
typedef JOINT_MAP::value_type TagJointPair
 

Private Member Functions

void Add (std::unique_ptr< ITEM > aItem, bool aAllowRedundant=false)
 
 NODE (const NODE &aB)
 nodes are not copyable More...
 
NODEoperator= (const NODE &aB)
 
JOINTtouchJoint (const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet)
 

tries to find matching joint and creates a new one if not found

More...
 
void linkJoint (const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
 

touches a joint and links it to an m_item

More...
 
void unlinkJoint (const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
 

unlinks an item from a joint

More...
 
void addSolid (SOLID *aSeg)
 

helpers for adding/removing items

More...
 
void addSegment (SEGMENT *aSeg)
 
void addVia (VIA *aVia)
 
void removeLine (LINE &aLine)
 
void removeSolidIndex (SOLID *aSeg)
 
void removeSegmentIndex (SEGMENT *aSeg)
 
void removeViaIndex (VIA *aVia)
 
void doRemove (ITEM *aItem)
 
void unlinkParent ()
 
void releaseChildren ()
 
void releaseGarbage ()
 
bool isRoot () const
 
SEGMENTfindRedundantSegment (const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, int aNet)
 
SEGMENTfindRedundantSegment (SEGMENT *aSeg)
 
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).

More...
 

Private Attributes

JOINT_MAP m_joints
 

hash table with the joints, linking the items.

More...
 
NODEm_parent
 

node this node was branched from

More...
 
NODEm_root
 

root node of the whole hierarchy

More...
 
std::set< NODE * > m_children
 

list of nodes branched from this one

More...
 
std::unordered_set< ITEM * > m_override
 

hash of root's items that have been changed in this node

More...
 
int m_maxClearance
 

worst case item-item clearance

More...
 
RULE_RESOLVERm_ruleResolver
 

Design rules resolver

More...
 
INDEXm_index
 

Geometric/Net index of the items

More...
 
int m_depth
 

depth of the node (number of parent nodes in the inheritance chain)

More...
 
std::unordered_set< ITEM * > m_garbageItems
 

Detailed Description

Class NODE.

Keeps the router "world" - i.e. all the tracks, vias, solids in a hierarchical and indexed way. Features:

  • spatial-indexed container for PCB item shapes
  • collision search & clearance checking
  • assembly of lines connecting joints, finding loops and unique paths
  • lightweight cloning/branching (for recursive optimization and shove springback)

Definition at line 140 of file pns_node.h.

Member Typedef Documentation

◆ ITEM_VECTOR

typedef std::vector<ITEM*> PNS::NODE::ITEM_VECTOR

Definition at line 144 of file pns_node.h.

◆ JOINT_MAP

typedef std::unordered_multimap<JOINT::HASH_TAG, JOINT, JOINT::JOINT_TAG_HASH> PNS::NODE::JOINT_MAP
private

Definition at line 425 of file pns_node.h.

◆ OBSTACLES

typedef std::vector<OBSTACLE> PNS::NODE::OBSTACLES

Definition at line 145 of file pns_node.h.

◆ OPT_OBSTACLE

Definition at line 143 of file pns_node.h.

◆ TagJointPair

typedef JOINT_MAP::value_type PNS::NODE::TagJointPair
private

Definition at line 427 of file pns_node.h.

Constructor & Destructor Documentation

◆ NODE() [1/2]

PNS::NODE::NODE ( )

Definition at line 45 of file pns_node.cpp.

46 {
47  wxLogTrace( "PNS", "NODE::create %p", this );
48  m_depth = 0;
49  m_root = this;
50  m_parent = NULL;
51  m_maxClearance = 800000; // fixme: depends on how thick traces are.
52  m_ruleResolver = NULL;
53  m_index = new INDEX;
54 
55 #ifdef DEBUG
56  allocNodes.insert( this );
57 #endif
58 }
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:501
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
RULE_RESOLVER * m_ruleResolver
Design rules resolver
Definition: pns_node.h:498
int m_maxClearance
worst case item-item clearance
Definition: pns_node.h:495
NODE * m_parent
node this node was branched from
Definition: pns_node.h:483

References m_depth, m_index, m_maxClearance, m_parent, m_root, and m_ruleResolver.

Referenced by Branch().

◆ ~NODE()

PNS::NODE::~NODE ( )

Definition at line 61 of file pns_node.cpp.

62 {
63  wxLogTrace( "PNS", "NODE::delete %p", this );
64 
65  if( !m_children.empty() )
66  {
67  wxLogTrace( "PNS", "attempting to free a node that has kids." );
68  assert( false );
69  }
70 
71 #ifdef DEBUG
72  if( allocNodes.find( this ) == allocNodes.end() )
73  {
74  wxLogTrace( "PNS", "attempting to free an already-free'd node." );
75  assert( false );
76  }
77 
78  allocNodes.erase( this );
79 #endif
80 
81  m_joints.clear();
82 
83  for( ITEM* item : *m_index )
84  {
85  if( item->BelongsTo( this ) )
86  delete item;
87  }
88 
90  unlinkParent();
91 
92  delete m_index;
93 }
std::set< NODE * > m_children
list of nodes branched from this one
Definition: pns_node.h:489
void unlinkParent()
Definition: pns_node.cpp:138
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:501
void releaseGarbage()
Definition: pns_node.cpp:1177
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:480

References m_children, m_index, m_joints, releaseGarbage(), and unlinkParent().

◆ NODE() [2/2]

PNS::NODE::NODE ( const NODE aB)
private

nodes are not copyable

Member Function Documentation

◆ Add() [1/5]

bool PNS::NODE::Add ( std::unique_ptr< SEGMENT aSegment,
bool  aAllowRedundant = false 
)

Function Add()

Adds an item to the current node.

Parameters
aSegmentitem to add
aAllowRedundantif true, duplicate items are allowed (e.g. a segment or via
Returns
true if added at the same coordinates as an existing one)

Definition at line 590 of file pns_node.cpp.

591 {
592  if( aSegment->Seg().A == aSegment->Seg().B )
593  {
594  wxLogTrace( "PNS", "attempting to add a segment with same end coordinates, ignoring." );
595  return false;
596  }
597 
598  if( !aAllowRedundant && findRedundantSegment( aSegment.get() ) )
599  return false;
600 
601  aSegment->SetOwner( this );
602  addSegment( aSegment.release() );
603 
604  return true;
605 }
void addSegment(SEGMENT *aSeg)
Definition: pns_node.cpp:582
SEGMENT * findRedundantSegment(const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, int aNet)
Definition: pns_node.cpp:1265

References addSegment(), and findRedundantSegment().

Referenced by Add(), Commit(), PNS::DRAGGER::dragMarkObstacles(), PNS::DRAGGER::dragShove(), PNS::DRAGGER::dumbDragVia(), PNS::MEANDER_PLACER::FixRoute(), PNS::DP_MEANDER_PLACER::FixRoute(), PNS::LINE_PLACER::FixRoute(), PNS::DIFF_PAIR_PLACER::FixRoute(), PNS::LINE_PLACER::removeLoops(), Replace(), PNS::SHOVE::runOptimizer(), PNS::SHOVE::ShoveLines(), PNS::SHOVE::ShoveMultiLines(), PNS::TOPOLOGY::SimplifyLine(), PNS::LINE_PLACER::simplifyNewLine(), PNS::LINE_PLACER::SplitAdjacentSegments(), PNS_KICAD_IFACE::syncGraphicalItem(), PNS_KICAD_IFACE::syncTextItem(), PNS_KICAD_IFACE::SyncWorld(), and PNS_KICAD_IFACE::syncZone().

◆ Add() [2/5]

void PNS::NODE::Add ( std::unique_ptr< SOLID aSolid)

Definition at line 535 of file pns_node.cpp.

536 {
537  aSolid->SetOwner( this );
538  addSolid( aSolid.release() );
539 }
void addSolid(SOLID *aSeg)
helpers for adding/removing items
Definition: pns_node.cpp:529

References addSolid().

◆ Add() [3/5]

void PNS::NODE::Add ( std::unique_ptr< VIA aVia)

Definition at line 547 of file pns_node.cpp.

548 {
549  aVia->SetOwner( this );
550  addVia( aVia.release() );
551 }
void addVia(VIA *aVia)
Definition: pns_node.cpp:541

References addVia().

◆ Add() [4/5]

void PNS::NODE::Add ( LINE aLine,
bool  aAllowRedundant = false 
)

Definition at line 553 of file pns_node.cpp.

554 {
555  assert( !aLine.IsLinked() );
556 
557  SHAPE_LINE_CHAIN& l = aLine.Line();
558 
559  for( int i = 0; i < l.SegmentCount(); i++ )
560  {
561  SEG s = l.CSegment( i );
562 
563  if( s.A != s.B )
564  {
565  SEGMENT* rseg;
566  if( !aAllowRedundant &&
567  (rseg = findRedundantSegment( s.A, s.B, aLine.Layers(), aLine.Net() )) )
568  {
569  // another line could be referencing this segment too :(
570  aLine.LinkSegment( rseg );
571  }
572  else
573  {
574  std::unique_ptr< SEGMENT > newseg( new SEGMENT( aLine, s ) );
575  aLine.LinkSegment( newseg.get() );
576  Add( std::move( newseg ), true );
577  }
578  }
579  }
580 }
SEGMENT * findRedundantSegment(const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, int aNet)
Definition: pns_node.cpp:1265
Definition: seg.h:36
Class SHAPE_LINE_CHAIN.
size_t i
Definition: json11.cpp:597
VECTOR2I A
Definition: seg.h:44
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:590
VECTOR2I B
Definition: seg.h:45

References SEG::A, Add(), SEG::B, findRedundantSegment(), i, PNS::LINE::IsLinked(), PNS::ITEM::Layers(), PNS::LINE::Line(), PNS::LINE::LinkSegment(), and PNS::ITEM::Net().

◆ Add() [5/5]

void PNS::NODE::Add ( std::unique_ptr< ITEM aItem,
bool  aAllowRedundant = false 
)
private

Definition at line 607 of file pns_node.cpp.

608 {
609  switch( aItem->Kind() )
610  {
611  case ITEM::SOLID_T: Add( ItemCast<SOLID>( std::move( aItem ) ) ); break;
612  case ITEM::SEGMENT_T: Add( ItemCast<SEGMENT>( std::move( aItem ) ), aAllowRedundant ); break;
613  case ITEM::VIA_T: Add( ItemCast<VIA>( std::move( aItem ) ) ); break;
614 
615  case ITEM::LINE_T:
616  default:
617  assert( false );
618  }
619 }
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:590

References Add(), PNS::ITEM::LINE_T, PNS::ITEM::SEGMENT_T, PNS::ITEM::SOLID_T, and PNS::ITEM::VIA_T.

◆ addSegment()

void PNS::NODE::addSegment ( SEGMENT aSeg)
private

Definition at line 582 of file pns_node.cpp.

583 {
584  linkJoint( aSeg->Seg().A, aSeg->Layers(), aSeg->Net(), aSeg );
585  linkJoint( aSeg->Seg().B, aSeg->Layers(), aSeg->Net(), aSeg );
586 
587  m_index->Add( aSeg );
588 }
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
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:501
void Add(ITEM *aItem)
Function Add()
Definition: pns_index.cpp:85

References SEG::A, PNS::INDEX::Add(), SEG::B, PNS::ITEM::Layers(), linkJoint(), m_index, PNS::ITEM::Net(), and PNS::SEGMENT::Seg().

Referenced by Add().

◆ addSolid()

void PNS::NODE::addSolid ( SOLID aSeg)
private

helpers for adding/removing items

Definition at line 529 of file pns_node.cpp.

530 {
531  linkJoint( aSolid->Pos(), aSolid->Layers(), aSolid->Net(), aSolid );
532  m_index->Add( aSolid );
533 }
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
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:501
void Add(ITEM *aItem)
Function Add()
Definition: pns_index.cpp:85

References PNS::INDEX::Add(), PNS::ITEM::Layers(), linkJoint(), m_index, PNS::ITEM::Net(), and PNS::SOLID::Pos().

Referenced by Add().

◆ addVia()

void PNS::NODE::addVia ( VIA aVia)
private

Definition at line 541 of file pns_node.cpp.

542 {
543  linkJoint( aVia->Pos(), aVia->Layers(), aVia->Net(), aVia );
544  m_index->Add( aVia );
545 }
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
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:501
void Add(ITEM *aItem)
Function Add()
Definition: pns_index.cpp:85

References PNS::INDEX::Add(), PNS::ITEM::Layers(), linkJoint(), m_index, PNS::ITEM::Net(), and PNS::VIA::Pos().

Referenced by Add().

◆ AllItemsInNet()

void PNS::NODE::AllItemsInNet ( int  aNet,
std::set< ITEM * > &  aItems 
)

Definition at line 1219 of file pns_node.cpp.

1220 {
1221  INDEX::NET_ITEMS_LIST* l_cur = m_index->GetItemsForNet( aNet );
1222 
1223  if( l_cur )
1224  {
1225  for( ITEM*item : *l_cur )
1226  aItems.insert( item );
1227  }
1228 
1229  if( !isRoot() )
1230  {
1231  INDEX::NET_ITEMS_LIST* l_root = m_root->m_index->GetItemsForNet( aNet );
1232 
1233  if( l_root )
1234  for( INDEX::NET_ITEMS_LIST::iterator i = l_root->begin(); i!= l_root->end(); ++i )
1235  if( !Overrides( *i ) )
1236  aItems.insert( *i );
1237  }
1238 }
std::list< ITEM * > NET_ITEMS_LIST
Definition: pns_index.h:49
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
bool isRoot() const
Definition: pns_node.h:459
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:501
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:486
NET_ITEMS_LIST * GetItemsForNet(int aNet)
Function GetItemsForNet()
Definition: pns_index.cpp:138
size_t i
Definition: json11.cpp:597

References PNS::INDEX::GetItemsForNet(), i, isRoot(), m_index, m_root, and Overrides().

Referenced by PNS::TOPOLOGY::AssembleDiffPair(), PNS::DIFF_PAIR_PLACER::findDpPrimitivePair(), and PNS::TOPOLOGY::NearestUnconnectedItem().

◆ AssembleLine()

const LINE PNS::NODE::AssembleLine ( SEGMENT aSeg,
int *  aOriginSegmentIndex = NULL,
bool  aStopAtLockedJoints = false 
)

Function AssembleLine()

Follows the joint map to assemble a line connecting two non-trivial joints starting from segment aSeg.

Parameters
aSegthe initial segment
aOriginSegmentIndexindex of aSeg in the resulting line
Returns
the line

Definition at line 820 of file pns_node.cpp.

821 {
822  const int MaxVerts = 1024 * 16;
823 
824  VECTOR2I corners[MaxVerts + 1];
825  SEGMENT* segs[MaxVerts + 1];
826 
827  LINE pl;
828  bool guardHit = false;
829 
830  int i_start = MaxVerts / 2, i_end = i_start + 1;
831 
832  pl.SetWidth( aSeg->Width() );
833  pl.SetLayers( aSeg->Layers() );
834  pl.SetNet( aSeg->Net() );
835  pl.SetOwner( this );
836 
837  followLine( aSeg, false, i_start, MaxVerts, corners, segs, guardHit, aStopAtLockedJoints );
838 
839  if( !guardHit )
840  followLine( aSeg, true, i_end, MaxVerts, corners, segs, guardHit, aStopAtLockedJoints );
841 
842  int n = 0;
843 
844  SEGMENT* prev_seg = NULL;
845  bool originSet = false;
846 
847  for( int i = i_start + 1; i < i_end; i++ )
848  {
849  const VECTOR2I& p = corners[i];
850 
851  pl.Line().Append( p );
852 
853  if( segs[i] && prev_seg != segs[i] )
854  {
855  pl.LinkSegment( segs[i] );
856 
857  // latter condition to avoid loops
858  if( segs[i] == aSeg && aOriginSegmentIndex && !originSet )
859  {
860  *aOriginSegmentIndex = n;
861  originSet = true;
862  }
863  n++;
864  }
865 
866  prev_seg = segs[i];
867  }
868 
869  assert( pl.SegmentCount() != 0 );
870 
871  return pl;
872 }
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
size_t i
Definition: json11.cpp:597

References SHAPE_LINE_CHAIN::Append(), followLine(), i, PNS::ITEM::Layers(), PNS::LINE::Line(), PNS::LINE::LinkSegment(), PNS::ITEM::Net(), PNS::LINE::SegmentCount(), PNS::ITEM::SetLayers(), PNS::ITEM::SetNet(), PNS::ITEM::SetOwner(), PNS::LINE::SetWidth(), and PNS::SEGMENT::Width().

Referenced by PNS::TOPOLOGY::AssembleDiffPair(), PNS::SHOVE::assembleLine(), PNS::TOPOLOGY::AssembleTrivialPath(), Dump(), FindLinesBetweenJoints(), PNS::DRAGGER::findViaFanoutByHandle(), PNS::TOPOLOGY::followTrivialPath(), PNS::LINE_PLACER::removeLoops(), PNS::TOPOLOGY::SimplifyLine(), PNS::LINE_PLACER::simplifyNewLine(), PNS::MEANDER_SKEW_PLACER::Start(), PNS::MEANDER_PLACER::Start(), and PNS::DRAGGER::startDragSegment().

◆ Branch()

NODE * PNS::NODE::Branch ( )

Function Branch()

Creates a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs to the root. Note that if there are any branches in use, their parents must NOT be deleted.

Returns
the new branch

Definition at line 104 of file pns_node.cpp.

105 {
106  NODE* child = new NODE;
107 
108  wxLogTrace( "PNS", "NODE::branch %p (parent %p)", child, this );
109 
110  m_children.insert( child );
111 
112  child->m_depth = m_depth + 1;
113  child->m_parent = this;
114  child->m_ruleResolver = m_ruleResolver;
115  child->m_root = isRoot() ? this : m_root;
117 
118  // Immmediate offspring of the root branch needs not copy anything. For the rest, deep-copy
119  // joints, overridden item maps and pointers to stored items.
120  if( !isRoot() )
121  {
122  JOINT_MAP::iterator j;
123 
124  for( ITEM* item : *m_index )
125  child->m_index->Add( item );
126 
127  child->m_joints = m_joints;
128  child->m_override = m_override;
129  }
130 
131  wxLogTrace( "PNS", "%d items, %d joints, %d overrides",
132  child->m_index->Size(), (int) child->m_joints.size(), (int) child->m_override.size() );
133 
134  return child;
135 }
std::set< NODE * > m_children
list of nodes branched from this one
Definition: pns_node.h:489
bool isRoot() const
Definition: pns_node.h:459
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:501
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
RULE_RESOLVER * m_ruleResolver
Design rules resolver
Definition: pns_node.h:498
std::unordered_set< ITEM * > m_override
hash of root's items that have been changed in this node
Definition: pns_node.h:492
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

References PNS::INDEX::Add(), isRoot(), m_children, m_depth, m_index, m_joints, m_maxClearance, m_override, m_parent, m_root, m_ruleResolver, NODE(), and PNS::INDEX::Size().

Referenced by PNS::TOOL_BASE::deleteTraces(), PNS::MEANDER_PLACER::doMove(), PNS::DRAGGER::dragMarkObstacles(), PNS::DIFF_PAIR_PLACER::initPlacement(), PNS::LINE_PLACER::initPlacement(), PNS::TOPOLOGY::LeadingRatLine(), PNS::DP_MEANDER_PLACER::Move(), PNS::LINE_PLACER::Move(), PNS::DIFF_PAIR_PLACER::Move(), PNS::SHOVE::SetInitialLine(), PNS::SHOVE::ShoveDraggingVia(), PNS::SHOVE::ShoveLines(), PNS::SHOVE::ShoveMultiLines(), PNS::MEANDER_SKEW_PLACER::Start(), PNS::MEANDER_PLACER::Start(), PNS::DP_MEANDER_PLACER::Start(), and PNS::DIFF_PAIR_PLACER::tryWalkDp().

◆ CheckColliding() [1/3]

NODE::OPT_OBSTACLE PNS::NODE::CheckColliding ( const ITEM aItem,
int  aKindMask = ITEM::ANY_T 
)

Function CheckColliding()

Checks if the item collides with anything else in the world, and if found, returns the obstacle.

Parameters
aItemthe item to find collisions with
aKindMaskmask of obstacle types to take into account
Returns
the obstacle, if found, otherwise empty.

Definition at line 421 of file pns_node.cpp.

422 {
423  OBSTACLES obs;
424 
425  obs.reserve( 100 );
426 
427  if( aItemA->Kind() == ITEM::LINE_T )
428  {
429  int n = 0;
430  const LINE* line = static_cast<const LINE*>( aItemA );
431  const SHAPE_LINE_CHAIN& l = line->CLine();
432 
433  for( int i = 0; i < l.SegmentCount(); i++ )
434  {
435  const SEGMENT s( *line, l.CSegment( i ) );
436  n += QueryColliding( &s, obs, aKindMask, 1 );
437 
438  if( n )
439  return OPT_OBSTACLE( obs[0] );
440  }
441 
442  if( line->EndsWithVia() )
443  {
444  n += QueryColliding( &line->Via(), obs, aKindMask, 1 );
445 
446  if( n )
447  return OPT_OBSTACLE( obs[0] );
448  }
449  }
450  else if( QueryColliding( aItemA, obs, aKindMask, 1 ) > 0 )
451  return OPT_OBSTACLE( obs[0] );
452 
453  return OPT_OBSTACLE();
454 }
int SegmentCount() const
Function SegmentCount()
const SEG CSegment(int aIndex) const
Function CSegment()
Class SHAPE_LINE_CHAIN.
size_t i
Definition: json11.cpp:597
OPT< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:143
std::vector< OBSTACLE > OBSTACLES
Definition: pns_node.h:145
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

References PNS::LINE::CLine(), SHAPE_LINE_CHAIN::CSegment(), PNS::LINE::EndsWithVia(), i, PNS::ITEM::Kind(), PNS::ITEM::LINE_T, QueryColliding(), SHAPE_LINE_CHAIN::SegmentCount(), and PNS::LINE::Via().

Referenced by PNS::DIFF_PAIR_PLACER::attemptWalk(), PNS::OPTIMIZER::checkColliding(), CheckColliding(), PNS::checkDpColliding(), PNS::MEANDER_PLACER::CheckFit(), PNS::DP_MEANDER_PLACER::CheckFit(), PNS::DRAGGER::dragMarkObstacles(), PNS::OPTIMIZER::fanoutCleanup(), PNS::LINE_PLACER::FixRoute(), PNS::SHOVE::onCollidingSolid(), PNS::SHOVE::processHullSet(), PNS::VIA::PushoutForce(), PNS::SHOVE::reduceSpringback(), PNS::LINE_PLACER::reduceTail(), PNS::LINE_PLACER::reduceToNearestObstacle(), PNS::DIFF_PAIR_PLACER::rhMarkObstacles(), PNS::LINE_PLACER::rhMarkObstacles(), PNS::DIFF_PAIR_PLACER::rhShoveOnly(), PNS::LINE_PLACER::rhWalkOnly(), PNS::WALKAROUND::Route(), PNS::SHOVE::shoveIteration(), PNS::SHOVE::ShoveLines(), PNS::WALKAROUND::singleStep(), PNS::verifyDpBypass(), and PNS::SHOVE::walkaroundLoneVia().

◆ CheckColliding() [2/3]

NODE::OPT_OBSTACLE PNS::NODE::CheckColliding ( const ITEM_SET aSet,
int  aKindMask = ITEM::ANY_T 
)

Function CheckColliding()

Checks if any item in the set collides with anything else in the world, and if found, returns the obstacle.

Parameters
aSetset of items to find collisions with
aKindMaskmask of obstacle types to take into account
Returns
the obstacle, if found, otherwise empty.

Definition at line 407 of file pns_node.cpp.

408 {
409  for( const ITEM* item : aSet.CItems() )
410  {
411  OPT_OBSTACLE obs = CheckColliding( item, aKindMask );
412 
413  if( obs )
414  return obs;
415  }
416 
417  return OPT_OBSTACLE();
418 }
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Function CheckColliding()
Definition: pns_node.cpp:421
OPT< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:143

References CheckColliding(), and PNS::ITEM_SET::CItems().

◆ CheckColliding() [3/3]

bool PNS::NODE::CheckColliding ( const ITEM aItemA,
const ITEM aItemB,
int  aKindMask = ITEM::ANY_T,
int  aForceClearance = -1 
)

Function CheckColliding()

Checks if 2 items collide. and if found, returns the obstacle.

Parameters
aItemAfirst item to find collisions with
aItemBsecond item to find collisions with
aKindMaskmask of obstacle types to take into account
Returns
the obstacle, if found, otherwise empty.

Definition at line 457 of file pns_node.cpp.

458 {
459  assert( aItemB );
460  int clearance;
461  if( aForceClearance >= 0 )
462  clearance = aForceClearance;
463  else
464  clearance = GetClearance( aItemA, aItemB );
465 
466  // fixme: refactor
467  if( aItemA->Kind() == ITEM::LINE_T )
468  clearance += static_cast<const LINE*>( aItemA )->Width() / 2;
469  if( aItemB->Kind() == ITEM::LINE_T )
470  clearance += static_cast<const LINE*>( aItemB )->Width() / 2;
471 
472  return aItemA->Collide( aItemB, clearance, false, nullptr, this );
473 }
int GetClearance(const ITEM *aA, const ITEM *aB) const
Returns the expected clearance between items a and b.
Definition: pns_node.cpp:95

References PNS::ITEM::Collide(), GetClearance(), PNS::ITEM::Kind(), and PNS::ITEM::LINE_T.

◆ ClearRanks()

void PNS::NODE::ClearRanks ( int  aMarkerMask = MK_HEAD | MK_VIOLATION)

Definition at line 1241 of file pns_node.cpp.

1242 {
1243  for( INDEX::ITEM_SET::iterator i = m_index->begin(); i != m_index->end(); ++i )
1244  {
1245  (*i)->SetRank( -1 );
1246  (*i)->Mark( (*i)->Marker() & (~aMarkerMask) );
1247  }
1248 }
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:501
ITEM_SET::iterator end()
Definition: pns_index.h:141
ITEM_SET::iterator begin()
Definition: pns_index.h:140
size_t i
Definition: json11.cpp:597

References PNS::INDEX::begin(), PNS::INDEX::end(), i, and m_index.

Referenced by PNS::SHOVE::ShoveDraggingVia(), PNS::SHOVE::ShoveLines(), and PNS::SHOVE::ShoveMultiLines().

◆ Commit()

void PNS::NODE::Commit ( NODE aNode)

Function Commit()

Applies the changes from a given branch (aNode) to the root branch. Called on a non-root branch will fail. Calling commit also kills all children nodes of the root branch.

Parameters
aNodenode to commit changes from

Definition at line 1192 of file pns_node.cpp.

1193  {
1194  if( aNode->isRoot() )
1195  return;
1196 
1197  for( ITEM* item : aNode->m_override )
1198  Remove( item );
1199 
1200  for( auto i : *aNode->m_index )
1201  {
1202  i->SetRank( -1 );
1203  i->Unmark();
1204  Add( std::unique_ptr<ITEM>( i ) );
1205  }
1206 
1207  releaseChildren();
1208  releaseGarbage();
1209  }
void releaseChildren()
Definition: pns_node.cpp:1164
void releaseGarbage()
Definition: pns_node.cpp:1177
void Remove(SOLID *aSolid)
Function Remove()
Definition: pns_node.cpp:715
size_t i
Definition: json11.cpp:597
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:590

References Add(), i, isRoot(), m_index, m_override, releaseChildren(), releaseGarbage(), and Remove().

◆ Depth()

int PNS::NODE::Depth ( ) const
inline

Returns the number of nodes in the inheritance chain (wrs to the root node)

Definition at line 183 of file pns_node.h.

184  {
185  return m_depth;
186  }
int m_depth
depth of the node (number of parent nodes in the inheritance chain)
Definition: pns_node.h:504

References m_depth.

Referenced by PNS::LINE_PLACER::Move().

◆ doRemove()

void PNS::NODE::doRemove ( ITEM aItem)
private

Definition at line 622 of file pns_node.cpp.

623 {
624  // case 1: removing an item that is stored in the root node from any branch:
625  // mark it as overridden, but do not remove
626  if( aItem->BelongsTo( m_root ) && !isRoot() )
627  m_override.insert( aItem );
628 
629  // case 2: the item belongs to this branch or a parent, non-root branch,
630  // or the root itself and we are the root: remove from the index
631  else if( !aItem->BelongsTo( m_root ) || isRoot() )
632  m_index->Remove( aItem );
633 
634  // the item belongs to this particular branch: un-reference it
635  if( aItem->BelongsTo( this ) )
636  {
637  aItem->SetOwner( NULL );
638  m_root->m_garbageItems.insert( aItem );
639  }
640 }
bool isRoot() const
Definition: pns_node.h:459
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:501
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:486
std::unordered_set< ITEM * > m_override
hash of root's items that have been changed in this node
Definition: pns_node.h:492
std::unordered_set< ITEM * > m_garbageItems
Definition: pns_node.h:506
void Remove(ITEM *aItem)
Function Remove()
Definition: pns_index.cpp:102

References PNS::ITEM::BelongsTo(), isRoot(), m_garbageItems, m_index, m_override, m_root, PNS::INDEX::Remove(), and PNS::ITEM::SetOwner().

Referenced by Remove().

◆ Dump()

void PNS::NODE::Dump ( bool  aLong = false)

Prints the contents and joints structure

Definition at line 1068 of file pns_node.cpp.

1069 {
1070 #if 0
1071  std::unordered_set<SEGMENT*> all_segs;
1073 
1074  for( i = m_items.begin(); i != m_items.end(); i++ )
1075  {
1076  if( (*i)->GetKind() == ITEM::SEGMENT_T )
1077  all_segs.insert( static_cast<SEGMENT*>( *i ) );
1078  }
1079 
1080  if( !isRoot() )
1081  {
1082  for( i = m_root->m_items.begin(); i != m_root->m_items.end(); i++ )
1083  {
1084  if( (*i)->GetKind() == ITEM::SEGMENT_T && !overrides( *i ) )
1085  all_segs.insert( static_cast<SEGMENT*>(*i) );
1086  }
1087  }
1088 
1089  JOINT_MAP::iterator j;
1090 
1091  if( aLong )
1092  for( j = m_joints.begin(); j != m_joints.end(); ++j )
1093  {
1094  wxLogTrace( "PNS", "joint : %s, links : %d\n",
1095  j->second.GetPos().Format().c_str(), j->second.LinkCount() );
1096  JOINT::LINKED_ITEMS::const_iterator k;
1097 
1098  for( k = j->second.GetLinkList().begin(); k != j->second.GetLinkList().end(); ++k )
1099  {
1100  const ITEM* m_item = *k;
1101 
1102  switch( m_item->GetKind() )
1103  {
1104  case ITEM::SEGMENT_T:
1105  {
1106  const SEGMENT* seg = static_cast<const SEGMENT*>( m_item );
1107  wxLogTrace( "PNS", " -> seg %s %s\n", seg->GetSeg().A.Format().c_str(),
1108  seg->GetSeg().B.Format().c_str() );
1109  break;
1110  }
1111 
1112  default:
1113  break;
1114  }
1115  }
1116  }
1117 
1118 
1119  int lines_count = 0;
1120 
1121  while( !all_segs.empty() )
1122  {
1123  SEGMENT* s = *all_segs.begin();
1124  LINE* l = AssembleLine( s );
1125 
1126  LINE::LinkedSegments* seg_refs = l->GetLinkedSegments();
1127 
1128  if( aLong )
1129  wxLogTrace( "PNS", "Line: %s, net %d ", l->GetLine().Format().c_str(), l->GetNet() );
1130 
1131  for( std::vector<SEGMENT*>::iterator j = seg_refs->begin(); j != seg_refs->end(); ++j )
1132  {
1133  wxLogTrace( "PNS", "%s ", (*j)->GetSeg().A.Format().c_str() );
1134 
1135  if( j + 1 == seg_refs->end() )
1136  wxLogTrace( "PNS", "%s\n", (*j)->GetSeg().B.Format().c_str() );
1137 
1138  all_segs.erase( *j );
1139  }
1140 
1141  lines_count++;
1142  }
1143 
1144  wxLogTrace( "PNS", "Local joints: %d, lines : %d \n", m_joints.size(), lines_count );
1145 #endif
1146 }
const LINE AssembleLine(SEGMENT *aSeg, int *aOriginSegmentIndex=NULL, bool aStopAtLockedJoints=false)
Function AssembleLine()
Definition: pns_node.cpp:820
bool isRoot() const
Definition: pns_node.h:459
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:486
SEGMENT_REFS & LinkedSegments()
Returns the list of segments from the owning node that constitute this line (or NULL if the line is n...
Definition: pns_line.h:197
size_t i
Definition: json11.cpp:597
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:480

References AssembleLine(), i, isRoot(), PNS::LINE::LinkedSegments(), m_joints, m_root, and PNS::ITEM::SEGMENT_T.

◆ FindItemByParent()

ITEM * PNS::NODE::FindItemByParent ( const BOARD_CONNECTED_ITEM aParent)

Definition at line 1297 of file pns_node.cpp.

1298 {
1299  INDEX::NET_ITEMS_LIST* l_cur = m_index->GetItemsForNet( aParent->GetNetCode() );
1300 
1301  for( ITEM*item : *l_cur )
1302  if( item->Parent() == aParent )
1303  return item;
1304 
1305  return NULL;
1306 }
std::list< ITEM * > NET_ITEMS_LIST
Definition: pns_index.h:49
int GetNetCode() const
Function GetNetCode.
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:501
NET_ITEMS_LIST * GetItemsForNet(int aNet)
Function GetItemsForNet()
Definition: pns_index.cpp:138

References PNS::INDEX::GetItemsForNet(), BOARD_CONNECTED_ITEM::GetNetCode(), and m_index.

Referenced by ROUTER_TOOL::InlineBreakTrack(), and ROUTER_TOOL::InlineDrag().

◆ FindJoint() [1/2]

JOINT * PNS::NODE::FindJoint ( const VECTOR2I aPos,
int  aLayer,
int  aNet 
)

Function FindJoint()

Searches for a joint at a given position, layer and belonging to given net.

Returns
the joint, if found, otherwise empty

Definition at line 954 of file pns_node.cpp.

955 {
956  JOINT::HASH_TAG tag;
957 
958  tag.net = aNet;
959  tag.pos = aPos;
960 
961  JOINT_MAP::iterator f = m_joints.find( tag ), end = m_joints.end();
962 
963  if( f == end && !isRoot() )
964  {
965  end = m_root->m_joints.end();
966  f = m_root->m_joints.find( tag ); // m_root->FindJoint(aPos, aLayer, aNet);
967  }
968 
969  if( f == end )
970  return NULL;
971 
972  while( f != end )
973  {
974  if( f->second.Layers().Overlaps( aLayer ) )
975  return &f->second;
976 
977  ++f;
978  }
979 
980  return NULL;
981 }
bool isRoot() const
Definition: pns_node.h:459
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:486
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:480

References isRoot(), m_joints, m_root, PNS::JOINT::HASH_TAG::net, and PNS::JOINT::HASH_TAG::pos.

Referenced by PNS::LINE_RESTRICTIONS::allowedAngles(), PNS::TOPOLOGY::AssembleTrivialPath(), PNS::TOPOLOGY::ConnectedJoints(), FindJoint(), FindLineEnds(), PNS::OPTIMIZER::findPadOrVia(), findRedundantSegment(), PNS::findViaByHandle(), PNS::DRAGGER::findViaFanoutByHandle(), followLine(), PNS::TOPOLOGY::followTrivialPath(), PNS::DIFF_PAIR_PLACER::getDanglingAnchor(), PNS::SHOVE::onCollidingSolid(), PNS::SHOVE::onReverseCollidingVia(), PNS::SHOVE::processHullSet(), PNS::SHOVE::pushOrShoveVia(), removeViaIndex(), and PNS::LINE_PLACER::SplitAdjacentSegments().

◆ FindJoint() [2/2]

JOINT* PNS::NODE::FindJoint ( const VECTOR2I aPos,
const ITEM aItem 
)
inline

Function FindJoint()

Searches for a joint at a given position, linked to given item.

Returns
the joint, if found, otherwise empty

Definition at line 380 of file pns_node.h.

381  {
382  return FindJoint( aPos, aItem->Layers().Start(), aItem->Net() );
383  }
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:954

References FindJoint(), PNS::ITEM::Layers(), PNS::ITEM::Net(), and LAYER_RANGE::Start().

◆ FindLineEnds()

void PNS::NODE::FindLineEnds ( const LINE aLine,
JOINT aA,
JOINT aB 
)

finds the joints corresponding to the ends of line aLine

Definition at line 875 of file pns_node.cpp.

876 {
877  aA = *FindJoint( aLine.CPoint( 0 ), &aLine );
878  aB = *FindJoint( aLine.CPoint( -1 ), &aLine );
879 }
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:954

References PNS::LINE::CPoint(), and FindJoint().

Referenced by FindLinesBetweenJoints(), and PNS::LINE_PLACER::removeLoops().

◆ FindLinesBetweenJoints()

int PNS::NODE::FindLinesBetweenJoints ( JOINT aA,
JOINT aB,
std::vector< LINE > &  aLines 
)

finds all lines between a pair of joints. Used by the loop removal procedure.

Definition at line 920 of file pns_node.cpp.

921 {
922  for( ITEM* item : aA.LinkList() )
923  {
924  if( item->Kind() == ITEM::SEGMENT_T )
925  {
926  SEGMENT* seg = static_cast<SEGMENT*>( item );
927  LINE line = AssembleLine( seg );
928 
929  if( !line.Layers().Overlaps( aB.Layers() ) )
930  continue;
931 
932  JOINT j_start, j_end;
933 
934  FindLineEnds( line, j_start, j_end );
935 
936  int id_start = line.CLine().Find( aA.Pos() );
937  int id_end = line.CLine().Find( aB.Pos() );
938 
939  if( id_end < id_start )
940  std::swap( id_end, id_start );
941 
942  if( id_start >= 0 && id_end >= 0 )
943  {
944  line.ClipVertexRange( id_start, id_end );
945  aLines.push_back( line );
946  }
947  }
948  }
949 
950  return 0;
951 }
const LINE AssembleLine(SEGMENT *aSeg, int *aOriginSegmentIndex=NULL, bool aStopAtLockedJoints=false)
Function AssembleLine()
Definition: pns_node.cpp:820
void FindLineEnds(const LINE &aLine, JOINT &aA, JOINT &aB)
finds the joints corresponding to the ends of line aLine
Definition: pns_node.cpp:875

References AssembleLine(), PNS::LINE::CLine(), PNS::LINE::ClipVertexRange(), SHAPE_LINE_CHAIN::Find(), FindLineEnds(), PNS::ITEM::Layers(), PNS::JOINT::LinkList(), LAYER_RANGE::Overlaps(), PNS::JOINT::Pos(), and PNS::ITEM::SEGMENT_T.

Referenced by PNS::LINE_PLACER::removeLoops().

◆ findRedundantSegment() [1/2]

SEGMENT * PNS::NODE::findRedundantSegment ( const VECTOR2I A,
const VECTOR2I B,
const LAYER_RANGE lr,
int  aNet 
)
private

Definition at line 1265 of file pns_node.cpp.

1267 {
1268  JOINT* jtStart = FindJoint( A, lr.Start(), aNet );
1269 
1270  if( !jtStart )
1271  return nullptr;
1272 
1273  for( ITEM* item : jtStart->LinkList() )
1274  {
1275  if( item->OfKind( ITEM::SEGMENT_T ) )
1276  {
1277  SEGMENT* seg2 = (SEGMENT*)item;
1278 
1279  const VECTOR2I a2( seg2->Seg().A );
1280  const VECTOR2I b2( seg2->Seg().B );
1281 
1282  if( seg2->Layers().Start() == lr.Start() &&
1283  ((A == a2 && B == b2) || (A == b2 && B == a2)) )
1284  return seg2;
1285  }
1286  }
1287 
1288  return nullptr;
1289 }
int Start() const
Definition: pns_layerset.h:83
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:954

References SEG::A, SEG::B, FindJoint(), PNS::ITEM::Layers(), PNS::JOINT::LinkList(), PNS::SEGMENT::Seg(), PNS::ITEM::SEGMENT_T, and LAYER_RANGE::Start().

Referenced by Add(), and findRedundantSegment().

◆ findRedundantSegment() [2/2]

SEGMENT * PNS::NODE::findRedundantSegment ( SEGMENT aSeg)
private

Definition at line 1291 of file pns_node.cpp.

1292 {
1293  return findRedundantSegment( aSeg->Seg().A, aSeg->Seg().B, aSeg->Layers(), aSeg->Net() );
1294 }
SEGMENT * findRedundantSegment(const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, int aNet)
Definition: pns_node.cpp:1265

References SEG::A, SEG::B, findRedundantSegment(), PNS::ITEM::Layers(), PNS::ITEM::Net(), and PNS::SEGMENT::Seg().

◆ followLine()

void PNS::NODE::followLine ( SEGMENT aCurrent,
bool  aScanDirection,
int &  aPos,
int  aLimit,
VECTOR2I aCorners,
SEGMENT **  aSegments,
bool &  aGuardHit,
bool  aStopAtLockedJoints 
)
private

scans the joint map, forming a line starting from segment (current).

Definition at line 780 of file pns_node.cpp.

783 {
784  bool prevReversed = false;
785 
786  const VECTOR2I guard = aScanDirection ? aCurrent->Seg().B : aCurrent->Seg().A;
787 
788  for( int count = 0 ; ; ++count )
789  {
790  const VECTOR2I p =
791  ( aScanDirection ^ prevReversed ) ? aCurrent->Seg().B : aCurrent->Seg().A;
792  const JOINT* jt = FindJoint( p, aCurrent );
793 
794  assert( jt );
795 
796  aCorners[aPos] = jt->Pos();
797  aSegments[aPos] = aCurrent;
798  aPos += ( aScanDirection ? 1 : -1 );
799 
800  if( count && guard == p)
801  {
802  aSegments[aPos] = NULL;
803  aGuardHit = true;
804  break;
805  }
806 
807  bool locked = aStopAtLockedJoints ? jt->IsLocked() : false;
808 
809  if( locked || !jt->IsLineCorner() || aPos < 0 || aPos == aLimit )
810  break;
811 
812  aCurrent = jt->NextSegment( aCurrent );
813 
814  prevReversed =
815  ( jt->Pos() == ( aScanDirection ? aCurrent->Seg().B : aCurrent->Seg().A ) );
816  }
817 }
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:954

References SEG::A, SEG::B, FindJoint(), PNS::JOINT::IsLineCorner(), PNS::JOINT::IsLocked(), PNS::JOINT::NextSegment(), PNS::JOINT::Pos(), and PNS::SEGMENT::Seg().

Referenced by AssembleLine().

◆ GetClearance()

int PNS::NODE::GetClearance ( const ITEM aA,
const ITEM aB 
) const

Returns the expected clearance between items a and b.

Definition at line 95 of file pns_node.cpp.

96 {
97  if( !m_ruleResolver )
98  return 100000;
99 
100  return m_ruleResolver->Clearance( aA, aB );
101 }
RULE_RESOLVER * m_ruleResolver
Design rules resolver
Definition: pns_node.h:498
virtual int Clearance(const ITEM *aA, const ITEM *aB) const =0

References PNS::RULE_RESOLVER::Clearance(), and m_ruleResolver.

Referenced by CheckColliding(), PNS::SHOVE::getClearance(), PNS::ROUTER::markViolations(), NearestObstacle(), PNS::OPTIMIZER::CACHE_VISITOR::operator()(), PNS::NODE::DEFAULT_OBSTACLE_VISITOR::operator()(), PNS::VIA::PushoutForce(), and PNS::LINE_PLACER::rhMarkObstacles().

◆ GetMaxClearance()

int PNS::NODE::GetMaxClearance ( ) const
inline

Returns the pre-set worst case clearance between any pair of items

Definition at line 154 of file pns_node.h.

155  {
156  return m_maxClearance;
157  }
int m_maxClearance
worst case item-item clearance
Definition: pns_node.h:495

References m_maxClearance.

Referenced by PNS::OPTIMIZER::checkColliding().

◆ GetRuleResolver()

RULE_RESOLVER* PNS::NODE::GetRuleResolver ( ) const
inline

Definition at line 171 of file pns_node.h.

172  {
173  return m_ruleResolver;
174  }
RULE_RESOLVER * m_ruleResolver
Design rules resolver
Definition: pns_node.h:498

References m_ruleResolver.

Referenced by PNS::TOPOLOGY::AssembleDiffPair(), PNS::DIFF_PAIR_PLACER::findDpPrimitivePair(), and PNS::SHOVE::onCollidingVia().

◆ GetUpdatedItems()

void PNS::NODE::GetUpdatedItems ( ITEM_VECTOR aRemoved,
ITEM_VECTOR aAdded 
)

Function GetUpdatedItems()

Returns the lists of items removed and added in this branch, with respect to the root branch.

Parameters
aRemovedremoved items
aAddedadded items

Definition at line 1149 of file pns_node.cpp.

1150 {
1151  aRemoved.reserve( m_override.size() );
1152  aAdded.reserve( m_index->Size() );
1153 
1154  if( isRoot() )
1155  return;
1156 
1157  for( ITEM* item : m_override )
1158  aRemoved.push_back( item );
1159 
1160  for( INDEX::ITEM_SET::iterator i = m_index->begin(); i != m_index->end(); ++i )
1161  aAdded.push_back( *i );
1162 }
bool isRoot() const
Definition: pns_node.h:459
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:501
std::unordered_set< ITEM * > m_override
hash of root's items that have been changed in this node
Definition: pns_node.h:492
ITEM_SET::iterator end()
Definition: pns_index.h:141
ITEM_SET::iterator begin()
Definition: pns_index.h:140
int Size() const
Function Size()
Definition: pns_index.h:138
size_t i
Definition: json11.cpp:597

References PNS::INDEX::begin(), PNS::INDEX::end(), i, isRoot(), m_index, m_override, and PNS::INDEX::Size().

Referenced by PNS::ROUTER::CommitRouting(), and PNS::ROUTER::updateView().

◆ HasChildren()

bool PNS::NODE::HasChildren ( ) const
inline

Definition at line 412 of file pns_node.h.

413  {
414  return !m_children.empty();
415  }
std::set< NODE * > m_children
list of nodes branched from this one
Definition: pns_node.h:489

References m_children.

◆ HitTest()

const ITEM_SET PNS::NODE::HitTest ( const VECTOR2I aPoint) const

Function HitTest()

Finds all items that contain the point aPoint.

Parameters
aPointthe point
Returns
the items

Definition at line 500 of file pns_node.cpp.

501 {
502  ITEM_SET items;
503 
504  // fixme: we treat a point as an infinitely small circle - this is inefficient.
505  SHAPE_CIRCLE s( aPoint, 0 );
506  HIT_VISITOR visitor( items, aPoint );
507  visitor.SetWorld( this, NULL );
508 
509  m_index->Query( &s, m_maxClearance, visitor );
510 
511  if( !isRoot() ) // fixme: could be made cleaner
512  {
513  ITEM_SET items_root;
514  visitor.SetWorld( m_root, NULL );
515  HIT_VISITOR visitor_root( items_root, aPoint );
516  m_root->m_index->Query( &s, m_maxClearance, visitor_root );
517 
518  for( ITEM* item : items_root.Items() )
519  {
520  if( !Overrides( item ) )
521  items.Add( item );
522  }
523  }
524 
525  return items;
526 }
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
bool isRoot() const
Definition: pns_node.h:459
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:501
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:486
int Query(const ITEM *aItem, int aMinDistance, Visitor &aVisitor)
Function Query()
Definition: pns_index.h:173
int m_maxClearance
worst case item-item clearance
Definition: pns_node.h:495

References PNS::ITEM_SET::Add(), isRoot(), PNS::ITEM_SET::Items(), m_index, m_maxClearance, m_root, Overrides(), PNS::INDEX::Query(), and PNS::OBSTACLE_VISITOR::SetWorld().

◆ isRoot()

bool PNS::NODE::isRoot ( ) const
inlineprivate

Definition at line 459 of file pns_node.h.

460  {
461  return m_parent == NULL;
462  }
NODE * m_parent
node this node was branched from
Definition: pns_node.h:483

References m_parent.

Referenced by AllItemsInNet(), Branch(), Commit(), doRemove(), Dump(), FindJoint(), GetUpdatedItems(), HitTest(), KillChildren(), QueryColliding(), releaseGarbage(), touchJoint(), and unlinkParent().

◆ JointCount()

int PNS::NODE::JointCount ( ) const
inline

Returns the number of joints

Definition at line 177 of file pns_node.h.

178  {
179  return m_joints.size();
180  }
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:480

References m_joints.

Referenced by PNS::SHOVE::shoveMainLoop().

◆ KillChildren()

void PNS::NODE::KillChildren ( )

Destroys all child nodes. Applicable only to the root node.

Definition at line 1212 of file pns_node.cpp.

1213 {
1214  assert( isRoot() );
1215  releaseChildren();
1216 }
void releaseChildren()
Definition: pns_node.cpp:1164
bool isRoot() const
Definition: pns_node.h:459

References isRoot(), and releaseChildren().

Referenced by PNS::DIFF_PAIR_PLACER::initPlacement(), and PNS::LINE_PLACER::initPlacement().

◆ linkJoint()

void PNS::NODE::linkJoint ( const VECTOR2I aPos,
const LAYER_RANGE aLayers,
int  aNet,
ITEM aWhere 
)
private

touches a joint and links it to an m_item

Definition at line 1049 of file pns_node.cpp.

1051 {
1052  JOINT& jt = touchJoint( aPos, aLayers, aNet );
1053 
1054  jt.Link( aWhere );
1055 }
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

References PNS::JOINT::Link(), and touchJoint().

Referenced by addSegment(), addSolid(), addVia(), and removeViaIndex().

◆ LockJoint()

void PNS::NODE::LockJoint ( const VECTOR2I aPos,
const ITEM aItem,
bool  aLock 
)

Definition at line 984 of file pns_node.cpp.

985 {
986  JOINT& jt = touchJoint( aPos, aItem->Layers(), aItem->Net() );
987  jt.Lock( aLock );
988 }
void Lock(bool aLock=true)
Definition: pns_joint.h:244
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

References PNS::ITEM::Layers(), PNS::JOINT::Lock(), PNS::ITEM::Net(), and touchJoint().

Referenced by PNS::SHOVE::ShoveLines().

◆ NearestObstacle()

NODE::OPT_OBSTACLE PNS::NODE::NearestObstacle ( const LINE aItem,
int  aKindMask = ITEM::ANY_T,
const std::set< ITEM * > *  aRestrictedSet = NULL 
)

Function NearestObstacle()

Follows the line in search of an obstacle that is nearest to the starting to the line's starting point.

Parameters
aItemthe item to find collisions with
aKindMaskmask of obstacle types to take into account
Returns
the obstacle, if found, otherwise empty.

Definition at line 298 of file pns_node.cpp.

300 {
301  OBSTACLES obs_list;
302  bool found_isects = false;
303 
304  const SHAPE_LINE_CHAIN& line = aItem->CLine();
305 
306  obs_list.reserve( 100 );
307 
308  int n = 0;
309 
310  for( int i = 0; i < line.SegmentCount(); i++ )
311  {
312  const SEGMENT s( *aItem, line.CSegment( i ) );
313  n += QueryColliding( &s, obs_list, aKindMask );
314  }
315 
316  if( aItem->EndsWithVia() )
317  n += QueryColliding( &aItem->Via(), obs_list, aKindMask );
318 
319  if( !n )
320  return OPT_OBSTACLE();
321 
322  LINE& aLine = (LINE&) *aItem;
323 
324  OBSTACLE nearest;
325  nearest.m_item = NULL;
326  nearest.m_distFirst = INT_MAX;
327 
328  for( const OBSTACLE& obs : obs_list )
329  {
330  VECTOR2I ip_last;
331  int dist_max = INT_MIN;
332 
333  if( aRestrictedSet && aRestrictedSet->find( obs.m_item ) == aRestrictedSet->end() )
334  continue;
335 
336  std::vector<SHAPE_LINE_CHAIN::INTERSECTION> isect_list;
337 
338  int clearance = GetClearance( obs.m_item, &aLine );
339 
340  SHAPE_LINE_CHAIN hull = obs.m_item->Hull( clearance, aItem->Width() );
341 
342  if( aLine.EndsWithVia() )
343  {
344  clearance = GetClearance( obs.m_item, &aLine.Via() );
345 
346  SHAPE_LINE_CHAIN viaHull = aLine.Via().Hull( clearance, aItem->Width() );
347 
348  viaHull.Intersect( hull, isect_list );
349 
350  for( SHAPE_LINE_CHAIN::INTERSECTION isect : isect_list )
351  {
352  int dist = aLine.CLine().Length() +
353  ( isect.p - aLine.Via().Pos() ).EuclideanNorm();
354 
355  if( dist < nearest.m_distFirst )
356  {
357  found_isects = true;
358  nearest.m_distFirst = dist;
359  nearest.m_ipFirst = isect.p;
360  nearest.m_item = obs.m_item;
361  nearest.m_hull = hull;
362  }
363 
364  if( dist > dist_max )
365  {
366  dist_max = dist;
367  ip_last = isect.p;
368  }
369  }
370  }
371 
372  isect_list.clear();
373 
374  hull.Intersect( aLine.CLine(), isect_list );
375 
376  for( SHAPE_LINE_CHAIN::INTERSECTION isect : isect_list )
377  {
378  int dist = aLine.CLine().PathLength( isect.p );
379 
380  if( dist < nearest.m_distFirst )
381  {
382  found_isects = true;
383  nearest.m_distFirst = dist;
384  nearest.m_ipFirst = isect.p;
385  nearest.m_item = obs.m_item;
386  nearest.m_hull = hull;
387  }
388 
389  if( dist > dist_max )
390  {
391  dist_max = dist;
392  ip_last = isect.p;
393  }
394  }
395 
396  nearest.m_ipLast = ip_last;
397  nearest.m_distLast = dist_max;
398  }
399 
400  if( !found_isects )
401  nearest.m_item = obs_list[0].m_item;
402 
403  return nearest;
404 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:123
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Function Intersect()
static const int dist[10][10]
Definition: ar_matrix.cpp:320
int GetClearance(const ITEM *aA, const ITEM *aB) const
Returns the expected clearance between items a and b.
Definition: pns_node.cpp:95
int SegmentCount() const
Function SegmentCount()
const SEG CSegment(int aIndex) const
Function CSegment()
Class SHAPE_LINE_CHAIN.
size_t i
Definition: json11.cpp:597
OPT< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:143
std::vector< OBSTACLE > OBSTACLES
Definition: pns_node.h:145
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

References PNS::LINE::CLine(), SHAPE_LINE_CHAIN::CSegment(), dist, PNS::LINE::EndsWithVia(), EuclideanNorm(), GetClearance(), PNS::VIA::Hull(), i, SHAPE_LINE_CHAIN::Intersect(), SHAPE_LINE_CHAIN::Length(), PNS::OBSTACLE::m_distFirst, PNS::OBSTACLE::m_distLast, PNS::OBSTACLE::m_hull, PNS::OBSTACLE::m_ipFirst, PNS::OBSTACLE::m_ipLast, PNS::OBSTACLE::m_item, SHAPE_LINE_CHAIN::PathLength(), PNS::VIA::Pos(), QueryColliding(), SHAPE_LINE_CHAIN::SegmentCount(), PNS::LINE::Via(), and PNS::LINE::Width().

Referenced by PNS::LINE::ClipToNearestObstacle(), PNS::WALKAROUND::nearestObstacle(), and PNS::SHOVE::shoveIteration().

◆ operator=()

NODE& PNS::NODE::operator= ( const NODE aB)
private

◆ Overrides()

bool PNS::NODE::Overrides ( ITEM aItem) const
inline

checks if this branch contains an updated version of the m_item from the root branch.

Definition at line 419 of file pns_node.h.

420  {
421  return m_override.find( aItem ) != m_override.end();
422  }
std::unordered_set< ITEM * > m_override
hash of root's items that have been changed in this node
Definition: pns_node.h:492

References m_override.

Referenced by AllItemsInNet(), HitTest(), and PNS::OBSTACLE_VISITOR::visit().

◆ QueryColliding() [1/2]

int PNS::NODE::QueryColliding ( const ITEM aItem,
NODE::OBSTACLES aObstacles,
int  aKindMask = ITEM::ANY_T,
int  aLimitCount = -1,
bool  aDifferentNetsOnly = true,
int  aForceClearance = -1 
)

Function QueryColliding()

Finds items collliding (closer than clearance) with the item aItem.

Parameters
aItemitem to check collisions against
aObstaclesset of colliding objects found
aKindMaskmask of obstacle types to take into account
aLimitCountstop looking for collisions after finding this number of colliding items
Returns
number of obstacles found

Definition at line 272 of file pns_node.cpp.

274 {
275  DEFAULT_OBSTACLE_VISITOR visitor( aObstacles, aItem, aKindMask, aDifferentNetsOnly );
276 
277 #ifdef DEBUG
278  assert( allocNodes.find( this ) != allocNodes.end() );
279 #endif
280 
281  visitor.SetCountLimit( aLimitCount );
282  visitor.SetWorld( this, NULL );
283  visitor.m_forceClearance = aForceClearance;
284  // first, look for colliding items in the local index
285  m_index->Query( aItem, m_maxClearance, visitor );
286 
287  // if we haven't found enough items, look in the root branch as well.
288  if( !isRoot() && ( visitor.m_matchCount < aLimitCount || aLimitCount < 0 ) )
289  {
290  visitor.SetWorld( m_root, this );
291  m_root->m_index->Query( aItem, m_maxClearance, visitor );
292  }
293 
294  return aObstacles.size();
295 }
bool isRoot() const
Definition: pns_node.h:459
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:501
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:486
int Query(const ITEM *aItem, int aMinDistance, Visitor &aVisitor)
Function Query()
Definition: pns_index.h:173
int m_maxClearance
worst case item-item clearance
Definition: pns_node.h:495

References isRoot(), PNS::NODE::DEFAULT_OBSTACLE_VISITOR::m_forceClearance, m_index, PNS::NODE::DEFAULT_OBSTACLE_VISITOR::m_matchCount, m_maxClearance, m_root, PNS::INDEX::Query(), PNS::NODE::DEFAULT_OBSTACLE_VISITOR::SetCountLimit(), and PNS::OBSTACLE_VISITOR::SetWorld().

Referenced by PNS::TOPOLOGY::AssembleCluster(), CheckColliding(), PNS::ROUTER::markViolations(), NearestObstacle(), and PNS::LINE_PLACER::rhMarkObstacles().

◆ QueryColliding() [2/2]

int PNS::NODE::QueryColliding ( const ITEM aItem,
OBSTACLE_VISITOR aVisitor 
)

Definition at line 256 of file pns_node.cpp.

257 {
258  aVisitor.SetWorld( this, NULL );
259  m_index->Query( aItem, m_maxClearance, aVisitor );
260 
261  // if we haven't found enough items, look in the root branch as well.
262  if( !isRoot() )
263  {
264  aVisitor.SetWorld( m_root, this );
265  m_root->m_index->Query( aItem, m_maxClearance, aVisitor );
266  }
267 
268  return 0;
269 }
bool isRoot() const
Definition: pns_node.h:459
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:501
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:486
int Query(const ITEM *aItem, int aMinDistance, Visitor &aVisitor)
Function Query()
Definition: pns_index.h:173
int m_maxClearance
worst case item-item clearance
Definition: pns_node.h:495

References isRoot(), m_index, m_maxClearance, m_root, PNS::INDEX::Query(), and PNS::OBSTACLE_VISITOR::SetWorld().

◆ releaseChildren()

void PNS::NODE::releaseChildren ( )
private

Definition at line 1164 of file pns_node.cpp.

1165 {
1166  // copy the kids as the NODE destructor erases the item from the parent node.
1167  std::set<NODE*> kids = m_children;
1168 
1169  for( NODE* node : kids )
1170  {
1171  node->releaseChildren();
1172  delete node;
1173  }
1174 }
std::set< NODE * > m_children
list of nodes branched from this one
Definition: pns_node.h:489

References m_children.

Referenced by Commit(), and KillChildren().

◆ releaseGarbage()

void PNS::NODE::releaseGarbage ( )
private

Definition at line 1177 of file pns_node.cpp.

1178 {
1179  if( !isRoot() )
1180  return;
1181 
1182  for( ITEM* item : m_garbageItems )
1183  {
1184  if( !item->BelongsTo( this ) )
1185  delete item;
1186  }
1187 
1188  m_garbageItems.clear();
1189 }
bool isRoot() const
Definition: pns_node.h:459
std::unordered_set< ITEM * > m_garbageItems
Definition: pns_node.h:506

References isRoot(), and m_garbageItems.

Referenced by Commit(), and ~NODE().

◆ Remove() [1/5]

◆ Remove() [2/5]

void PNS::NODE::Remove ( VIA aVia)

Definition at line 721 of file pns_node.cpp.

722 {
723  removeViaIndex( aVia );
724  doRemove( aVia );
725 }
void doRemove(ITEM *aItem)
Definition: pns_node.cpp:622
void removeViaIndex(VIA *aVia)
Definition: pns_node.cpp:649

References doRemove(), and removeViaIndex().

◆ Remove() [3/5]

void PNS::NODE::Remove ( SEGMENT aSegment)

Definition at line 727 of file pns_node.cpp.

728 {
729  removeSegmentIndex( aSegment );
730  doRemove( aSegment );
731 }
void doRemove(ITEM *aItem)
Definition: pns_node.cpp:622
void removeSegmentIndex(SEGMENT *aSeg)
Definition: pns_node.cpp:643

References doRemove(), and removeSegmentIndex().

◆ Remove() [4/5]

void PNS::NODE::Remove ( ITEM aItem)

Definition at line 733 of file pns_node.cpp.

734 {
735  switch( aItem->Kind() )
736  {
737  case ITEM::SOLID_T:
738  Remove( static_cast<SOLID*>( aItem ) );
739  break;
740 
741  case ITEM::SEGMENT_T:
742  Remove( static_cast<SEGMENT*>( aItem ) );
743  break;
744 
745  case ITEM::LINE_T:
746  {
747  auto l = static_cast<LINE *> ( aItem );
748 
749  for ( auto s : l->LinkedSegments() )
750  Remove( s );
751 
752  break;
753  }
754 
755  case ITEM::VIA_T:
756  Remove( static_cast<VIA*>( aItem ) );
757  break;
758 
759  default:
760  break;
761  }
762 }
void Remove(SOLID *aSolid)
Function Remove()
Definition: pns_node.cpp:715

References PNS::ITEM::Kind(), PNS::ITEM::LINE_T, Remove(), PNS::ITEM::SEGMENT_T, PNS::ITEM::SOLID_T, and PNS::ITEM::VIA_T.

◆ Remove() [5/5]

void PNS::NODE::Remove ( LINE aLine)

Function Remove()

Just as the name says, removes a line from this branch.

Parameters
aLineitem to remove

Definition at line 765 of file pns_node.cpp.

766 {
767  // LINE does not have a seperate remover, as LINEs are never truly a member of the tree
768  std::vector<SEGMENT*>& segRefs = aLine.LinkedSegments();
769 
770  for( SEGMENT* seg : segRefs )
771  {
772  Remove( seg );
773  }
774 
775  aLine.SetOwner( nullptr );
776  aLine.ClearSegmentLinks();
777 }
void Remove(SOLID *aSolid)
Function Remove()
Definition: pns_node.cpp:715

References PNS::LINE::ClearSegmentLinks(), PNS::LINE::LinkedSegments(), Remove(), and PNS::ITEM::SetOwner().

◆ RemoveByMarker()

void PNS::NODE::RemoveByMarker ( int  aMarker)

Definition at line 1251 of file pns_node.cpp.

1252 {
1253  std::list<ITEM*> garbage;
1254 
1255  for( ITEM* item : *m_index )
1256  {
1257  if( item->Marker() & aMarker )
1258  garbage.push_back( item );
1259  }
1260 
1261  for( ITEM* item : garbage )
1262  Remove( item );
1263 }
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:501
void Remove(SOLID *aSolid)
Function Remove()
Definition: pns_node.cpp:715

References m_index, and Remove().

Referenced by PNS::SHOVE::ShoveLines(), and PNS::SHOVE::ShoveMultiLines().

◆ removeLine()

void PNS::NODE::removeLine ( LINE aLine)
private

◆ removeSegmentIndex()

void PNS::NODE::removeSegmentIndex ( SEGMENT aSeg)
private

Definition at line 643 of file pns_node.cpp.

644 {
645  unlinkJoint( aSeg->Seg().A, aSeg->Layers(), aSeg->Net(), aSeg );
646  unlinkJoint( aSeg->Seg().B, aSeg->Layers(), aSeg->Net(), aSeg );
647 }
void unlinkJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
unlinks an item from a joint
Definition: pns_node.cpp:1058

References SEG::A, SEG::B, PNS::ITEM::Layers(), PNS::ITEM::Net(), PNS::SEGMENT::Seg(), and unlinkJoint().

Referenced by Remove().

◆ removeSolidIndex()

void PNS::NODE::removeSolidIndex ( SOLID aSeg)
private

Definition at line 697 of file pns_node.cpp.

698 {
699  // fixme: this fucks up the joints, but it's only used for marking colliding obstacles for the moment, so we don't care.
700 }

Referenced by Remove().

◆ removeViaIndex()

void PNS::NODE::removeViaIndex ( VIA aVia)
private

Definition at line 649 of file pns_node.cpp.

650 {
651  // We have to split a single joint (associated with a via, binding together multiple layers)
652  // into multiple independent joints. As I'm a lazy bastard, I simply delete the via and all
653  // its links and re-insert them.
654 
655  JOINT::HASH_TAG tag;
656 
657  VECTOR2I p( aVia->Pos() );
658  LAYER_RANGE vLayers( aVia->Layers() );
659  int net = aVia->Net();
660 
661  JOINT* jt = FindJoint( p, vLayers.Start(), net );
662  JOINT::LINKED_ITEMS links( jt->LinkList() );
663 
664  tag.net = net;
665  tag.pos = p;
666 
667  bool split;
668  do
669  {
670  split = false;
671  std::pair<JOINT_MAP::iterator, JOINT_MAP::iterator> range = m_joints.equal_range( tag );
672 
673  if( range.first == m_joints.end() )
674  break;
675 
676  // find and remove all joints containing the via to be removed
677 
678  for( JOINT_MAP::iterator f = range.first; f != range.second; ++f )
679  {
680  if( aVia->LayersOverlap( &f->second ) )
681  {
682  m_joints.erase( f );
683  split = true;
684  break;
685  }
686  }
687  } while( split );
688 
689  // and re-link them, using the former via's link list
690  for(ITEM* item : links)
691  {
692  if( item != aVia )
693  linkJoint( p, item->Layers(), net, item );
694  }
695 }
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
ITEM_SET::ENTRIES LINKED_ITEMS
Definition: pns_joint.h:46
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:954
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:480
Class LAYER_RANGE.
Definition: pns_layerset.h:32

References FindJoint(), PNS::ITEM::Layers(), PNS::ITEM::LayersOverlap(), linkJoint(), PNS::JOINT::LinkList(), m_joints, PNS::JOINT::HASH_TAG::net, PNS::ITEM::Net(), PNS::JOINT::HASH_TAG::pos, and PNS::VIA::Pos().

Referenced by Remove().

◆ Replace() [1/2]

void PNS::NODE::Replace ( ITEM aOldItem,
std::unique_ptr< ITEM aNewItem 
)

Function Replace()

Just as the name says, replaces an item with another one.

Parameters
aOldItemitem to be removed
aNewItemitem add instead

Definition at line 703 of file pns_node.cpp.

704 {
705  Remove( aOldItem );
706  Add( std::move( aNewItem ) );
707 }
void Remove(SOLID *aSolid)
Function Remove()
Definition: pns_node.cpp:715
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:590

References Add(), and Remove().

Referenced by PNS::SHOVE::replaceItems(), and PNS::SHOVE::replaceLine().

◆ Replace() [2/2]

void PNS::NODE::Replace ( LINE aOldLine,
LINE aNewLine 
)

Definition at line 709 of file pns_node.cpp.

710 {
711  Remove( aOldLine );
712  Add( aNewLine );
713 }
void Remove(SOLID *aSolid)
Function Remove()
Definition: pns_node.cpp:715
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:590

References Add(), and Remove().

◆ SetMaxClearance()

void PNS::NODE::SetMaxClearance ( int  aClearance)
inline

Sets the worst-case clerance between any pair of items

Definition at line 160 of file pns_node.h.

161  {
162  m_maxClearance = aClearance;
163  }
int m_maxClearance
worst case item-item clearance
Definition: pns_node.h:495

References m_maxClearance.

Referenced by PNS_KICAD_IFACE::SyncWorld().

◆ SetRuleResolver()

void PNS::NODE::SetRuleResolver ( RULE_RESOLVER aFunc)
inline

Assigns a clerance resolution function object

Definition at line 166 of file pns_node.h.

167  {
168  m_ruleResolver = aFunc;
169  }
RULE_RESOLVER * m_ruleResolver
Design rules resolver
Definition: pns_node.h:498

References m_ruleResolver.

Referenced by PNS_KICAD_IFACE::SyncWorld().

◆ touchJoint()

JOINT & PNS::NODE::touchJoint ( const VECTOR2I aPos,
const LAYER_RANGE aLayers,
int  aNet 
)
private

tries to find matching joint and creates a new one if not found

Definition at line 991 of file pns_node.cpp.

992 {
993  JOINT::HASH_TAG tag;
994 
995  tag.pos = aPos;
996  tag.net = aNet;
997 
998  // try to find the joint in this node.
999  JOINT_MAP::iterator f = m_joints.find( tag );
1000 
1001  std::pair<JOINT_MAP::iterator, JOINT_MAP::iterator> range;
1002 
1003  // not found and we are not root? find in the root and copy results here.
1004  if( f == m_joints.end() && !isRoot() )
1005  {
1006  range = m_root->m_joints.equal_range( tag );
1007 
1008  for( f = range.first; f != range.second; ++f )
1009  m_joints.insert( *f );
1010  }
1011 
1012  // now insert and combine overlapping joints
1013  JOINT jt( aPos, aLayers, aNet );
1014 
1015  bool merged;
1016 
1017  do
1018  {
1019  merged = false;
1020  range = m_joints.equal_range( tag );
1021 
1022  if( range.first == m_joints.end() )
1023  break;
1024 
1025  for( f = range.first; f != range.second; ++f )
1026  {
1027  if( aLayers.Overlaps( f->second.Layers() ) )
1028  {
1029  jt.Merge( f->second );
1030  m_joints.erase( f );
1031  merged = true;
1032  break;
1033  }
1034  }
1035  }
1036  while( merged );
1037 
1038  return m_joints.insert( TagJointPair( tag, jt ) )->second;
1039 }
bool Overlaps(const LAYER_RANGE &aOther) const
Definition: pns_layerset.h:68
bool isRoot() const
Definition: pns_node.h:459
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:486
JOINT_MAP::value_type TagJointPair
Definition: pns_node.h:427
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:480

References isRoot(), m_joints, m_root, PNS::JOINT::Merge(), PNS::JOINT::HASH_TAG::net, LAYER_RANGE::Overlaps(), and PNS::JOINT::HASH_TAG::pos.

Referenced by linkJoint(), LockJoint(), and unlinkJoint().

◆ unlinkJoint()

void PNS::NODE::unlinkJoint ( const VECTOR2I aPos,
const LAYER_RANGE aLayers,
int  aNet,
ITEM aWhere 
)
private

unlinks an item from a joint

Definition at line 1058 of file pns_node.cpp.

1060 {
1061  // fixme: remove dangling joints
1062  JOINT& jt = touchJoint( aPos, aLayers, aNet );
1063 
1064  jt.Unlink( aWhere );
1065 }
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

References touchJoint(), and PNS::JOINT::Unlink().

Referenced by removeSegmentIndex().

◆ unlinkParent()

void PNS::NODE::unlinkParent ( )
private

Definition at line 138 of file pns_node.cpp.

139 {
140  if( isRoot() )
141  return;
142 
143  m_parent->m_children.erase( this );
144 }
std::set< NODE * > m_children
list of nodes branched from this one
Definition: pns_node.h:489
bool isRoot() const
Definition: pns_node.h:459
NODE * m_parent
node this node was branched from
Definition: pns_node.h:483

References isRoot(), m_children, and m_parent.

Referenced by ~NODE().

Member Data Documentation

◆ m_children

std::set<NODE*> PNS::NODE::m_children
private

list of nodes branched from this one

Definition at line 489 of file pns_node.h.

Referenced by Branch(), HasChildren(), releaseChildren(), unlinkParent(), and ~NODE().

◆ m_depth

int PNS::NODE::m_depth
private

depth of the node (number of parent nodes in the inheritance chain)

Definition at line 504 of file pns_node.h.

Referenced by Branch(), Depth(), and NODE().

◆ m_garbageItems

std::unordered_set<ITEM*> PNS::NODE::m_garbageItems
private

Definition at line 506 of file pns_node.h.

Referenced by doRemove(), and releaseGarbage().

◆ m_index

INDEX* PNS::NODE::m_index
private

◆ m_joints

JOINT_MAP PNS::NODE::m_joints
private

hash table with the joints, linking the items.

Joints are hashed by their position, layer set and net.

Definition at line 480 of file pns_node.h.

Referenced by Branch(), Dump(), FindJoint(), JointCount(), removeViaIndex(), touchJoint(), and ~NODE().

◆ m_maxClearance

int PNS::NODE::m_maxClearance
private

worst case item-item clearance

Definition at line 495 of file pns_node.h.

Referenced by Branch(), GetMaxClearance(), HitTest(), NODE(), QueryColliding(), and SetMaxClearance().

◆ m_override

std::unordered_set<ITEM*> PNS::NODE::m_override
private

hash of root's items that have been changed in this node

Definition at line 492 of file pns_node.h.

Referenced by Branch(), Commit(), doRemove(), GetUpdatedItems(), and Overrides().

◆ m_parent

NODE* PNS::NODE::m_parent
private

node this node was branched from

Definition at line 483 of file pns_node.h.

Referenced by Branch(), isRoot(), NODE(), and unlinkParent().

◆ m_root

NODE* PNS::NODE::m_root
private

root node of the whole hierarchy

Definition at line 486 of file pns_node.h.

Referenced by AllItemsInNet(), Branch(), doRemove(), Dump(), FindJoint(), HitTest(), NODE(), QueryColliding(), and touchJoint().

◆ m_ruleResolver

RULE_RESOLVER* PNS::NODE::m_ruleResolver
private

Design rules resolver

Definition at line 498 of file pns_node.h.

Referenced by Branch(), GetClearance(), GetRuleResolver(), NODE(), and SetRuleResolver().


The documentation for this class was generated from the following files: