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 ()
 
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)
 
int FindByMarker (int aMarker, ITEM_SET &aItems)
 
int 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 136 of file pns_node.h.

Member Typedef Documentation

◆ ITEM_VECTOR

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

Definition at line 140 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 422 of file pns_node.h.

◆ OBSTACLES

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

Definition at line 141 of file pns_node.h.

◆ OPT_OBSTACLE

Definition at line 139 of file pns_node.h.

◆ TagJointPair

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

Definition at line 424 of file pns_node.h.

Constructor & Destructor Documentation

◆ NODE() [1/2]

PNS::NODE::NODE ( )

Definition at line 48 of file pns_node.cpp.

49 {
50  wxLogTrace( "PNS", "NODE::create %p", this );
51  m_depth = 0;
52  m_root = this;
53  m_parent = NULL;
54  m_maxClearance = 800000; // fixme: depends on how thick traces are.
55  m_ruleResolver = NULL;
56  m_index = new INDEX;
57 
58 #ifdef DEBUG
59  allocNodes.insert( this );
60 #endif
61 }
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:498
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:483
int m_depth
depth of the node (number of parent nodes in the inheritance chain)
Definition: pns_node.h:501
RULE_RESOLVER * m_ruleResolver
Design rules resolver
Definition: pns_node.h:495
int m_maxClearance
worst case item-item clearance
Definition: pns_node.h:492
NODE * m_parent
node this node was branched from
Definition: pns_node.h:480

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

Referenced by Branch().

◆ ~NODE()

PNS::NODE::~NODE ( )

Definition at line 64 of file pns_node.cpp.

65 {
66  wxLogTrace( "PNS", "NODE::delete %p", this );
67 
68  if( !m_children.empty() )
69  {
70  wxLogTrace( "PNS", "attempting to free a node that has kids." );
71  assert( false );
72  }
73 
74 #ifdef DEBUG
75  if( allocNodes.find( this ) == allocNodes.end() )
76  {
77  wxLogTrace( "PNS", "attempting to free an already-free'd node." );
78  assert( false );
79  }
80 
81  allocNodes.erase( this );
82 #endif
83 
84  m_joints.clear();
85 
86  for( INDEX::ITEM_SET::iterator i = m_index->begin(); i != m_index->end(); ++i )
87  {
88  if( (*i)->BelongsTo( this ) )
89  delete *i;
90  }
91 
93  unlinkParent();
94 
95  delete m_index;
96 }
std::set< NODE * > m_children
list of nodes branched from this one
Definition: pns_node.h:486
void unlinkParent()
Definition: pns_node.cpp:142
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:498
void releaseGarbage()
Definition: pns_node.cpp:1192
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
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:477

References PNS::INDEX::begin(), PNS::INDEX::end(), i, 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 595 of file pns_node.cpp.

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

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 540 of file pns_node.cpp.

541 {
542  aSolid->SetOwner( this );
543  addSolid( aSolid.release() );
544 }
void addSolid(SOLID *aSeg)
helpers for adding/removing items
Definition: pns_node.cpp:534

References addSolid().

◆ Add() [3/5]

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

Definition at line 552 of file pns_node.cpp.

553 {
554  aVia->SetOwner( this );
555  addVia( aVia.release() );
556 }
void addVia(VIA *aVia)
Definition: pns_node.cpp:546

References addVia().

◆ Add() [4/5]

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

Definition at line 558 of file pns_node.cpp.

559 {
560  assert( !aLine.IsLinked() );
561 
562  SHAPE_LINE_CHAIN& l = aLine.Line();
563 
564  for( int i = 0; i < l.SegmentCount(); i++ )
565  {
566  SEG s = l.CSegment( i );
567 
568  if( s.A != s.B )
569  {
570  SEGMENT* rseg;
571  if( !aAllowRedundant &&
572  (rseg = findRedundantSegment( s.A, s.B, aLine.Layers(), aLine.Net() )) )
573  {
574  // another line could be referencing this segment too :(
575  aLine.LinkSegment( rseg );
576  }
577  else
578  {
579  std::unique_ptr< SEGMENT > newseg( new SEGMENT( aLine, s ) );
580  aLine.LinkSegment( newseg.get() );
581  Add( std::move( newseg ), true );
582  }
583  }
584  }
585 }
SEGMENT * findRedundantSegment(const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, int aNet)
Definition: pns_node.cpp:1298
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:595
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 612 of file pns_node.cpp.

613 {
614  switch( aItem->Kind() )
615  {
616  case ITEM::SOLID_T:
617  Add( ItemCast<SOLID>( std::move( aItem ) ) );
618  break;
619 
620  case ITEM::SEGMENT_T:
621  Add( ItemCast<SEGMENT>( std::move( aItem ) ), aAllowRedundant );
622  break;
623 
624  case ITEM::LINE_T:
625  assert( false );
626  break;
627 
628  case ITEM::VIA_T:
629  Add( ItemCast<VIA>( std::move( aItem ) ) );
630  break;
631 
632  default:
633  assert( false );
634  }
635 }
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:595

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 587 of file pns_node.cpp.

