KiCad PCB EDA Suite
PNS::NODE Class Reference

Class NODE. More...

#include <pns_node.h>

Classes

struct  DEFAULT_OBSTACLE_VISITOR
 

Public Types

typedef boost::optional< 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 boost::unordered_multimap< JOINT::HASH_TAG, JOINTJOINT_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...
 
boost::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...
 
boost::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 boost::unordered_multimap<JOINT::HASH_TAG, JOINT> PNS::NODE::JOINT_MAP
private

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

Constructor & Destructor Documentation

PNS::NODE::NODE ( )

Definition at line 50 of file pns_node.cpp.

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

Referenced by Branch().

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

Definition at line 66 of file pns_node.cpp.

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

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

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

Definition at line 541 of file pns_node.cpp.

References addSolid().

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

Definition at line 553 of file pns_node.cpp.

References addVia().

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

Definition at line 559 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().

560 {
561  assert( !aLine.IsLinked() );
562 
563  SHAPE_LINE_CHAIN& l = aLine.Line();
564 
565  for( int i = 0; i < l.SegmentCount(); i++ )
566  {
567  SEG s = l.CSegment( i );
568 
569  if( s.A != s.B )
570  {
571  SEGMENT* rseg;
572  if( !aAllowRedundant &&
573  (rseg = findRedundantSegment( s.A, s.B, aLine.Layers(), aLine.Net() )) )
574  {
575  // another line could be referencing this segment too :(
576  aLine.LinkSegment( rseg );
577  }
578  else
579  {
580  std::unique_ptr< SEGMENT > newseg( new SEGMENT( aLine, s ) );
581  aLine.LinkSegment( newseg.get() );
582  Add( std::move( newseg ), true );
583  }
584  }
585  }
586 }
VECTOR2I & B
Definition: seg.h:52
VECTOR2I & A
Definition: seg.h:51
SEGMENT * findRedundantSegment(const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, int aNet)
Definition: pns_node.cpp:1298
Definition: seg.h:37
Class SHAPE_LINE_CHAIN.
Struct SEGMENT is a simple container used when filling areas with segments.
Definition: class_zone.h:57
void Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:596
void PNS::NODE::Add ( std::unique_ptr< ITEM aItem,
bool  aAllowRedundant = false 
)
private

Definition at line 611 of file pns_node.cpp.

References Add(), 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 }
void Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:596
void PNS::NODE::addSegment ( SEGMENT aSeg)
private

Definition at line 588 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().

589 {
590  linkJoint( aSeg->Seg().A, aSeg->Layers(), aSeg->Net(), aSeg );
591  linkJoint( aSeg->Seg().B, aSeg->Layers(), aSeg->Net(), aSeg );
592 
593  m_index->Add( aSeg );
594 }
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:499
void Add(ITEM *aItem)
Function Add()
Definition: pns_index.h:210
void PNS::NODE::addSolid ( SOLID aSeg)
private

helpers for adding/removing items

Definition at line 535 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().

536 {
537  linkJoint( aSolid->Pos(), aSolid->Layers(), aSolid->Net(), aSolid );
538  m_index->Add( aSolid );
539 }
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:499
void Add(ITEM *aItem)
Function Add()
Definition: pns_index.h:210
void PNS::NODE::addVia ( VIA aVia)
private

Definition at line 547 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().

548 {
549  linkJoint( aVia->Pos(), aVia->Layers(), aVia->Net(), aVia );
550  m_index->Add( aVia );
551 }
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:499
void Add(ITEM *aItem)
Function Add()
Definition: pns_index.h:210
void PNS::NODE::AllItemsInNet ( int  aNet,
std::set< ITEM * > &  aItems 
)

Definition at line 1234 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().

1235 {
1236  INDEX::NET_ITEMS_LIST* l_cur = m_index->GetItemsForNet( aNet );
1237 
1238  if( l_cur )
1239  {
1240  for( ITEM*item : *l_cur )
1241  aItems.insert( item );
1242  }
1243 
1244  if( !isRoot() )
1245  {
1246  INDEX::NET_ITEMS_LIST* l_root = m_root->m_index->GetItemsForNet( aNet );
1247 
1248  if( l_root )
1249  for( INDEX::NET_ITEMS_LIST::iterator i = l_root->begin(); i!= l_root->end(); ++i )
1250  if( !Overrides( *i ) )
1251  aItems.insert( *i );
1252  }
1253 }
std::list< ITEM * > NET_ITEMS_LIST
Definition: pns_index.h:48
bool Overrides(ITEM *aItem) const
checks if this branch contains an updated version of the m_item from the root branch.
Definition: pns_node.h:417
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:499
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:484
bool isRoot() const
Definition: pns_node.h:457
NET_ITEMS_LIST * GetItemsForNet(int aNet)
Function GetItemsForNet()
Definition: pns_index.h:319
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(), 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().

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
Struct SEGMENT is a simple container used when filling areas with segments.
Definition: class_zone.h:57
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 109 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().

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

