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

Member Typedef Documentation

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

Definition at line 141 of file pns_node.h.

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.

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

Definition at line 142 of file pns_node.h.

Definition at line 140 of file pns_node.h.

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

Definition at line 424 of file pns_node.h.

Constructor & Destructor Documentation

PNS::NODE::NODE ( )

Definition at line 48 of file pns_node.cpp.

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

Referenced by Branch().

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
PNS::NODE::~NODE ( )

Definition at line 64 of file pns_node.cpp.

References PNS::INDEX::begin(), PNS::INDEX::end(), m_children, m_index, m_joints, releaseGarbage(), and unlinkParent().

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:141
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:498
void releaseGarbage()
Definition: pns_node.cpp:1189
ITEM_SET::iterator end()
Definition: pns_index.h:141
ITEM_SET::iterator begin()
Definition: pns_index.h:140
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:477
PNS::NODE::NODE ( const NODE aB)
private

nodes are not copyable

Member Function Documentation

void 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 at the same coordinates as an existing one)

Definition at line 594 of file pns_node.cpp.

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(), and PNS_KICAD_IFACE::SyncWorld().

595 {
596  if( aSegment->Seg().A == aSegment->Seg().B )
597  {
598  wxLogTrace( "PNS", "attempting to add a segment with same end coordinates, ignoring." );
599  return;
600  }
601 
602  if( !aAllowRedundant && findRedundantSegment( aSegment.get() ) )
603  return;
604 
605  aSegment->SetOwner( this );
606  addSegment( aSegment.release() );
607 }
void addSegment(SEGMENT *aSeg)
Definition: pns_node.cpp:586
SEGMENT * findRedundantSegment(const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, int aNet)
Definition: pns_node.cpp:1296
void PNS::NODE::Add ( std::unique_ptr< SOLID aSolid)

Definition at line 539 of file pns_node.cpp.

References addSolid().

540 {
541  aSolid->SetOwner( this );
542  addSolid( aSolid.release() );
543 }
void addSolid(SOLID *aSeg)
helpers for adding/removing items
Definition: pns_node.cpp:533
void PNS::NODE::Add ( std::unique_ptr< VIA aVia)

Definition at line 551 of file pns_node.cpp.

References addVia().

552 {
553  aVia->SetOwner( this );
554  addVia( aVia.release() );
555 }
void addVia(VIA *aVia)
Definition: pns_node.cpp:545
void PNS::NODE::Add ( LINE aLine,
bool  aAllowRedundant = false 
)

Definition at line 557 of file pns_node.cpp.

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

558 {
559  assert( !aLine.IsLinked() );
560 
561  SHAPE_LINE_CHAIN& l = aLine.Line();
562 
563  for( int i = 0; i < l.SegmentCount(); i++ )
564  {
565  SEG s = l.CSegment( i );
566 
567  if( s.A != s.B )
568  {
569  SEGMENT* rseg;
570  if( !aAllowRedundant &&
571  (rseg = findRedundantSegment( s.A, s.B, aLine.Layers(), aLine.Net() )) )
572  {
573  // another line could be referencing this segment too :(
574  aLine.LinkSegment( rseg );
575  }
576  else
577  {
578  std::unique_ptr< SEGMENT > newseg( new SEGMENT( aLine, s ) );
579  aLine.LinkSegment( newseg.get() );
580  Add( std::move( newseg ), true );
581  }
582  }
583  }
584 }
SEGMENT * findRedundantSegment(const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, int aNet)
Definition: pns_node.cpp:1296
Definition: seg.h:36
Class SHAPE_LINE_CHAIN.
VECTOR2I A
Definition: seg.h:46
void Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:594
VECTOR2I B
Definition: seg.h:47
void PNS::NODE::Add ( std::unique_ptr< ITEM aItem,
bool  aAllowRedundant = false 
)
private

Definition at line 609 of file pns_node.cpp.

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

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

Definition at line 586 of file pns_node.cpp.

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

Referenced by Add().

587 {
588  linkJoint( aSeg->Seg().A, aSeg->Layers(), aSeg->Net(), aSeg );
589  linkJoint( aSeg->Seg().B, aSeg->Layers(), aSeg->Net(), aSeg );
590 
591  m_index->Add( aSeg );
592 }
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:1061
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:498
void Add(ITEM *aItem)
Function Add()
Definition: pns_index.h:212
void PNS::NODE::addSolid ( SOLID aSeg)
private