588 {
589  linkJoint( aSeg->Seg().A, aSeg->Layers(), aSeg->Net(), aSeg );
590  linkJoint( aSeg->Seg().B, aSeg->Layers(), aSeg->Net(), aSeg );
591 
592  m_index->Add( aSeg );
593 }
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:1064
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:498
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 534 of file pns_node.cpp.

535 {
536  linkJoint( aSolid->Pos(), aSolid->Layers(), aSolid->Net(), aSolid );
537  m_index->Add( aSolid );
538 }
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:1064
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:498
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 546 of file pns_node.cpp.

547 {
548  linkJoint( aVia->Pos(), aVia->Layers(), aVia->Net(), aVia );
549  m_index->Add( aVia );
550 }
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:1064
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:498
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 1234 of file pns_node.cpp.

1235 {
1236  INDEX::NET_ITEMS_LIST* l_cur = m_index->GetItemsForNet( aNet );
1237 
1238  if( l_cur )
1239  {
1240  for( ITEM*item : *l_cur )
1241  aItems.insert( item );
1242  }
1243 
1244  if( !isRoot() )
1245  {
1246  INDEX::NET_ITEMS_LIST* l_root = m_root->m_index->GetItemsForNet( aNet );
1247 
1248  if( l_root )
1249  for( INDEX::NET_ITEMS_LIST::iterator i = l_root->begin(); i!= l_root->end(); ++i )
1250  if( !Overrides( *i ) )
1251  aItems.insert( *i );
1252  }
1253 }
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:416
bool isRoot() const
Definition: pns_node.h:456
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:498
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:483
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 835 of file pns_node.cpp.

836 {
837  const int MaxVerts = 1024 * 16;
838 
839  VECTOR2I corners[MaxVerts + 1];
840  SEGMENT* segs[MaxVerts + 1];
841 
842  LINE pl;
843  bool guardHit = false;
844 
845  int i_start = MaxVerts / 2, i_end = i_start + 1;
846 
847  pl.SetWidth( aSeg->Width() );
848  pl.SetLayers( aSeg->Layers() );
849  pl.SetNet( aSeg->Net() );
850  pl.SetOwner( this );
851 
852  followLine( aSeg, false, i_start, MaxVerts, corners, segs, guardHit, aStopAtLockedJoints );
853 
854  if( !guardHit )
855  followLine( aSeg, true, i_end, MaxVerts, corners, segs, guardHit, aStopAtLockedJoints );
856 
857  int n = 0;
858 
859  SEGMENT* prev_seg = NULL;
860  bool originSet = false;
861 
862  for( int i = i_start + 1; i < i_end; i++ )
863  {
864  const VECTOR2I& p = corners[i];
865 
866  pl.Line().Append( p );
867 
868  if( segs[i] && prev_seg != segs[i] )
869  {
870  pl.LinkSegment( segs[i] );
871 
872  // latter condition to avoid loops
873  if( segs[i] == aSeg && aOriginSegmentIndex && !originSet )
874  {
875  *aOriginSegmentIndex = n;
876  originSet = true;
877  }
878  n++;
879  }
880 
881  prev_seg = segs[i];
882  }
883 
884  assert( pl.SegmentCount() != 0 );
885 
886  return pl;
887 }
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:795
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::TOPOLOGY::followTrivialPath(), PNS::LINE_PLACER::removeLoops(), PNS::TOPOLOGY::SimplifyLine(), PNS::LINE_PLACER::simplifyNewLine(), PNS::MEANDER_SKEW_PLACER::Start(), PNS::MEANDER_PLACER::Start(), PNS::DRAGGER::startDragSegment(), and PNS::DRAGGER::startDragVia().

◆ 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 107 of file pns_node.cpp.

108 {
109  NODE* child = new NODE;
110 
111  wxLogTrace( "PNS", "NODE::branch %p (parent %p)", child, this );
112 
113  m_children.insert( child );
114 
115  child->m_depth = m_depth + 1;
116  child->m_parent = this;
117  child->m_ruleResolver = m_ruleResolver;
118  child->m_root = isRoot() ? this : m_root;
120 
121  // immmediate offspring of the root branch needs not copy anything.
122  // For the rest, deep-copy joints, overridden item map and pointers
123  // to stored items.
124  if( !isRoot() )
125  {
126  JOINT_MAP::iterator j;
127 
128  for( INDEX::ITEM_SET::iterator i = m_index->begin(); i != m_index->end(); ++i )
129  child->m_index->Add( *i );
130 
131  child->m_joints = m_joints;
132  child->m_override = m_override;
133  }
134 
135  wxLogTrace( "PNS", "%d items, %d joints, %d overrides",
136  child->m_index->Size(), (int) child->m_joints.size(), (int) child->m_override.size() );
137 
138  return child;
139 }
std::set< NODE * > m_children
list of nodes branched from this one
Definition: pns_node.h:486
bool isRoot() const
Definition: pns_node.h:456
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:498
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:483
int m_depth
depth of the node (number of parent nodes in the inheritance chain)
Definition: pns_node.h:501
RULE_RESOLVER * m_ruleResolver
Design rules resolver
Definition: pns_node.h:495
std::unordered_set< ITEM * > m_override
hash of root's items that have been changed in this node
Definition: pns_node.h:489
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
int m_maxClearance
worst case item-item clearance
Definition: pns_node.h:492
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:477