428 {
429  OBSTACLES obs;
430 
431  obs.reserve( 100 );
432 
433  if( aItemA->Kind() == ITEM::LINE_T )
434  {
435  int n = 0;
436  const LINE* line = static_cast<const LINE*>( aItemA );
437  const SHAPE_LINE_CHAIN& l = line->CLine();
438 
439  for( int i = 0; i < l.SegmentCount(); i++ )
440  {
441  const SEGMENT s( *line, l.CSegment( i ) );
442  n += QueryColliding( &s, obs, aKindMask, 1 );
443 
444  if( n )
445  return OPT_OBSTACLE( obs[0] );
446  }
447 
448  if( line->EndsWithVia() )
449  {
450  n += QueryColliding( &line->Via(), obs, aKindMask, 1 );
451 
452  if( n )
453  return OPT_OBSTACLE( obs[0] );
454  }
455  }
456  else if( QueryColliding( aItemA, obs, aKindMask, 1 ) > 0 )
457  return OPT_OBSTACLE( obs[0] );
458 
459  return OPT_OBSTACLE();
460 }
boost::optional< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:140
const SEG CSegment(int aIndex) const
Function CSegment()
Class SHAPE_LINE_CHAIN.
Struct SEGMENT is a simple container used when filling areas with segments.
Definition: class_zone.h:57
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:278
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 413 of file pns_node.cpp.

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

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

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

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

Definition at line 1256 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().

1257 {
1258  for( INDEX::ITEM_SET::iterator i = m_index->begin(); i != m_index->end(); ++i )
1259  {
1260  (*i)->SetRank( -1 );
1261  (*i)->Mark( (*i)->Marker() & (~aMarkerMask) );
1262  }
1263 }
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:499
ITEM_SET::iterator end()
Definition: pns_index.h:140
ITEM_SET::iterator begin()
Definition: pns_index.h:139
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 Add(), PNS::INDEX::begin(), PNS::INDEX::end(), isRoot(), m_index, m_override, releaseChildren(), releaseGarbage(), and Remove().

1207 {
1208  if( aNode->isRoot() )
1209  return;
1210 
1211  for( ITEM* item : aNode->m_override )
1212  Remove( item );
1213 
1214  for( INDEX::ITEM_SET::iterator i = aNode->m_index->begin();
1215  i != aNode->m_index->end(); ++i )
1216  {
1217  (*i)->SetRank( -1 );
1218  (*i)->Unmark();
1219  Add( std::unique_ptr<ITEM>( *i ) );
1220  }
1221 
1222  releaseChildren();
1223  releaseGarbage();
1224 }
void releaseChildren()
Definition: pns_node.cpp:1178
void releaseGarbage()
Definition: pns_node.cpp:1191
void Remove(SOLID *aSolid)
Function Remove()
Definition: pns_node.cpp:729
void Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:596
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:502
void PNS::NODE::doRemove ( ITEM aItem)
private

Definition at line 637 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().

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:499
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:484
boost::unordered_set< ITEM * > m_override
hash of root's items that have been changed in this node
Definition: pns_node.h:490
bool isRoot() const
Definition: pns_node.h:457
boost::unordered_set< ITEM * > m_garbageItems
Definition: pns_node.h:504
void Remove(ITEM *aItem)
Function Remove()
Definition: pns_index.h:227
void PNS::NODE::Dump ( bool  aLong = false)

Prints the contents and joints structure

Definition at line 1082 of file pns_node.cpp.

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