helpers for adding/removing items

Definition at line 533 of file pns_node.cpp.

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

Referenced by Add().

534 {
535  linkJoint( aSolid->Pos(), aSolid->Layers(), aSolid->Net(), aSolid );
536  m_index->Add( aSolid );
537 }
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:1061
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:498
void Add(ITEM *aItem)
Function Add()
Definition: pns_index.h:212
void PNS::NODE::addVia ( VIA aVia)
private

Definition at line 545 of file pns_node.cpp.

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

Referenced by Add().

546 {
547  linkJoint( aVia->Pos(), aVia->Layers(), aVia->Net(), aVia );
548  m_index->Add( aVia );
549 }
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:1061
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:498
void Add(ITEM *aItem)
Function Add()
Definition: pns_index.h:212
void PNS::NODE::AllItemsInNet ( int  aNet,
std::set< ITEM * > &  aItems 
)

Definition at line 1232 of file pns_node.cpp.

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

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

1233 {
1234  INDEX::NET_ITEMS_LIST* l_cur = m_index->GetItemsForNet( aNet );
1235 
1236  if( l_cur )
1237  {
1238  for( ITEM*item : *l_cur )
1239  aItems.insert( item );
1240  }
1241 
1242  if( !isRoot() )
1243  {
1244  INDEX::NET_ITEMS_LIST* l_root = m_root->m_index->GetItemsForNet( aNet );
1245 
1246  if( l_root )
1247  for( INDEX::NET_ITEMS_LIST::iterator i = l_root->begin(); i!= l_root->end(); ++i )
1248  if( !Overrides( *i ) )
1249  aItems.insert( *i );
1250  }
1251 }
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
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
bool isRoot() const
Definition: pns_node.h:456
NET_ITEMS_LIST * GetItemsForNet(int aNet)
Function GetItemsForNet()
Definition: pns_index.h:321
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 832 of file pns_node.cpp.

References SHAPE_LINE_CHAIN::Append(), followLine(), 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().

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

References PNS::INDEX::Add(), PNS::INDEX::begin(), PNS::INDEX::end(), isRoot(), m_children, m_depth, m_index, m_joints, 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().

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;
119 
120  // immmediate offspring of the root branch needs not copy anything.
121  // For the rest, deep-copy joints, overridden item map and pointers
122  // to stored items.
123  if( !isRoot() )
124  {
125  JOINT_MAP::iterator j;
126 
127  for( INDEX::ITEM_SET::iterator i = m_index->begin(); i != m_index->end(); ++i )
128  child->m_index->Add( *i );
129 
130  child->m_joints = m_joints;
131  child->m_override = m_override;
132  }
133 
134  wxLogTrace( "PNS", "%d items, %d joints, %d overrides",
135  child->m_index->Size(), (int) child->m_joints.size(), (int) child->m_override.size() );
136 
137  return child;
138 }
std::set< NODE * > m_children
list of nodes branched from this one
Definition: pns_node.h:486
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
bool isRoot() const
Definition: pns_node.h:456
ITEM_SET::iterator end()
Definition: pns_index.h:141
ITEM_SET::iterator begin()
Definition: pns_index.h:140
void Add(ITEM *aItem)
Function Add()
Definition: pns_index.h:212
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:477
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 425 of file pns_node.cpp.

References PNS::LINE::CLine(), SHAPE_LINE_CHAIN::CSegment(), PNS::LINE::EndsWithVia(), 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().

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

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

412 {
413  for( const ITEM* item : aSet.CItems() )
414  {
415  OPT_OBSTACLE obs = CheckColliding( item, aKindMask );
416 
417  if( obs )
418  return obs;
419  }
420 
421  return OPT_OBSTACLE();
422 }
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Function CheckColliding()
Definition: pns_node.cpp:425
OPT< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:140
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 461 of file pns_node.cpp.

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

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

Definition at line 1254 of file pns_node.cpp.

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

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

1255 {
1256  for( INDEX::ITEM_SET::iterator i = m_index->begin(); i != m_index->end(); ++i )
1257  {
1258  (*i)->SetRank( -1 );
1259  (*i)->Mark( (*i)->Marker() & (~aMarkerMask) );
1260  }
1261 }
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
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 1204 of file pns_node.cpp.