References PNS::INDEX::Add(), PNS::INDEX::begin(), PNS::INDEX::end(), i, 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::DRAGGER::dragShove(), 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 426 of file pns_node.cpp.

427 {
428  OBSTACLES obs;
429 
430  obs.reserve( 100 );
431 
432  if( aItemA->Kind() == ITEM::LINE_T )
433  {
434  int n = 0;
435  const LINE* line = static_cast<const LINE*>( aItemA );
436  const SHAPE_LINE_CHAIN& l = line->CLine();
437 
438  for( int i = 0; i < l.SegmentCount(); i++ )
439  {
440  const SEGMENT s( *line, l.CSegment( i ) );
441  n += QueryColliding( &s, obs, aKindMask, 1 );
442 
443  if( n )
444  return OPT_OBSTACLE( obs[0] );
445  }
446 
447  if( line->EndsWithVia() )
448  {
449  n += QueryColliding( &line->Via(), obs, aKindMask, 1 );
450 
451  if( n )
452  return OPT_OBSTACLE( obs[0] );
453  }
454  }
455  else if( QueryColliding( aItemA, obs, aKindMask, 1 ) > 0 )
456  return OPT_OBSTACLE( obs[0] );
457 
458  return OPT_OBSTACLE();
459 }
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:139
std::vector< OBSTACLE > OBSTACLES
Definition: pns_node.h:141
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

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 412 of file pns_node.cpp.

413 {
414  for( const ITEM* item : aSet.CItems() )
415  {
416  OPT_OBSTACLE obs = CheckColliding( item, aKindMask );
417 
418  if( obs )
419  return obs;
420  }
421 
422  return OPT_OBSTACLE();
423 }
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Function CheckColliding()
Definition: pns_node.cpp:426
OPT< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:139

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 462 of file pns_node.cpp.

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

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 1256 of file pns_node.cpp.

1257 {
1258  for( INDEX::ITEM_SET::iterator i = m_index->begin(); i != m_index->end(); ++i )
1259  {
1260  (*i)->SetRank( -1 );
1261  (*i)->Mark( (*i)->Marker() & (~aMarkerMask) );
1262  }
1263 }
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:498
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 1207 of file pns_node.cpp.

1208  {
1209  if( aNode->isRoot() )
1210  return;
1211 
1212  for( ITEM* item : aNode->m_override )
1213  Remove( item );
1214 
1215  for( auto i : *aNode->m_index )
1216  {
1217  i->SetRank( -1 );
1218  i->Unmark();
1219  Add( std::unique_ptr<ITEM>( i ) );
1220  }
1221 
1222  releaseChildren();
1223  releaseGarbage();
1224  }
void releaseChildren()
Definition: pns_node.cpp:1179
void releaseGarbage()
Definition: pns_node.cpp:1192
void Remove(SOLID *aSolid)
Function Remove()
Definition: pns_node.cpp:730
size_t i
Definition: json11.cpp:597
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:595

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 179 of file pns_node.h.

180  {
181  return m_depth;
182  }
int m_depth
depth of the node (number of parent nodes in the inheritance chain)
Definition: pns_node.h:501

References m_depth.

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

◆ doRemove()

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

Definition at line 638 of file pns_node.cpp.

639 {
640  // case 1: removing an item that is stored in the root node from any branch:
641  // mark it as overridden, but do not remove
642  if( aItem->BelongsTo( m_root ) && !isRoot() )
643  m_override.insert( aItem );
644 
645  // case 2: the item belongs to this branch or a parent, non-root branch,
646  // or the root itself and we are the root: remove from the index
647  else if( !aItem->BelongsTo( m_root ) || isRoot() )
648  m_index->Remove( aItem );
649 
650  // the item belongs to this particular branch: un-reference it
651  if( aItem->BelongsTo( this ) )
652  {
653  aItem->SetOwner( NULL );
654  m_root->m_garbageItems.insert( aItem );
655  }
656 }
bool isRoot() const
Definition: pns_node.h:456
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:498
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:483
std::unordered_set< ITEM * > m_override
hash of root's items that have been changed in this node
Definition: pns_node.h:489
std::unordered_set< ITEM * > m_garbageItems
Definition: pns_node.h:503
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 1083 of file pns_node.cpp.

