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

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

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

Definition at line 139 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(), i, 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:1191
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
PNS::NODE::NODE ( const NODE aB)
private

nodes are not copyable

Member Function Documentation

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

Referenced by 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(), 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().

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 false;
600  }
601 
602  if( !aAllowRedundant && findRedundantSegment( aSegment.get() ) )
603  return false;
604 
605  aSegment->SetOwner( this );
606  addSegment( aSegment.release() );
607 
608  return true;
609 }
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:1297
void PNS::NODE::Add ( std::unique_ptr< SOLID aSolid)

Definition at line 539 of file pns_node.cpp.

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.

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, SEG::B, i, 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:1297
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:594
VECTOR2I B
Definition: seg.h:45
void PNS::NODE::Add ( std::unique_ptr< ITEM aItem,
bool  aAllowRedundant = false 
)
private

Definition at line 611 of file pns_node.cpp.

References PNS::ITEM::LINE_T, PNS::ITEM::SEGMENT_T, PNS::ITEM::SOLID_T, and PNS::ITEM::VIA_T.

612 {
613  switch( aItem->Kind() )
614  {
615  case ITEM::SOLID_T:
616  Add( ItemCast<SOLID>( std::move( aItem ) ) );
617  break;
618 
619  case ITEM::SEGMENT_T:
620  Add( ItemCast<SEGMENT>( std::move( aItem ) ), aAllowRedundant );
621  break;
622 
623  case ITEM::LINE_T:
624  assert( false );
625  break;
626 
627  case ITEM::VIA_T:
628  Add( ItemCast<VIA>( std::move( aItem ) ) );
629  break;
630 
631  default:
632  assert( false );
633  }
634 }
bool 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, SEG::B, PNS::ITEM::Layers(), PNS::ITEM::Net(), and PNS::SEGMENT::Seg().

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:1063
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:498
void Add(ITEM *aItem)
Function Add()
Definition: pns_index.h:214
void PNS::NODE::addSolid ( SOLID aSeg)
private

helpers for adding/removing items

Definition at line 533 of file pns_node.cpp.

References PNS::ITEM::Layers(), PNS::ITEM::Net(), and PNS::SOLID::Pos().

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:1063
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:498
void Add(ITEM *aItem)
Function Add()
Definition: pns_index.h:214
void PNS::NODE::addVia ( VIA aVia)
private

Definition at line 545 of file pns_node.cpp.

References PNS::ITEM::Layers(), PNS::ITEM::Net(), and PNS::VIA::Pos().

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:1063
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:498
void Add(ITEM *aItem)
Function Add()
Definition: pns_index.h:214
void PNS::NODE::AllItemsInNet ( int  aNet,
std::set< ITEM * > &  aItems 
)

Definition at line 1233 of file pns_node.cpp.

References i.

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

1234 {
1235  INDEX::NET_ITEMS_LIST* l_cur = m_index->GetItemsForNet( aNet );
1236 
1237  if( l_cur )
1238  {
1239  for( ITEM*item : *l_cur )
1240  aItems.insert( item );
1241  }
1242 
1243  if( !isRoot() )
1244  {
1245  INDEX::NET_ITEMS_LIST* l_root = m_root->m_index->GetItemsForNet( aNet );
1246 
1247  if( l_root )
1248  for( INDEX::NET_ITEMS_LIST::iterator i = l_root->begin(); i!= l_root->end(); ++i )
1249  if( !Overrides( *i ) )
1250  aItems.insert( *i );
1251  }
1252 }
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:323
size_t i
Definition: json11.cpp:597
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 834 of file pns_node.cpp.

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

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

Referenced by PNS::DIFF_PAIR_PLACER::attemptWalk(), PNS::OPTIMIZER::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.
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: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 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:139
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(), 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 1255 of file pns_node.cpp.

References i.

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

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

References i, isRoot(), m_index, and m_override.

1207  {
1208  if( aNode->isRoot() )
1209  return;
1210 
1211  for( ITEM* item : aNode->m_override )
1212  Remove( item );
1213 
1214  for( auto i : *aNode->m_index )
1215  {
1216  i->SetRank( -1 );
1217  i->Unmark();
1218  Add( std::unique_ptr<ITEM>( i ) );
1219  }
1220 
1221  releaseChildren();
1222  releaseGarbage();
1223  }
void releaseChildren()
Definition: pns_node.cpp:1178
void releaseGarbage()
Definition: pns_node.cpp:1191
void Remove(SOLID *aSolid)
Function Remove()
Definition: pns_node.cpp:729
size_t i
Definition: json11.cpp:597
bool 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 179 of file pns_node.h.

