Hi all,
attached are experimental patches for the pns router. The intent is
refactoring how revisions are handled and thereby improving the peak
memory footprint on deep springback stacks considerably. Other
advantages would include a self-contained spatial state without
complicating interrelations between a set of nodes.
I'd be really grateful for anybody testing this, Chris was already to so
kind to give it a run during his last session.
Cheers!
Michael
>From 16f4a4cc0c59a244defa49719de4a64ef9bdd702 Mon Sep 17 00:00:00 2001
From: decimad <michste...@gmail.com>
Date: Wed, 31 Aug 2016 22:44:00 +0200
Subject: [PATCH] Reimplement PNS::NODE revisioning by means of the the class
PNS::REVISION
Many changes, still largely untested, this is no patch to be applied without further testing and fixing
---
pcbnew/router/CMakeLists.txt | 1 +
pcbnew/router/length_tuner_tool.cpp | 4 +-
pcbnew/router/pns_diff_pair_placer.cpp | 98 +++----
pcbnew/router/pns_diff_pair_placer.h | 13 +-
pcbnew/router/pns_dp_meander_placer.cpp | 42 +--
pcbnew/router/pns_dp_meander_placer.h | 14 +-
pcbnew/router/pns_dragger.cpp | 57 ++--
pcbnew/router/pns_dragger.h | 9 +-
pcbnew/router/pns_index.cpp | 133 +++++++++
pcbnew/router/pns_index.h | 117 +-------
pcbnew/router/pns_kicad_iface.cpp | 12 +-
pcbnew/router/pns_kicad_iface.h | 4 +-
pcbnew/router/pns_line.cpp | 8 +-
pcbnew/router/pns_line_placer.cpp | 109 ++++----
pcbnew/router/pns_line_placer.h | 17 +-
pcbnew/router/pns_meander_placer.cpp | 46 ++--
pcbnew/router/pns_meander_placer.h | 12 +-
pcbnew/router/pns_meander_skew_placer.cpp | 11 +-
pcbnew/router/pns_node.cpp | 437 ++++++++++++++----------------
pcbnew/router/pns_node.h | 203 +++++++++-----
pcbnew/router/pns_placement_algo.h | 11 +-
pcbnew/router/pns_revision.cpp | 34 ++-
pcbnew/router/pns_revision.h | 19 +-
pcbnew/router/pns_router.cpp | 60 ++--
pcbnew/router/pns_router.h | 22 +-
pcbnew/router/pns_shove.cpp | 161 ++++++-----
pcbnew/router/pns_shove.h | 7 +-
pcbnew/router/pns_tool_base.cpp | 6 +-
pcbnew/router/pns_topology.cpp | 8 +-
pcbnew/router/router_tool.cpp | 8 +-
30 files changed, 883 insertions(+), 800 deletions(-)
create mode 100644 pcbnew/router/pns_index.cpp
diff --git a/pcbnew/router/CMakeLists.txt b/pcbnew/router/CMakeLists.txt
index 12de287..776476e 100644
--- a/pcbnew/router/CMakeLists.txt
+++ b/pcbnew/router/CMakeLists.txt
@@ -28,6 +28,7 @@ set( PCBNEW_PNS_SRCS
pns_meander_placer_base.cpp
pns_meander_skew_placer.cpp
pns_revision.cpp
+ pns_index.cpp
pns_node.cpp
pns_optimizer.cpp
pns_router.cpp
diff --git a/pcbnew/router/length_tuner_tool.cpp b/pcbnew/router/length_tuner_tool.cpp
index e7cc806..b3ae89c 100644
--- a/pcbnew/router/length_tuner_tool.cpp
+++ b/pcbnew/router/length_tuner_tool.cpp
@@ -196,12 +196,12 @@ void LENGTH_TUNER_TOOL::performTuning()
}
else if( evt->IsClick( BUT_LEFT ) )
{
- if( m_router->FixRoute( evt->Position(), NULL ) )
+ if( m_router->CommitRoute( evt->Position(), NULL ) )
break;
}
else if( evt->IsAction( &ACT_EndTuning ) )
{
- if( m_router->FixRoute( end, NULL ) )
+ if( m_router->CommitRoute( end, NULL ) )
break;
}
else if( evt->IsAction( &ACT_AmplDecrease ) )
diff --git a/pcbnew/router/pns_diff_pair_placer.cpp b/pcbnew/router/pns_diff_pair_placer.cpp
index 7c05ddc..0adc06f 100644
--- a/pcbnew/router/pns_diff_pair_placer.cpp
+++ b/pcbnew/router/pns_diff_pair_placer.cpp
@@ -46,10 +46,8 @@ DIFF_PAIR_PLACER::DIFF_PAIR_PLACER( ROUTER* aRouter ) :
m_netP = 0;
m_netN = 0;
m_iteration = 0;
- m_world = NULL;
- m_shove = NULL;
- m_currentNode = NULL;
- m_lastNode = NULL;
+ m_shove = nullptr;
+ m_node = nullptr;
m_placingVia = false;
m_viaDiameter = 0;
m_viaDrill = 0;
@@ -73,7 +71,7 @@ DIFF_PAIR_PLACER::~DIFF_PAIR_PLACER()
void DIFF_PAIR_PLACER::setWorld( NODE* aWorld )
{
- m_world = aWorld;
+ m_node = aWorld;
}
const VIA DIFF_PAIR_PLACER::makeVia( const VECTOR2I& aP, int aNet )
@@ -112,8 +110,8 @@ bool DIFF_PAIR_PLACER::rhMarkObstacles( const VECTOR2I& aP )
if( !routeHead( aP ) )
return false;
- bool collP = static_cast<bool>( m_currentNode->CheckColliding( &m_currentTrace.PLine() ) );
- bool collN = static_cast<bool>( m_currentNode->CheckColliding( &m_currentTrace.NLine() ) );
+ bool collP = static_cast<bool>( m_node->CheckColliding( &m_currentTrace.PLine() ) );
+ bool collN = static_cast<bool>( m_node->CheckColliding( &m_currentTrace.NLine() ) );
m_fitOk = !( collP || collN ) ;
@@ -148,7 +146,7 @@ bool DIFF_PAIR_PLACER::propagateDpHeadForces ( const VECTOR2I& aP, VECTOR2I& aNe
}
// fixme: I'm too lazy to do it well. Circular approximaton will do for the moment.
- if( virtHead.PushoutForce( m_currentNode, lead, force, solidsOnly, 40 ) )
+ if( virtHead.PushoutForce( m_node, lead, force, solidsOnly, 40 ) )
{
aNewP = aP + force;
return true;
@@ -247,12 +245,12 @@ bool DIFF_PAIR_PLACER::tryWalkDp( NODE* aNode, DIFF_PAIR &aPair, bool aSolidsOnl
for( int attempt = 0; attempt <= 3; attempt++ )
{
DIFF_PAIR p;
- NODE *tmp = m_currentNode->Branch();
+ SCOPED_BRANCH temp_branch( m_node );
bool pfirst = ( attempt & 1 ) ? true : false;
bool wind_cw = ( attempt & 2 ) ? true : false;
- if( attemptWalk( tmp, &aPair, p, pfirst, wind_cw, aSolidsOnly ) )
+ if( attemptWalk( temp_branch.get(), &aPair, p, pfirst, wind_cw, aSolidsOnly ) )
{
// double len = p.TotalLength();
double cl = p.CoupledLength();
@@ -266,13 +264,11 @@ bool DIFF_PAIR_PLACER::tryWalkDp( NODE* aNode, DIFF_PAIR &aPair, bool aSolidsOnl
best = p;
}
}
-
- delete tmp;
}
if( bestScore > 0.0 )
{
- OPTIMIZER optimizer( m_currentNode );
+ OPTIMIZER optimizer( m_node );
aPair.SetShape( best );
optimizer.Optimize( &aPair );
@@ -289,7 +285,7 @@ bool DIFF_PAIR_PLACER::rhWalkOnly( const VECTOR2I& aP )
if( !routeHead ( aP ) )
return false;
- m_fitOk = tryWalkDp( m_currentNode, m_currentTrace, false );
+ m_fitOk = tryWalkDp( m_node, m_currentTrace, false );
return m_fitOk;
}
@@ -315,8 +311,6 @@ bool DIFF_PAIR_PLACER::route( const VECTOR2I& aP )
bool DIFF_PAIR_PLACER::rhShoveOnly( const VECTOR2I& aP )
{
- m_currentNode = m_shove->CurrentNode();
-
bool ok = routeHead( aP );
m_fitOk = false;
@@ -324,7 +318,7 @@ bool DIFF_PAIR_PLACER::rhShoveOnly( const VECTOR2I& aP )
if( !ok )
return false;
- if( !tryWalkDp( m_currentNode, m_currentTrace, true ) )
+ if( !tryWalkDp( m_node, m_currentTrace, true ) )
return false;
LINE pLine( m_currentTrace.PLine() );
@@ -336,14 +330,10 @@ bool DIFF_PAIR_PLACER::rhShoveOnly( const VECTOR2I& aP )
SHOVE::SHOVE_STATUS status = m_shove->ShoveMultiLines( head );
- m_currentNode = m_shove->CurrentNode();
-
if( status == SHOVE::SH_OK )
{
- m_currentNode = m_shove->CurrentNode();
-
- if( !m_currentNode->CheckColliding( &m_currentTrace.PLine() ) &&
- !m_currentNode->CheckColliding( &m_currentTrace.NLine() ) )
+ if( !m_node->CheckColliding( &m_currentTrace.PLine() ) &&
+ !m_node->CheckColliding( &m_currentTrace.NLine() ) )
{
m_fitOk = true;
}
@@ -375,13 +365,10 @@ void DIFF_PAIR_PLACER::FlipPosture()
NODE* DIFF_PAIR_PLACER::CurrentNode( bool aLoopsRemoved ) const
{
- if( m_lastNode )
- return m_lastNode;
-
- return m_currentNode;
+ // fixme, use m_hasPostprocessed
+ return m_node;
}
-
bool DIFF_PAIR_PLACER::SetLayer( int aLayer )
{
if( m_idle )
@@ -475,9 +462,9 @@ bool DIFF_PAIR_PLACER::findDpPrimitivePair( const VECTOR2I& aP, ITEM* aItem, DP_
{
int netP, netN;
- wxLogTrace( "PNS", "world %p\n", m_world );
+ wxLogTrace( "PNS", "world %p\n", m_node );
- bool result = m_world->GetRuleResolver()->DpNetPair( aItem, netP, netN );
+ bool result = m_node->GetRuleResolver()->DpNetPair( aItem, netP, netN );
if( !result )
return false;
@@ -487,7 +474,7 @@ bool DIFF_PAIR_PLACER::findDpPrimitivePair( const VECTOR2I& aP, ITEM* aItem, DP_
wxLogTrace( "PNS", "result %d\n", !!result );
- OPT_VECTOR2I refAnchor = getDanglingAnchor( m_currentNode, aItem );
+ OPT_VECTOR2I refAnchor = getDanglingAnchor( m_node, aItem );
ITEM* primRef = aItem;
wxLogTrace( "PNS", "refAnchor %p\n", aItem );
@@ -497,7 +484,7 @@ bool DIFF_PAIR_PLACER::findDpPrimitivePair( const VECTOR2I& aP, ITEM* aItem, DP_
std::set<ITEM*> coupledItems;
- m_currentNode->AllItemsInNet( coupledNet, coupledItems );
+ m_node->AllItemsInNet( coupledNet, coupledItems );
double bestDist = std::numeric_limits<double>::max();
bool found = false;
@@ -505,7 +492,7 @@ bool DIFF_PAIR_PLACER::findDpPrimitivePair( const VECTOR2I& aP, ITEM* aItem, DP_
{
if( item->Kind() == aItem->Kind() )
{
- OPT_VECTOR2I anchor = getDanglingAnchor( m_currentNode, item );
+ OPT_VECTOR2I anchor = getDanglingAnchor( m_node, item );
if( !anchor )
continue;
@@ -565,7 +552,6 @@ bool DIFF_PAIR_PLACER::Start( const VECTOR2I& aP, ITEM* aStartItem )
}
setWorld( Router()->GetWorld() );
- m_currentNode = m_world;
if( !findDpPrimitivePair( aP, aStartItem, m_start ) )
{
@@ -610,6 +596,11 @@ bool DIFF_PAIR_PLACER::Start( const VECTOR2I& aP, ITEM* aStartItem )
return true;
}
+void DIFF_PAIR_PLACER::Cancel()
+{
+
+}
+
void DIFF_PAIR_PLACER::initPlacement()
{
@@ -618,15 +609,10 @@ void DIFF_PAIR_PLACER::initPlacement()
m_currentEndItem = NULL;
m_startDiagonal = m_initialDiagonal;
- NODE* world = Router()->GetWorld();
-
- world->KillChildren();
- NODE* rootNode = world->Branch();
-
- setWorld( rootNode );
+ setWorld( Router()->GetWorld() );
+ m_node->ClearBranches();
+ m_node->BranchMove();
- m_lastNode = NULL;
- m_currentNode = rootNode;
m_currentMode = Settings().Mode();
if( m_shove )
@@ -636,7 +622,7 @@ void DIFF_PAIR_PLACER::initPlacement()
if( m_currentMode == RM_Shove || m_currentMode == RM_Smart )
{
- m_shove = new SHOVE( m_currentNode, Router() );
+ m_shove = new SHOVE( m_node, Router() );
}
}
@@ -718,18 +704,14 @@ bool DIFF_PAIR_PLACER::Move( const VECTOR2I& aP , ITEM* aEndItem )
m_currentEndItem = aEndItem;
m_fitOk = false;
- delete m_lastNode;
- m_lastNode = NULL;
+ m_postProcessed.Reset();
if( !route( aP ) )
return false;
- NODE* latestNode = m_currentNode;
- m_lastNode = latestNode->Branch();
+ m_postProcessed.Reset( m_node );
- assert( m_lastNode != NULL );
m_currentEnd = aP;
-
updateLeadingRatLine();
return true;
@@ -748,7 +730,7 @@ void DIFF_PAIR_PLACER::UpdateSizes( const SIZES_SETTINGS& aSizes )
}
-bool DIFF_PAIR_PLACER::FixRoute( const VECTOR2I& aP, ITEM* aEndItem )
+bool DIFF_PAIR_PLACER::CommitRoute( const VECTOR2I& aP, ITEM* aEndItem )
{
if( !m_fitOk )
return false;
@@ -760,7 +742,7 @@ bool DIFF_PAIR_PLACER::FixRoute( const VECTOR2I& aP, ITEM* aEndItem )
if( m_currentTrace.CP().SegmentCount() > 1 )
m_initialDiagonal = !DIRECTION_45( m_currentTrace.CP().CSegment( -2 ) ).IsDiagonal();
- TOPOLOGY topo( m_lastNode );
+ TOPOLOGY topo( m_node );
if( !m_snapOnTarget && !m_currentTrace.EndsWithVias() )
{
@@ -778,8 +760,8 @@ bool DIFF_PAIR_PLACER::FixRoute( const VECTOR2I& aP, ITEM* aEndItem )
if( m_currentTrace.EndsWithVias() )
{
- m_lastNode->Add( Clone( m_currentTrace.PLine().Via() ) );
- m_lastNode->Add( Clone( m_currentTrace.NLine().Via() ) );
+ m_node->Add( Clone( m_currentTrace.PLine().Via() ) );
+ m_node->Add( Clone( m_currentTrace.NLine().Via() ) );
m_chainedPlacement = false;
}
else
@@ -790,17 +772,17 @@ bool DIFF_PAIR_PLACER::FixRoute( const VECTOR2I& aP, ITEM* aEndItem )
LINE lineP( m_currentTrace.PLine() );
LINE lineN( m_currentTrace.NLine() );
- m_lastNode->Add( lineP );
- m_lastNode->Add( lineN );
+ m_node->Add( lineP );
+ m_node->Add( lineN );
topo.SimplifyLine( &lineP );
topo.SimplifyLine( &lineN );
m_prevPair = m_currentTrace.EndingPrimitives();
- Router()->CommitRouting( m_lastNode );
+ m_postProcessed.Commit();
+ Router()->CommitRouting();
- m_lastNode = NULL;
m_placingVia = false;
if( m_snapOnTarget )
@@ -826,7 +808,7 @@ void DIFF_PAIR_PLACER::GetModifiedNets( std::vector<int> &aNets ) const
void DIFF_PAIR_PLACER::updateLeadingRatLine()
{
SHAPE_LINE_CHAIN ratLineN, ratLineP;
- TOPOLOGY topo( m_lastNode );
+ TOPOLOGY topo( m_node );
if( topo.LeadingRatLine( &m_currentTrace.PLine(), ratLineP ) )
{
diff --git a/pcbnew/router/pns_diff_pair_placer.h b/pcbnew/router/pns_diff_pair_placer.h
index b84a2e1..9cadb22 100644
--- a/pcbnew/router/pns_diff_pair_placer.h
+++ b/pcbnew/router/pns_diff_pair_placer.h
@@ -66,6 +66,8 @@ public:
*/
bool Start( const VECTOR2I& aP, ITEM* aStartItem );
+ void Cancel() override;
+
/**
* Function Move()
*
@@ -76,7 +78,7 @@ public:
bool Move( const VECTOR2I& aP, ITEM* aEndItem );
/**
- * Function FixRoute()
+ * Function CommitRoute()
*
* Commits the currently routed track to the parent node, taking
* aP as the final end point and aEndItem as the final anchor (if provided).
@@ -84,7 +86,7 @@ public:
* result is violating design rules - in such case, the track is only committed
* if Settings.CanViolateDRC() is on.
*/
- bool FixRoute( const VECTOR2I& aP, ITEM* aEndItem );
+ bool CommitRoute( const VECTOR2I& aP, ITEM* aEndItem );
/**
* Function ToggleVia()
@@ -253,9 +255,6 @@ private:
///> current algorithm iteration
int m_iteration;
- ///> pointer to world to search colliding items
- NODE* m_world;
-
///> current routing start point (end of tail, beginning of head)
VECTOR2I m_p_start;
@@ -263,10 +262,10 @@ private:
SHOVE* m_shove;
///> Current world state
- NODE* m_currentNode;
+ NODE* m_node;
///> Postprocessed world state (including marked collisions & removed loops)
- NODE* m_lastNode;
+ SCOPED_BRANCH m_postProcessed;
SIZES_SETTINGS m_sizes;
diff --git a/pcbnew/router/pns_dp_meander_placer.cpp b/pcbnew/router/pns_dp_meander_placer.cpp
index 589c6d6..6e349bd 100644
--- a/pcbnew/router/pns_dp_meander_placer.cpp
+++ b/pcbnew/router/pns_dp_meander_placer.cpp
@@ -38,8 +38,7 @@ using boost::optional;
DP_MEANDER_PLACER::DP_MEANDER_PLACER( ROUTER* aRouter ) :
MEANDER_PLACER_BASE( aRouter )
{
- m_world = NULL;
- m_currentNode = NULL;
+ m_node = NULL;
// Init temporary variables (do not leave uninitialized members)
m_initialSegment = NULL;
@@ -61,10 +60,7 @@ const LINE DP_MEANDER_PLACER::Trace() const
NODE* DP_MEANDER_PLACER::CurrentNode( bool aLoopsRemoved ) const
{
- if( !m_currentNode )
- return m_world;
-
- return m_currentNode;
+ return m_node;
}
@@ -82,12 +78,13 @@ bool DP_MEANDER_PLACER::Start( const VECTOR2I& aP, ITEM* aStartItem )
p = m_initialSegment->Seg().NearestPoint( aP );
- m_currentNode=NULL;
m_currentStart = p;
- m_world = Router()->GetWorld()->Branch();
+ m_node = Router()->GetWorld();
+ m_node->BranchMove();
+
- TOPOLOGY topo( m_world );
+ TOPOLOGY topo( m_node );
if( !topo.AssembleDiffPair( m_initialSegment, m_originPair ) )
{
@@ -107,14 +104,19 @@ bool DP_MEANDER_PLACER::Start( const VECTOR2I& aP, ITEM* aStartItem )
m_tunedPathP = topo.AssembleTrivialPath( m_originPair.PLine().GetLink( 0 ) );
m_tunedPathN = topo.AssembleTrivialPath( m_originPair.NLine().GetLink( 0 ) );
- m_world->Remove( m_originPair.PLine() );
- m_world->Remove( m_originPair.NLine() );
+ m_node->Remove( m_originPair.PLine() );
+ m_node->Remove( m_originPair.NLine() );
m_currentWidth = m_originPair.Width();
return true;
}
+void DP_MEANDER_PLACER::Cancel()
+{
+ m_processed.Reset();
+}
+
void DP_MEANDER_PLACER::release()
{
@@ -168,10 +170,7 @@ bool DP_MEANDER_PLACER::Move( const VECTOR2I& aP, ITEM* aEndItem )
DIFF_PAIR::COUPLED_SEGMENTS_VEC coupledSegments;
- if( m_currentNode )
- delete m_currentNode;
-
- m_currentNode = m_world->Branch();
+ m_processed.Reset( m_node );
SHAPE_LINE_CHAIN preP, tunedP, postP;
SHAPE_LINE_CHAIN preN, tunedN, postN;
@@ -302,15 +301,16 @@ bool DP_MEANDER_PLACER::Move( const VECTOR2I& aP, ITEM* aEndItem )
}
-bool DP_MEANDER_PLACER::FixRoute( const VECTOR2I& aP, ITEM* aEndItem )
+bool DP_MEANDER_PLACER::CommitRoute( const VECTOR2I& aP, ITEM* aEndItem )
{
LINE lP( m_originPair.PLine(), m_finalShapeP );
LINE lN( m_originPair.NLine(), m_finalShapeN );
- m_currentNode->Add( lP );
- m_currentNode->Add( lN );
+ m_node->Add( lP );
+ m_node->Add( lN );
- Router()->CommitRouting( m_currentNode );
+ m_processed.Commit();
+ Router()->CommitRouting();
return true;
}
@@ -321,10 +321,10 @@ bool DP_MEANDER_PLACER::CheckFit( MEANDER_SHAPE* aShape )
LINE l1( m_originPair.PLine(), aShape->CLine( 0 ) );
LINE l2( m_originPair.NLine(), aShape->CLine( 1 ) );
- if( m_currentNode->CheckColliding( &l1 ) )
+ if( m_node->CheckColliding( &l1 ) )
return false;
- if( m_currentNode->CheckColliding( &l2 ) )
+ if( m_node->CheckColliding( &l2 ) )
return false;
int w = aShape->Width();
diff --git a/pcbnew/router/pns_dp_meander_placer.h b/pcbnew/router/pns_dp_meander_placer.h
index dc21f7b..f756fa4 100644
--- a/pcbnew/router/pns_dp_meander_placer.h
+++ b/pcbnew/router/pns_dp_meander_placer.h
@@ -60,6 +60,9 @@ public:
*/
bool Start( const VECTOR2I& aP, ITEM* aStartItem );
+ /// @copydoc PLACEMENT_ALGO::Cancel()
+ void Cancel() override;
+
/**
* Function Move()
*
@@ -70,7 +73,7 @@ public:
bool Move( const VECTOR2I& aP, ITEM* aEndItem );
/**
- * Function FixRoute()
+ * Function CommitRoute()
*
* Commits the currently routed track to the parent node, taking
* aP as the final end point and aEndItem as the final anchor (if provided).
@@ -78,7 +81,7 @@ public:
* result is violating design rules - in such case, the track is only committed
* if Settings.CanViolateDRC() is on.
*/
- bool FixRoute( const VECTOR2I& aP, ITEM* aEndItem );
+ bool CommitRoute( const VECTOR2I& aP, ITEM* aEndItem );
const LINE Trace() const;
@@ -121,14 +124,13 @@ private:
int origPathLength() const;
- ///> pointer to world to search colliding items
- NODE* m_world;
-
///> current routing start point (end of tail, beginning of head)
VECTOR2I m_currentStart;
///> Current world state
- NODE* m_currentNode;
+ NODE* m_node;
+
+ SCOPED_BRANCH m_processed;
DIFF_PAIR m_originPair;
DIFF_PAIR::COUPLED_SEGMENTS_VEC m_coupledSegments;
diff --git a/pcbnew/router/pns_dragger.cpp b/pcbnew/router/pns_dragger.cpp
index 541bfe1..77849bb 100644
--- a/pcbnew/router/pns_dragger.cpp
+++ b/pcbnew/router/pns_dragger.cpp
@@ -28,8 +28,7 @@ namespace PNS {
DRAGGER::DRAGGER( ROUTER* aRouter ) :
ALGO_BASE( aRouter )
{
- m_world = NULL;
- m_lastNode = NULL;
+ m_node = nullptr;
m_mode = DRAG_SEGMENT;
m_draggedVia = NULL;
m_shove = NULL;
@@ -49,7 +48,7 @@ DRAGGER::~DRAGGER()
void DRAGGER::SetWorld( NODE* aWorld )
{
- m_world = aWorld;
+ m_node = aWorld;
}
@@ -57,7 +56,7 @@ bool DRAGGER::startDragSegment( const VECTOR2D& aP, SEGMENT* aSeg )
{
int w2 = aSeg->Width() / 2;
- m_draggedLine = m_world->AssembleLine( aSeg, &m_draggedSegmentIndex );
+ m_draggedLine = m_node->AssembleLine( aSeg, &m_draggedSegmentIndex );
m_shove->SetInitialLine( m_draggedLine );
m_lastValidDraggedLine = m_draggedLine;
m_lastValidDraggedLine.ClearSegmentLinks();
@@ -82,7 +81,7 @@ bool DRAGGER::startDragVia( const VECTOR2D& aP, VIA* aVia )
m_mode = DRAG_VIA;
VECTOR2I p0( aVia->Pos() );
- JOINT* jt = m_world->FindJoint( p0, aVia->Layers().Start(), aVia->Net() );
+ JOINT* jt = m_node->FindJoint( p0, aVia->Layers().Start(), aVia->Net() );
if( !jt )
return false;
@@ -93,7 +92,7 @@ bool DRAGGER::startDragVia( const VECTOR2D& aP, VIA* aVia )
{
int segIndex;
SEGMENT* seg = ( SEGMENT*) item;
- LINE l = m_world->AssembleLine( seg, &segIndex );
+ LINE l = m_node->AssembleLine( seg, &segIndex );
if( segIndex != 0 )
l.Reverse();
@@ -108,8 +107,7 @@ bool DRAGGER::startDragVia( const VECTOR2D& aP, VIA* aVia )
bool DRAGGER::Start( const VECTOR2I& aP, ITEM* aStartItem )
{
- m_shove = new SHOVE( m_world, Router() );
- m_lastNode = NULL;
+ m_shove = new SHOVE( m_node, Router() );
m_draggedItems.Clear();
m_currentMode = Settings().Mode();
@@ -133,11 +131,7 @@ bool DRAGGER::Start( const VECTOR2I& aP, ITEM* aStartItem )
bool DRAGGER::dragMarkObstacles( const VECTOR2I& aP )
{
- if( m_lastNode )
- {
- delete m_lastNode;
- m_lastNode = NULL;
- }
+ m_processed.Reset();
switch( m_mode )
{
@@ -152,13 +146,13 @@ bool DRAGGER::dragMarkObstacles( const VECTOR2I& aP )
else
dragged.DragCorner( aP, m_draggedSegmentIndex, thresh );
- m_lastNode = m_shove->CurrentNode()->Branch();
+ m_processed.Reset( m_node );
m_lastValidDraggedLine = dragged;
m_lastValidDraggedLine.ClearSegmentLinks();
m_lastValidDraggedLine.Unmark();
- m_lastNode->Add( m_lastValidDraggedLine );
+ m_node->Add( m_lastValidDraggedLine );
m_draggedItems.Clear();
m_draggedItems.Add( m_lastValidDraggedLine );
@@ -167,8 +161,8 @@ bool DRAGGER::dragMarkObstacles( const VECTOR2I& aP )
case DRAG_VIA: // fixme...
{
- m_lastNode = m_shove->CurrentNode()->Branch();
- dumbDragVia( m_initialVia, m_lastNode, aP );
+ m_processed.Reset( m_node );
+ dumbDragVia( m_initialVia, m_node, aP );
break;
}
@@ -177,7 +171,7 @@ bool DRAGGER::dragMarkObstacles( const VECTOR2I& aP )
if( Settings().CanViolateDRC() )
m_dragStatus = true;
else
- m_dragStatus = !m_world->CheckColliding( m_draggedItems );
+ m_dragStatus = !m_node->CheckColliding( m_draggedItems );
return true;
}
@@ -195,8 +189,8 @@ void DRAGGER::dumbDragVia( VIA* aVia, NODE* aNode, const VECTOR2I& aP )
m_draggedItems.Add( m_draggedVia );
- m_lastNode->Remove( aVia );
- m_lastNode->Add( std::move( via_clone ) );
+ m_node->Remove( aVia );
+ m_node->Add( std::move( via_clone ) );
for( ITEM* item : m_origViaConnections.Items() )
{
@@ -210,8 +204,8 @@ void DRAGGER::dumbDragVia( VIA* aVia, NODE* aNode, const VECTOR2I& aP )
m_draggedItems.Add( draggedLine );
- m_lastNode->Remove( origLine );
- m_lastNode->Add( draggedLine );
+ m_node->Remove( origLine );
+ m_node->Add( draggedLine );
}
}
}
@@ -221,11 +215,7 @@ bool DRAGGER::dragShove( const VECTOR2I& aP )
{
bool ok = false;
- if( m_lastNode )
- {
- delete m_lastNode;
- m_lastNode = NULL;
- }
+ m_processed.Reset();
switch( m_mode )
{
@@ -250,14 +240,14 @@ bool DRAGGER::dragShove( const VECTOR2I& aP )
ok = true;
}
- m_lastNode = m_shove->CurrentNode()->Branch();
+ m_processed.Reset( m_node );
if( ok )
m_lastValidDraggedLine = dragged;
m_lastValidDraggedLine.ClearSegmentLinks();
m_lastValidDraggedLine.Unmark();
- m_lastNode->Add( m_lastValidDraggedLine );
+ m_node->Add( m_lastValidDraggedLine );
m_draggedItems.Clear();
m_draggedItems.Add( m_lastValidDraggedLine );
@@ -272,7 +262,7 @@ bool DRAGGER::dragShove( const VECTOR2I& aP )
if( st == SHOVE::SH_OK || st == SHOVE::SH_HEAD_MODIFIED )
ok = true;
- m_lastNode = m_shove->CurrentNode()->Branch();
+ m_processed.Reset( m_node );
if( ok )
{
@@ -291,11 +281,12 @@ bool DRAGGER::dragShove( const VECTOR2I& aP )
}
-bool DRAGGER::FixRoute()
+bool DRAGGER::CommitRoute()
{
if( m_dragStatus )
{
- Router()->CommitRouting( CurrentNode() );
+ m_processed.Commit();
+ Router()->CommitRouting();
return true;
}
@@ -323,7 +314,7 @@ bool DRAGGER::Drag( const VECTOR2I& aP )
NODE* DRAGGER::CurrentNode() const
{
- return m_lastNode;
+ return m_node;
}
diff --git a/pcbnew/router/pns_dragger.h b/pcbnew/router/pns_dragger.h
index 8c87837..5dd3e8d 100644
--- a/pcbnew/router/pns_dragger.h
+++ b/pcbnew/router/pns_dragger.h
@@ -71,13 +71,13 @@ public:
bool Drag( const VECTOR2I& aP );
/**
- * Function FixRoute()
+ * Function CommitRoute()
*
* Checks if the result of current dragging operation is correct
* and eventually commits it to the world.
* @return true, if dragging finished with success.
*/
- bool FixRoute();
+ bool CommitRoute();
/**
* Function CurrentNode()
@@ -110,8 +110,9 @@ private:
bool startDragVia( const VECTOR2D& aP, VIA* aVia );
void dumbDragVia( VIA* aVia, NODE* aNode, const VECTOR2I& aP );
- NODE* m_world;
- NODE* m_lastNode;
+ NODE* m_node;
+ SCOPED_BRANCH m_processed;
+
DragMode m_mode;
LINE m_draggedLine;
VIA* m_draggedVia;
diff --git a/pcbnew/router/pns_index.cpp b/pcbnew/router/pns_index.cpp
new file mode 100644
index 0000000..0c05e9b
--- /dev/null
+++ b/pcbnew/router/pns_index.cpp
@@ -0,0 +1,133 @@
+/*
+* KiRouter - a push-and-(sometimes-)shove PCB router
+*
+* Copyright (C) 2013-2014 CERN
+* Copyright (C) 2016 KiCad Developers, see AUTHORS.txt for contributors.
+* Author: Tomasz Wlostowski <tomasz.wlostow...@cern.ch>
+*
+* This program is free software: you can redistribute it and/or modify it
+* under the terms of the GNU General Public License as published by the
+* Free Software Foundation, either version 3 of the License, or (at your
+* option) any later version.
+*
+* This program is distributed in the hope that it will be useful, but
+* WITHOUT ANY WARRANTY; without even the implied warranty of
+* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+* General Public License for more details.
+*
+* You should have received a copy of the GNU General Public License along
+* with this program. If not, see <http://www.gnu.org/licenses/>.
+*/
+
+#include "pns_index.h"
+
+namespace PNS {
+
+INDEX::INDEX()
+{
+ memset( m_subIndices, 0, sizeof( m_subIndices ) );
+}
+
+INDEX::ITEM_SHAPE_INDEX* INDEX::getSubindex( const ITEM* aItem )
+{
+ int idx_n = -1;
+
+ const LAYER_RANGE l = aItem->Layers();
+
+ switch( aItem->Kind() )
+ {
+ case ITEM::VIA_T:
+ idx_n = SI_Multilayer;
+ break;
+
+ case ITEM::SOLID_T:
+ {
+ if( l.IsMultilayer() )
+ idx_n = SI_Multilayer;
+ else if( l.Start() == B_Cu ) // fixme: use kicad layer codes
+ idx_n = SI_PadsTop;
+ else if( l.Start() == F_Cu )
+ idx_n = SI_PadsBottom;
+ }
+ break;
+
+ case ITEM::SEGMENT_T:
+ case ITEM::LINE_T:
+ idx_n = SI_Traces + 2 * l.Start() + SI_SegStraight;
+ break;
+
+ default:
+ break;
+ }
+
+ assert( idx_n >= 0 && idx_n < MaxSubIndices );
+
+ if( !m_subIndices[idx_n] )
+ m_subIndices[idx_n] = new ITEM_SHAPE_INDEX;
+
+ return m_subIndices[idx_n];
+}
+
+void INDEX::Add( ITEM* aItem )
+{
+ ITEM_SHAPE_INDEX* idx = getSubindex( aItem );
+
+ idx->Add( aItem );
+ m_allItems.insert( aItem );
+ int net = aItem->Net();
+
+ if( net >= 0 )
+ {
+ m_netMap[net].push_back( aItem );
+ }
+}
+
+void INDEX::Remove( ITEM* aItem )
+{
+ ITEM_SHAPE_INDEX* idx = getSubindex( aItem );
+
+ idx->Remove( aItem );
+ m_allItems.erase( aItem );
+
+ int net = aItem->Net();
+
+ if( net >= 0 && m_netMap.find( net ) != m_netMap.end() )
+ m_netMap[net].remove( aItem );
+}
+
+void INDEX::Replace( ITEM* aOldItem, ITEM* aNewItem )
+{
+ Remove( aOldItem );
+ Add( aNewItem );
+}
+
+void INDEX::Clear()
+{
+ for( int i = 0; i < MaxSubIndices; ++i )
+ {
+ ITEM_SHAPE_INDEX* idx = m_subIndices[i];
+
+ if( idx )
+ delete idx;
+
+ m_subIndices[i] = NULL;
+ }
+
+ m_allItems.clear();
+ m_netMap.clear();
+}
+
+INDEX::~INDEX()
+{
+ Clear();
+}
+
+INDEX::NET_ITEMS_LIST* INDEX::GetItemsForNet( int aNet )
+{
+ if( m_netMap.find( aNet ) == m_netMap.end() )
+ return NULL;
+
+ return &m_netMap[aNet];
+}
+
+}
diff --git a/pcbnew/router/pns_index.h b/pcbnew/router/pns_index.h
index a948865..5de6b1e 100644
--- a/pcbnew/router/pns_index.h
+++ b/pcbnew/router/pns_index.h
@@ -29,6 +29,7 @@
#include <list>
#include <geometry/shape_index.h>
+#include <boost/unordered_set.hpp>
#include "pns_item.h"
@@ -87,7 +88,7 @@ public:
* @return number of items found.
*/
template<class Visitor>
- int Query( const ITEM* aItem, int aMinDistance, Visitor& aVisitor );
+ int Query( const ITEM* aItem, int aMinDistance, Visitor& aVisitor ) const;
/**
* Function Query()
@@ -103,7 +104,7 @@ public:
* @return number of items found.
*/
template<class Visitor>
- int Query( const SHAPE* aShape, int aMinDistance, Visitor& aVisitor );
+ int Query( const SHAPE* aShape, int aMinDistance, Visitor& aVisitor ) const;
/**
* Function Clear()
@@ -149,7 +150,7 @@ private:
static const int SI_PadsBottom = 1;
template <class Visitor>
- int querySingle( int index, const SHAPE* aShape, int aMinDistance, Visitor& aVisitor );
+ int querySingle( int index, const SHAPE* aShape, int aMinDistance, Visitor& aVisitor ) const;
ITEM_SHAPE_INDEX* getSubindex( const ITEM* aItem );
@@ -158,86 +159,8 @@ private:
ITEM_SET m_allItems;
};
-INDEX::INDEX()
-{
- memset( m_subIndices, 0, sizeof( m_subIndices ) );
-}
-
-INDEX::ITEM_SHAPE_INDEX* INDEX::getSubindex( const ITEM* aItem )
-{
- int idx_n = -1;
-
- const LAYER_RANGE l = aItem->Layers();
-
- switch( aItem->Kind() )
- {
- case ITEM::VIA_T:
- idx_n = SI_Multilayer;
- break;
-
- case ITEM::SOLID_T:
- {
- if( l.IsMultilayer() )
- idx_n = SI_Multilayer;
- else if( l.Start() == B_Cu ) // fixme: use kicad layer codes
- idx_n = SI_PadsTop;
- else if( l.Start() == F_Cu )
- idx_n = SI_PadsBottom;
- }
- break;
-
- case ITEM::SEGMENT_T:
- case ITEM::LINE_T:
- idx_n = SI_Traces + 2 * l.Start() + SI_SegStraight;
- break;
-
- default:
- break;
- }
-
- assert( idx_n >= 0 && idx_n < MaxSubIndices );
-
- if( !m_subIndices[idx_n] )
- m_subIndices[idx_n] = new ITEM_SHAPE_INDEX;
-
- return m_subIndices[idx_n];
-}
-
-void INDEX::Add( ITEM* aItem )
-{
- ITEM_SHAPE_INDEX* idx = getSubindex( aItem );
-
- idx->Add( aItem );
- m_allItems.insert( aItem );
- int net = aItem->Net();
-
- if( net >= 0 )
- {
- m_netMap[net].push_back( aItem );
- }
-}
-
-void INDEX::Remove( ITEM* aItem )
-{
- ITEM_SHAPE_INDEX* idx = getSubindex( aItem );
-
- idx->Remove( aItem );
- m_allItems.erase( aItem );
-
- int net = aItem->Net();
-
- if( net >= 0 && m_netMap.find( net ) != m_netMap.end() )
- m_netMap[net].remove( aItem );
-}
-
-void INDEX::Replace( ITEM* aOldItem, ITEM* aNewItem )
-{
- Remove( aOldItem );
- Add( aNewItem );
-}
-
template<class Visitor>
-int INDEX::querySingle( int index, const SHAPE* aShape, int aMinDistance, Visitor& aVisitor )
+int INDEX::querySingle( int index, const SHAPE* aShape, int aMinDistance, Visitor& aVisitor ) const
{
if( !m_subIndices[index] )
return 0;
@@ -246,7 +169,7 @@ int INDEX::querySingle( int index, const SHAPE* aShape, int aMinDistance, Visito
}
template<class Visitor>
-int INDEX::Query( const ITEM* aItem, int aMinDistance, Visitor& aVisitor )
+int INDEX::Query( const ITEM* aItem, int aMinDistance, Visitor& aVisitor ) const
{
const SHAPE* shape = aItem->Shape();
int total = 0;
@@ -279,7 +202,7 @@ int INDEX::Query( const ITEM* aItem, int aMinDistance, Visitor& aVisitor )
}
template<class Visitor>
-int INDEX::Query( const SHAPE* aShape, int aMinDistance, Visitor& aVisitor )
+int INDEX::Query( const SHAPE* aShape, int aMinDistance, Visitor& aVisitor ) const
{
int total = 0;
@@ -289,32 +212,6 @@ int INDEX::Query( const SHAPE* aShape, int aMinDistance, Visitor& aVisitor )
return total;
}
-void INDEX::Clear()
-{
- for( int i = 0; i < MaxSubIndices; ++i )
- {
- ITEM_SHAPE_INDEX* idx = m_subIndices[i];
-
- if( idx )
- delete idx;
-
- m_subIndices[i] = NULL;
- }
-}
-
-INDEX::~INDEX()
-{
- Clear();
-}
-
-INDEX::NET_ITEMS_LIST* INDEX::GetItemsForNet( int aNet )
-{
- if( m_netMap.find( aNet ) == m_netMap.end() )
- return NULL;
-
- return &m_netMap[aNet];
-}
-
}
#endif
diff --git a/pcbnew/router/pns_kicad_iface.cpp b/pcbnew/router/pns_kicad_iface.cpp
index 9166707..5b8e34c 100644
--- a/pcbnew/router/pns_kicad_iface.cpp
+++ b/pcbnew/router/pns_kicad_iface.cpp
@@ -154,7 +154,7 @@ int PNS_PCBNEW_RULE_RESOLVER::Clearance( const PNS::ITEM* aA, const PNS::ITEM* a
int net_b = aB->Net();
int cl_b = ( net_b >= 0 ? m_clearanceCache[net_b].clearance : m_defaultClearance );
- bool linesOnly = aA->OfKind( PNS::ITEM::SEGMENT_T | PNS::ITEM::LINE_T )
+ bool linesOnly = aA->OfKind( PNS::ITEM::SEGMENT_T | PNS::ITEM::LINE_T )
&& aB->OfKind( PNS::ITEM::SEGMENT_T | PNS::ITEM::LINE_T );
if( linesOnly && net_a >= 0 && net_b >= 0 && m_clearanceCache[net_a].coupledNet == net_b )
@@ -743,7 +743,7 @@ void PNS_KICAD_IFACE::SyncWorld( PNS::NODE *aWorld )
if( type == PCB_TRACE_T ) {
std::unique_ptr< PNS::SEGMENT > segment = syncTrack( t );
if( segment ) {
- aWorld->Add( std::move( segment ) );
+ aWorld->Add( std::move( segment ) );
}
} else if( type == PCB_VIA_T ) {
std::unique_ptr< PNS::VIA > via = syncVia( static_cast<VIA*>( t ) );
@@ -800,7 +800,7 @@ void PNS_KICAD_IFACE::DisplayItem( const PNS::ITEM* aItem, int aColor, int aClea
}
-void PNS_KICAD_IFACE::HideItem( PNS::ITEM* aItem )
+void PNS_KICAD_IFACE::HideItem( const PNS::ITEM* aItem )
{
BOARD_CONNECTED_ITEM* parent = aItem->Parent();
@@ -815,7 +815,7 @@ void PNS_KICAD_IFACE::HideItem( PNS::ITEM* aItem )
}
-void PNS_KICAD_IFACE::RemoveItem( PNS::ITEM* aItem )
+void PNS_KICAD_IFACE::RemoveItem( const PNS::ITEM* aItem )
{
BOARD_CONNECTED_ITEM* parent = aItem->Parent();
@@ -836,7 +836,7 @@ void PNS_KICAD_IFACE::AddItem( PNS::ITEM* aItem )
{
case PNS::ITEM::SEGMENT_T:
{
- PNS::SEGMENT* seg = static_cast<PNS::SEGMENT*>( aItem );
+ const PNS::SEGMENT* seg = static_cast<const PNS::SEGMENT*>( aItem );
TRACK* track = new TRACK( m_board );
const SEG& s = seg->Seg();
track->SetStart( wxPoint( s.A.x, s.A.y ) );
@@ -851,7 +851,7 @@ void PNS_KICAD_IFACE::AddItem( PNS::ITEM* aItem )
case PNS::ITEM::VIA_T:
{
VIA* via_board = new VIA( m_board );
- PNS::VIA* via = static_cast<PNS::VIA*>( aItem );
+ const PNS::VIA* via = static_cast<const PNS::VIA*>( aItem );
via_board->SetPosition( wxPoint( via->Pos().x, via->Pos().y ) );
via_board->SetWidth( via->Diameter() );
via_board->SetDrill( via->Drill() );
diff --git a/pcbnew/router/pns_kicad_iface.h b/pcbnew/router/pns_kicad_iface.h
index 3cf6ffb..6c08987 100644
--- a/pcbnew/router/pns_kicad_iface.h
+++ b/pcbnew/router/pns_kicad_iface.h
@@ -47,10 +47,10 @@ public:
void SetView( KIGFX::VIEW* aView );
void SyncWorld( PNS::NODE* aWorld );
void EraseView();
- void HideItem( PNS::ITEM* aItem );
+ void HideItem( const PNS::ITEM* aItem );
void DisplayItem( const PNS::ITEM* aItem, int aColor = 0, int aClearance = 0 );
void AddItem( PNS::ITEM* aItem );
- void RemoveItem( PNS::ITEM* aItem );
+ void RemoveItem( const PNS::ITEM* aItem );
void Commit();
void UpdateNet( int aNetCode );
diff --git a/pcbnew/router/pns_line.cpp b/pcbnew/router/pns_line.cpp
index 0d8ce01..49366e9 100644
--- a/pcbnew/router/pns_line.cpp
+++ b/pcbnew/router/pns_line.cpp
@@ -123,13 +123,13 @@ void LINE::copyLinks( const LINE* aParent )
SEGMENT* SEGMENT::Clone() const
{
- SEGMENT* s = new SEGMENT;
+ SEGMENT* s = new SEGMENT;
- s->m_seg = m_seg;
- s->m_net = m_net;
+ s->m_seg = m_seg;
+ s->m_net = m_net;
s->m_layers = m_layers;
s->m_marker = m_marker;
- s->m_rank = m_rank;
+ s->m_rank = m_rank;
return s;
}
diff --git a/pcbnew/router/pns_line_placer.cpp b/pcbnew/router/pns_line_placer.cpp
index 9dadabe..3225c1a 100644
--- a/pcbnew/router/pns_line_placer.cpp
+++ b/pcbnew/router/pns_line_placer.cpp
@@ -40,13 +40,11 @@ LINE_PLACER::LINE_PLACER( ROUTER* aRouter ) :
PLACEMENT_ALGO( aRouter )
{
m_initial_direction = DIRECTION_45::N;
- m_world = NULL;
+ m_node = nullptr;
m_shove = NULL;
- m_currentNode = NULL;
m_idle = true;
// Init temporary variables (do not leave uninitialized members)
- m_lastNode = NULL;
m_placingVia = false;
m_currentNet = 0;
m_currentLayer = 0;
@@ -64,7 +62,7 @@ LINE_PLACER::~LINE_PLACER()
void LINE_PLACER::setWorld( NODE* aWorld )
{
- m_world = aWorld;
+ m_node = aWorld;
}
@@ -247,7 +245,7 @@ bool LINE_PLACER::reduceTail( const VECTOR2I& aEnd )
LINE tmp( m_tail, replacement );
- if( m_currentNode->CheckColliding( &tmp, ITEM::ANY_T ) )
+ if( m_node->CheckColliding( &tmp, ITEM::ANY_T ) )
break;
if( DIRECTION_45( replacement.CSegment( 0 ) ) == dir )
@@ -363,7 +361,7 @@ bool LINE_PLACER::rhWalkOnly( const VECTOR2I& aP, LINE& aNewHead )
viaOk = buildInitialLine( aP, initTrack );
- WALKAROUND walkaround( m_currentNode, Router() );
+ WALKAROUND walkaround( m_node, Router() );
walkaround.SetSolidsOnly( false );
walkaround.SetIterationLimit( Settings().WalkaroundIterationLimit() );
@@ -387,7 +385,7 @@ bool LINE_PLACER::rhWalkOnly( const VECTOR2I& aP, LINE& aNewHead )
if( wf == WALKAROUND::STUCK )
{
- walkFull = walkFull.ClipToNearestObstacle( m_currentNode );
+ walkFull = walkFull.ClipToNearestObstacle( m_node );
rv = true;
}
else if( m_placingVia && viaOk )
@@ -395,9 +393,9 @@ bool LINE_PLACER::rhWalkOnly( const VECTOR2I& aP, LINE& aNewHead )
walkFull.AppendVia( makeVia( walkFull.CPoint( -1 ) ) );
}
- OPTIMIZER::Optimize( &walkFull, effort, m_currentNode );
+ OPTIMIZER::Optimize( &walkFull, effort, m_node );
- if( m_currentNode->CheckColliding( &walkFull ) )
+ if( m_node->CheckColliding( &walkFull ) )
{
aNewHead = m_head;
return false;
@@ -414,7 +412,7 @@ bool LINE_PLACER::rhMarkObstacles( const VECTOR2I& aP, LINE& aNewHead )
{
buildInitialLine( aP, m_head );
aNewHead = m_head;
- return static_cast<bool>( m_currentNode->CheckColliding( &m_head ) );
+ return static_cast<bool>(m_node->CheckColliding( &m_head ) );
}
@@ -425,10 +423,10 @@ bool LINE_PLACER::rhShoveOnly( const VECTOR2I& aP, LINE& aNewHead )
bool viaOk = buildInitialLine( aP, initTrack );
- m_currentNode = m_shove->CurrentNode();
- OPTIMIZER optimizer( m_currentNode );
+ m_node = m_shove->CurrentNode();
+ OPTIMIZER optimizer( m_node );
- WALKAROUND walkaround( m_currentNode, Router() );
+ WALKAROUND walkaround( m_node, Router() );
walkaround.SetSolidsOnly( true );
walkaround.SetIterationLimit( 10 );
@@ -474,8 +472,6 @@ bool LINE_PLACER::rhShoveOnly( const VECTOR2I& aP, LINE& aNewHead )
SHOVE::SHOVE_STATUS status = m_shove->ShoveLines( l );
- m_currentNode = m_shove->CurrentNode();
-
if( status == SHOVE::SH_OK || status == SHOVE::SH_HEAD_MODIFIED )
{
if( status == SHOVE::SH_HEAD_MODIFIED )
@@ -483,7 +479,7 @@ bool LINE_PLACER::rhShoveOnly( const VECTOR2I& aP, LINE& aNewHead )
l2 = m_shove->NewHead();
}
- optimizer.SetWorld( m_currentNode );
+ optimizer.SetWorld( m_node );
optimizer.SetEffortLevel( OPTIMIZER::MERGE_OBTUSE | OPTIMIZER::SMART_PADS );
optimizer.SetCollisionMask( ITEM::ANY_T );
optimizer.Optimize( &l2 );
@@ -494,7 +490,7 @@ bool LINE_PLACER::rhShoveOnly( const VECTOR2I& aP, LINE& aNewHead )
}
else
{
- walkaround.SetWorld( m_currentNode );
+ walkaround.SetWorld( m_node );
walkaround.SetSolidsOnly( false );
walkaround.SetIterationLimit( 10 );
walkaround.SetApproachCursor( true, aP );
@@ -530,7 +526,7 @@ bool LINE_PLACER::optimizeTailHeadTransition()
{
LINE tmp = Trace();
- if( OPTIMIZER::Optimize( &tmp, OPTIMIZER::FANOUT_CLEANUP, m_currentNode ) )
+ if( OPTIMIZER::Optimize( &tmp, OPTIMIZER::FANOUT_CLEANUP, m_node ) )
{
if( tmp.SegmentCount() < 1 )
return false;
@@ -569,7 +565,7 @@ bool LINE_PLACER::optimizeTailHeadTransition()
// If so, replace the (threshold) last tail points and the head with
// the optimized line
- if( OPTIMIZER::Optimize( &new_head, OPTIMIZER::MERGE_OBTUSE, m_currentNode ) )
+ if( OPTIMIZER::Optimize( &new_head, OPTIMIZER::MERGE_OBTUSE, m_node ) )
{
LINE tmp( m_tail, opt_line );
@@ -676,10 +672,7 @@ void LINE_PLACER::FlipPosture()
NODE* LINE_PLACER::CurrentNode( bool aLoopsRemoved ) const
{
- if( aLoopsRemoved && m_lastNode )
- return m_lastNode;
-
- return m_currentNode;
+ return m_node;
}
@@ -697,7 +690,7 @@ void LINE_PLACER::splitAdjacentSegments( NODE* aNode, ITEM* aSeg, const VECTOR2I
return;
SEGMENT* s_old = static_cast<SEGMENT*>( aSeg );
-
+
std::unique_ptr< SEGMENT > s_new[2] = {
Clone( *s_old ),
Clone( *s_old )
@@ -760,6 +753,11 @@ bool LINE_PLACER::Start( const VECTOR2I& aP, ITEM* aStartItem )
return true;
}
+void LINE_PLACER::Cancel()
+{
+ m_processedBranch.Release();
+ m_workingBranch.Release();
+}
void LINE_PLACER::initPlacement()
{
@@ -779,27 +777,23 @@ void LINE_PLACER::initPlacement()
m_p_start = m_currentStart;
m_direction = m_initial_direction;
- NODE* world = Router()->GetWorld();
-
- world->KillChildren();
- NODE* rootNode = world->Branch();
+ //Router()->ResetWorld();
- splitAdjacentSegments( rootNode, m_startItem, m_currentStart );
+ setWorld( Router()->GetWorld() );
+ m_workingBranch.Reset( m_node );
- setWorld( rootNode );
+ splitAdjacentSegments( m_node, m_startItem, m_currentStart );
wxLogTrace( "PNS", "world %p, intitial-direction %s layer %d\n",
- m_world, m_direction.Format().c_str(), m_currentLayer );
+ m_node, m_direction.Format().c_str(), m_currentLayer );
- m_lastNode = NULL;
- m_currentNode = m_world;
m_currentMode = Settings().Mode();
m_shove.reset();
if( m_currentMode == RM_Shove || m_currentMode == RM_Smart )
{
- m_shove.reset( new SHOVE( m_world->Branch(), Router() ) );
+ m_shove.reset( new SHOVE( m_node, Router() ) );
}
}
@@ -810,14 +804,12 @@ bool LINE_PLACER::Move( const VECTOR2I& aP, ITEM* aEndItem )
VECTOR2I p = aP;
int eiDepth = -1;
+/*
if( aEndItem && aEndItem->Owner() )
eiDepth = static_cast<NODE*>( aEndItem->Owner() )->Depth();
+*/
- if( m_lastNode )
- {
- delete m_lastNode;
- m_lastNode = NULL;
- }
+ m_processedBranch.Commit();
route( p );
@@ -828,15 +820,14 @@ bool LINE_PLACER::Move( const VECTOR2I& aP, ITEM* aEndItem )
else
m_currentEnd = current.CLine().CPoint( -1 );
- NODE* latestNode = m_currentNode;
- m_lastNode = latestNode->Branch();
+ m_processedBranch.Reset( m_node );
- if( eiDepth >= 0 && aEndItem && latestNode->Depth() > eiDepth && current.SegmentCount() )
+ if( /* eiDepth >= 0 &&*/ aEndItem && /* m_node->Depth() > eiDepth && */ current.SegmentCount() )
{
- splitAdjacentSegments( m_lastNode, aEndItem, current.CPoint( -1 ) );
+ splitAdjacentSegments( m_node, aEndItem, current.CPoint( -1 ) );
if( Settings().RemoveLoops() )
- removeLoops( m_lastNode, current );
+ removeLoops( m_node, current );
}
updateLeadingRatLine();
@@ -844,7 +835,7 @@ bool LINE_PLACER::Move( const VECTOR2I& aP, ITEM* aEndItem )
}
-bool LINE_PLACER::FixRoute( const VECTOR2I& aP, ITEM* aEndItem )
+bool LINE_PLACER::CommitRoute( const VECTOR2I& aP, ITEM* aEndItem )
{
bool realEnd = false;
int lastV;
@@ -853,7 +844,7 @@ bool LINE_PLACER::FixRoute( const VECTOR2I& aP, ITEM* aEndItem )
if( m_currentMode == RM_MarkObstacles &&
!Settings().CanViolateDRC() &&
- m_world->CheckColliding( &pl ) )
+ m_node->CheckColliding( &pl ) )
return false;
const SHAPE_LINE_CHAIN& l = pl.CLine();
@@ -862,11 +853,10 @@ bool LINE_PLACER::FixRoute( const VECTOR2I& aP, ITEM* aEndItem )
{
if( pl.EndsWithVia() )
{
- m_lastNode->Add( Clone( pl.Via() ) );
- Router()->CommitRouting( m_lastNode );
-
- m_lastNode = NULL;
- m_currentNode = NULL;
+ m_node->Add( Clone( pl.Via() ) );
+ m_processedBranch.Commit();
+ m_workingBranch.Release();
+ Router()->CommitRouting();
m_idle = true;
}
@@ -898,19 +888,18 @@ bool LINE_PLACER::FixRoute( const VECTOR2I& aP, ITEM* aEndItem )
seg->SetWidth( pl.Width() );
seg->SetLayer( m_currentLayer );
lastSeg = seg.get();
- m_lastNode->Add( std::move( seg ) );
+ m_node->Add( std::move( seg ) );
}
if( pl.EndsWithVia() )
- m_lastNode->Add( Clone( pl.Via() ) );
+ m_node->Add( Clone( pl.Via() ) );
if( realEnd )
- simplifyNewLine( m_lastNode, lastSeg );
-
- Router()->CommitRouting( m_lastNode );
+ simplifyNewLine( m_node, lastSeg );
- m_lastNode = NULL;
- m_currentNode = NULL;
+ m_processedBranch.Commit();
+ m_workingBranch.Release();
+ Router()->CommitRouting();
if( !realEnd )
{
@@ -1015,7 +1004,7 @@ void LINE_PLACER::updateLeadingRatLine()
{
LINE current = Trace();
SHAPE_LINE_CHAIN ratLine;
- TOPOLOGY topo( m_lastNode );
+ TOPOLOGY topo( m_node );
if( topo.LeadingRatLine( ¤t, ratLine ) )
Dbg()->AddLine( ratLine, 5, 10000 );
@@ -1075,7 +1064,7 @@ bool LINE_PLACER::buildInitialLine( const VECTOR2I& aP, LINE& aHead )
bool solidsOnly = ( m_currentMode != RM_Walkaround );
- if( v.PushoutForce( m_currentNode, lead, force, solidsOnly, 40 ) )
+ if( v.PushoutForce( m_node, lead, force, solidsOnly, 40 ) )
{
SHAPE_LINE_CHAIN line = m_direction.BuildInitialTrace( m_p_start, aP + force );
aHead = LINE( aHead, line );
diff --git a/pcbnew/router/pns_line_placer.h b/pcbnew/router/pns_line_placer.h
index e0f33df..2e90e95 100644
--- a/pcbnew/router/pns_line_placer.h
+++ b/pcbnew/router/pns_line_placer.h
@@ -63,6 +63,8 @@ public:
*/
bool Start( const VECTOR2I& aP, ITEM* aStartItem );
+ void Cancel() override;
+
/**
* Function Move()
*
@@ -73,7 +75,7 @@ public:
bool Move( const VECTOR2I& aP, ITEM* aEndItem );
/**
- * Function FixRoute()
+ * Function CommitRoute()
*
* Commits the currently routed track to the parent node, taking
* aP as the final end point and aEndItem as the final anchor (if provided).
@@ -81,7 +83,7 @@ public:
* result is violating design rules - in such case, the track is only committed
* if Settings.CanViolateDRC() is on.
*/
- bool FixRoute( const VECTOR2I& aP, ITEM* aEndItem );
+ bool CommitRoute( const VECTOR2I& aP, ITEM* aEndItem );
/**
* Function ToggleVia()
@@ -361,8 +363,8 @@ private:
///> routing "tail": part of the track that has been already fixed due to collisions with obstacles
LINE m_tail;
- ///> pointer to world to search colliding items
- NODE* m_world;
+ ///> current world state
+ NODE* m_node;
///> current routing start point (end of tail, beginning of head)
VECTOR2I m_p_start;
@@ -370,11 +372,10 @@ private:
///> The shove engine
std::unique_ptr< SHOVE > m_shove;
- ///> Current world state
- NODE* m_currentNode;
-
+ ///> Working branch
+ SCOPED_BRANCH m_workingBranch;
///> Postprocessed world state (including marked collisions & removed loops)
- NODE* m_lastNode;
+ SCOPED_BRANCH m_processedBranch;
SIZES_SETTINGS m_sizes;
diff --git a/pcbnew/router/pns_meander_placer.cpp b/pcbnew/router/pns_meander_placer.cpp
index e0f876d..41a334a 100644
--- a/pcbnew/router/pns_meander_placer.cpp
+++ b/pcbnew/router/pns_meander_placer.cpp
@@ -33,8 +33,7 @@ namespace PNS {
MEANDER_PLACER::MEANDER_PLACER( ROUTER* aRouter ) :
MEANDER_PLACER_BASE( aRouter )
{
- m_world = NULL;
- m_currentNode = NULL;
+ m_node = nullptr;
// Init temporary variables (do not leave uninitialized members)
m_initialSegment = NULL;
@@ -47,16 +46,16 @@ MEANDER_PLACER::~MEANDER_PLACER()
{
}
+void MEANDER_PLACER::setWorld( NODE* aNode )
+{
+ m_node = aNode;
+}
NODE* MEANDER_PLACER::CurrentNode( bool aLoopsRemoved ) const
{
- if( !m_currentNode )
- return m_world;
-
- return m_currentNode;
+ return m_node;
}
-
bool MEANDER_PLACER::Start( const VECTOR2I& aP, ITEM* aStartItem )
{
VECTOR2I p;
@@ -71,16 +70,17 @@ bool MEANDER_PLACER::Start( const VECTOR2I& aP, ITEM* aStartItem )
p = m_initialSegment->Seg().NearestPoint( aP );
- m_currentNode = NULL;
m_currentStart = p;
- m_world = Router()->GetWorld()->Branch();
- m_originLine = m_world->AssembleLine( m_initialSegment );
+ m_node = Router()->GetWorld();
+ m_workingBranch.Reset( m_node );
- TOPOLOGY topo( m_world );
+ m_originLine = m_node->AssembleLine( m_initialSegment );
+
+ TOPOLOGY topo( m_node );
m_tunedPath = topo.AssembleTrivialPath( m_initialSegment );
- m_world->Remove( m_originLine );
+ m_node->Remove( m_originLine );
m_currentWidth = m_originLine.Width();
m_currentEnd = VECTOR2I( 0, 0 );
@@ -88,6 +88,11 @@ bool MEANDER_PLACER::Start( const VECTOR2I& aP, ITEM* aStartItem )
return true;
}
+void MEANDER_PLACER::Cancel()
+{
+ m_processedBranch.Reset();
+ m_workingBranch.Reset();
+}
int MEANDER_PLACER::origPathLength() const
{
@@ -114,10 +119,7 @@ bool MEANDER_PLACER::doMove( const VECTOR2I& aP, ITEM* aEndItem, int aTargetLeng
{
SHAPE_LINE_CHAIN pre, tuned, post;
- if( m_currentNode )
- delete m_currentNode;
-
- m_currentNode = m_world->Branch();
+ m_processedBranch.Reset( m_node );
cutTunedLine( m_originLine.CLine(), m_currentStart, aP, pre, tuned, post );
@@ -188,15 +190,17 @@ bool MEANDER_PLACER::doMove( const VECTOR2I& aP, ITEM* aEndItem, int aTargetLeng
}
-bool MEANDER_PLACER::FixRoute( const VECTOR2I& aP, ITEM* aEndItem )
+bool MEANDER_PLACER::CommitRoute( const VECTOR2I& aP, ITEM* aEndItem )
{
- if( !m_currentNode )
+ if( !m_processedBranch )
return false;
m_currentTrace = LINE( m_originLine, m_finalShape );
- m_currentNode->Add( m_currentTrace );
+ m_node->Add( m_currentTrace );
- Router()->CommitRouting( m_currentNode );
+ m_processedBranch.Commit();
+ m_workingBranch.Release();
+ Router()->CommitRouting();
return true;
}
@@ -205,7 +209,7 @@ bool MEANDER_PLACER::CheckFit( MEANDER_SHAPE* aShape )
{
LINE l( m_originLine, aShape->CLine( 0 ) );
- if( m_currentNode->CheckColliding( &l ) )
+ if( m_node->CheckColliding( &l ) )
return false;
int w = aShape->Width();
diff --git a/pcbnew/router/pns_meander_placer.h b/pcbnew/router/pns_meander_placer.h
index 894a04a..07a44f9 100644
--- a/pcbnew/router/pns_meander_placer.h
+++ b/pcbnew/router/pns_meander_placer.h
@@ -55,11 +55,14 @@ public:
/// @copydoc PLACEMENT_ALGO::Start()
virtual bool Start( const VECTOR2I& aP, ITEM* aStartItem );
+ /// @copydoc PLACEMENT_ALGO::Cancel()
+ void Cancel() override;
+
/// @copydoc PLACEMENT_ALGO::Move()
virtual bool Move( const VECTOR2I& aP, ITEM* aEndItem );
- /// @copydoc PLACEMENT_ALGO::FixRoute()
- virtual bool FixRoute( const VECTOR2I& aP, ITEM* aEndItem );
+ /// @copydoc PLACEMENT_ALGO::CommitRoute()
+ virtual bool CommitRoute( const VECTOR2I& aP, ITEM* aEndItem );
/// @copydoc PLACEMENT_ALGO::CurrentNode()
NODE* CurrentNode( bool aLoopsRemoved = false ) const;
@@ -97,13 +100,14 @@ protected:
virtual int origPathLength() const;
///> pointer to world to search colliding items
- NODE* m_world;
+ NODE* m_node;
///> current routing start point (end of tail, beginning of head)
VECTOR2I m_currentStart;
///> Current world state
- NODE* m_currentNode;
+ SCOPED_BRANCH m_workingBranch;
+ SCOPED_BRANCH m_processedBranch;
LINE m_originLine;
LINE m_currentTrace;
diff --git a/pcbnew/router/pns_meander_skew_placer.cpp b/pcbnew/router/pns_meander_skew_placer.cpp
index ae59b97..7b1fb2f 100644
--- a/pcbnew/router/pns_meander_skew_placer.cpp
+++ b/pcbnew/router/pns_meander_skew_placer.cpp
@@ -58,13 +58,14 @@ bool MEANDER_SKEW_PLACER::Start( const VECTOR2I& aP, ITEM* aStartItem )
p = m_initialSegment->Seg().NearestPoint( aP );
- m_currentNode = NULL;
+ m_node = NULL;
m_currentStart = p;
- m_world = Router()->GetWorld( )->Branch();
- m_originLine = m_world->AssembleLine( m_initialSegment );
+ setWorld( Router()->GetWorld() );
+ m_workingBranch.Reset( Router()->GetWorld( ) );
+ m_originLine = m_node->AssembleLine( m_initialSegment );
- TOPOLOGY topo( m_world );
+ TOPOLOGY topo( m_node );
m_tunedPath = topo.AssembleTrivialPath( m_initialSegment );
if( !topo.AssembleDiffPair ( m_initialSegment, m_originPair ) )
@@ -85,7 +86,7 @@ bool MEANDER_SKEW_PLACER::Start( const VECTOR2I& aP, ITEM* aStartItem )
m_tunedPathP = topo.AssembleTrivialPath( m_originPair.PLine().GetLink( 0 ) );
m_tunedPathN = topo.AssembleTrivialPath( m_originPair.NLine().GetLink( 0 ) );
- m_world->Remove( m_originLine );
+ m_node->Remove( m_originLine );
m_currentWidth = m_originLine.Width();
m_currentEnd = VECTOR2I( 0, 0 );
diff --git a/pcbnew/router/pns_node.cpp b/pcbnew/router/pns_node.cpp
index fbadc92..d119757 100644
--- a/pcbnew/router/pns_node.cpp
+++ b/pcbnew/router/pns_node.cpp
@@ -43,115 +43,178 @@ using boost::unordered_map;
namespace PNS {
-#ifdef DEBUG
-static boost::unordered_set<NODE*> allocNodes;
-#endif
-
-NODE::NODE()
+NODE::NODE( REVISION* aRevision )
+ : m_revision( aRevision )
{
wxLogTrace( "PNS", "NODE::create %p", this );
m_depth = 0;
- m_root = this;
- m_parent = NULL;
m_maxClearance = 800000; // fixme: depends on how thick traces are.
m_ruleResolver = NULL;
- m_index = new INDEX;
-
-#ifdef DEBUG
- allocNodes.insert( this );
-#endif
}
NODE::~NODE()
{
wxLogTrace( "PNS", "NODE::delete %p", this );
+}
- if( !m_children.empty() )
- {
- wxLogTrace( "PNS", "attempting to free a node that has kids.\n" );
- assert( false );
- }
+int NODE::GetClearance( const ITEM* aA, const ITEM* aB ) const
+{
+ if( !m_ruleResolver )
+ return 100000;
-#ifdef DEBUG
- if( allocNodes.find( this ) == allocNodes.end() )
- {
- wxLogTrace( "PNS", "attempting to free an already-free'd node.\n" );
- assert( false );
- }
+ return m_ruleResolver->Clearance( aA, aB );
+}
- allocNodes.erase( this );
-#endif
+// ================
+// Revision Methods
+// ================
- m_joints.clear();
+REVISION* NODE::GetRevision()
+{
+ return m_revision;
+}
+
+REVISION_PATH NODE::Path( REVISION* aAncestor ) const
+{
+ return m_revision->Path( aAncestor );
+}
- for( INDEX::ITEM_SET::iterator i = m_index->begin(); i != m_index->end(); ++i )
+CHANGE_SET NODE::GetRevisionChanges() const
+{
+ return m_revision->GetRevisionChanges();
+}
+
+REVISION* NODE::BranchMove()
+{
+ REVISION* result = m_revision;
+ m_revision = m_revision->Branch();
+ ++m_depth;
+ return result;
+}
+
+void NODE::Squash()
+{
+ --m_depth;
+ m_revision = m_revision->Squash();
+}
+
+void NODE::SquashToRevision( REVISION* aAncestor )
+{
+ while( m_revision != aAncestor )
{
- if( (*i)->BelongsTo( this ) )
- delete *i;
+ Squash();
}
+}
- unlinkParent();
+void NODE::SquashToParentRevision( REVISION* aAncestor )
+{
+ while( m_revision->Parent() != aAncestor )
+ {
+ Squash();
+ }
+}
- delete m_index;
+void NODE::Revert()
+{
+ --m_depth;
+ revertRevision( m_revision );
+ m_revision = m_revision->Revert();
}
-int NODE::GetClearance( const ITEM* aA, const ITEM* aB ) const
+void NODE::RevertToRevision( REVISION* aAncestor )
{
- if( !m_ruleResolver )
- return 100000;
+ while( m_revision != aAncestor )
+ {
+ Revert();
+ }
+}
- return m_ruleResolver->Clearance( aA, aB );
+void NODE::RevertToParentRevision( REVISION* aAncestor )
+{
+ while( m_revision->Parent() != aAncestor )
+ {
+ Revert();
+ }
}
+void NODE::CheckoutAncestor( REVISION* aAncestor )
+{
+ WalkPathUp( Path( aAncestor ) );
+}
-NODE* NODE::Branch()
+void NODE::CheckoutDescendant( REVISION* aDescendant )
{
- NODE* child = new NODE;
+ WalkPathDown( aDescendant->Path( m_revision ) );
+}
- wxLogTrace( "PNS", "NODE::branch %p (parent %p)", child, this );
+void NODE::WalkPathUp( const REVISION_PATH& aPath )
+{
+ for( auto revision : aPath )
+ {
+ assert(revision == m_revision);
+ --m_depth;
+ revertRevision( revision );
+ m_revision = const_cast<REVISION*>(m_revision->Parent());
+ }
+}
- m_children.insert( child );
+void NODE::WalkPathDown( const REVISION_PATH& aPath )
+{
+ for( auto it = aPath.rbegin(); it != aPath.rend(); ++it )
+ {
+ assert( (*it)->Parent() == m_revision );
+ ++m_depth;
+ applyRevision( (*it) );
+ m_revision = const_cast<REVISION*>(*it);
+ }
+}
- child->m_depth = m_depth + 1;
- child->m_parent = this;
- child->m_ruleResolver = m_ruleResolver;
- child->m_root = isRoot() ? this : m_root;
+void NODE::ClearBranches()
+{
+ m_revision->ClearBranches();
+}
- // immmediate offspring of the root branch needs not copy anything.
- // For the rest, deep-copy joints, overridden item map and pointers
- // to stored items.
- if( !isRoot() )
+void NODE::applyRevision( const REVISION* aRevision )
+{
+ for( auto item_ptr : aRevision->RemovedItems() )
{
- JOINT_MAP::iterator j;
-
- for( INDEX::ITEM_SET::iterator i = m_index->begin(); i != m_index->end(); ++i )
- child->m_index->Add( *i );
+ removeItemIndex( item_ptr );
+ }
- child->m_joints = m_joints;
- child->m_override = m_override;
+ for( auto& item_ptr : aRevision->AddedItems() )
+ {
+ addItemIndex( item_ptr.get() );
}
+}
- wxLogTrace( "PNS", "%d items, %lu joints, %lu overrides",
- child->m_index->Size(), child->m_joints.size(), child->m_override.size() );
+void NODE::revertRevision( const REVISION* aRevision )
+{
+ for( auto& item_ptr : aRevision->AddedItems() )
+ {
+ removeItemIndex( item_ptr.get() );
+ }
- return child;
+ for( auto item_ptr : aRevision->RemovedItems() )
+ {
+ addItemIndex( item_ptr );
+ }
}
-
-void NODE::unlinkParent()
+void NODE::Clear()
{
- if( isRoot() )
- return;
-
- m_parent->m_children.erase( this );
+ m_index.Clear();
+ m_joints.clear();
+ m_revision->Clear();
}
+// =============
+// Index Methods
+// =============
OBSTACLE_VISITOR::OBSTACLE_VISITOR( const ITEM* aItem ) :
m_item( aItem ),
m_node( NULL ),
- m_override( NULL ),
m_extraClearance( 0 )
{
if( aItem && aItem->Kind() == ITEM::LINE_T )
@@ -159,20 +222,20 @@ OBSTACLE_VISITOR::OBSTACLE_VISITOR( const ITEM* aItem ) :
}
-void OBSTACLE_VISITOR::SetWorld( const NODE* aNode, const NODE* aOverride )
+void OBSTACLE_VISITOR::SetWorld( const NODE* aNode )
{
m_node = aNode;
- m_override = aOverride;
}
bool OBSTACLE_VISITOR::visit( ITEM* aCandidate )
{
+/*
// check if there is a more recent branch with a newer
// (possibily modified) version of this item.
if( m_override && m_override->Overrides( aCandidate ) )
return true;
-
+*/
return false;
}
@@ -257,16 +320,8 @@ struct NODE::DEFAULT_OBSTACLE_VISITOR : public OBSTACLE_VISITOR
int NODE::QueryColliding( const ITEM* aItem, OBSTACLE_VISITOR& aVisitor )
{
- aVisitor.SetWorld( this, NULL );
- m_index->Query( aItem, m_maxClearance, aVisitor );
-
- // if we haven't found enough items, look in the root branch as well.
- if( !isRoot() )
- {
- aVisitor.SetWorld( m_root, this );
- m_root->m_index->Query( aItem, m_maxClearance, aVisitor );
- }
-
+ aVisitor.SetWorld( this );
+ m_index.Query( aItem, m_maxClearance, aVisitor );
return 0;
}
@@ -281,17 +336,9 @@ int NODE::QueryColliding( const ITEM* aItem,
#endif
visitor.SetCountLimit( aLimitCount );
- visitor.SetWorld( this, NULL );
+ visitor.SetWorld( this );
visitor.m_forceClearance = aForceClearance;
- // first, look for colliding items in the local index
- m_index->Query( aItem, m_maxClearance, visitor );
-
- // if we haven't found enough items, look in the root branch as well.
- if( !isRoot() && ( visitor.m_matchCount < aLimitCount || aLimitCount < 0 ) )
- {
- visitor.SetWorld( m_root, this );
- m_root->m_index->Query( aItem, m_maxClearance, visitor );
- }
+ m_index.Query( aItem, m_maxClearance, visitor );
return aObstacles.size();
}
@@ -506,23 +553,9 @@ const ITEM_SET NODE::HitTest( const VECTOR2I& aPoint ) const
// fixme: we treat a point as an infinitely small circle - this is inefficient.
SHAPE_CIRCLE s( aPoint, 0 );
HIT_VISITOR visitor( items, aPoint );
- visitor.SetWorld( this, NULL );
-
- m_index->Query( &s, m_maxClearance, visitor );
+ visitor.SetWorld( this );
- if( !isRoot() ) // fixme: could be made cleaner
- {
- ITEM_SET items_root;
- visitor.SetWorld( m_root, NULL );
- HIT_VISITOR visitor_root( items_root, aPoint );
- m_root->m_index->Query( &s, m_maxClearance, visitor_root );
-
- for( ITEM* item : items_root.Items() )
- {
- if( !Overrides( item ) )
- items.Add( item );
- }
- }
+ m_index.Query( &s, m_maxClearance, visitor );
return items;
}
@@ -531,25 +564,27 @@ const ITEM_SET NODE::HitTest( const VECTOR2I& aPoint ) const
void NODE::addSolidIndex( SOLID* aSolid )
{
linkJoint( aSolid->Pos(), aSolid->Layers(), aSolid->Net(), aSolid );
- m_index->Add( aSolid );
+ m_index.Add( aSolid );
}
void NODE::Add( std::unique_ptr< SOLID > aSolid )
{
aSolid->SetOwner( this );
- addSolidIndex( aSolid.release() );
+ addSolidIndex( aSolid.get() );
+ m_revision->AddItem( std::move( aSolid ) );
}
void NODE::addViaIndex( VIA* aVia )
{
linkJoint( aVia->Pos(), aVia->Layers(), aVia->Net(), aVia );
- m_index->Add( aVia );
+ m_index.Add( aVia );
}
void NODE::Add( std::unique_ptr< VIA > aVia )
{
aVia->SetOwner( this );
- addViaIndex( aVia.release() );
+ addViaIndex( aVia.get() );
+ m_revision->AddItem( std::move( aVia ) );
}
void NODE::Add( LINE& aLine, bool aAllowRedundant )
@@ -586,8 +621,7 @@ void NODE::addSegmentIndex( SEGMENT* aSeg )
{
linkJoint( aSeg->Seg().A, aSeg->Layers(), aSeg->Net(), aSeg );
linkJoint( aSeg->Seg().B, aSeg->Layers(), aSeg->Net(), aSeg );
-
- m_index->Add( aSeg );
+ m_index.Add( aSeg );
}
void NODE::Add( std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant )
@@ -602,7 +636,8 @@ void NODE::Add( std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant )
return;
aSegment->SetOwner( this );
- addSegmentIndex( aSegment.release() );
+ addSegmentIndex( aSegment.get() );
+ m_revision->AddItem( std::move( aSegment ) );
}
void NODE::Add( std::unique_ptr< ITEM > aItem, bool aAllowRedundant )
@@ -630,31 +665,36 @@ void NODE::Add( std::unique_ptr< ITEM > aItem, bool aAllowRedundant )
}
}
-
-void NODE::doRemove( ITEM* aItem )
+void NODE::addItemIndex( ITEM* aItem )
{
- // Can't remove items in non-leaf-revisions.
- assert( !m_children.size() );
+ switch( aItem->Kind() )
+ {
+ case ITEM::SOLID_T:
+ addSolidIndex( static_cast<SOLID*>( aItem ) );
+ break;
+
+ case ITEM::SEGMENT_T:
+ addSegmentIndex( static_cast<SEGMENT*>( aItem ) );
+ break;
- // Can't remove items from child-revisions here
- assert( aItem->Owner()->Depth() <= Depth() );
+ case ITEM::LINE_T:
+ assert( false );
+ break;
- if( aItem->Owner() == this ) {
- delete aItem;
- } else {
- // if the item doesn't belong to this node, it must
- // have been added in an ancestor revision.
- m_override.insert( aItem );
+ case ITEM::VIA_T:
+ addViaIndex( static_cast<VIA*>( aItem ) );
+ break;
+
+ default:
+ assert( false );
}
}
-
void NODE::removeSegmentIndex( SEGMENT* aSeg )
{
unlinkJoint( aSeg->Seg().A, aSeg->Layers(), aSeg->Net(), aSeg );
unlinkJoint( aSeg->Seg().B, aSeg->Layers(), aSeg->Net(), aSeg );
-
- m_index->Remove( aSeg );
+ m_index.Remove( aSeg );
}
void NODE::removeViaIndex( VIA* aVia )
@@ -703,13 +743,14 @@ void NODE::removeViaIndex( VIA* aVia )
linkJoint( p, item->Layers(), net, item );
}
- m_index->Remove( aVia );
+ m_index.Remove( aVia );
}
void NODE::removeSolidIndex( SOLID* aSolid )
{
// fixme: this fucks up the joints, but it's only used for marking colliding obstacles for the moment, so we don't care.
- m_index->Remove( aSolid );
+ unlinkJoint( aSolid->Pos(), aSolid->Layers(), aSolid->Net(), aSolid );
+ m_index.Remove( aSolid );
}
@@ -728,31 +769,31 @@ void NODE::Replace( LINE& aOldLine, LINE& aNewLine )
void NODE::Remove( SOLID* aSolid )
{
removeSolidIndex( aSolid );
- doRemove( aSolid );
+ m_revision->RemoveItem( aSolid );
}
void NODE::Remove( VIA* aVia )
{
removeViaIndex( aVia );
- doRemove( aVia );
+ m_revision->RemoveItem( aVia );
}
void NODE::Remove( SEGMENT* aSegment )
{
removeSegmentIndex( aSegment );
- doRemove( aSegment );
+ m_revision->RemoveItem( aSegment );
}
-void NODE::Remove( ITEM* aItem )
+void NODE::removeItemIndex( ITEM* aItem )
{
switch( aItem->Kind() )
{
case ITEM::SOLID_T:
- Remove( static_cast<SOLID*>( aItem ) );
+ removeSolidIndex( static_cast<SOLID*>(aItem) );
break;
case ITEM::SEGMENT_T:
- Remove( static_cast<SEGMENT*>( aItem ) );
+ removeSegmentIndex( static_cast<SEGMENT*>(aItem) );
break;
case ITEM::LINE_T:
@@ -760,7 +801,7 @@ void NODE::Remove( ITEM* aItem )
break;
case ITEM::VIA_T:
- Remove( static_cast<VIA*>( aItem ) );
+ removeViaIndex( static_cast<VIA*>(aItem) );
break;
default:
@@ -768,6 +809,12 @@ void NODE::Remove( ITEM* aItem )
}
}
+void NODE::Remove( ITEM* aItem )
+{
+ removeItemIndex( aItem );
+ m_revision->RemoveItem( aItem );
+}
+
void NODE::Remove( LINE& aLine )
{
@@ -967,12 +1014,6 @@ JOINT* NODE::FindJoint( const VECTOR2I& aPos, int aLayer, int aNet )
JOINT_MAP::iterator f = m_joints.find( tag ), end = m_joints.end();
- if( f == end && !isRoot() )
- {
- end = m_root->m_joints.end();
- f = m_root->m_joints.find( tag ); // m_root->FindJoint(aPos, aLayer, aNet);
- }
-
if( f == end )
return NULL;
@@ -997,24 +1038,8 @@ void NODE::LockJoint( const VECTOR2I& aPos, const ITEM* aItem, bool aLock )
JOINT& NODE::touchJoint( const VECTOR2I& aPos, const LAYER_RANGE& aLayers, int aNet )
{
- JOINT::HASH_TAG tag;
-
- tag.pos = aPos;
- tag.net = aNet;
-
- // try to find the joint in this node.
- JOINT_MAP::iterator f = m_joints.find( tag );
-
- std::pair<JOINT_MAP::iterator, JOINT_MAP::iterator> range;
-
- // not found and we are not root? find in the root and copy results here.
- if( f == m_joints.end() && !isRoot() )
- {
- range = m_root->m_joints.equal_range( tag );
-
- for( f = range.first; f != range.second; ++f )
- m_joints.insert( *f );
- }
+ JOINT::HASH_TAG tag{ aPos, aNet };
+ using JOINT_ITERATOR = JOINT_MAP::iterator;
// now insert and combine overlapping joints
JOINT jt( aPos, aLayers, aNet );
@@ -1023,13 +1048,14 @@ JOINT& NODE::touchJoint( const VECTOR2I& aPos, const LAYER_RANGE& aLayers, int a
do
{
+ std::pair<JOINT_ITERATOR, JOINT_ITERATOR> range;
merged = false;
range = m_joints.equal_range( tag );
if( range.first == m_joints.end() )
break;
- for( f = range.first; f != range.second; ++f )
+ for( JOINT_ITERATOR f = range.first; f != range.second; ++f )
{
if( aLayers.Overlaps( f->second.Layers() ) )
{
@@ -1152,99 +1178,34 @@ void NODE::Dump( bool aLong )
#endif
}
-
-void NODE::GetUpdatedItems( ITEM_VECTOR& aRemoved, ITEM_VECTOR& aAdded )
-{
- aRemoved.reserve( m_override.size() );
- aAdded.reserve( m_index->Size() );
-
- if( isRoot() )
- return;
-
- for( ITEM* item : m_override )
- aRemoved.push_back( item );
-
- for( INDEX::ITEM_SET::iterator i = m_index->begin(); i != m_index->end(); ++i )
- aAdded.push_back( *i );
-}
-
-void NODE::releaseChildren()
-{
- // copy the kids as the NODE destructor erases the item from the parent node.
- std::set<NODE*> kids = m_children;
-
- for( NODE* node : kids )
- {
- node->releaseChildren();
- delete node;
- }
-}
-
-void NODE::Commit( NODE* aNode )
-{
- if( aNode->isRoot() )
- return;
-
- for( ITEM* item : aNode->m_override )
- Remove( item );
-
- for( INDEX::ITEM_SET::iterator i = aNode->m_index->begin();
- i != aNode->m_index->end(); ++i )
- {
- (*i)->SetRank( -1 );
- (*i)->Unmark();
- Add( std::unique_ptr<ITEM>( *i ) );
- }
-
- releaseChildren();
-}
-
-
-void NODE::KillChildren()
-{
- assert( isRoot() );
- releaseChildren();
-}
-
-
void NODE::AllItemsInNet( int aNet, std::set<ITEM*>& aItems )
{
- INDEX::NET_ITEMS_LIST* l_cur = m_index->GetItemsForNet( aNet );
+ INDEX::NET_ITEMS_LIST* l_cur = m_index.GetItemsForNet( aNet );
if( l_cur )
{
for( ITEM*item : *l_cur )
aItems.insert( item );
}
-
- if( !isRoot() )
- {
- INDEX::NET_ITEMS_LIST* l_root = m_root->m_index->GetItemsForNet( aNet );
-
- if( l_root )
- for( INDEX::NET_ITEMS_LIST::iterator i = l_root->begin(); i!= l_root->end(); ++i )
- if( !Overrides( *i ) )
- aItems.insert( *i );
- }
}
void NODE::ClearRanks( int aMarkerMask )
{
- for( INDEX::ITEM_SET::iterator i = m_index->begin(); i != m_index->end(); ++i )
+ for( auto& itemptr : m_index )
{
- (*i)->SetRank( -1 );
- (*i)->Mark( (*i)->Marker() & (~aMarkerMask) );
+ itemptr->SetRank( -1 );
+ itemptr->Mark( itemptr->Marker() & (~aMarkerMask) );
}
}
int NODE::FindByMarker( int aMarker, ITEM_SET& aItems )
{
- for( INDEX::ITEM_SET::iterator i = m_index->begin(); i != m_index->end(); ++i )
+ for( auto& itemptr : m_index )
{
- if( (*i)->Marker() & aMarker )
- aItems.Add( *i );
+ if( itemptr->Marker() & aMarker )
+ aItems.Add( itemptr );
}
return 0;
@@ -1253,19 +1214,19 @@ int NODE::FindByMarker( int aMarker, ITEM_SET& aItems )
int NODE::RemoveByMarker( int aMarker )
{
- std::list<ITEM*> garbage;
+ std::vector<ITEM*> garbage;
- for( INDEX::ITEM_SET::iterator i = m_index->begin(); i != m_index->end(); ++i )
+ for( auto& itemptr : m_index )
{
- if( (*i)->Marker() & aMarker )
+ if( itemptr->Marker() & aMarker )
{
- garbage.push_back( *i );
+ garbage.push_back( itemptr );
}
}
- for( std::list<ITEM*>::const_iterator i = garbage.begin(), end = garbage.end(); i != end; ++i )
+ for( auto garbage_item : garbage )
{
- Remove( *i );
+ Remove( garbage_item );
}
return 0;
@@ -1305,9 +1266,9 @@ SEGMENT* NODE::findRedundantSegment( SEGMENT* aSeg )
ITEM *NODE::FindItemByParent( const BOARD_CONNECTED_ITEM* aParent )
{
- INDEX::NET_ITEMS_LIST* l_cur = m_index->GetItemsForNet( aParent->GetNetCode() );
+ INDEX::NET_ITEMS_LIST* l_cur = m_index.GetItemsForNet( aParent->GetNetCode() );
- for( ITEM*item : *l_cur )
+ for( ITEM* item : *l_cur )
if( item->Parent() == aParent )
return item;
diff --git a/pcbnew/router/pns_node.h b/pcbnew/router/pns_node.h
index a686d58..4fb9677 100644
--- a/pcbnew/router/pns_node.h
+++ b/pcbnew/router/pns_node.h
@@ -36,6 +36,8 @@
#include "pns_item.h"
#include "pns_joint.h"
#include "pns_itemset.h"
+#include "pns_revision.h"
+#include "pns_index.h"
namespace PNS {
@@ -43,7 +45,6 @@ class SEGMENT;
class LINE;
class SOLID;
class VIA;
-class INDEX;
class ROUTER;
class NODE;
@@ -100,7 +101,7 @@ public:
OBSTACLE_VISITOR( const ITEM* aItem );
- void SetWorld( const NODE* aNode, const NODE* aOverride = NULL );
+ void SetWorld( const NODE* aNode );
virtual bool operator()( ITEM* aCandidate ) = 0;
@@ -111,12 +112,9 @@ protected:
///> the item we are looking for collisions with
const ITEM* m_item;
- ///> node we are searching in (either root or a branch)
+ ///> node we are searching in
const NODE* m_node;
- ///> node that overrides root entries
- const NODE* m_override;
-
///> additional clearance
int m_extraClearance;
};
@@ -140,9 +138,62 @@ public:
typedef std::vector<ITEM*> ITEM_VECTOR;
typedef std::vector<OBSTACLE> OBSTACLES;
- NODE();
+ NODE( REVISION* aRevision );
~NODE();
+ void Clear();
+
+ /// Revision Methods
+public:
+ /**
+ * 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.
+ * @return pointer to the old revision
+ */
+ REVISION* BranchMove();
+
+ void Revert();
+ void RevertToParentRevision( REVISION* aAncestor );
+ void RevertToRevision( REVISION* aAncestor );
+
+ void Squash();
+ void SquashToParentRevision( REVISION* aAncestor );
+ void SquashToRevision( REVISION* aAncestor );
+
+ REVISION_PATH Path( REVISION* aAncestor ) const;
+
+ CHANGE_SET GetRevisionChanges() const;
+
+ void CheckoutAncestor ( REVISION* aAncestor );
+ void CheckoutDescendant( REVISION* aDescendant );
+
+ void WalkPathUp ( const REVISION_PATH& aPath );
+ void WalkPathDown( const REVISION_PATH& aPath );
+
+ REVISION* GetRevision();
+
+ ///> Clears all branches.
+ void ClearBranches();
+
+ /**
+ * Function GetUpdatedItems()
+ *
+ * Returns the lists of items removed and added in this branch, with
+ * respect to the root branch.
+ * @param aRemoved removed items
+ * @param aAdded added items
+ */
+ CHANGE_SET GetUpdatedItems();
+
+private:
+ void applyRevision ( const REVISION* aRevision );
+ void revertRevision( const REVISION* aRevision );
+
+ /// Index Methods
+public:
///> Returns the expected clearance between items a and b.
int GetClearance( const ITEM* aA, const ITEM* aB ) const;
@@ -314,16 +365,6 @@ public:
void Replace( LINE& aOldLine, LINE& aNewLine );
/**
- * 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.
- * @return the new branch
- */
- NODE* Branch();
-
- /**
* Function AssembleLine()
*
* Follows the joint map to assemble a line connecting two non-trivial
@@ -339,16 +380,6 @@ public:
void Dump( bool aLong = false );
/**
- * Function GetUpdatedItems()
- *
- * Returns the lists of items removed and added in this branch, with
- * respect to the root branch.
- * @param aRemoved removed items
- * @param aAdded added items
- */
- void GetUpdatedItems( ITEM_VECTOR& aRemoved, ITEM_VECTOR& aAdded );
-
- /**
* Function Commit()
*
* Applies the changes from a given branch (aNode) to the root branch. Called on
@@ -394,9 +425,6 @@ public:
///> finds the joints corresponding to the ends of line aLine
void FindLineEnds( const LINE& aLine, JOINT& aA, JOINT& aB );
- ///> Destroys all child nodes. Applicable only to the root node.
- void KillChildren();
-
void AllItemsInNet( int aNet, std::set<ITEM*>& aItems );
void ClearRanks( int aMarkerMask = MK_HEAD | MK_VIOLATION );
@@ -406,26 +434,14 @@ public:
ITEM* FindItemByParent( const BOARD_CONNECTED_ITEM* aParent );
- bool HasChildren() const
- {
- return !m_children.empty();
- }
-
- ///> checks if this branch contains an updated version of the m_item
- ///> from the root branch.
- bool Overrides( ITEM* aItem ) const
- {
- return m_override.find( aItem ) != m_override.end();
- }
-
private:
struct DEFAULT_OBSTACLE_VISITOR;
typedef boost::unordered_multimap<JOINT::HASH_TAG, JOINT> JOINT_MAP;
typedef JOINT_MAP::value_type TagJointPair;
/// nodes are not copyable
- NODE( const NODE& aB );
- NODE& operator=( const NODE& aB );
+ NODE( const NODE& aB ) = delete;
+ NODE& operator=( const NODE& aB ) = delete;
///> tries to find matching joint and creates a new one if not found
JOINT& touchJoint( const VECTOR2I& aPos,
@@ -444,20 +460,18 @@ private:
void addSolidIndex( SOLID* aSeg );
void addSegmentIndex( SEGMENT* aSeg );
void addViaIndex( VIA* aVia );
+ void addItemIndex( ITEM* aItem);
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 removeItemIndex( ITEM* aItem );
bool isRoot() const
{
- return m_parent == NULL;
+ return !m_revision->Parent();
}
SEGMENT* findRedundantSegment( const VECTOR2I& A, const VECTOR2I& B,
@@ -478,18 +492,6 @@ private:
///> their position, layer set and net.
JOINT_MAP m_joints;
- ///> node this node was branched from
- NODE* m_parent;
-
- ///> root node of the whole hierarchy
- NODE* m_root;
-
- ///> list of nodes branched from this one
- std::set<NODE*> m_children;
-
- ///> hash of root's items that have been changed in this node
- boost::unordered_set<ITEM*> m_override;
-
///> worst case item-item clearance
int m_maxClearance;
@@ -497,12 +499,89 @@ private:
RULE_RESOLVER* m_ruleResolver;
///> Geometric/Net index of the items
- INDEX* m_index;
+ INDEX m_index;
+
+ ///> Current revision
+ REVISION* m_revision;
///> depth of the node (number of parent nodes in the inheritance chain)
int m_depth;
};
+class SCOPED_BRANCH
+{
+public:
+ SCOPED_BRANCH()
+ : m_node( nullptr )
+ {}
+
+ SCOPED_BRANCH( NODE* aNode )
+ : m_node( aNode )
+ {
+ m_old_revision = m_node->BranchMove();
+ }
+
+ explicit operator bool() const
+ {
+ return m_node != nullptr;
+ }
+
+ NODE* operator->()
+ {
+ return m_node;
+ }
+
+ NODE* get()
+ {
+ return m_node;
+ }
+
+ void Release()
+ {
+ m_node = nullptr;
+ }
+
+ REVISION* OriginalRevision()
+ {
+ return m_old_revision;
+ }
+
+ void Commit()
+ {
+ if( m_node ) {
+ m_node->SquashToRevision( m_old_revision );
+ m_node = nullptr;
+ }
+ }
+
+ void Reset()
+ {
+ if( m_node ) {
+ m_node->RevertToRevision( m_old_revision );
+ m_node = nullptr;
+ }
+ }
+
+ void Reset( NODE* node )
+ {
+ Reset();
+ if( node ) {
+ m_node = node;
+ m_old_revision = m_node->BranchMove();
+ }
+ }
+
+ ~SCOPED_BRANCH()
+ {
+ Reset();
+ }
+
+private:
+ NODE* m_node;
+ REVISION* m_old_revision;
+};
+
+
}
#endif
diff --git a/pcbnew/router/pns_placement_algo.h b/pcbnew/router/pns_placement_algo.h
index e7a9540..2756829 100644
--- a/pcbnew/router/pns_placement_algo.h
+++ b/pcbnew/router/pns_placement_algo.h
@@ -59,6 +59,13 @@ public:
virtual bool Start( const VECTOR2I& aP, ITEM* aStartItem ) = 0;
/**
+ * Function Cancel()
+ *
+ * Cancels the active placement
+ */
+ virtual void Cancel() = 0;
+
+ /**
* Function Move()
*
* Moves the end of the currently routed primtive(s) to the point aP, taking
@@ -68,7 +75,7 @@ public:
virtual bool Move( const VECTOR2I& aP, ITEM* aEndItem ) = 0;
/**
- * Function FixRoute()
+ * Function CommitRoute()
*
* Commits the currently routed items to the parent node, taking
* aP as the final end point and aEndItem as the final anchor (if provided).
@@ -76,7 +83,7 @@ public:
* result is violating design rules - in such case, the track is only committed
* if Settings.CanViolateDRC() is on.
*/
- virtual bool FixRoute( const VECTOR2I& aP, ITEM* aEndItem ) = 0;
+ virtual bool CommitRoute( const VECTOR2I& aP, ITEM* aEndItem ) = 0;
/**
* Function ToggleVia()
diff --git a/pcbnew/router/pns_revision.cpp b/pcbnew/router/pns_revision.cpp
index 2a793c8..8c31c39 100644
--- a/pcbnew/router/pns_revision.cpp
+++ b/pcbnew/router/pns_revision.cpp
@@ -60,7 +60,7 @@ namespace PNS {
}
}
- void CHANGE_SET::Add( const ITEM* aItem )
+ void CHANGE_SET::Add( ITEM* aItem )
{
auto it = std::find( m_removed_items.begin(), m_removed_items.end(), aItem );
if( it != m_removed_items.end() )
@@ -73,7 +73,7 @@ namespace PNS {
}
}
- void CHANGE_SET::Remove( const ITEM* aItem )
+ void CHANGE_SET::Remove( ITEM* aItem )
{
auto it = std::find( m_added_items.begin(), m_added_items.end(), aItem );
@@ -87,10 +87,11 @@ namespace PNS {
}
}
- CHANGE_SET CHANGE_SET::FromPath( std::vector< const REVISION* > aPath )
+ CHANGE_SET CHANGE_SET::FromPath( const REVISION_PATH& aPath )
{
CHANGE_SET result;
- std::reverse( aPath.begin(), aPath.end() );
+ auto copy = aPath; // fixme
+ std::reverse( copy.begin(), copy.end() );
for( auto diffstate : aPath ) {
result.Apply( diffstate );
@@ -133,6 +134,20 @@ namespace PNS {
{
}
+ void REVISION::Clear()
+ {
+ m_added_items.clear();
+ m_removed_items.clear();
+ m_branches.clear();
+ }
+
+ CHANGE_SET REVISION::GetRevisionChanges() const
+ {
+ CHANGE_SET changes;
+ changes.Apply( this );
+ return changes;
+ }
+
void REVISION::AddItem( std::unique_ptr< ITEM > aItem )
{
m_added_items.push_back( std::move( aItem ) );
@@ -200,6 +215,13 @@ namespace PNS {
aDiff->m_added_items.clear();
}
+ REVISION* REVISION::Revert()
+ {
+ auto result = m_parent;
+ m_parent->RemoveBranch( this );
+ return result;
+ }
+
REVISION * REVISION::Squash()
{
assert( m_parent );
@@ -246,9 +268,9 @@ namespace PNS {
return m_added_items.size() + m_removed_items.size();
}
- std::vector<const REVISION*> REVISION::Path( const REVISION * aAncestor ) const
+ REVISION_PATH REVISION::Path( const REVISION * aAncestor ) const
{
- std::vector< const REVISION* > result;
+ REVISION_PATH result;
const REVISION* state = this;
while( state != aAncestor )
diff --git a/pcbnew/router/pns_revision.h b/pcbnew/router/pns_revision.h
index db8d4a8..c57e188 100644
--- a/pcbnew/router/pns_revision.h
+++ b/pcbnew/router/pns_revision.h
@@ -38,6 +38,9 @@ namespace PNS {
class ITEM;
class REVISION;
+ /// Note: Paths are directed towards roots
+ using REVISION_PATH = std::vector< const REVISION* >;
+
///
/// Class SEQUENCE
/// Wraps up a [start, end) iterator sequence.
@@ -78,7 +81,7 @@ namespace PNS {
class CHANGE_SET {
private:
- using ITEMS_CONTAINER = std::vector< const ITEM* >;
+ using ITEMS_CONTAINER = std::vector< ITEM* >;
public:
using ITEM_ITERATOR = ITEMS_CONTAINER::iterator;
@@ -89,10 +92,10 @@ namespace PNS {
void Apply ( const REVISION* aState );
void Revert( const REVISION* aState );
- void Add ( const ITEM* aItem );
- void Remove( const ITEM* aItem );
+ void Add ( ITEM* aItem );
+ void Remove( ITEM* aItem );
- static CHANGE_SET FromPath( std::vector< const REVISION* > aPath );
+ static CHANGE_SET FromPath( const REVISION_PATH& aPath );
SEQUENCE< ITEM_ITERATOR > AddedItems();
SEQUENCE< CONST_ITEM_ITERATOR > AddedItems() const;
@@ -154,6 +157,10 @@ namespace PNS {
*/
bool IsShadowed( const ITEM* aItem );
+ CHANGE_SET GetRevisionChanges() const;
+ REVISION* Revert();
+ void Clear();
+
/**
* Function Squash
* Squash this revision into parent.
@@ -218,7 +225,7 @@ namespace PNS {
* @note Undefined behaviour if aAncestor is not an ancestor of this revision
* @pre Parent()[->Parent()*] == aAncestor
*/
- std::vector< const REVISION* > Path( const REVISION* aAncestor ) const;
+ REVISION_PATH Path( const REVISION* aAncestor ) const;
//
@@ -242,6 +249,8 @@ namespace PNS {
std::vector< ITEM* > m_removed_items;
};
+
+
}
#endif
diff --git a/pcbnew/router/pns_router.cpp b/pcbnew/router/pns_router.cpp
index 1a72718..9c2efd0 100644
--- a/pcbnew/router/pns_router.cpp
+++ b/pcbnew/router/pns_router.cpp
@@ -65,6 +65,7 @@ namespace PNS {
static ROUTER* theRouter;
ROUTER::ROUTER()
+ : m_node( &m_world )
{
theRouter = this;
@@ -73,7 +74,6 @@ ROUTER::ROUTER()
m_mode = PNS_MODE_ROUTE_SINGLE;
// Initialize all other variables:
- m_lastNode = nullptr;
m_iterLimit = 0;
m_showInterSteps = false;
m_snapshotIter = 0;
@@ -98,21 +98,19 @@ ROUTER::~ROUTER()
void ROUTER::SyncWorld( )
{
ClearWorld();
+ m_iface->SyncWorld( &m_node );
+// m_node.BranchMove();
+}
- m_world = std::unique_ptr< NODE >( new NODE );
- m_iface->SyncWorld( m_world.get() );
-
+void ROUTER::ResetWorld()
+{
+ m_node.RevertToRevision( &m_world );
}
void ROUTER::ClearWorld()
{
- if( m_world )
- {
- m_world->KillChildren();
- m_world.reset();
- }
-
m_placer.reset();
+ m_node.RevertToRevision( &m_world );
}
@@ -124,12 +122,7 @@ bool ROUTER::RoutingInProgress() const
const ITEM_SET ROUTER::QueryHoverItems( const VECTOR2I& aP )
{
- if( m_state == IDLE )
- return m_world->HitTest( aP );
- else
- {
- return m_placer->CurrentNode()->HitTest( aP );
- }
+ return m_node.HitTest( aP );
}
bool ROUTER::StartDragging( const VECTOR2I& aP, ITEM* aStartItem )
@@ -138,7 +131,7 @@ bool ROUTER::StartDragging( const VECTOR2I& aP, ITEM* aStartItem )
return false;
m_dragger.reset( new DRAGGER( this ) );
- m_dragger->SetWorld( m_world.get() );
+ m_dragger->SetWorld( &m_node );
m_dragger->SetDebugDecorator ( m_iface->GetDebugDecorator () );
if( m_dragger->Start ( aP, aStartItem ) )
@@ -272,12 +265,12 @@ void ROUTER::updateView( NODE* aNode, ITEM_SET& aCurrent )
if( Settings().Mode() == RM_MarkObstacles )
markViolations( aNode, aCurrent, removed );
- aNode->GetUpdatedItems( removed, added );
+ CHANGE_SET changes = CHANGE_SET::FromPath( m_node.Path( &m_world ) );
- for ( auto item : added )
+ for ( auto item : changes.AddedItems() )
m_iface->DisplayItem( item );
- for ( auto item : removed )
+ for ( auto item : changes.RemovedItems() )
m_iface->HideItem ( item );
}
@@ -319,35 +312,34 @@ void ROUTER::movePlacing( const VECTOR2I& aP, ITEM* aEndItem )
}
-void ROUTER::CommitRouting( NODE* aNode )
+void ROUTER::CommitRouting()
{
- NODE::ITEM_VECTOR removed, added;
+ m_node.SquashToParentRevision( &m_world );
+ CHANGE_SET changes = m_node.GetRevisionChanges();
- aNode->GetUpdatedItems( removed, added );
-
- for ( auto item : removed )
+ for ( auto item : changes.RemovedItems() )
m_iface->RemoveItem ( item );
- for ( auto item : added )
+ for ( auto item : changes.AddedItems() )
m_iface->AddItem( item );
m_iface->Commit();
- m_world->Commit( aNode );
+ m_node.Squash();
}
-bool ROUTER::FixRoute( const VECTOR2I& aP, ITEM* aEndItem )
+bool ROUTER::CommitRoute( const VECTOR2I& aP, ITEM* aEndItem )
{
bool rv = false;
switch( m_state )
{
case ROUTE_TRACK:
- rv = m_placer->FixRoute( aP, aEndItem );
+ rv = m_placer->CommitRoute( aP, aEndItem );
break;
case DRAG_SEGMENT:
- rv = m_dragger->FixRoute();
+ rv = m_dragger->CommitRoute();
break;
default:
@@ -378,14 +370,18 @@ void ROUTER::StopRouting()
if( !RoutingInProgress() )
return;
+ if( m_placer ) {
+ m_placer->Cancel();
+ }
+
m_placer.reset();
m_dragger.reset();
m_iface->EraseView();
m_state = IDLE;
- m_world->KillChildren();
- m_world->ClearRanks();
+ m_node.RevertToRevision( &m_world );
+ m_node.ClearRanks();
}
diff --git a/pcbnew/router/pns_router.h b/pcbnew/router/pns_router.h
index 66b0e52..8662f0a 100644
--- a/pcbnew/router/pns_router.h
+++ b/pcbnew/router/pns_router.h
@@ -84,9 +84,9 @@ enum ROUTER_MODE {
virtual void SetRouter( ROUTER* aRouter ) = 0;
virtual void SyncWorld( NODE* aNode ) = 0;
virtual void AddItem( ITEM* aItem ) = 0;
- virtual void RemoveItem( ITEM* aItem ) = 0;
+ virtual void RemoveItem( const ITEM* aItem ) = 0;
virtual void DisplayItem( const ITEM* aItem, int aColor = -1, int aClearance = -1 ) = 0;
- virtual void HideItem( ITEM* aItem ) = 0;
+ virtual void HideItem( const ITEM* aItem ) = 0;
virtual void Commit() = 0;
// virtual void Abort () = 0;
@@ -118,6 +118,7 @@ public:
static ROUTER* GetInstance();
void ClearWorld();
+ void ResetWorld();
void SyncWorld();
void SetView( KIGFX::VIEW* aView );
@@ -125,15 +126,20 @@ public:
bool RoutingInProgress() const;
bool StartRouting( const VECTOR2I& aP, ITEM* aItem, int aLayer );
void Move( const VECTOR2I& aP, ITEM* aItem );
- bool FixRoute( const VECTOR2I& aP, ITEM* aItem );
+ bool CommitRoute( const VECTOR2I& aP, ITEM* aItem );
void StopRouting();
int GetClearance( const ITEM* aA, const ITEM* aB ) const;
- NODE* GetWorld() const
+ const NODE* GetWorld() const
{
- return m_world.get();
+ return &m_node;
+ }
+
+ NODE* GetWorld()
+ {
+ return &m_node;
}
void FlipPosture();
@@ -177,7 +183,7 @@ public:
ROUTING_SETTINGS& Settings() { return m_settings; }
- void CommitRouting( NODE* aNode );
+ void CommitRouting();
/**
* Applies stored settings.
@@ -251,8 +257,8 @@ private:
VECTOR2I m_currentEnd;
RouterState m_state;
- std::unique_ptr< NODE > m_world;
- NODE* m_lastNode;
+ REVISION m_world;
+ NODE m_node;
std::unique_ptr< PLACEMENT_ALGO > m_placer;
std::unique_ptr< DRAGGER > m_dragger;
diff --git a/pcbnew/router/pns_shove.cpp b/pcbnew/router/pns_shove.cpp
index a795780..c160c12 100644
--- a/pcbnew/router/pns_shove.cpp
+++ b/pcbnew/router/pns_shove.cpp
@@ -53,7 +53,7 @@ void SHOVE::replaceItems( ITEM* aOld, std::unique_ptr< ITEM > aNew )
m_affectedAreaSum = m_affectedAreaSum ? m_affectedAreaSum->Merge( *changed_area ) : *changed_area;
}
- m_currentNode->Replace( aOld, std::move( aNew ) );
+ m_node->Replace( aOld, std::move( aNew ) );
}
void SHOVE::replaceLine( LINE& aOld, LINE& aNew )
@@ -65,7 +65,7 @@ void SHOVE::replaceLine( LINE& aOld, LINE& aNew )
m_affectedAreaSum = m_affectedAreaSum ? m_affectedAreaSum->Merge( *changed_area ) : *changed_area;
}
- m_currentNode->Replace( aOld, aNew );
+ m_node->Replace( aOld, aNew );
}
int SHOVE::getClearance( const ITEM* aA, const ITEM* aB ) const
@@ -73,7 +73,7 @@ int SHOVE::getClearance( const ITEM* aA, const ITEM* aB ) const
if( m_forceClearance >= 0 )
return m_forceClearance;
- return m_currentNode->GetClearance( aA, aB );
+ return m_node->GetClearance( aA, aB );
}
@@ -88,8 +88,7 @@ SHOVE::SHOVE( NODE* aWorld, ROUTER* aRouter ) :
ALGO_BASE( aRouter )
{
m_forceClearance = -1;
- m_root = aWorld;
- m_currentNode = aWorld;
+ m_node = aWorld;
// Initialize other temporary variables:
m_draggedVia = NULL;
@@ -105,7 +104,7 @@ SHOVE::~SHOVE()
LINE SHOVE::assembleLine( const SEGMENT* aSeg, int* aIndex )
{
- return m_currentNode->AssembleLine( const_cast<SEGMENT*>( aSeg ), aIndex, true );
+ return m_node->AssembleLine( const_cast<SEGMENT*>( aSeg ), aIndex, true );
}
// A dumb function that checks if the shoved line is shoved the right way, e.g.
@@ -150,7 +149,7 @@ SHOVE::SHOVE_STATUS SHOVE::walkaroundLoneVia( LINE& aCurrent, LINE& aObstacle,
aShoved.SetShape( shortest );
- if( m_currentNode->CheckColliding( &aShoved, &aCurrent ) )
+ if( m_node->CheckColliding( &aShoved, &aCurrent ) )
return SH_INCOMPLETE;
return SH_OK;
@@ -228,15 +227,15 @@ SHOVE::SHOVE_STATUS SHOVE::processHullSet( LINE& aCurrent, LINE& aObstacle,
continue;
}
- bool colliding = m_currentNode->CheckColliding( &l, &aCurrent, ITEM::ANY_T, m_forceClearance );
+ bool colliding = m_node->CheckColliding( &l, &aCurrent, ITEM::ANY_T, m_forceClearance );
if( ( aCurrent.Marker() & MK_HEAD ) && !colliding )
{
- JOINT* jtStart = m_currentNode->FindJoint( aCurrent.CPoint( 0 ), &aCurrent );
+ JOINT* jtStart = m_node->FindJoint( aCurrent.CPoint( 0 ), &aCurrent );
for( ITEM* item : jtStart->LinkList() )
{
- if( m_currentNode->CheckColliding( item, &l ) )
+ if( m_node->CheckColliding( item, &l ) )
colliding = true;
}
}
@@ -411,14 +410,14 @@ SHOVE::SHOVE_STATUS SHOVE::onCollidingLine( LINE& aCurrent, LINE& aObstacle )
SHOVE::SHOVE_STATUS SHOVE::onCollidingSolid( LINE& aCurrent, ITEM* aObstacle )
{
- WALKAROUND walkaround( m_currentNode, Router() );
+ WALKAROUND walkaround( m_node, Router() );
LINE walkaroundLine( aCurrent );
if( aCurrent.EndsWithVia() )
{
VIA vh = aCurrent.Via();
VIA* via = NULL;
- JOINT* jtStart = m_currentNode->FindJoint( vh.Pos(), &aCurrent );
+ JOINT* jtStart = m_node->FindJoint( vh.Pos(), &aCurrent );
if( !jtStart )
return SH_INCOMPLETE;
@@ -432,11 +431,11 @@ SHOVE::SHOVE_STATUS SHOVE::onCollidingSolid( LINE& aCurrent, ITEM* aObstacle )
}
}
- if( via && m_currentNode->CheckColliding( via, aObstacle ) )
+ if( via && m_node->CheckColliding( via, aObstacle ) )
return onCollidingVia( aObstacle, via );
}
- TOPOLOGY topo( m_currentNode );
+ TOPOLOGY topo( m_node );
std::set<ITEM*> cluster = topo.AssembleCluster( aObstacle, aCurrent.Layers().Start() );
@@ -472,20 +471,20 @@ SHOVE::SHOVE_STATUS SHOVE::onCollidingSolid( LINE& aCurrent, ITEM* aObstacle )
}
- WALKAROUND::WALKAROUND_STATUS status = walkaround.Route( aCurrent, walkaroundLine, false );
+ WALKAROUND::WALKAROUND_STATUS status = walkaround.Route( aCurrent, walkaroundLine, false );
if( status != WALKAROUND::DONE )
continue;
walkaroundLine.ClearSegmentLinks();
walkaroundLine.Unmark();
- walkaroundLine.Line().Simplify();
+ walkaroundLine.Line().Simplify();
- if( walkaroundLine.HasLoops() )
+ if( walkaroundLine.HasLoops() )
continue;
- if( aCurrent.Marker() & MK_HEAD )
- {
+ if( aCurrent.Marker() & MK_HEAD )
+ {
walkaroundLine.Mark( MK_HEAD );
if( m_multiLineMode )
@@ -494,13 +493,13 @@ SHOVE::SHOVE_STATUS SHOVE::onCollidingSolid( LINE& aCurrent, ITEM* aObstacle )
m_newHead = walkaroundLine;
}
- sanityCheck( &aCurrent, &walkaroundLine );
+ sanityCheck( &aCurrent, &walkaroundLine );
if( !m_lineStack.empty() )
{
LINE lastLine = m_lineStack.front();
- if( m_currentNode->CheckColliding( &lastLine, &walkaroundLine ) )
+ if( m_node->CheckColliding( &lastLine, &walkaroundLine ) )
{
LINE dummy( lastLine );
@@ -546,22 +545,29 @@ bool SHOVE::reduceSpringback( const ITEM_SET& aHeadSet )
{
SPRINGBACK_TAG spTag = m_nodeStack.back();
- if( !spTag.m_node->CheckColliding( aHeadSet ) )
+ REVISION* old_revision = m_node->GetRevision();
+ m_node->CheckoutAncestor( spTag.m_revision );
+
+ if( !m_node->CheckColliding( aHeadSet ) )
{
rv = true;
-
- delete spTag.m_node;
m_nodeStack.pop_back();
+ m_node->ClearBranches();
}
else
- break;
+ {
+ m_node->CheckoutDescendant( old_revision );
+ assert( m_node->GetRevision() == old_revision );
+ break;
+ }
+
}
return rv;
}
-bool SHOVE::pushSpringback( NODE* aNode, const ITEM_SET& aHeadItems,
+bool SHOVE::pushSpringback( REVISION* aRevision, const ITEM_SET& aHeadItems,
const COST_ESTIMATOR& aCost, const OPT_BOX2I& aAffectedArea )
{
SPRINGBACK_TAG st;
@@ -570,8 +576,8 @@ bool SHOVE::pushSpringback( NODE* aNode, const ITEM_SET& aHeadItems,
if( !m_nodeStack.empty() )
prev_area = m_nodeStack.back().m_affectedArea;
- st.m_node = aNode;
- st.m_cost = aCost;
+ st.m_revision = aRevision;
+ st.m_cost = aCost;
st.m_headItems = aHeadItems;
if( aAffectedArea )
@@ -593,7 +599,7 @@ SHOVE::SHOVE_STATUS SHOVE::pushVia( VIA* aVia, const VECTOR2I& aForce, int aCurr
{
LINE_PAIR_VEC draggedLines;
VECTOR2I p0( aVia->Pos() );
- JOINT* jt = m_currentNode->FindJoint( p0, aVia );
+ JOINT* jt = m_node->FindJoint( p0, aVia );
VECTOR2I p0_pushed( p0 + aForce );
if( !jt )
@@ -610,7 +616,7 @@ SHOVE::SHOVE_STATUS SHOVE::pushVia( VIA* aVia, const VECTOR2I& aForce, int aCurr
while( aForce.x != 0 || aForce.y != 0 )
{
- JOINT* jt_next = m_currentNode->FindJoint( p0_pushed, aVia );
+ JOINT* jt_next = m_node->FindJoint( p0_pushed, aVia );
if( !jt_next )
break;
@@ -697,7 +703,7 @@ SHOVE::SHOVE_STATUS SHOVE::pushVia( VIA* aVia, const VECTOR2I& aForce, int aCurr
}
else
{
- m_currentNode->Remove( lp.first );
+ m_node->Remove( lp.first );
}
#ifdef DEBUG
@@ -765,7 +771,7 @@ SHOVE::SHOVE_STATUS SHOVE::onReverseCollidingVia( LINE& aCurrent, VIA* aObstacle
LINE cur( aCurrent );
cur.ClearSegmentLinks();
- JOINT* jt = m_currentNode->FindJoint( aObstacleVia->Pos(), aObstacleVia );
+ JOINT* jt = m_node->FindJoint( aObstacleVia->Pos(), aObstacleVia );
LINE shoved( aCurrent );
shoved.ClearSegmentLinks();
@@ -931,7 +937,7 @@ SHOVE::SHOVE_STATUS SHOVE::shoveIteration( int aIter )
for( int i = 0; i < 3; i++ )
{
- nearest = m_currentNode->NearestObstacle( ¤tLine, search_order[i] );
+ nearest = m_node->NearestObstacle( ¤tLine, search_order[i] );
if( nearest )
break;
@@ -956,7 +962,7 @@ SHOVE::SHOVE_STATUS SHOVE::shoveIteration( int aIter )
VIA* revVia = (VIA*) ni;
wxLogTrace( "PNS", "iter %d: reverse-collide-via", aIter );
- if( currentLine.EndsWithVia() && m_currentNode->CheckColliding( ¤tLine.Via(), revVia ) )
+ if( currentLine.EndsWithVia() && m_node->CheckColliding( ¤tLine.Via(), revVia ) )
{
st = SH_INCOMPLETE;
}
@@ -1031,8 +1037,8 @@ SHOVE::SHOVE_STATUS SHOVE::shoveMainLoop()
m_affectedAreaSum = OPT_BOX2I();
- wxLogTrace( "PNS", "ShoveStart [root: %d jts, current: %d jts]", m_root->JointCount(),
- m_currentNode->JointCount() );
+ wxLogTrace( "PNS", "ShoveStart [root: %d jts, current: %d jts]", m_node->JointCount(), // fixme
+ m_node->JointCount() );
int iterLimit = Settings().ShoveIterationLimit();
TIME_LIMIT timeLimit = Settings().ShoveTimeLimit();
@@ -1099,16 +1105,14 @@ SHOVE::SHOVE_STATUS SHOVE::ShoveLines( const LINE& aCurrentHead )
reduceSpringback( headSet );
- NODE* parent = m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
+ SCOPED_BRANCH branch( m_node );
+ m_node->ClearRanks();
+ m_node->Add( head );
- m_currentNode = parent->Branch();
- m_currentNode->ClearRanks();
- m_currentNode->Add( head );
-
- m_currentNode->LockJoint( head.CPoint(0), &head, true );
+ m_node->LockJoint( head.CPoint(0), &head, true );
if( !head.EndsWithVia() )
- m_currentNode->LockJoint( head.CPoint( -1 ), &head, true );
+ m_node->LockJoint( head.CPoint( -1 ), &head, true );
head.Mark( MK_HEAD );
head.SetRank( 100000 );
@@ -1118,18 +1122,15 @@ SHOVE::SHOVE_STATUS SHOVE::ShoveLines( const LINE& aCurrentHead )
if( head.EndsWithVia() )
{
- std::unique_ptr< VIA >headVia = Clone( head.Via() );
+ std::unique_ptr< VIA > headVia = Clone( head.Via() );
headVia->Mark( MK_HEAD );
headVia->SetRank( 100000 );
m_logger.Log( headVia.get(), 0, "head-via" );
- m_currentNode->Add( std::move( headVia ) );
+ m_node->Add( std::move( headVia ) );
}
if( !pushLine( head ) )
{
- delete m_currentNode;
- m_currentNode = parent;
-
return SH_INCOMPLETE;
}
@@ -1137,28 +1138,31 @@ SHOVE::SHOVE_STATUS SHOVE::ShoveLines( const LINE& aCurrentHead )
if( st == SH_OK )
{
- runOptimizer( m_currentNode );
+ runOptimizer( m_node );
if( m_newHead )
- st = m_currentNode->CheckColliding( &( *m_newHead ) ) ? SH_INCOMPLETE : SH_HEAD_MODIFIED;
+ st = m_node->CheckColliding( &( *m_newHead ) ) ? SH_INCOMPLETE : SH_HEAD_MODIFIED;
else
- st = m_currentNode->CheckColliding( &head ) ? SH_INCOMPLETE : SH_OK;
+ st = m_node->CheckColliding( &head ) ? SH_INCOMPLETE : SH_OK;
}
- m_currentNode->RemoveByMarker( MK_HEAD );
+ m_node->RemoveByMarker( MK_HEAD );
wxLogTrace( "PNS", "Shove status : %s after %d iterations",
( ( st == SH_OK || st == SH_HEAD_MODIFIED ) ? "OK" : "FAILURE"), m_iter );
if( st == SH_OK || st == SH_HEAD_MODIFIED )
{
- pushSpringback( m_currentNode, headSet, COST_ESTIMATOR(), m_affectedAreaSum );
+ // it seems inefficient, but if nothing changed then the next iteration will
+ // revert the pushed revision anyways and this way we get springing back to
+ // the root revision without additional effort (at least most of the times).
+ // Delay a proper implementation for times with less urgent problems.
+ // (and then use m_noode->GetRevision()->NumChanges() here)
+ pushSpringback( m_node->GetRevision(), headSet, COST_ESTIMATOR(), m_affectedAreaSum );
+ branch.Release();
}
else
{
- delete m_currentNode;
-
- m_currentNode = parent;
m_newHead = OPT_LINE();
}
@@ -1201,10 +1205,9 @@ SHOVE::SHOVE_STATUS SHOVE::ShoveMultiLines( const ITEM_SET& aHeadSet )
reduceSpringback( headSet );
- NODE* parent = m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
+ SCOPED_BRANCH branch( m_node );
+ m_node->ClearRanks();
- m_currentNode = parent->Branch();
- m_currentNode->ClearRanks();
int n = 0;
for( const ITEM* item : aHeadSet.CItems() )
@@ -1213,7 +1216,7 @@ SHOVE::SHOVE_STATUS SHOVE::ShoveMultiLines( const ITEM_SET& aHeadSet )
LINE head( *headOrig );
head.ClearSegmentLinks();
- m_currentNode->Add( head );
+ m_node->Add( head );
head.Mark( MK_HEAD );
head.SetRank( 100000 );
@@ -1230,7 +1233,7 @@ SHOVE::SHOVE_STATUS SHOVE::ShoveMultiLines( const ITEM_SET& aHeadSet )
headVia->Mark( MK_HEAD );
headVia->SetRank( 100000 );
m_logger.Log( headVia.get(), 0, "head-via" );
- m_currentNode->Add( std::move( headVia ) );
+ m_node->Add( std::move( headVia ) );
}
}
@@ -1240,23 +1243,23 @@ SHOVE::SHOVE_STATUS SHOVE::ShoveMultiLines( const ITEM_SET& aHeadSet )
st = shoveMainLoop();
if( st == SH_OK )
- runOptimizer( m_currentNode );
+ runOptimizer( m_node );
- m_currentNode->RemoveByMarker( MK_HEAD );
+ m_node->RemoveByMarker( MK_HEAD );
wxLogTrace( "PNS", "Shove status : %s after %d iterations",
( st == SH_OK ? "OK" : "FAILURE"), m_iter );
if( st == SH_OK )
{
- pushSpringback( m_currentNode, ITEM_SET(), COST_ESTIMATOR(), m_affectedAreaSum );
+ pushSpringback( m_node->GetRevision(), ITEM_SET(), COST_ESTIMATOR(), m_affectedAreaSum );
}
else
{
- delete m_currentNode;
- m_currentNode = parent;
+ branch.Reset();
}
+ branch.Release();
return st;
}
@@ -1272,14 +1275,8 @@ SHOVE::SHOVE_STATUS SHOVE::ShoveDraggingVia( VIA* aVia, const VECTOR2I& aWhere,
m_draggedVia = NULL;
m_draggedViaHeadSet.Clear();
- NODE* parent = m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
-
- m_currentNode = parent;
-
- parent = m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
-
- m_currentNode = parent->Branch();
- m_currentNode->ClearRanks();
+ SCOPED_BRANCH branch( m_node );
+ m_node->ClearRanks();
aVia->Mark( MK_HEAD );
@@ -1287,7 +1284,7 @@ SHOVE::SHOVE_STATUS SHOVE::ShoveDraggingVia( VIA* aVia, const VECTOR2I& aWhere,
st = shoveMainLoop();
if( st == SH_OK )
- runOptimizer( m_currentNode );
+ runOptimizer( m_node );
if( st == SH_OK || st == SH_HEAD_MODIFIED )
{
@@ -1297,7 +1294,7 @@ SHOVE::SHOVE_STATUS SHOVE::ShoveDraggingVia( VIA* aVia, const VECTOR2I& aWhere,
*aNewVia = m_draggedVia;
}
- pushSpringback( m_currentNode, m_draggedViaHeadSet, COST_ESTIMATOR(), m_affectedAreaSum );
+ pushSpringback( m_node->GetRevision(), m_draggedViaHeadSet, COST_ESTIMATOR(), m_affectedAreaSum );
}
else
{
@@ -1306,10 +1303,10 @@ SHOVE::SHOVE_STATUS SHOVE::ShoveDraggingVia( VIA* aVia, const VECTOR2I& aWhere,
*aNewVia = nullptr;
}
- delete m_currentNode;
- m_currentNode = parent;
+ branch.Reset();
}
+ branch.Release();
return st;
}
@@ -1394,22 +1391,22 @@ void SHOVE::runOptimizer( NODE* aNode )
NODE* SHOVE::CurrentNode()
{
- return m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
+ return m_node;
}
const LINE SHOVE::NewHead() const
{
assert( m_newHead );
-
return *m_newHead;
}
void SHOVE::SetInitialLine( LINE& aInitial )
{
- m_root = m_root->Branch();
- m_root->Remove( aInitial );
+ // fixme? Add working branch?
+ m_node->BranchMove();
+ m_node->Remove( aInitial );
}
}
diff --git a/pcbnew/router/pns_shove.h b/pcbnew/router/pns_shove.h
index c25c993..00b4913 100644
--- a/pcbnew/router/pns_shove.h
+++ b/pcbnew/router/pns_shove.h
@@ -96,7 +96,7 @@ private:
int64_t m_length;
int m_segments;
VECTOR2I m_p;
- NODE* m_node;
+ REVISION* m_revision;
ITEM_SET m_headItems;
COST_ESTIMATOR m_cost;
OPT_BOX2I m_affectedArea;
@@ -106,7 +106,7 @@ private:
LINE& aShoved, const HULL_SET& hulls );
bool reduceSpringback( const ITEM_SET& aHeadItems );
- bool pushSpringback( NODE* aNode, const ITEM_SET& aHeadItems,
+ bool pushSpringback( REVISION* aRevision, const ITEM_SET& aHeadItems,
const COST_ESTIMATOR& aCost, const OPT_BOX2I& aAffectedArea );
SHOVE_STATUS walkaroundLoneVia( LINE& aCurrent, LINE& aObstacle, LINE& aShoved );
@@ -145,8 +145,7 @@ private:
std::vector<LINE> m_lineStack;
std::vector<LINE> m_optimizerQueue;
- NODE* m_root;
- NODE* m_currentNode;
+ NODE* m_node;
OPT_LINE m_newHead;
diff --git a/pcbnew/router/pns_tool_base.cpp b/pcbnew/router/pns_tool_base.cpp
index 0e99918..75a9b9d 100644
--- a/pcbnew/router/pns_tool_base.cpp
+++ b/pcbnew/router/pns_tool_base.cpp
@@ -318,7 +318,8 @@ void TOOL_BASE::updateEndItem( TOOL_EVENT& aEvent )
void TOOL_BASE::deleteTraces( ITEM* aStartItem, bool aWholeTrack )
{
- NODE *node = m_router->GetWorld()->Branch();
+ auto* node = m_router->GetWorld();
+ SCOPED_BRANCH branch( node );
if( !aStartItem )
return;
@@ -336,7 +337,8 @@ void TOOL_BASE::deleteTraces( ITEM* aStartItem, bool aWholeTrack )
node->Remove( ent.item );
}
- m_router->CommitRouting( node );
+ branch.Release();
+ m_router->CommitRouting();
}
diff --git a/pcbnew/router/pns_topology.cpp b/pcbnew/router/pns_topology.cpp
index 5eca29b..90bc39d 100644
--- a/pcbnew/router/pns_topology.cpp
+++ b/pcbnew/router/pns_topology.cpp
@@ -101,10 +101,10 @@ bool TOPOLOGY::LeadingRatLine( const LINE* aTrack, SHAPE_LINE_CHAIN& aRatLine )
if( !track.PointCount() )
return false;
- std::unique_ptr<NODE> tmpNode( m_world->Branch() );
- tmpNode->Add( track );
+ SCOPED_BRANCH temp_branch( m_world );
+ m_world->Add( track );
- JOINT* jt = tmpNode->FindJoint( track.CPoint( -1 ), &track );
+ JOINT* jt = m_world->FindJoint( track.CPoint( -1 ), &track );
if( !jt )
return false;
@@ -117,7 +117,7 @@ bool TOPOLOGY::LeadingRatLine( const LINE* aTrack, SHAPE_LINE_CHAIN& aRatLine )
{
int anchor;
- TOPOLOGY topo( tmpNode.get() );
+ TOPOLOGY topo( m_world );
ITEM* it = topo.NearestUnconnectedItem( jt, &anchor );
if( !it )
diff --git a/pcbnew/router/router_tool.cpp b/pcbnew/router/router_tool.cpp
index 2e62349..f0acbbc 100644
--- a/pcbnew/router/router_tool.cpp
+++ b/pcbnew/router/router_tool.cpp
@@ -564,7 +564,7 @@ void ROUTER_TOOL::performRouting()
updateEndItem( *evt );
bool needLayerSwitch = m_router->IsPlacingVia();
- if( m_router->FixRoute( m_endSnapPoint, m_endItem ) )
+ if( m_router->CommitRoute( m_endSnapPoint, m_endItem ) )
break;
if( needLayerSwitch )
@@ -604,7 +604,7 @@ void ROUTER_TOOL::performRouting()
{
bool still_routing = true;
while( still_routing )
- still_routing = m_router->FixRoute( m_endSnapPoint, m_endItem );
+ still_routing = m_router->CommitRoute( m_endSnapPoint, m_endItem );
break;
}
@@ -774,7 +774,7 @@ void ROUTER_TOOL::performDragging()
}
else if( evt->IsClick( BUT_LEFT ) )
{
- if( m_router->FixRoute( m_endSnapPoint, m_endItem ) )
+ if( m_router->CommitRoute( m_endSnapPoint, m_endItem ) )
{
modified = true;
break;
@@ -845,7 +845,7 @@ int ROUTER_TOOL::InlineDrag( const TOOL_EVENT& aEvent )
}
else if( evt->IsMouseUp( BUT_LEFT ) || evt->IsClick( BUT_LEFT ) )
{
- modified = m_router->FixRoute( p0, NULL );
+ modified = m_router->CommitRoute( p0, NULL );
break;
}
}
--
2.9.0.windows.1
>From 5c4bb9332c60228a2ba809d41fdbd9a226ec68a4 Mon Sep 17 00:00:00 2001
From: decimad <michste...@gmail.com>
Date: Tue, 30 Aug 2016 20:26:15 +0200
Subject: [PATCH] remove garbage items functionality (delete removed items
early) rename private remove helpers to reflect their task (moved
m_index-calls in)
---
pcbnew/router/pns_node.cpp | 59 +++++++++++++++-------------------------
pcbnew/router/pns_node.h | 12 ++++----
pcbnew/router/pns_optimizer.cpp | 5 +++-
pcbnew/router/pns_shove.cpp | 2 +-
pcbnew/router/pns_walkaround.cpp | 4 +++
5 files changed, 36 insertions(+), 46 deletions(-)
diff --git a/pcbnew/router/pns_node.cpp b/pcbnew/router/pns_node.cpp
index efd1b21..fbadc92 100644
--- a/pcbnew/router/pns_node.cpp
+++ b/pcbnew/router/pns_node.cpp
@@ -91,7 +91,6 @@ NODE::~NODE()
delete *i;
}
- releaseGarbage();
unlinkParent();
delete m_index;
@@ -529,7 +528,7 @@ const ITEM_SET NODE::HitTest( const VECTOR2I& aPoint ) const
}
-void NODE::addSolid( SOLID* aSolid )
+void NODE::addSolidIndex( SOLID* aSolid )
{
linkJoint( aSolid->Pos(), aSolid->Layers(), aSolid->Net(), aSolid );
m_index->Add( aSolid );
@@ -538,10 +537,10 @@ void NODE::addSolid( SOLID* aSolid )
void NODE::Add( std::unique_ptr< SOLID > aSolid )
{
aSolid->SetOwner( this );
- addSolid( aSolid.release() );
+ addSolidIndex( aSolid.release() );
}
-void NODE::addVia( VIA* aVia )
+void NODE::addViaIndex( VIA* aVia )
{
linkJoint( aVia->Pos(), aVia->Layers(), aVia->Net(), aVia );
m_index->Add( aVia );
@@ -550,7 +549,7 @@ void NODE::addVia( VIA* aVia )
void NODE::Add( std::unique_ptr< VIA > aVia )
{
aVia->SetOwner( this );
- addVia( aVia.release() );
+ addViaIndex( aVia.release() );
}
void NODE::Add( LINE& aLine, bool aAllowRedundant )
@@ -580,9 +579,10 @@ void NODE::Add( LINE& aLine, bool aAllowRedundant )
}
}
}
+ aLine.SetOwner( this );
}
-void NODE::addSegment( SEGMENT* aSeg )
+void NODE::addSegmentIndex( SEGMENT* aSeg )
{
linkJoint( aSeg->Seg().A, aSeg->Layers(), aSeg->Net(), aSeg );
linkJoint( aSeg->Seg().B, aSeg->Layers(), aSeg->Net(), aSeg );
@@ -602,7 +602,7 @@ void NODE::Add( std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant )
return;
aSegment->SetOwner( this );
- addSegment( aSegment.release() );
+ addSegmentIndex( aSegment.release() );
}
void NODE::Add( std::unique_ptr< ITEM > aItem, bool aAllowRedundant )
@@ -633,21 +633,18 @@ void NODE::Add( std::unique_ptr< ITEM > aItem, bool aAllowRedundant )
void NODE::doRemove( ITEM* aItem )
{
- // case 1: removing an item that is stored in the root node from any branch:
- // mark it as overridden, but do not remove
- if( aItem->BelongsTo( m_root ) && !isRoot() )
- m_override.insert( aItem );
+ // Can't remove items in non-leaf-revisions.
+ assert( !m_children.size() );
- // case 2: the item belongs to this branch or a parent, non-root branch,
- // or the root itself and we are the root: remove from the index
- else if( !aItem->BelongsTo( m_root ) || isRoot() )
- m_index->Remove( aItem );
+ // Can't remove items from child-revisions here
+ assert( aItem->Owner()->Depth() <= Depth() );
- // the item belongs to this particular branch: un-reference it
- if( aItem->BelongsTo( this ) )
- {
- aItem->SetOwner( NULL );
- m_root->m_garbageItems.insert( aItem );
+ if( aItem->Owner() == this ) {
+ delete aItem;
+ } else {
+ // if the item doesn't belong to this node, it must
+ // have been added in an ancestor revision.
+ m_override.insert( aItem );
}
}
@@ -656,6 +653,8 @@ void NODE::removeSegmentIndex( SEGMENT* aSeg )
{
unlinkJoint( aSeg->Seg().A, aSeg->Layers(), aSeg->Net(), aSeg );
unlinkJoint( aSeg->Seg().B, aSeg->Layers(), aSeg->Net(), aSeg );
+
+ m_index->Remove( aSeg );
}
void NODE::removeViaIndex( VIA* aVia )
@@ -703,11 +702,14 @@ void NODE::removeViaIndex( VIA* aVia )
if( item != aVia )
linkJoint( p, item->Layers(), net, item );
}
+
+ m_index->Remove( aVia );
}
void NODE::removeSolidIndex( SOLID* aSolid )
{
// fixme: this fucks up the joints, but it's only used for marking colliding obstacles for the moment, so we don't care.
+ m_index->Remove( aSolid );
}
@@ -1178,22 +1180,6 @@ void NODE::releaseChildren()
}
}
-
-void NODE::releaseGarbage()
-{
- if( !isRoot() )
- return;
-
- for( ITEM* item : m_garbageItems )
- {
- if( !item->BelongsTo( this ) )
- delete item;
- }
-
- m_garbageItems.clear();
-}
-
-
void NODE::Commit( NODE* aNode )
{
if( aNode->isRoot() )
@@ -1211,7 +1197,6 @@ void NODE::Commit( NODE* aNode )
}
releaseChildren();
- releaseGarbage();
}
diff --git a/pcbnew/router/pns_node.h b/pcbnew/router/pns_node.h
index e584e0c..a686d58 100644
--- a/pcbnew/router/pns_node.h
+++ b/pcbnew/router/pns_node.h
@@ -441,10 +441,11 @@ private:
int aNet, ITEM* aWhere );
///> helpers for adding/removing items
- void addSolid( SOLID* aSeg );
- void addSegment( SEGMENT* aSeg );
- void addVia( VIA* aVia );
-
+ void addSolidIndex( SOLID* aSeg );
+ void addSegmentIndex( SEGMENT* aSeg );
+ void addViaIndex( VIA* aVia );
+
+
void removeLine( LINE& aLine );
void removeSolidIndex( SOLID* aSeg );
void removeSegmentIndex( SEGMENT* aSeg );
@@ -453,7 +454,6 @@ private:
void doRemove( ITEM* aItem );
void unlinkParent();
void releaseChildren();
- void releaseGarbage();
bool isRoot() const
{
@@ -501,8 +501,6 @@ private:
///> depth of the node (number of parent nodes in the inheritance chain)
int m_depth;
-
- boost::unordered_set<ITEM*> m_garbageItems;
};
}
diff --git a/pcbnew/router/pns_optimizer.cpp b/pcbnew/router/pns_optimizer.cpp
index a916d7f..ab90fd7 100644
--- a/pcbnew/router/pns_optimizer.cpp
+++ b/pcbnew/router/pns_optimizer.cpp
@@ -545,6 +545,7 @@ bool OPTIMIZER::mergeFull( LINE* aLine )
step--;
}
+ aLine->ClearSegmentLinks(); /// @todo: WUT
aLine->SetShape( current_path );
return current_path.SegmentCount() < segs_pre;
@@ -555,8 +556,10 @@ bool OPTIMIZER::Optimize( LINE* aLine, LINE* aResult )
{
if( !aResult )
aResult = aLine;
- else
+ else {
*aResult = *aLine;
+ aResult->ClearSegmentLinks();
+ }
m_keepPostures = false;
diff --git a/pcbnew/router/pns_shove.cpp b/pcbnew/router/pns_shove.cpp
index 3bd3567..a795780 100644
--- a/pcbnew/router/pns_shove.cpp
+++ b/pcbnew/router/pns_shove.cpp
@@ -35,7 +35,6 @@
#include "pns_via.h"
#include "pns_utils.h"
#include "pns_router.h"
-#include "pns_shove.h"
#include "pns_utils.h"
#include "pns_topology.h"
@@ -173,6 +172,7 @@ SHOVE::SHOVE_STATUS SHOVE::processHullSet( LINE& aCurrent, LINE& aObstacle,
SHAPE_LINE_CHAIN path;
LINE l( aObstacle );
+ l.ClearSegmentLinks();
for( int i = 0; i < (int) aHulls.size(); i++ )
{
diff --git a/pcbnew/router/pns_walkaround.cpp b/pcbnew/router/pns_walkaround.cpp
index 3e26ea4..28db210 100644
--- a/pcbnew/router/pns_walkaround.cpp
+++ b/pcbnew/router/pns_walkaround.cpp
@@ -136,6 +136,7 @@ WALKAROUND::WALKAROUND_STATUS WALKAROUND::singleStep( LINE& aPath,
}
pnew.Simplify();
+ aPath.ClearSegmentLinks();
aPath.SetShape( pnew );
return IN_PROGRESS;
@@ -146,6 +147,9 @@ WALKAROUND::WALKAROUND_STATUS WALKAROUND::Route( const LINE& aInitialPath,
LINE& aWalkPath, bool aOptimize )
{
LINE path_cw( aInitialPath ), path_ccw( aInitialPath );
+ path_cw.ClearSegmentLinks();
+ path_ccw.ClearSegmentLinks();
+
WALKAROUND_STATUS s_cw = IN_PROGRESS, s_ccw = IN_PROGRESS;
SHAPE_LINE_CHAIN best_path;
--
2.9.0.windows.1
>From 30c70dbef9f061d00c907c243d7b8537a365870f Mon Sep 17 00:00:00 2001
From: decimad <michste...@gmail.com>
Date: Wed, 31 Aug 2016 00:45:01 +0200
Subject: [PATCH] Add class PNS::REVISION that will serve to factor revision
tree management out of PNS::NODE
---
pcbnew/router/CMakeLists.txt | 1 +
pcbnew/router/pns_revision.cpp | 293 +++++++++++++++++++++++++++++++++++++++++
pcbnew/router/pns_revision.h | 247 ++++++++++++++++++++++++++++++++++
3 files changed, 541 insertions(+)
create mode 100644 pcbnew/router/pns_revision.cpp
create mode 100644 pcbnew/router/pns_revision.h
diff --git a/pcbnew/router/CMakeLists.txt b/pcbnew/router/CMakeLists.txt
index be9b7c3..12de287 100644
--- a/pcbnew/router/CMakeLists.txt
+++ b/pcbnew/router/CMakeLists.txt
@@ -27,6 +27,7 @@ set( PCBNEW_PNS_SRCS
pns_meander_placer.cpp
pns_meander_placer_base.cpp
pns_meander_skew_placer.cpp
+ pns_revision.cpp
pns_node.cpp
pns_optimizer.cpp
pns_router.cpp
diff --git a/pcbnew/router/pns_revision.cpp b/pcbnew/router/pns_revision.cpp
new file mode 100644
index 0000000..2a793c8
--- /dev/null
+++ b/pcbnew/router/pns_revision.cpp
@@ -0,0 +1,293 @@
+/*
+* REVISION - helper class for the KiRouter
+*
+* Copyright (C) 2016 KiCad Developers, see AUTHORS.txt for contributors.
+* Author: Michael Steinberg <michste...@gmail.com>
+*
+* This program is free software: you can redistribute it and/or modify it
+* under the terms of the GNU General Public License as published by the
+* Free Software Foundation, either version 3 of the License, or (at your
+* option) any later version.
+*
+* This program is distributed in the hope that it will be useful, but
+* WITHOUT ANY WARRANTY; without even the implied warranty of
+* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+* General Public License for more details.
+*
+* You should have received a copy of the GNU General Public License along
+* with this program. If not, see <http://www.gnu.org/licenses/>.
+*/
+
+#include <cassert>
+#include <algorithm>
+#include "pns_item.h"
+#include "pns_revision.h"
+
+namespace PNS {
+
+ //
+ // CHANGE_SET
+ //
+ void CHANGE_SET::Clear()
+ {
+ m_added_items.clear();
+ m_removed_items.clear();
+ }
+
+ void CHANGE_SET::Apply( const REVISION* aState )
+ {
+ for( auto& item : aState->AddedItems() )
+ {
+ Add( item.get() );
+ }
+
+ for( auto item : aState->RemovedItems() )
+ {
+ Remove( item );
+ }
+ }
+
+ void CHANGE_SET::Revert( const REVISION* aState )
+ {
+ for( auto& item : aState->AddedItems() )
+ {
+ Remove( item.get() );
+ }
+
+ for( auto item : aState->RemovedItems() )
+ {
+ Add( item );
+ }
+ }
+
+ void CHANGE_SET::Add( const ITEM* aItem )
+ {
+ auto it = std::find( m_removed_items.begin(), m_removed_items.end(), aItem );
+ if( it != m_removed_items.end() )
+ {
+ m_removed_items.erase( it );
+ }
+ else
+ {
+ m_added_items.push_back( aItem );
+ }
+ }
+
+ void CHANGE_SET::Remove( const ITEM* aItem )
+ {
+ auto it = std::find( m_added_items.begin(), m_added_items.end(), aItem );
+
+ if( it != m_added_items.end() )
+ {
+ m_added_items.erase( it );
+ }
+ else
+ {
+ m_removed_items.push_back( aItem );
+ }
+ }
+
+ CHANGE_SET CHANGE_SET::FromPath( std::vector< const REVISION* > aPath )
+ {
+ CHANGE_SET result;
+ std::reverse( aPath.begin(), aPath.end() );
+
+ for( auto diffstate : aPath ) {
+ result.Apply( diffstate );
+ }
+
+ return result;
+ }
+
+ SEQUENCE< CHANGE_SET::ITEM_ITERATOR > CHANGE_SET::AddedItems()
+ {
+ return{ m_added_items.begin(), m_added_items.end() };
+ }
+
+ SEQUENCE< CHANGE_SET::CONST_ITEM_ITERATOR > CHANGE_SET::AddedItems() const
+ {
+ return{ m_added_items.begin(), m_added_items.end() };
+ }
+
+ SEQUENCE< CHANGE_SET::ITEM_ITERATOR > CHANGE_SET::RemovedItems()
+ {
+ return{ m_removed_items.begin(), m_removed_items.end() };
+ }
+
+ SEQUENCE< CHANGE_SET::CONST_ITEM_ITERATOR > CHANGE_SET::RemovedItems() const
+ {
+ return{ m_removed_items.begin(), m_removed_items.end() };
+ }
+
+
+ //
+ // DiffState
+ //
+
+ REVISION::REVISION()
+ : m_parent( nullptr )
+ {
+ }
+
+ REVISION::~REVISION()
+ {
+ }
+
+ void REVISION::AddItem( std::unique_ptr< ITEM > aItem )
+ {
+ m_added_items.push_back( std::move( aItem ) );
+ }
+
+ void REVISION::RemoveItem( ITEM* aItem )
+ {
+ auto it = std::find_if(
+ m_added_items.begin(),
+ m_added_items.end(),
+ [aItem]( const std::unique_ptr< ITEM >& ptr ) { return ptr.get() == aItem; }
+ );
+
+ if( it != m_added_items.end() )
+ {
+ m_added_items.erase( it );
+ }
+ else
+ {
+ // maybe check if the item is here already
+ m_removed_items.push_back( aItem );
+ }
+ }
+
+ bool REVISION::IsShadowed( const ITEM* aItem )
+ {
+ bool here = std::find( m_removed_items.begin(), m_removed_items.end(), aItem )
+ != m_removed_items.end();
+ return here || (m_parent && m_parent->IsShadowed( aItem ));
+ }
+
+ std::unique_ptr< REVISION > REVISION::ReleaseBranch( const REVISION* aBranch )
+ {
+ auto it = std::find_if(
+ m_branches.begin(),
+ m_branches.end(),
+ [aBranch]( const std::unique_ptr< REVISION >& ref ) { return ref.get() == aBranch; }
+ );
+
+ if( it != m_branches.end() )
+ {
+ auto ptr = std::move( *it );
+ m_branches.erase( it );
+ ptr->m_parent = nullptr;
+ return ptr;
+ }
+ else
+ {
+ return{};
+ }
+ }
+
+ void REVISION::Absorb( REVISION* aDiff )
+ {
+ for( auto* item_ptr : aDiff->m_removed_items )
+ {
+ RemoveItem( item_ptr );
+ }
+ aDiff->m_removed_items.clear();
+
+ for( auto& item_ptr : aDiff->m_added_items )
+ {
+ AddItem( std::move( item_ptr ) );
+ }
+ aDiff->m_added_items.clear();
+ }
+
+ REVISION * REVISION::Squash()
+ {
+ assert( m_parent );
+ m_parent->Absorb( this );
+
+ // Releasing this branch will set parent_ to nullptr, so copy it early.
+ auto parent = m_parent;
+ auto myself = m_parent->ReleaseBranch( this );
+
+ parent->ClearBranches();
+
+ parent->m_branches.insert( parent->m_branches.end(),
+ std::make_move_iterator( m_branches.begin() ),
+ std::make_move_iterator( m_branches.end() )
+ );
+
+ return parent;
+ }
+
+ void REVISION::ClearBranches()
+ {
+ m_branches.clear();
+ }
+
+ REVISION* REVISION::Branch()
+ {
+ m_branches.emplace_back( std::unique_ptr< REVISION >( new REVISION() ) );
+ m_branches.back()->m_parent = this;
+ return m_branches.back().get();
+ }
+
+ void REVISION::RemoveBranch( REVISION* aBranch )
+ {
+ ReleaseBranch( aBranch );
+ }
+
+ const REVISION* REVISION::Parent() const
+ {
+ return m_parent;
+ }
+
+ size_t REVISION::NumChanges() const
+ {
+ return m_added_items.size() + m_removed_items.size();
+ }
+
+ std::vector<const REVISION*> REVISION::Path( const REVISION * aAncestor ) const
+ {
+ std::vector< const REVISION* > result;
+ const REVISION* state = this;
+
+ while( state != aAncestor )
+ {
+ result.push_back( state );
+ state = state->Parent();
+ }
+
+ return result;
+ }
+
+ SEQUENCE< REVISION::ADDED_ITEM_ITERATOR > REVISION::AddedItems()
+ {
+ return{ m_added_items.begin(), m_added_items.end() };
+ }
+
+ SEQUENCE< REVISION::CONST_ADDED_ITEM_ITERATOR > REVISION::AddedItems() const
+ {
+ return{ m_added_items.begin(), m_added_items.end() };
+ }
+
+ SEQUENCE< REVISION::REMOVED_ITEM_ITERATOR> REVISION::RemovedItems()
+ {
+ return{ m_removed_items.begin(), m_removed_items.end() };
+ }
+
+ SEQUENCE< REVISION::CONST_REMOVED_ITEM_ITERATOR> REVISION::RemovedItems() const
+ {
+ return{ m_removed_items.begin(), m_removed_items.end() };
+ }
+
+ SEQUENCE< REVISION::BRANCH_ITERATOR > REVISION::Branches()
+ {
+ return{ m_branches.begin(), m_branches.end() };
+ }
+
+ SEQUENCE< REVISION::CONST_BRANCH_ITERATOR > REVISION::Branches() const
+ {
+ return{ m_branches.begin(), m_branches.end() };
+ }
+
+}
diff --git a/pcbnew/router/pns_revision.h b/pcbnew/router/pns_revision.h
new file mode 100644
index 0000000..db8d4a8
--- /dev/null
+++ b/pcbnew/router/pns_revision.h
@@ -0,0 +1,247 @@
+/*
+* REVISION - helper class for the KiRouter
+*
+* Copyright (C) 2016 KiCad Developers, see AUTHORS.txt for contributors.
+* Author: Michael Steinberg <michste...@gmail.com>
+*
+* This program is free software: you can redistribute it and/or modify it
+* under the terms of the GNU General Public License as published by the
+* Free Software Foundation, either version 3 of the License, or (at your
+* option) any later version.
+*
+* This program is distributed in the hope that it will be useful, but
+* WITHOUT ANY WARRANTY; without even the implied warranty of
+* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+* General Public License for more details.
+*
+* You should have received a copy of the GNU General Public License along
+* with this program. If not, see <http://www.gnu.org/licenses/>.
+*/
+
+#ifndef PNS_DIFF_STATE_H__
+#define PNS_DIFF_STATE_H__
+
+#include <memory>
+#include <vector>
+
+namespace PNS {
+
+ /// REVISION Overview
+ /// REVISIONs track the add-/remove-ITEM actions in form of a revision-tree and
+ /// manage the lifetime of the added ITEMs.
+ /// One can branch every revision, drop branches, squash changes into parent revisions etc.
+ /// The class helps implementing revisions of states with a dynamic set of immutable items,
+ /// as is the case with the spatial state of PNS::NODE, that is used throughout to implement
+ /// the push&shove routing.
+ /// -> Could possibly be made a template.
+
+ class ITEM;
+ class REVISION;
+
+ ///
+ /// Class SEQUENCE
+ /// Wraps up a [start, end) iterator sequence.
+ ///
+
+ template< typename ITERATOR >
+ class SEQUENCE
+ {
+ public:
+ SEQUENCE( ITERATOR aBegin, ITERATOR aEnd )
+ : m_begin( std::move( aBegin ) ), m_end( std::move( aEnd ) )
+ {}
+
+ SEQUENCE( SEQUENCE&& ) = default;
+ SEQUENCE& operator=( SEQUENCE&& ) = default;
+
+ size_t size() const {
+ return std::distance( m_begin, m_end );
+ }
+
+ const ITERATOR& begin() {
+ return m_begin;
+ }
+
+ const ITERATOR& end() {
+ return m_end;
+ }
+
+ private:
+ ITERATOR m_begin, m_end;
+ };
+
+ ///
+ /// Class CHANGE_SET
+ /// Holds aggregated changes over multiple revisions, non-owned items
+ /// Can be generated out of a revision-path.
+ ///
+
+ class CHANGE_SET {
+ private:
+ using ITEMS_CONTAINER = std::vector< const ITEM* >;
+
+ public:
+ using ITEM_ITERATOR = ITEMS_CONTAINER::iterator;
+ using CONST_ITEM_ITERATOR = ITEMS_CONTAINER::const_iterator;
+
+ public:
+ void Clear();
+ void Apply ( const REVISION* aState );
+ void Revert( const REVISION* aState );
+
+ void Add ( const ITEM* aItem );
+ void Remove( const ITEM* aItem );
+
+ static CHANGE_SET FromPath( std::vector< const REVISION* > aPath );
+
+ SEQUENCE< ITEM_ITERATOR > AddedItems();
+ SEQUENCE< CONST_ITEM_ITERATOR > AddedItems() const;
+
+ SEQUENCE< ITEM_ITERATOR > RemovedItems();
+ SEQUENCE< CONST_ITEM_ITERATOR > RemovedItems() const;
+
+ private:
+ ITEMS_CONTAINER m_added_items;
+ ITEMS_CONTAINER m_removed_items;
+ };
+
+ ///
+ /// Class REVISION
+ /// Tracks differences of world revisions and manages all ITEM's lifetimes
+ ///
+
+ class REVISION {
+ public:
+ REVISION();
+ ~REVISION();
+
+ private:
+ using ADDED_ITEMS_CONTAINER = std::vector< std::unique_ptr< ITEM > >;
+ using REMOVED_ITEMS_CONTAINER = std::vector< ITEM* >;
+ using BRANCHES_CONTAINER = std::vector< std::unique_ptr< REVISION > >;
+
+ public:
+ using ADDED_ITEM_ITERATOR = ADDED_ITEMS_CONTAINER::iterator;
+ using CONST_ADDED_ITEM_ITERATOR = ADDED_ITEMS_CONTAINER::const_iterator;
+
+ using REMOVED_ITEM_ITERATOR = REMOVED_ITEMS_CONTAINER::iterator;
+ using CONST_REMOVED_ITEM_ITERATOR = REMOVED_ITEMS_CONTAINER::const_iterator;
+
+ using BRANCH_ITERATOR = BRANCHES_CONTAINER::iterator;
+ using CONST_BRANCH_ITERATOR = BRANCHES_CONTAINER::const_iterator;
+
+ public:
+ /**
+ * Function AddItem
+ * Add an item to this revision. The revision tree takes ownership.
+ * @note Undefined behaviour if this revision is not a leaf.
+ * @param aItem to be added to the revision tree
+ */
+ void AddItem( std::unique_ptr< ITEM > aItem );
+
+ /**
+ * Function RemoveItem
+ * Remove aItem if it was added in this revision or shadow it otherwise
+ * @note Undefined behaviour if this revision is not a leaf.
+ * @param aItem to be be removed or shadowed in this revision's sub-tree
+ */
+ void RemoveItem( ITEM* aItem );
+
+ /**
+ * Function IsShadowed
+ * Checks if aItem is alive but shadowed (removed in a revision including this one)
+ * @return true iff the item is shadowed
+ */
+ bool IsShadowed( const ITEM* aItem );
+
+ /**
+ * Function Squash
+ * Squash this revision into parent.
+ * @note Undefined behaviour if this revision is a root revision
+ * @return REVISION* - parent of this revision.
+ * @pre Parent() != nullptr
+ * @post this revision is deleted
+ */
+ REVISION* Squash();
+
+ /**
+ * Function ClearBranches
+ * Remove all branches of this revision, thereby deleting all items introduced
+ * below this revision.
+ * @post Branches().size() == 0
+ */
+ void ClearBranches();
+
+ /**
+ * Function Branch
+ * Create a new branch of this revision and return a pointer to it.
+ * @return REVISION* pointer to the created branch
+ * @post retval->Parent() == this
+ */
+ REVISION* Branch();
+
+ /**
+ * Function RemoveBranch
+ * Remove a branch from this revision.
+ * @note Undefined behaviour if aBranch is not a branch of this revision.
+ * @param aBranch Pointer to a branch
+ */
+ void RemoveBranch( REVISION* aBranch );
+
+ /**
+ * Function ReleaseBranch
+ * Release a branch from this revision and return an owning pointer to it.
+ * @note Undefined behaviour if aBranch is not a branch of this revision.
+ * @param aBranch Pointer to a branch
+ * @return Owning pointer to the former branch.
+ */
+ std::unique_ptr< REVISION > ReleaseBranch( const REVISION* aBranch );
+
+ /**
+ * Function Parent
+ * Returns the parent of this branch or nullptr if this revision is a root
+ * @return Const pointer to parent revision or nullptr if root
+ */
+ const REVISION* Parent() const;
+
+ /**
+ * Function NumChanges
+ * Return the aggregate number of individual non-cancelling changes in this revision
+ * @return Aggregate number of individual non-cancelling changes in this revision
+ */
+ size_t NumChanges() const;
+
+ /**
+ * Function Path
+ * Returns a path of DIFF_STATEs from this revision to an ancestor revion. Paths are
+ * always directed towards the root of the revision tree.
+ * @note Undefined behaviour if aAncestor is not an ancestor of this revision
+ * @pre Parent()[->Parent()*] == aAncestor
+ */
+ std::vector< const REVISION* > Path( const REVISION* aAncestor ) const;
+
+
+ //
+ // Sequence accessors for { added items; removed items; branches }
+ //
+ SEQUENCE< ADDED_ITEM_ITERATOR > AddedItems();
+ SEQUENCE< CONST_ADDED_ITEM_ITERATOR > AddedItems() const;
+
+ SEQUENCE< REMOVED_ITEM_ITERATOR > RemovedItems();
+ SEQUENCE< CONST_REMOVED_ITEM_ITERATOR > RemovedItems() const;
+
+ SEQUENCE< BRANCH_ITERATOR > Branches();
+ SEQUENCE< CONST_BRANCH_ITERATOR > Branches() const;
+ private:
+ void Absorb( REVISION* aDiff );
+
+ REVISION* m_parent;
+ std::vector< std::unique_ptr< REVISION > > m_branches;
+
+ std::vector< std::unique_ptr< ITEM > > m_added_items;
+ std::vector< ITEM* > m_removed_items;
+ };
+
+}
+
+#endif
--
2.9.0.windows.1
_______________________________________________
Mailing list: https://launchpad.net/~kicad-developers
Post to : kicad-developers@lists.launchpad.net
Unsubscribe : https://launchpad.net/~kicad-developers
More help : https://help.launchpad.net/ListHelp
