3 This file is part of the MSP Märklin suite
4 Copyright © 2007-2010 Mikkosoft Productions, Mikko Rasa
5 Distributed under the GPL
9 #include <msp/strings/formatter.h>
13 #include "tracktype.h"
20 using namespace Marklin;
30 track(0), ep(0), prev(0), dist(0)
33 Node(const Track &t, unsigned e):
34 track(&t), ep(e), prev(0), dist(0)
37 Node(const Track &t, unsigned e, Node &r, float d):
38 track(&t), ep(e), prev(&r), dist(prev->dist+d)
41 bool operator<(const Node &other) const
42 { return dist>other.dist; }
49 TrackMatch(const Track &t): track(t) { }
51 bool operator()(const Track &t) const { return &t==&track; }
58 TrackInRoute(const Route &r): route(r) { }
60 bool operator()(const Track &t) const { return route.get_tracks().count(&t); }
63 template<typename Pred>
64 list<const Track *> dijkstra(const Track &from, unsigned ep, const Pred &goal)
66 // XXX Fails to find some routes - should use track+ep as key
67 map<const Track *, Node> track_nodes;
68 priority_queue<Node> nodes;
71 nodes.push(Node(from, ep));
75 Node lowest = nodes.top();
78 if(track_nodes.count(lowest.track))
81 Node &ref = track_nodes[lowest.track] = lowest;
82 if(goal(*lowest.track))
88 const TrackType &type = lowest.track->get_type();
89 const vector<Endpoint> &eps = type.get_endpoints();
90 const vector<Track *> &links = lowest.track->get_links();
91 for(unsigned i=0; i<eps.size(); ++i)
93 if(i==lowest.ep || !links[i] || track_nodes.count(links[i]))
96 unsigned mask = eps[i].paths&eps[lowest.ep].paths;
101 for(; !(mask&1); ++path, mask>>=1) ;
102 nodes.push(Node(*links[i], links[i]->get_endpoint_by_link(*lowest.track), ref, type.get_path_length(path)));
107 throw InvalidParameterValue("Could not find a route");
109 list<const Track *> result;
110 for(Node *node=final; node; node=node->prev)
111 result.push_front(node->track);
118 template<typename Pred>
119 Route *create_route(const Track &from, unsigned ep, const Pred &goal)
121 list<const Track *> tracks = dijkstra(from, ep, goal);
123 Route *route = new Route(from.get_layout(), format("-%d-", ++count));
124 for(list<const Track *>::iterator i=tracks.begin(); i!=tracks.end(); ++i)
125 route->add_track(**i);
135 Route::Route(Layout &l, const string &n):
139 layout.add_route(*this);
140 layout.signal_track_removed.connect(sigc::mem_fun(this, &Route::track_removed));
145 layout.remove_route(*this);
148 int Route::get_turnout(unsigned id) const
150 map<unsigned, int>::const_iterator i = turnouts.find(id);
151 if(i!=turnouts.end())
156 void Route::add_track(const Track &trk)
158 if(tracks.count(&trk))
163 unsigned valid = check_validity(trk);
165 throw Exception("Not linked to existing tracks");
167 throw Exception("Branching routes not allowed");
169 throw Exception("Route must be smooth");
176 void Route::add_tracks(const set<const Track *> &trks)
178 set<const Track *> pending;
179 for(set<const Track *>::const_iterator i=trks.begin(); i!=trks.end(); ++i)
180 if(!tracks.count(*i))
183 while(!pending.empty())
186 for(set<const Track *>::const_iterator i=pending.begin(); i!=pending.end(); ++i)
187 if(tracks.empty() || check_validity(**i)==7)
196 throw Exception("Could not add all tracks to route");
202 void Route::save(list<DataFile::Statement> &st) const
204 for(map<unsigned, int>::const_iterator i=turnouts.begin(); i!=turnouts.end(); ++i)
205 st.push_back((DataFile::Statement("turnout"), i->first, i->second));
208 void Route::update_turnouts()
211 for(set<const Track *>::const_iterator i=tracks.begin(); i!=tracks.end(); ++i)
212 if(unsigned tid=(*i)->get_turnout_id())
216 const vector<Endpoint> &endpoints = (*i)->get_type().get_endpoints();
217 const vector<Track *> &links = (*i)->get_links();
219 // Build a combined path mask from linked endpoints
221 for(unsigned j=0; j<endpoints.size(); ++j)
223 if(!tracks.count(links[j]))
226 if(unsigned tid2=links[j]->get_turnout_id())
228 const Endpoint &ep = links[j]->get_type().get_endpoints()[links[j]->get_endpoint_by_link(**i)];
229 int p = get_turnout(tid2);
230 if(p>=0 && !(ep.paths&(1<<p)))
232 // The linked track is a turnout and has a path which is incompatible with this endpoint
233 mask &= ~endpoints[j].paths;
237 mask &= endpoints[j].paths;
240 if(mask && !(mask&(mask-1)))
242 // Exactly one possible choice, set the path accordingly
244 for(; (mask && !(mask&1)); mask>>=1, ++path) ;
245 turnouts[tid] = path;
247 else if(!turnouts.count(tid))
248 // More than one possible choice, and no existing entry - set as undecided
252 // Remove any turnouts that do not exist in the route
253 for(map<unsigned, int>::iterator i=turnouts.begin(); i!=turnouts.end();)
255 if(!found.count(i->first))
262 unsigned Route::check_validity(const Track &trk) const
265 for(set<const Track *>::const_iterator i=tracks.begin(); i!=tracks.end(); ++i)
267 int epi=(*i)->get_endpoint_by_link(trk);
270 // Linked to an existing track - good
272 const vector<Endpoint> &endpoints = (*i)->get_type().get_endpoints();
273 if(unsigned tid=(*i)->get_turnout_id())
275 int r = get_turnout(tid);
278 // Linking to a turnout with path set is only good if we're continuing that path
279 if(endpoints[epi].paths&(1<<r))
284 // Linked to a turnout with no path set - find out other linked tracks
286 const vector<Track *> &links = (*i)->get_links();
288 for(unsigned k=0; k<endpoints.size(); ++k)
289 if(tracks.count(links[k]))
295 // Only good if at most one other track is linked to the turnout
299 if(epj>=0 && !(endpoints[epi].paths&endpoints[epj].paths))
300 // Impossible path through the turnout - not good
306 // Linked to something linear - good
314 void Route::track_removed(Track &t)
319 Route *Route::find(const Track &from, unsigned ep, const Track &to)
321 return create_route(from, ep, TrackMatch(to));
324 Route *Route::find(const Track &from, unsigned ep, const Route &to)
326 return create_route(from, ep, TrackInRoute(to));
330 Route::Loader::Loader(Route &r):
331 DataFile::BasicLoader<Route>(r)
333 add("turnout", &Loader::turnout);
336 void Route::Loader::turnout(unsigned id, unsigned path)
338 obj.turnouts[id] = path;
341 } // namespace Marklin