References PNS::ITEM::ANY_T.

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

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
void PNS::NODE::doRemove ( ITEM aItem)
private

Definition at line 637 of file pns_node.cpp.

References PNS::ITEM::BelongsTo(), PNS::OBSTACLE_VISITOR::m_override, Remove(), and PNS::ITEM::SetOwner().

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

Prints the contents and joints structure

Definition at line 1082 of file pns_node.cpp.

References i, PNS::LINE::LinkedSegments(), PNS::OBSTACLE_VISITOR::m_item, and PNS::ITEM::SEGMENT_T.

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

References PNS::ITEM_SET::Add(), and i.

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

Definition at line 1329 of file pns_node.cpp.

References BOARD_CONNECTED_ITEM::GetNetCode().

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

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

References PNS::JOINT::HASH_TAG::net, and PNS::JOINT::HASH_TAG::pos.

Referenced by PNS::LINE_RESTRICTIONS::allowedAngles(), PNS::TOPOLOGY::AssembleTrivialPath(), PNS::TOPOLOGY::ConnectedJoints(), PNS::OPTIMIZER::findPadOrVia(), PNS::TOPOLOGY::followTrivialPath(), PNS::DIFF_PAIR_PLACER::getDanglingAnchor(), PNS::SHOVE::onCollidingSolid(), PNS::SHOVE::onReverseCollidingVia(), PNS::SHOVE::processHullSet(), PNS::SHOVE::pushVia(), PNS::LINE_PLACER::SplitAdjacentSegments(), and PNS::DRAGGER::startDragVia().

969 {
970  JOINT::HASH_TAG tag;
971 
972  tag.net = aNet;
973  tag.pos = aPos;
974 
975  JOINT_MAP::iterator f = m_joints.find( tag ), end = m_joints.end();
976 
977  if( f == end && !isRoot() )
978  {
979  end = m_root->m_joints.end();
980  f = m_root->m_joints.find( tag ); // m_root->FindJoint(aPos, aLayer, aNet);
981  }
982 
983  if( f == end )
984  return NULL;
985 
986  while( f != end )
987  {
988  if( f->second.Layers().Overlaps( aLayer ) )
989  return &f->second;
990 
991  ++f;
992  }
993 
994  return NULL;
995 }
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 PNS::ITEM::ANY_T, PNS::ITEM::Layers(), PNS::MK_HEAD, PNS::MK_VIOLATION, 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:968
void PNS::NODE::FindLineEnds ( const LINE aLine,
JOINT aA,
JOINT aB 
)

finds the joints corresponding to the ends of line aLine

Definition at line 889 of file pns_node.cpp.

References SEG::A, SEG::B, PNS::LINE::CPoint(), PNS::JOINT::LinkList(), next(), PNS::SEGMENT::Seg(), and PNS::ITEM::SEGMENT_T.

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

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

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

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

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

Definition at line 1297 of file pns_node.cpp.

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

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

Definition at line 1323 of file pns_node.cpp.

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

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

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

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

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

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

Definition at line 167 of file pns_node.h.

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

168  {
169  return m_ruleResolver;
170  }
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 1163 of file pns_node.cpp.

References i, and PNS::OBSTACLE_VISITOR::m_override.

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

1164 {
1165  aRemoved.reserve( m_override.size() );
1166  aAdded.reserve( m_index->Size() );
1167 
1168  if( isRoot() )
1169  return;
1170 
1171  for( ITEM* item : m_override )
1172  aRemoved.push_back( item );
1173 
1174  for( INDEX::ITEM_SET::iterator i = m_index->begin(); i != m_index->end(); ++i )
1175  aAdded.push_back( *i );
1176 }
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&#39;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
size_t i
Definition: json11.cpp:597
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
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(), PNS::ITEM_SET::Items(), 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:262
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.

Referenced by Branch(), Commit(), 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 173 of file pns_node.h.

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

174  {
175  return m_joints.size();
176  }
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 1226 of file pns_node.cpp.

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

1227 {
1228  assert( isRoot() );
1229  releaseChildren();
1230 }
void releaseChildren()
Definition: pns_node.cpp:1178
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 1063 of file pns_node.cpp.

References PNS::JOINT::Link().

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