References Add(), PNS::INDEX::begin(), PNS::INDEX::end(), isRoot(), m_index, m_override, releaseChildren(), releaseGarbage(), and Remove().

1205 {
1206  if( aNode->isRoot() )
1207  return;
1208 
1209  for( ITEM* item : aNode->m_override )
1210  Remove( item );
1211 
1212  for( INDEX::ITEM_SET::iterator i = aNode->m_index->begin();
1213  i != aNode->m_index->end(); ++i )
1214  {
1215  (*i)->SetRank( -1 );
1216  (*i)->Unmark();
1217  Add( std::unique_ptr<ITEM>( *i ) );
1218  }
1219 
1220  releaseChildren();
1221  releaseGarbage();
1222 }
void releaseChildren()
Definition: pns_node.cpp:1176
void releaseGarbage()
Definition: pns_node.cpp:1189
void Remove(SOLID *aSolid)
Function Remove()
Definition: pns_node.cpp:727
void Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:594
int PNS::NODE::Depth ( ) const
inline

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

Definition at line 180 of file pns_node.h.

References m_depth.

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

181  {
182  return m_depth;
183  }
int m_depth
depth of the node (number of parent nodes in the inheritance chain)
Definition: pns_node.h:501
void PNS::NODE::doRemove ( ITEM aItem)
private

Definition at line 635 of file pns_node.cpp.

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

Referenced by Remove().

636 {
637  // case 1: removing an item that is stored in the root node from any branch:
638  // mark it as overridden, but do not remove
639  if( aItem->BelongsTo( m_root ) && !isRoot() )
640  m_override.insert( aItem );
641 
642  // case 2: the item belongs to this branch or a parent, non-root branch,
643  // or the root itself and we are the root: remove from the index
644  else if( !aItem->BelongsTo( m_root ) || isRoot() )
645  m_index->Remove( aItem );
646 
647  // the item belongs to this particular branch: un-reference it
648  if( aItem->BelongsTo( this ) )
649  {
650  aItem->SetOwner( NULL );
651  m_root->m_garbageItems.insert( aItem );
652  }
653 }
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
bool isRoot() const
Definition: pns_node.h:456
std::unordered_set< ITEM * > m_garbageItems
Definition: pns_node.h:503
void Remove(ITEM *aItem)
Function Remove()
Definition: pns_index.h:229
void PNS::NODE::Dump ( bool  aLong = false)

Prints the contents and joints structure

Definition at line 1080 of file pns_node.cpp.

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

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

Definition at line 1264 of file pns_node.cpp.

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

1265 {
1266  for( INDEX::ITEM_SET::iterator i = m_index->begin(); i != m_index->end(); ++i )
1267  {
1268  if( (*i)->Marker() & aMarker )
1269  aItems.Add( *i );
1270  }
1271 
1272  return 0;
1273 }
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
ITEM * PNS::NODE::FindItemByParent ( const BOARD_CONNECTED_ITEM aParent)

Definition at line 1328 of file pns_node.cpp.

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

Referenced by ROUTER_TOOL::InlineDrag().

1329 {
1330  INDEX::NET_ITEMS_LIST* l_cur = m_index->GetItemsForNet( aParent->GetNetCode() );
1331 
1332  for( ITEM*item : *l_cur )
1333  if( item->Parent() == aParent )
1334  return item;
1335 
1336  return NULL;
1337 }
std::list< ITEM * > NET_ITEMS_LIST
Definition: pns_index.h:49
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.h:321
int GetNetCode() const
Function GetNetCode.
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 966 of file pns_node.cpp.

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().

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

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

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:966
void PNS::NODE::FindLineEnds ( const LINE aLine,
JOINT aA,
JOINT aB 
)

finds the joints corresponding to the ends of line aLine

Definition at line 887 of file pns_node.cpp.

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

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

888 {
889  aA = *FindJoint( aLine.CPoint( 0 ), &aLine );
890  aB = *FindJoint( aLine.CPoint( -1 ), &aLine );
891 }
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:966
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 932 of file pns_node.cpp.

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().

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

Definition at line 1296 of file pns_node.cpp.

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().

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

Definition at line 1322 of file pns_node.cpp.

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

