From 8c7fc0b79ce88e0295e0e6ea52cb7eb753158d8a Mon Sep 17 00:00:00 2001
From: Mikko Rasa <tdb@tdb.fi>
Date: Mon, 23 Feb 2015 16:42:00 +0200
Subject: [PATCH] Rewrite goal initialization for TrainRouteMetric

The previous code incorrectly added all tracks as goals when a direction
was specified, instead of only the ends.  This caused cost estimate creep
in the route planner, resulting in suboptimal performance.
---
 source/libr2c2/trackchain.h         |  1 +
 source/libr2c2/trainroutemetric.cpp | 32 +++++++++++++++++------------
 source/libr2c2/zone.h               |  3 +--
 3 files changed, 21 insertions(+), 15 deletions(-)

diff --git a/source/libr2c2/trackchain.h b/source/libr2c2/trackchain.h
index 7102e56..74d1948 100644
--- a/source/libr2c2/trackchain.h
+++ b/source/libr2c2/trackchain.h
@@ -72,6 +72,7 @@ public:
 	bool has_track(Track &) const;
 	virtual TrackIter iter_for(Track &, Direction) const;
 	TrackIter get_end(unsigned) const;
+	virtual TrackIter get_end(Direction) const { return get_end(0); }
 	bool is_loop() const;
 
 private:
diff --git a/source/libr2c2/trainroutemetric.cpp b/source/libr2c2/trainroutemetric.cpp
index 1fc4fce..d3878d4 100644
--- a/source/libr2c2/trainroutemetric.cpp
+++ b/source/libr2c2/trainroutemetric.cpp
@@ -9,22 +9,28 @@ namespace R2C2 {
 
 TrainRouteMetric::TrainRouteMetric(const TrackChain &tc, TrackChain::Direction dir)
 {
-	/* Initialize goals for tracks in the target chain.  We travel outwards from
-	the target in the search phase so the iters appear to point the wrong way. */
-	TrackChain::Direction reverse_dir = (dir==TrackChain::DOWN ? TrackChain::UP : TrackChain::DOWN);
-	const TrackChain::TrackSet &ctracks = tc.get_tracks();
-	for(TrackChain::TrackSet::const_iterator i=ctracks.begin(); i!=ctracks.end(); ++i)
+	vector<TrackIter> ends;
+	if(dir==TrackChain::UNSPECIFIED)
 	{
-		if(dir==TrackChain::UNSPECIFIED)
+		for(unsigned i=0; i<2; ++i)
+			if(TrackIter end = tc.get_end(i))
+				ends.push_back(end);
+	}
+	else if(TrackIter end = tc.get_end(dir))
+		ends.push_back(end);
+
+	/* Initialize goals for the ends of the target chain.  We travel away from
+	the goals in the search phase so the iters appear to point the wrong way. */
+	for(vector<TrackIter>::const_iterator i=ends.begin(); i!=ends.end(); ++i)
+	{
+		const TrackType::Endpoint &ep = i->endpoint();
+		unsigned nls = (*i)->get_n_link_slots();
+		for(unsigned j=0; j<nls; ++j)
 		{
-			unsigned nls = (*i)->get_n_link_slots();
-			for(unsigned j=0; j<nls; ++j)
-				if(Track *link = (*i)->get_link(j))
-					if(!ctracks.count(link))
-						goals.push_back(TrackIter(*i, j));
+			TrackIter iter(i->track(), j);
+			if(ep.has_common_paths(iter.endpoint()))
+				goals.push_back(iter);
 		}
-		else if(TrackIter iter = tc.iter_for(**i, reverse_dir))
-			goals.push_back(iter);
 	}
 
 	list<TrackIter> queue;
diff --git a/source/libr2c2/zone.h b/source/libr2c2/zone.h
index fc44d4f..cee45e8 100644
--- a/source/libr2c2/zone.h
+++ b/source/libr2c2/zone.h
@@ -49,8 +49,7 @@ public:
 private:
 	TrackIter next_iter(const TrackIter &) const;
 public:
-	using TrackChain::get_end;
-	TrackIter get_end(Direction) const;
+	virtual TrackIter get_end(Direction) const;
 
 	void save(std::list<Msp::DataFile::Statement> &) const;
 	virtual Msp::DataFile::Statement save_reference() const;
-- 
2.45.2