1084 {
1085 #if 0
1086  std::unordered_set<SEGMENT*> all_segs;
1088 
1089  for( i = m_items.begin(); i != m_items.end(); i++ )
1090  {
1091  if( (*i)->GetKind() == ITEM::SEGMENT_T )
1092  all_segs.insert( static_cast<SEGMENT*>( *i ) );
1093  }
1094 
1095  if( !isRoot() )
1096  {
1097  for( i = m_root->m_items.begin(); i != m_root->m_items.end(); i++ )
1098  {
1099  if( (*i)->GetKind() == ITEM::SEGMENT_T && !overrides( *i ) )
1100  all_segs.insert( static_cast<SEGMENT*>(*i) );
1101  }
1102  }
1103 
1104  JOINT_MAP::iterator j;
1105 
1106  if( aLong )
1107  for( j = m_joints.begin(); j != m_joints.end(); ++j )
1108  {
1109  wxLogTrace( "PNS", "joint : %s, links : %d\n",
1110  j->second.GetPos().Format().c_str(), j->second.LinkCount() );
1111  JOINT::LINKED_ITEMS::const_iterator k;
1112 
1113  for( k = j->second.GetLinkList().begin(); k != j->second.GetLinkList().end(); ++k )
1114  {
1115  const ITEM* m_item = *k;
1116 
1117  switch( m_item->GetKind() )
1118  {
1119  case ITEM::SEGMENT_T:
1120  {
1121  const SEGMENT* seg = static_cast<const SEGMENT*>( m_item );
1122  wxLogTrace( "PNS", " -> seg %s %s\n", seg->GetSeg().A.Format().c_str(),
1123  seg->GetSeg().B.Format().c_str() );
1124  break;
1125  }
1126 
1127  default:
1128  break;
1129  }
1130  }
1131  }
1132 
1133 
1134  int lines_count = 0;
1135 
1136  while( !all_segs.empty() )
1137  {
1138  SEGMENT* s = *all_segs.begin();
1139  LINE* l = AssembleLine( s );
1140 
1141  LINE::LinkedSegments* seg_refs = l->GetLinkedSegments();
1142 
1143  if( aLong )
1144  wxLogTrace( "PNS", "Line: %s, net %d ", l->GetLine().Format().c_str(), l->GetNet() );
1145 
1146  for( std::vector<SEGMENT*>::iterator j = seg_refs->begin(); j != seg_refs->end(); ++j )
1147  {
1148  wxLogTrace( "PNS", "%s ", (*j)->GetSeg().A.Format().c_str() );
1149 
1150  if( j + 1 == seg_refs->end() )
1151  wxLogTrace( "PNS", "%s\n", (*j)->GetSeg().B.Format().c_str() );
1152 
1153  all_segs.erase( *j );
1154  }
1155 
1156  lines_count++;
1157  }
1158 
1159  wxLogTrace( "PNS", "Local joints: %d, lines : %d \n", m_joints.size(), lines_count );
1160 #endif
1161 }
const LINE AssembleLine(SEGMENT *aSeg, int *aOriginSegmentIndex=NULL, bool aStopAtLockedJoints=false)
Function AssembleLine()
Definition: pns_node.cpp:835
bool isRoot() const
Definition: pns_node.h:456
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:483
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:181
size_t i
Definition: json11.cpp:597
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:477

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

◆ FindByMarker()

int PNS::NODE::FindByMarker ( int  aMarker,
ITEM_SET aItems 
)

Definition at line 1266 of file pns_node.cpp.

1267 {
1268  for( INDEX::ITEM_SET::iterator i = m_index->begin(); i != m_index->end(); ++i )
1269  {
1270  if( (*i)->Marker() & aMarker )
1271  aItems.Add( *i );
1272  }
1273 
1274  return 0;
1275 }
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:498
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::ITEM_SET::Add(), PNS::INDEX::begin(), PNS::INDEX::end(), i, and m_index.

◆ FindItemByParent()

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

Definition at line 1330 of file pns_node.cpp.

1331 {
1332  INDEX::NET_ITEMS_LIST* l_cur = m_index->GetItemsForNet( aParent->GetNetCode() );
1333 
1334  for( ITEM*item : *l_cur )
1335  if( item->Parent() == aParent )
1336  return item;
1337 
1338  return NULL;
1339 }
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:498
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 969 of file pns_node.cpp.