1083 {
1084 #if 0
1085  boost::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:484
bool isRoot() const
Definition: pns_node.h:457
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
Struct SEGMENT is a simple container used when filling areas with segments.
Definition: class_zone.h:57
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:478
int PNS::NODE::FindByMarker ( int  aMarker,
ITEM_SET aItems 
)

Definition at line 1266 of file pns_node.cpp.

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

1267 {
1268  for( INDEX::ITEM_SET::iterator i = m_index->begin(); i != m_index->end(); ++i )
1269  {
1270  if( (*i)->Marker() & aMarker )
1271  aItems.Add( *i );
1272  }
1273 
1274  return 0;
1275 }
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:499
ITEM_SET::iterator end()
Definition: pns_index.h:140
ITEM_SET::iterator begin()
Definition: pns_index.h:139
ITEM * PNS::NODE::FindItemByParent ( const BOARD_CONNECTED_ITEM aParent)

Definition at line 1330 of file pns_node.cpp.

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

Referenced by ROUTER_TOOL::InlineDrag().

1331 {
1332  INDEX::NET_ITEMS_LIST* l_cur = m_index->GetItemsForNet( aParent->GetNetCode() );
1333 
1334  for( ITEM*item : *l_cur )
1335  if( item->Parent() == aParent )
1336  return item;
1337 
1338  return NULL;
1339 }
std::list< ITEM * > NET_ITEMS_LIST
Definition: pns_index.h:48
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:499
NET_ITEMS_LIST * GetItemsForNet(int aNet)
Function GetItemsForNet()
Definition: pns_index.h:319
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 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().

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:484
bool isRoot() const
Definition: pns_node.h:457
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:478
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 377 of file pns_node.h.

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

378  {
379  return FindJoint( aPos, aItem->Layers().Start(), aItem->Net() );
380  }
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 PNS::LINE::CPoint(), and FindJoint().

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

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
Struct SEGMENT is a simple container used when filling areas with segments.
Definition: class_zone.h:57
SEGMENT * PNS::NODE::findRedundantSegment ( const VECTOR2I A,
const VECTOR2I B,
const LAYER_RANGE lr,
int  aNet 
)
private

Definition at line 1298 of file pns_node.cpp.

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

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

Definition at line 1324 of file pns_node.cpp.

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

1325 {
1326  return findRedundantSegment( aSeg->Seg().A, aSeg->Seg().B, aSeg->Layers(), aSeg->Net() );
1327 }
SEGMENT * findRedundantSegment(const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, int aNet)
Definition: pns_node.cpp:1298
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, FindJoint(), PNS::JOINT::IsLineCorner(), PNS::JOINT::IsLocked(), PNS::JOINT::NextSegment(), PNS::JOINT::Pos(), and PNS::SEGMENT::Seg().

Referenced by AssembleLine().

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

101 {
102  if( !m_ruleResolver )
103  return 100000;
104 
105  return m_ruleResolver->Clearance( aA, aB );
106 }
RULE_RESOLVER * m_ruleResolver
Design rules resolver
Definition: pns_node.h:496
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:493
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:496
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 PNS::INDEX::begin(), PNS::INDEX::end(), isRoot(), m_index, m_override, and PNS::INDEX::Size().

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:137
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:499
boost::unordered_set< ITEM * > m_override
hash of root's items that have been changed in this node
Definition: pns_node.h:490
bool isRoot() const
Definition: pns_node.h:457
ITEM_SET::iterator end()
Definition: pns_index.h:140
ITEM_SET::iterator begin()
Definition: pns_index.h:139
bool PNS::NODE::HasChildren ( ) const
inline

Definition at line 410 of file pns_node.h.

References m_children.

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

507 {
508  ITEM_SET items;
509 
510  // fixme: we treat a point as an infinitely small circle - this is inefficient.
511  SHAPE_CIRCLE s( aPoint, 0 );
512  HIT_VISITOR visitor( items, aPoint );
513  visitor.SetWorld( this, NULL );
514 
515  m_index->Query( &s, m_maxClearance, visitor );
516 
517  if( !isRoot() ) // fixme: could be made cleaner
518  {
519  ITEM_SET items_root;
520  visitor.SetWorld( m_root, NULL );
521  HIT_VISITOR visitor_root( items_root, aPoint );
522  m_root->m_index->Query( &s, m_maxClearance, visitor_root );
523 
524  for( ITEM* item : items_root.Items() )
525  {
526  if( !Overrides( item ) )
527  items.Add( item );
528  }
529  }
530 
531  return items;
532 }
bool Overrides(ITEM *aItem) const
checks if this branch contains an updated version of the m_item from the root branch.
Definition: pns_node.h:417
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:499
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:484
bool isRoot() const
Definition: pns_node.h:457
int Query(const ITEM *aItem, int aMinDistance, Visitor &aVisitor)
Function Query()
Definition: pns_index.h:258
int m_maxClearance
worst case item-item clearance
Definition: pns_node.h:493
bool PNS::NODE::isRoot ( ) const
inlineprivate

Definition at line 457 of file pns_node.h.

References m_parent.

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

458  {
459  return m_parent == NULL;
460  }
NODE * m_parent
node this node was branched from
Definition: pns_node.h:481
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:478
void PNS::NODE::KillChildren ( )

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

Definition at line 1227 of file pns_node.cpp.

References isRoot(), and releaseChildren().

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

1228 {
1229  assert( isRoot() );
1230  releaseChildren();
1231 }
void releaseChildren()
Definition: pns_node.cpp:1178
bool isRoot() const
Definition: pns_node.h:457
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(), and touchJoint().

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

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(), PNS::ITEM::Net(), and touchJoint().

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:226
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 304 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().

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

References m_override.

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

418  {
419  return m_override.find( aItem ) != m_override.end();
420  }
boost::unordered_set< ITEM * > m_override
hash of root's items that have been changed in this node
Definition: pns_node.h:490
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 278 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().

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

Definition at line 262 of file pns_node.cpp.

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

263 {
264  aVisitor.SetWorld( this, NULL );
265  m_index->Query( aItem, m_maxClearance, aVisitor );
266 
267  // if we haven't found enough items, look in the root branch as well.
268  if( !isRoot() )
269  {
270  aVisitor.SetWorld( m_root, this );
271  m_root->m_index->Query( aItem, m_maxClearance, aVisitor );
272  }
273 
274  return 0;
275 }
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:499
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:484
bool isRoot() const
Definition: pns_node.h:457
int Query(const ITEM *aItem, int aMinDistance, Visitor &aVisitor)
Function Query()
Definition: pns_index.h:258
int m_maxClearance
worst case item-item clearance
Definition: pns_node.h:493
void PNS::NODE::releaseChildren ( )
private

Definition at line 1178 of file pns_node.cpp.

References m_children.

Referenced by Commit(), and KillChildren().

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:487
void PNS::NODE::releaseGarbage ( )
private

Definition at line 1191 of file pns_node.cpp.

References isRoot(), and m_garbageItems.

Referenced by Commit(), and ~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:457
boost::unordered_set< ITEM * > m_garbageItems
Definition: pns_node.h:504
void PNS::NODE::Remove ( VIA aVia)

Definition at line 735 of file pns_node.cpp.

References doRemove(), and removeViaIndex().

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.

References doRemove(), and removeSegmentIndex().

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, Remove(), 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
aItemitem to remove

Definition at line 779 of file pns_node.cpp.

References PNS::LINE::ClearSegmentLinks(), PNS::LINE::LinkedSegments(), Remove(), 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
Struct SEGMENT is a simple container used when filling areas with segments.
Definition: class_zone.h:57
int PNS::NODE::RemoveByMarker ( int  aMarker)

Definition at line 1278 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().

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

Referenced by Remove().

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.

Referenced by Remove().

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

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:47
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:478
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.

References Add(), and Remove().

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
void Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:596
void PNS::NODE::Replace ( LINE aOldLine,
LINE aNewLine 
)

Definition at line 723 of file pns_node.cpp.

References Add(), and Remove().

724 {
725  Remove( aOldLine );
726  Add( aNewLine );
727 }
void Remove(SOLID *aSolid)
Function Remove()
Definition: pns_node.cpp:729
void Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:596
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:493
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:496
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 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().

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:484
bool isRoot() const
Definition: pns_node.h:457
bool Overlaps(const LAYER_RANGE &aOther) const
Definition: pns_layerset.h:68
JOINT_MAP::value_type TagJointPair
Definition: pns_node.h:425
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:478
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 touchJoint(), and PNS::JOINT::Unlink().

Referenced by removeSegmentIndex().

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

References isRoot(), m_children, and m_parent.

Referenced by ~NODE().

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

Member Data Documentation

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

list of nodes branched from this one

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

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

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

Definition at line 504 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 478 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 493 of file pns_node.h.

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

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

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

Definition at line 490 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 481 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 484 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 496 of file pns_node.h.

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


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