1323 {
1324  return findRedundantSegment( aSeg->Seg().A, aSeg->Seg().B, aSeg->Layers(), aSeg->Net() );
1325 }
SEGMENT * findRedundantSegment(const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, int aNet)
Definition: pns_node.cpp:1296
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 792 of file pns_node.cpp.

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().

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

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().

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
int PNS::NODE::GetMaxClearance ( ) const
inline

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

Definition at line 151 of file pns_node.h.

References m_maxClearance.

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

152  {
153  return m_maxClearance;
154  }
int m_maxClearance
worst case item-item clearance
Definition: pns_node.h:492
RULE_RESOLVER* PNS::NODE::GetRuleResolver ( )
inline

Definition at line 168 of file pns_node.h.

References m_ruleResolver.

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

169  {
170  return m_ruleResolver;
171  }
RULE_RESOLVER * m_ruleResolver
Design rules resolver
Definition: pns_node.h:495
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 1161 of file pns_node.cpp.

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

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

1162 {
1163  aRemoved.reserve( m_override.size() );
1164  aAdded.reserve( m_index->Size() );
1165 
1166  if( isRoot() )
1167  return;
1168 
1169  for( ITEM* item : m_override )
1170  aRemoved.push_back( item );
1171 
1172  for( INDEX::ITEM_SET::iterator i = m_index->begin(); i != m_index->end(); ++i )
1173  aAdded.push_back( *i );
1174 }
int Size() const
Function Size()
Definition: pns_index.h:138
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
bool isRoot() const
Definition: pns_node.h:456
ITEM_SET::iterator end()
Definition: pns_index.h:141
ITEM_SET::iterator begin()
Definition: pns_index.h:140
bool PNS::NODE::HasChildren ( ) const
inline

Definition at line 409 of file pns_node.h.

References m_children.

410  {
411  return !m_children.empty();
412  }
std::set< NODE * > m_children
list of nodes branched from this one
Definition: pns_node.h:486
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 504 of file pns_node.cpp.

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().

505 {
506  ITEM_SET items;
507 
508  // fixme: we treat a point as an infinitely small circle - this is inefficient.
509  SHAPE_CIRCLE s( aPoint, 0 );
510  HIT_VISITOR visitor( items, aPoint );
511  visitor.SetWorld( this, NULL );
512 
513  m_index->Query( &s, m_maxClearance, visitor );
514 
515  if( !isRoot() ) // fixme: could be made cleaner
516  {
517  ITEM_SET items_root;
518  visitor.SetWorld( m_root, NULL );
519  HIT_VISITOR visitor_root( items_root, aPoint );
520  m_root->m_index->Query( &s, m_maxClearance, visitor_root );
521 
522  for( ITEM* item : items_root.Items() )
523  {
524  if( !Overrides( item ) )
525  items.Add( item );
526  }
527  }
528 
529  return items;
530 }
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
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
bool isRoot() const
Definition: pns_node.h:456
int Query(const ITEM *aItem, int aMinDistance, Visitor &aVisitor)
Function Query()
Definition: pns_index.h:260
int m_maxClearance
worst case item-item clearance
Definition: pns_node.h:492
bool PNS::NODE::isRoot ( ) const
inlineprivate

Definition at line 456 of file pns_node.h.

References m_parent.

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

457  {
458  return m_parent == NULL;
459  }
NODE * m_parent
node this node was branched from
Definition: pns_node.h:480
int PNS::NODE::JointCount ( ) const
inline

Returns the number of joints

Definition at line 174 of file pns_node.h.

References m_joints.

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

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

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

Definition at line 1225 of file pns_node.cpp.

References isRoot(), and releaseChildren().

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

1226 {
1227  assert( isRoot() );
1228  releaseChildren();
1229 }
void releaseChildren()
Definition: pns_node.cpp:1176
bool isRoot() const
Definition: pns_node.h:456
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 1061 of file pns_node.cpp.

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

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

1063 {
1064  JOINT& jt = touchJoint( aPos, aLayers, aNet );
1065 
1066  jt.Link( aWhere );
1067 }
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:1003
void PNS::NODE::LockJoint ( const VECTOR2I aPos,
const ITEM aItem,
bool  aLock 
)

Definition at line 996 of file pns_node.cpp.

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

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