970 {
971  JOINT::HASH_TAG tag;
972 
973  tag.net = aNet;
974  tag.pos = aPos;
975 
976  JOINT_MAP::iterator f = m_joints.find( tag ), end = m_joints.end();
977 
978  if( f == end && !isRoot() )
979  {
980  end = m_root->m_joints.end();
981  f = m_root->m_joints.find( tag ); // m_root->FindJoint(aPos, aLayer, aNet);
982  }
983 
984  if( f == end )
985  return NULL;
986 
987  while( f != end )
988  {
989  if( f->second.Layers().Overlaps( aLayer ) )
990  return &f->second;
991 
992  ++f;
993  }
994 
995  return NULL;
996 }
bool isRoot() const
Definition: pns_node.h:456
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:483
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:477

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(), followLine(), PNS::TOPOLOGY::followTrivialPath(), PNS::DIFF_PAIR_PLACER::getDanglingAnchor(), PNS::SHOVE::onCollidingSolid(), PNS::SHOVE::onReverseCollidingVia(), PNS::SHOVE::processHullSet(), PNS::SHOVE::pushVia(), removeViaIndex(), PNS::LINE_PLACER::SplitAdjacentSegments(), and PNS::DRAGGER::startDragVia().

◆ 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 376 of file pns_node.h.

377  {
378  return FindJoint( aPos, aItem->Layers().Start(), aItem->Net() );
379  }
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:969

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 890 of file pns_node.cpp.

891 {
892  aA = *FindJoint( aLine.CPoint( 0 ), &aLine );
893  aB = *FindJoint( aLine.CPoint( -1 ), &aLine );
894 }
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:969

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 935 of file pns_node.cpp.

936 {
937  for( ITEM* item : aA.LinkList() )
938  {
939  if( item->Kind() == ITEM::SEGMENT_T )
940  {
941  SEGMENT* seg = static_cast<SEGMENT*>( item );
942  LINE line = AssembleLine( seg );
943 
944  if( !line.Layers().Overlaps( aB.Layers() ) )
945  continue;
946 
947  JOINT j_start, j_end;
948 
949  FindLineEnds( line, j_start, j_end );
950 
951  int id_start = line.CLine().Find( aA.Pos() );
952  int id_end = line.CLine().Find( aB.Pos() );
953 
954  if( id_end < id_start )
955  std::swap( id_end, id_start );
956 
957  if( id_start >= 0 && id_end >= 0 )
958  {
959  line.ClipVertexRange( id_start, id_end );
960  aLines.push_back( line );
961  }
962  }
963  }
964 
965  return 0;
966 }
const LINE AssembleLine(SEGMENT *aSeg, int *aOriginSegmentIndex=NULL, bool aStopAtLockedJoints=false)
Function AssembleLine()
Definition: pns_node.cpp:835
void FindLineEnds(const LINE &aLine, JOINT &aA, JOINT &aB)
finds the joints corresponding to the ends of line aLine
Definition: pns_node.cpp:890

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 1298 of file pns_node.cpp.

1300 {
1301  JOINT* jtStart = FindJoint( A, lr.Start(), aNet );
1302 
1303  if( !jtStart )
1304  return nullptr;
1305 
1306  for( ITEM* item : jtStart->LinkList() )
1307  {
1308  if( item->OfKind( ITEM::SEGMENT_T ) )
1309  {
1310  SEGMENT* seg2 = (SEGMENT*)item;
1311 
1312  const VECTOR2I a2( seg2->Seg().A );
1313  const VECTOR2I b2( seg2->Seg().B );
1314 
1315  if( seg2->Layers().Start() == lr.Start() &&
1316  ((A == a2 && B == b2) || (A == b2 && B == a2)) )
1317  return seg2;
1318  }
1319  }
1320 
1321  return nullptr;
1322 }
int Start() const
Definition: pns_layerset.h:83
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:969

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 1324 of file pns_node.cpp.

1325 {
1326  return findRedundantSegment( aSeg->Seg().A, aSeg->Seg().B, aSeg->Layers(), aSeg->Net() );
1327 }
SEGMENT * findRedundantSegment(const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, int aNet)
Definition: pns_node.cpp:1298

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 795 of file pns_node.cpp.

798 {
799  bool prevReversed = false;
800 
801  const VECTOR2I guard = aScanDirection ? aCurrent->Seg().B : aCurrent->Seg().A;
802 
803  for( int count = 0 ; ; ++count )
804  {
805  const VECTOR2I p =
806  ( aScanDirection ^ prevReversed ) ? aCurrent->Seg().B : aCurrent->Seg().A;
807  const JOINT* jt = FindJoint( p, aCurrent );
808 
809  assert( jt );
810 
811  aCorners[aPos] = jt->Pos();
812  aSegments[aPos] = aCurrent;
813  aPos += ( aScanDirection ? 1 : -1 );
814 
815  if( count && guard == p)
816  {
817  aSegments[aPos] = NULL;
818  aGuardHit = true;
819  break;
820  }
821 
822  bool locked = aStopAtLockedJoints ? jt->IsLocked() : false;
823 
824  if( locked || !jt->IsLineCorner() || aPos < 0 || aPos == aLimit )
825  break;
826 
827  aCurrent = jt->NextSegment( aCurrent );
828 
829  prevReversed =
830  ( jt->Pos() == ( aScanDirection ? aCurrent->Seg().B : aCurrent->Seg().A ) );
831  }
832 }
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:969

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 98 of file pns_node.cpp.