Definition at line 998 of file pns_node.cpp.

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

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

999 {
1000  JOINT& jt = touchJoint( aPos, aItem->Layers(), aItem->Net() );
1001  jt.Lock( aLock );
1002 }
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:1005
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(), 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(), 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: ar_matrix.cpp:320
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.
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: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.

Referenced by PNS::OBSTACLE_VISITOR::visit().

417  {
418  return m_override.find( aItem ) != m_override.end();
419  }
std::unordered_set< ITEM * > m_override
hash of root&#39;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 PNS::NODE::DEFAULT_OBSTACLE_VISITOR::m_forceClearance, PNS::NODE::DEFAULT_OBSTACLE_VISITOR::m_matchCount, PNS::NODE::DEFAULT_OBSTACLE_VISITOR::SetCountLimit(), and PNS::OBSTACLE_VISITOR::SetWorld().

Referenced by PNS::TOPOLOGY::AssembleCluster(), and PNS::ROUTER::markViolations().

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:262
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 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:262
int m_maxClearance
worst case item-item clearance
Definition: pns_node.h:492
void PNS::NODE::releaseChildren ( )
private

Definition at line 1178 of file pns_node.cpp.

1179 {
1180  // copy the kids as the NODE destructor erases the item from the parent node.
1181  std::set<NODE*> kids = m_children;
1182 
1183  for( NODE* node : kids )
1184  {
1185  node->releaseChildren();
1186  delete node;
1187  }
1188 }
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 1191 of file pns_node.cpp.

Referenced by ~NODE().

1192 {
1193  if( !isRoot() )
1194  return;
1195 
1196  for( ITEM* item : m_garbageItems )
1197  {
1198  if( !item->BelongsTo( this ) )
1199  delete item;
1200  }
1201 
1202  m_garbageItems.clear();
1203 }
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 735 of file pns_node.cpp.

736 {
737  removeViaIndex( aVia );
738  doRemove( aVia );
739 }
void doRemove(ITEM *aItem)
Definition: pns_node.cpp:637
void removeViaIndex(VIA *aVia)
Definition: pns_node.cpp:664
void PNS::NODE::Remove ( SEGMENT aSegment)

Definition at line 741 of file pns_node.cpp.

742 {
743  removeSegmentIndex( aSegment );
744  doRemove( aSegment );
745 }
void doRemove(ITEM *aItem)
Definition: pns_node.cpp:637
void removeSegmentIndex(SEGMENT *aSeg)
Definition: pns_node.cpp:658
void PNS::NODE::Remove ( ITEM aItem)

Definition at line 747 of file pns_node.cpp.

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

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

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

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

Definition at line 1277 of file pns_node.cpp.

References i.

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

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

Definition at line 658 of file pns_node.cpp.

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

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

Definition at line 711 of file pns_node.cpp.

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

Definition at line 664 of file pns_node.cpp.

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

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

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

718 {
719  Remove( aOldItem );
720  Add( std::move( aNewItem ) );
721 }
void Remove(SOLID *aSolid)
Function Remove()
Definition: pns_node.cpp:729
bool 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 723 of file pns_node.cpp.

724 {
725  Remove( aOldLine );
726  Add( aNewLine );
727 }
void Remove(SOLID *aSolid)
Function Remove()
Definition: pns_node.cpp:729
bool 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 156 of file pns_node.h.

Referenced by PNS_KICAD_IFACE::SyncWorld().

157  {
158  m_maxClearance = aClearance;
159  }
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 162 of file pns_node.h.

Referenced by PNS_KICAD_IFACE::SyncWorld().

163  {
164  m_ruleResolver = aFunc;
165  }
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 1005 of file pns_node.cpp.

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

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

References PNS::JOINT::Unlink().

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

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

Definition at line 503 of file pns_node.h.

INDEX* PNS::NODE::m_index
private

Geometric/Net index of the items

Definition at line 498 of file pns_node.h.

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

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

int PNS::NODE::m_maxClearance
private

worst case item-item clearance

Definition at line 492 of file pns_node.h.

Referenced by NODE().

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

NODE* PNS::NODE::m_parent
private

node this node was branched from

Definition at line 480 of file pns_node.h.

Referenced by Branch(), 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 Branch(), and NODE().

RULE_RESOLVER* PNS::NODE::m_ruleResolver
private

Design rules resolver

Definition at line 495 of file pns_node.h.

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


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