997 {
998  JOINT& jt = touchJoint( aPos, aItem->Layers(), aItem->Net() );
999  jt.Lock( aLock );
1000 }
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:1003
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 302 of file pns_node.cpp.

References PNS::LINE::CLine(), SHAPE_LINE_CHAIN::CSegment(), dist, PNS::LINE::EndsWithVia(), EuclideanNorm(), GetClearance(), PNS::VIA::Hull(), 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(), PNS::LINE_PLACER::rhMarkObstacles(), and PNS::SHOVE::shoveIteration().

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

References m_override.

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

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

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(), and NearestObstacle().

278 {
279  DEFAULT_OBSTACLE_VISITOR visitor( aObstacles, aItem, aKindMask, aDifferentNetsOnly );
280 
281 #ifdef DEBUG
282  assert( allocNodes.find( this ) != allocNodes.end() );
283 #endif
284 
285  visitor.SetCountLimit( aLimitCount );
286  visitor.SetWorld( this, NULL );
287  visitor.m_forceClearance = aForceClearance;
288  // first, look for colliding items in the local index
289  m_index->Query( aItem, m_maxClearance, visitor );
290 
291  // if we haven't found enough items, look in the root branch as well.
292  if( !isRoot() && ( visitor.m_matchCount < aLimitCount || aLimitCount < 0 ) )
293  {
294  visitor.SetWorld( m_root, this );
295  m_root->m_index->Query( aItem, m_maxClearance, visitor );
296  }
297 
298  return aObstacles.size();
299 }
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
bool isRoot() const
Definition: pns_node.h:456
int Query(const ITEM *aItem, int aMinDistance, Visitor &aVisitor)
Function Query()
Definition: pns_index.h:260
int m_maxClearance
worst case item-item clearance
Definition: pns_node.h:492
int PNS::NODE::QueryColliding ( const ITEM aItem,
OBSTACLE_VISITOR aVisitor 
)

Definition at line 260 of file pns_node.cpp.

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

261 {
262  aVisitor.SetWorld( this, NULL );
263  m_index->Query( aItem, m_maxClearance, aVisitor );
264 
265  // if we haven't found enough items, look in the root branch as well.
266  if( !isRoot() )
267  {
268  aVisitor.SetWorld( m_root, this );
269  m_root->m_index->Query( aItem, m_maxClearance, aVisitor );
270  }
271 
272  return 0;
273 }
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
bool isRoot() const
Definition: pns_node.h:456
int Query(const ITEM *aItem, int aMinDistance, Visitor &aVisitor)
Function Query()
Definition: pns_index.h:260
int m_maxClearance
worst case item-item clearance
Definition: pns_node.h:492
void PNS::NODE::releaseChildren ( )
private

Definition at line 1176 of file pns_node.cpp.

References m_children.

Referenced by Commit(), and KillChildren().

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

Definition at line 1189 of file pns_node.cpp.

References isRoot(), and m_garbageItems.

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

1190 {
1191  if( !isRoot() )
1192  return;
1193 
1194  for( ITEM* item : m_garbageItems )
1195  {
1196  if( !item->BelongsTo( this ) )
1197  delete item;
1198  }
1199 
1200  m_garbageItems.clear();
1201 }
bool isRoot() const
Definition: pns_node.h:456
std::unordered_set< ITEM * > m_garbageItems
Definition: pns_node.h:503
void PNS::NODE::Remove ( VIA aVia)

Definition at line 733 of file pns_node.cpp.

References doRemove(), and removeViaIndex().

734 {
735  removeViaIndex( aVia );
736  doRemove( aVia );
737 }
void doRemove(ITEM *aItem)
Definition: pns_node.cpp:635
void removeViaIndex(VIA *aVia)
Definition: pns_node.cpp:662
void PNS::NODE::Remove ( SEGMENT aSegment)

Definition at line 739 of file pns_node.cpp.

References doRemove(), and removeSegmentIndex().

740 {
741  removeSegmentIndex( aSegment );
742  doRemove( aSegment );
743 }
void doRemove(ITEM *aItem)
Definition: pns_node.cpp:635
void removeSegmentIndex(SEGMENT *aSeg)
Definition: pns_node.cpp:656
void PNS::NODE::Remove ( ITEM aItem)

