+namespace {
+
+using namespace Marklin;
+
+typedef std::pair<Track *, unsigned> Key;
+
+struct Node
+{
+ TrackIter track;
+ Node *prev;
+ float dist;
+
+ Node():
+ prev(0), dist(0)
+ { }
+
+ Node(const TrackIter &t):
+ track(t), prev(0), dist(0)
+ { }
+
+ Node(const TrackIter &t, Node &r, float d):
+ track(t), prev(&r), dist(prev->dist+d)
+ { }
+
+ bool operator<(const Node &other) const
+ { return dist>other.dist; }
+};
+
+struct TrackMatch
+{
+ Track &track;
+
+ TrackMatch(Track &t): track(t) { }
+
+ bool operator()(Track &t) const { return &t==&track; }
+};
+
+struct TrackInSet
+{
+ const set<Track *> &tracks;
+
+ TrackInSet(const set<Track *> &t): tracks(t) { }
+
+ bool operator()(Track &t) const { return tracks.count(&t); }
+};
+
+template<typename Pred>
+list<Track *> dijkstra(const TrackIter &from, const Pred &goal)
+{
+ map<Key, Node> track_nodes;
+ priority_queue<Node> nodes;
+ Node *final = 0;
+
+ nodes.push(from);
+
+ while(!nodes.empty())
+ {
+ Node lowest = nodes.top();
+ nodes.pop();
+
+ Key key(lowest.track.track(), lowest.track.entry());
+ if(track_nodes.count(key))
+ continue;
+
+ Node &ref = track_nodes[key] = lowest;
+ if(goal(*lowest.track))
+ {
+ final = &ref;
+ break;
+ }
+
+ unsigned paths = lowest.track->get_type().get_endpoints()[lowest.track.entry()].paths;
+ for(unsigned i=0; paths>>i; ++i)
+ if(paths&(1<<i))
+ {
+ TrackIter next = lowest.track.next(i);
+ if(!next)
+ continue;
+
+ if(track_nodes.count(Key(next.track(), next.entry())))
+ continue;
+
+ nodes.push(Node(next, ref, lowest.track->get_type().get_path_length(i)));
+ }
+ }
+
+ list<Track *> result;
+ for(Node *node=final; node; node=node->prev)
+ result.push_front(&*node->track);
+
+ return result;
+}
+
+template<typename Pred>
+Route *create_route(const TrackIter &from, const Pred &goal)
+{
+ list<Track *> tracks = dijkstra(from, goal);
+
+ if(tracks.empty())
+ return 0;
+
+ Route *route = new Route(from->get_layout());
+ for(list<Track *>::iterator i=tracks.begin(); i!=tracks.end(); ++i)
+ route->add_track(**i);
+
+ route->set_name("Pathfinder");
+ route->set_temporary(true);
+
+ return route;
+}
+
+}
+
+