99 {
100  if( !m_ruleResolver )
101  return 100000;
102 
103  return m_ruleResolver->Clearance( aA, aB );
104 }
RULE_RESOLVER * m_ruleResolver
Design rules resolver
Definition: pns_node.h:495
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 150 of file pns_node.h.

151  {
152  return m_maxClearance;
153  }
int m_maxClearance
worst case item-item clearance
Definition: pns_node.h:492

References m_maxClearance.

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

◆ GetRuleResolver()

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

Definition at line 167 of file pns_node.h.

168  {
169  return m_ruleResolver;
170  }
RULE_RESOLVER * m_ruleResolver
Design rules resolver
Definition: pns_node.h:495

References m_ruleResolver.

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

◆ 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 1164 of file pns_node.cpp.

1165 {
1166  aRemoved.reserve( m_override.size() );
1167  aAdded.reserve( m_index->Size() );
1168 
1169  if( isRoot() )
1170  return;
1171 
1172  for( ITEM* item : m_override )
1173  aRemoved.push_back( item );
1174 
1175  for( INDEX::ITEM_SET::iterator i = m_index->begin(); i != m_index->end(); ++i )
1176  aAdded.push_back( *i );
1177 }
bool isRoot() const
Definition: pns_node.h:456
INDEX * m_index
Geometric/Net index of the items
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:489
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 409 of file pns_node.h.

410  {
411  return !m_children.empty();
412  }
std::set< NODE * > m_children
list of nodes branched from this one
Definition: pns_node.h:486

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 505 of file pns_node.cpp.

506 {
507  ITEM_SET items;
508 
509  // fixme: we treat a point as an infinitely small circle - this is inefficient.
510  SHAPE_CIRCLE s( aPoint, 0 );
511  HIT_VISITOR visitor( items, aPoint );
512  visitor.SetWorld( this, NULL );
513 
514  m_index->Query( &s, m_maxClearance, visitor );
515 
516  if( !isRoot() ) // fixme: could be made cleaner
517  {
518  ITEM_SET items_root;
519  visitor.SetWorld( m_root, NULL );
520  HIT_VISITOR visitor_root( items_root, aPoint );
521  m_root->m_index->Query( &s, m_maxClearance, visitor_root );
522 
523  for( ITEM* item : items_root.Items() )
524  {
525  if( !Overrides( item ) )
526  items.Add( item );
527  }
528  }
529 
530  return items;
531 }
bool Overrides(ITEM *aItem) const
checks if this branch contains an updated version of the m_item from the root branch.
Definition: pns_node.h:416
bool isRoot() const
Definition: pns_node.h:456
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:498
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:483
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:492

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 456 of file pns_node.h.

457  {
458  return m_parent == NULL;
459  }
NODE * m_parent
node this node was branched from
Definition: pns_node.h:480

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 173 of file pns_node.h.

174  {
175  return m_joints.size();
176  }
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:477

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 1227 of file pns_node.cpp.

1228 {
1229  assert( isRoot() );
1230  releaseChildren();
1231 }
void releaseChildren()
Definition: pns_node.cpp:1179
bool isRoot() const
Definition: pns_node.h:456

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 1064 of file pns_node.cpp.

1066 {
1067  JOINT& jt = touchJoint( aPos, aLayers, aNet );
1068 
1069  jt.Link( aWhere );
1070 }
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:1006

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 999 of file pns_node.cpp.

1000 {
1001  JOINT& jt = touchJoint( aPos, aItem->Layers(), aItem->Net() );
1002  jt.Lock( aLock );
1003 }
void Lock(bool aLock=true)
Definition: pns_joint.h:239
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:1006

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 303 of file pns_node.cpp.

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

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 416 of file pns_node.h.

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

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 277 of file pns_node.cpp.

279 {
280  DEFAULT_OBSTACLE_VISITOR visitor( aObstacles, aItem, aKindMask, aDifferentNetsOnly );
281 
282 #ifdef DEBUG
283  assert( allocNodes.find( this ) != allocNodes.end() );
284 #endif
285 
286  visitor.SetCountLimit( aLimitCount );
287  visitor.SetWorld( this, NULL );
288  visitor.m_forceClearance = aForceClearance;
289  // first, look for colliding items in the local index
290  m_index->Query( aItem, m_maxClearance, visitor );
291 
292  // if we haven't found enough items, look in the root branch as well.
293  if( !isRoot() && ( visitor.m_matchCount < aLimitCount || aLimitCount < 0 ) )
294  {
295  visitor.SetWorld( m_root, this );
296  m_root->m_index->Query( aItem, m_maxClearance, visitor );
297  }
298 
299  return aObstacles.size();
300 }
bool isRoot() const
Definition: pns_node.h:456
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:498
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:483
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:492

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 261 of file pns_node.cpp.

262 {
263  aVisitor.SetWorld( this, NULL );
264  m_index->Query( aItem, m_maxClearance, aVisitor );
265 
266  // if we haven't found enough items, look in the root branch as well.
267  if( !isRoot() )
268  {
269  aVisitor.SetWorld( m_root, this );
270  m_root->m_index->Query( aItem, m_maxClearance, aVisitor );
271  }
272 
273  return 0;
274 }
bool isRoot() const
Definition: pns_node.h:456
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:498
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:483
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:492

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 1179 of file pns_node.cpp.

1180 {
1181  // copy the kids as the NODE destructor erases the item from the parent node.
1182  std::set<NODE*> kids = m_children;
1183 
1184  for( NODE* node : kids )
1185  {
1186  node->releaseChildren();
1187  delete node;
1188  }
1189 }
std::set< NODE * > m_children
list of nodes branched from this one
Definition: pns_node.h:486

References m_children.

Referenced by Commit(), and KillChildren().

◆ releaseGarbage()

void PNS::NODE::releaseGarbage ( )
private

Definition at line 1192 of file pns_node.cpp.

1193 {
1194  if( !isRoot() )
1195  return;
1196 
1197  for( ITEM* item : m_garbageItems )
1198  {
1199  if( !item->BelongsTo( this ) )
1200  delete item;
1201  }
1202 
1203  m_garbageItems.clear();
1204 }
bool isRoot() const
Definition: pns_node.h:456
std::unordered_set< ITEM * > m_garbageItems
Definition: pns_node.h:503

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 736 of file pns_node.cpp.

737 {
738  removeViaIndex( aVia );
739  doRemove( aVia );
740 }
void doRemove(ITEM *aItem)
Definition: pns_node.cpp:638
void removeViaIndex(VIA *aVia)
Definition: pns_node.cpp:665

References doRemove(), and removeViaIndex().

◆ Remove() [3/5]

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

Definition at line 742 of file pns_node.cpp.

743 {
744  removeSegmentIndex( aSegment );
745  doRemove( aSegment );
746 }
void doRemove(ITEM *aItem)
Definition: pns_node.cpp:638
void removeSegmentIndex(SEGMENT *aSeg)
Definition: pns_node.cpp:659

References doRemove(), and removeSegmentIndex().

◆ Remove() [4/5]

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

Definition at line 748 of file pns_node.cpp.

749 {
750  switch( aItem->Kind() )
751  {
752  case ITEM::SOLID_T:
753  Remove( static_cast<SOLID*>( aItem ) );
754  break;
755 
756  case ITEM::SEGMENT_T:
757  Remove( static_cast<SEGMENT*>( aItem ) );
758  break;
759 
760  case ITEM::LINE_T:
761  {
762  auto l = static_cast<LINE *> ( aItem );
763 
764  for ( auto s : l->LinkedSegments() )
765  Remove( s );
766 
767  break;
768  }
769 
770  case ITEM::VIA_T:
771  Remove( static_cast<VIA*>( aItem ) );
772  break;
773 
774  default:
775  break;
776  }
777 }
void Remove(SOLID *aSolid)
Function Remove()
Definition: pns_node.cpp:730

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 780 of file pns_node.cpp.

781 {
782  // LINE does not have a seperate remover, as LINEs are never truly a member of the tree
783  std::vector<SEGMENT*>& segRefs = aLine.LinkedSegments();
784 
785  for( SEGMENT* seg : segRefs )
786  {
787  Remove( seg );
788  }
789 
790  aLine.SetOwner( nullptr );
791  aLine.ClearSegmentLinks();
792 }
void Remove(SOLID *aSolid)
Function Remove()
Definition: pns_node.cpp:730

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

◆ RemoveByMarker()

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

Definition at line 1278 of file pns_node.cpp.

1279 {
1280  std::list<ITEM*> garbage;
1281 
1282  for( INDEX::ITEM_SET::iterator i = m_index->begin(); i != m_index->end(); ++i )
1283  {
1284  if( (*i)->Marker() & aMarker )
1285  {
1286  garbage.push_back( *i );
1287  }
1288  }
1289 
1290  for( std::list<ITEM*>::const_iterator i = garbage.begin(), end = garbage.end(); i != end; ++i )
1291  {
1292  Remove( *i );
1293  }
1294 
1295  return 0;
1296 }
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:498
void Remove(SOLID *aSolid)
Function Remove()
Definition: pns_node.cpp:730
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, 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 659 of file pns_node.cpp.

660 {
661  unlinkJoint( aSeg->Seg().A, aSeg->Layers(), aSeg->Net(), aSeg );
662  unlinkJoint( aSeg->Seg().B, aSeg->Layers(), aSeg->Net(), aSeg );
663 }
void unlinkJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
unlinks an item from a joint
Definition: pns_node.cpp:1073

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 712 of file pns_node.cpp.

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

Referenced by Remove().

◆ removeViaIndex()

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

Definition at line 665 of file pns_node.cpp.

666 {
667  // We have to split a single joint (associated with a via, binding together multiple layers)
668  // into multiple independent joints. As I'm a lazy bastard, I simply delete the via and all its links and re-insert them.
669 
670  JOINT::HASH_TAG tag;
671 
672  VECTOR2I p( aVia->Pos() );
673  LAYER_RANGE vLayers( aVia->Layers() );
674  int net = aVia->Net();
675 
676  JOINT* jt = FindJoint( p, vLayers.Start(), net );
677  JOINT::LINKED_ITEMS links( jt->LinkList() );
678 
679  tag.net = net;
680  tag.pos = p;
681 
682  bool split;
683  do
684  {
685  split = false;
686  std::pair<JOINT_MAP::iterator, JOINT_MAP::iterator> range = m_joints.equal_range( tag );
687 
688  if( range.first == m_joints.end() )
689  break;
690 
691  // find and remove all joints containing the via to be removed
692 
693  for( JOINT_MAP::iterator f = range.first; f != range.second; ++f )
694  {
695  if( aVia->LayersOverlap( &f->second ) )
696  {
697  m_joints.erase( f );
698  split = true;
699  break;
700  }
701  }
702  } while( split );
703 
704  // and re-link them, using the former via's link list
705  for(ITEM* item : links)
706  {
707  if( item != aVia )
708  linkJoint( p, item->Layers(), net, item );
709  }
710 }
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:1064
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:969
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:477
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 718 of file pns_node.cpp.

719 {
720  Remove( aOldItem );
721  Add( std::move( aNewItem ) );
722 }
void Remove(SOLID *aSolid)
Function Remove()
Definition: pns_node.cpp:730
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:595

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 724 of file pns_node.cpp.

725 {
726  Remove( aOldLine );
727  Add( aNewLine );
728 }
void Remove(SOLID *aSolid)
Function Remove()
Definition: pns_node.cpp:730
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:595

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 156 of file pns_node.h.

157  {
158  m_maxClearance = aClearance;
159  }
int m_maxClearance
worst case item-item clearance
Definition: pns_node.h:492

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 162 of file pns_node.h.

163  {
164  m_ruleResolver = aFunc;
165  }
RULE_RESOLVER * m_ruleResolver
Design rules resolver
Definition: pns_node.h:495

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 1006 of file pns_node.cpp.

1007 {
1008  JOINT::HASH_TAG tag;
1009 
1010  tag.pos = aPos;
1011  tag.net = aNet;
1012 
1013  // try to find the joint in this node.
1014  JOINT_MAP::iterator f = m_joints.find( tag );
1015 
1016  std::pair<JOINT_MAP::iterator, JOINT_MAP::iterator> range;
1017 
1018  // not found and we are not root? find in the root and copy results here.
1019  if( f == m_joints.end() && !isRoot() )
1020  {
1021  range = m_root->m_joints.equal_range( tag );
1022 
1023  for( f = range.first; f != range.second; ++f )
1024  m_joints.insert( *f );
1025  }
1026 
1027  // now insert and combine overlapping joints
1028  JOINT jt( aPos, aLayers, aNet );
1029 
1030  bool merged;
1031 
1032  do
1033  {
1034  merged = false;
1035  range = m_joints.equal_range( tag );
1036 
1037  if( range.first == m_joints.end() )
1038  break;
1039 
1040  for( f = range.first; f != range.second; ++f )
1041  {
1042  if( aLayers.Overlaps( f->second.Layers() ) )
1043  {
1044  jt.Merge( f->second );
1045  m_joints.erase( f );
1046  merged = true;
1047  break;
1048  }
1049  }
1050  }
1051  while( merged );
1052 
1053  return m_joints.insert( TagJointPair( tag, jt ) )->second;
1054 }
bool Overlaps(const LAYER_RANGE &aOther) const
Definition: pns_layerset.h:68
bool isRoot() const
Definition: pns_node.h:456
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:483
JOINT_MAP::value_type TagJointPair
Definition: pns_node.h:424
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:477

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 1073 of file pns_node.cpp.

1075 {
1076  // fixme: remove dangling joints
1077  JOINT& jt = touchJoint( aPos, aLayers, aNet );
1078 
1079  jt.Unlink( aWhere );
1080 }
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:1006

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

Referenced by removeSegmentIndex().

◆ unlinkParent()

void PNS::NODE::unlinkParent ( )
private

Definition at line 142 of file pns_node.cpp.

143 {
144  if( isRoot() )
145  return;
146 
147  m_parent->m_children.erase( this );
148 }
std::set< NODE * > m_children
list of nodes branched from this one
Definition: pns_node.h:486
bool isRoot() const
Definition: pns_node.h:456
NODE * m_parent
node this node was branched from
Definition: pns_node.h:480

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 486 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 501 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 503 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 477 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 492 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 489 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 480 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 483 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 495 of file pns_node.h.

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


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