Definition at line 745 of file pns_node.cpp.

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

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

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

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

Definition at line 1276 of file pns_node.cpp.

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

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

1277 {
1278  std::list<ITEM*> garbage;
1279 
1280  for( INDEX::ITEM_SET::iterator i = m_index->begin(); i != m_index->end(); ++i )
1281  {
1282  if( (*i)->Marker() & aMarker )
1283  {
1284  garbage.push_back( *i );
1285  }
1286  }
1287 
1288  for( std::list<ITEM*>::const_iterator i = garbage.begin(), end = garbage.end(); i != end; ++i )
1289  {
1290  Remove( *i );
1291  }
1292 
1293  return 0;
1294 }
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:498
void Remove(SOLID *aSolid)
Function Remove()
Definition: pns_node.cpp:727
ITEM_SET::iterator end()
Definition: pns_index.h:141
ITEM_SET::iterator begin()
Definition: pns_index.h:140
void PNS::NODE::removeLine ( LINE aLine)
private
void PNS::NODE::removeSegmentIndex ( SEGMENT aSeg)
private

Definition at line 656 of file pns_node.cpp.

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

Referenced by Remove().

657 {
658  unlinkJoint( aSeg->Seg().A, aSeg->Layers(), aSeg->Net(), aSeg );
659  unlinkJoint( aSeg->Seg().B, aSeg->Layers(), aSeg->Net(), aSeg );
660 }
void unlinkJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
unlinks an item from a joint
Definition: pns_node.cpp:1070
void PNS::NODE::removeSolidIndex ( SOLID aSeg)
private

Definition at line 709 of file pns_node.cpp.

Referenced by Remove().

710 {
711  // fixme: this fucks up the joints, but it's only used for marking colliding obstacles for the moment, so we don't care.
712 }
void PNS::NODE::removeViaIndex ( VIA aVia)
private

Definition at line 662 of file pns_node.cpp.

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().

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

References Add(), and Remove().

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

716 {
717  Remove( aOldItem );
718  Add( std::move( aNewItem ) );
719 }
void Remove(SOLID *aSolid)
Function Remove()
Definition: pns_node.cpp:727
void Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:594
void PNS::NODE::Replace ( LINE aOldLine,
LINE aNewLine 
)

Definition at line 721 of file pns_node.cpp.

References Add(), and Remove().

722 {
723  Remove( aOldLine );
724  Add( aNewLine );
725 }
void Remove(SOLID *aSolid)
Function Remove()
Definition: pns_node.cpp:727
void Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:594
void PNS::NODE::SetMaxClearance ( int  aClearance)
inline

Sets the worst-case clerance between any pair of items

Definition at line 157 of file pns_node.h.

References m_maxClearance.

Referenced by PNS_KICAD_IFACE::SyncWorld().

158  {
159  m_maxClearance = aClearance;
160  }
int m_maxClearance
worst case item-item clearance
Definition: pns_node.h:492
void PNS::NODE::SetRuleResolver ( RULE_RESOLVER aFunc)
inline

Assigns a clerance resolution function object

Definition at line 163 of file pns_node.h.

References m_ruleResolver.

Referenced by PNS_KICAD_IFACE::SyncWorld().

164  {
165  m_ruleResolver = aFunc;
166  }
RULE_RESOLVER * m_ruleResolver
Design rules resolver
Definition: pns_node.h:495
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 1003 of file pns_node.cpp.

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().

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

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

Referenced by removeSegmentIndex().

1072 {
1073  // fixme: remove dangling joints
1074  JOINT& jt = touchJoint( aPos, aLayers, aNet );
1075 
1076  jt.Unlink( aWhere );
1077 }
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:1003
void PNS::NODE::unlinkParent ( )
private

Definition at line 141 of file pns_node.cpp.

References isRoot(), m_children, and m_parent.

Referenced by ~NODE().

142 {
143  if( isRoot() )
144  return;
145 
146  m_parent->m_children.erase( this );
147 }
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

Member Data Documentation

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().

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().

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

Definition at line 503 of file pns_node.h.

Referenced by doRemove(), and releaseGarbage().

INDEX* PNS::NODE::m_index
private
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().

int PNS::NODE::m_maxClearance
private

worst case item-item clearance

Definition at line 492 of file pns_node.h.

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

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().

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().

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().

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: