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) { return &t==&track; }
54 template<typename Pred>
55 list<const Track *> dijkstra(const Track &from, unsigned ep, Pred goal)
57 // XXX Fails to find some routes - should use track+ep as key
58 map<const Track *, Node> track_nodes;
59 priority_queue<Node> nodes;
62 nodes.push(Node(from, ep));
66 Node lowest = nodes.top();
69 if(track_nodes.count(lowest.track))
72 Node &ref = track_nodes[lowest.track] = lowest;
73 if(goal(*lowest.track))
79 const TrackType &type = lowest.track->get_type();
80 const vector<Endpoint> &eps = type.get_endpoints();
81 const vector<Track *> &links = lowest.track->get_links();
82 for(unsigned i=0; i<eps.size(); ++i)
84 if(i==lowest.ep || !links[i] || track_nodes.count(links[i]))
87 unsigned mask = eps[i].paths&eps[lowest.ep].paths;
92 for(; !(mask&1); ++path, mask>>=1) ;
93 nodes.push(Node(*links[i], links[i]->get_endpoint_by_link(*lowest.track), ref, type.get_path_length(path)));
98 throw InvalidParameterValue("Could not find a route");
100 list<const Track *> result;
101 for(Node *node=final; node; node=node->prev)
102 result.push_front(node->track);
112 Route::Route(Layout &l, const string &n):
116 layout.add_route(*this);
117 layout.signal_track_removed.connect(sigc::mem_fun(this, &Route::track_removed));
122 layout.remove_route(*this);
125 int Route::get_turnout(unsigned id) const
127 map<unsigned, int>::const_iterator i = turnouts.find(id);
128 if(i!=turnouts.end())
133 void Route::add_track(const Track &trk)
135 if(tracks.count(&trk))
140 unsigned valid = check_validity(trk);
142 throw Exception("Not linked to existing tracks");
144 throw Exception("Branching routes not allowed");
146 throw Exception("Route must be smooth");
153 void Route::add_tracks(const set<const Track *> &trks)
155 set<const Track *> pending;
156 for(set<const Track *>::const_iterator i=trks.begin(); i!=trks.end(); ++i)
157 if(!tracks.count(*i))
160 while(!pending.empty())
163 for(set<const Track *>::const_iterator i=pending.begin(); i!=pending.end(); ++i)
164 if(tracks.empty() || check_validity(**i)==7)
173 throw Exception("Could not add all tracks to route");
179 void Route::save(list<DataFile::Statement> &st) const
181 for(map<unsigned, int>::const_iterator i=turnouts.begin(); i!=turnouts.end(); ++i)
182 st.push_back((DataFile::Statement("turnout"), i->first, i->second));
185 void Route::update_turnouts()
188 for(set<const Track *>::const_iterator i=tracks.begin(); i!=tracks.end(); ++i)
189 if(unsigned tid=(*i)->get_turnout_id())
193 const vector<Endpoint> &endpoints = (*i)->get_type().get_endpoints();
194 const vector<Track *> &links = (*i)->get_links();
196 // Build a combined path mask from linked endpoints
198 for(unsigned j=0; j<endpoints.size(); ++j)
200 if(!tracks.count(links[j]))
203 if(unsigned tid2=links[j]->get_turnout_id())
205 const Endpoint &ep = links[j]->get_type().get_endpoints()[links[j]->get_endpoint_by_link(**i)];
206 int p = get_turnout(tid2);
207 if(p>=0 && !(ep.paths&(1<<p)))
209 // The linked track is a turnout and has a path which is incompatible with this endpoint
210 mask &= ~endpoints[j].paths;
214 mask &= endpoints[j].paths;
217 if(mask && !(mask&(mask-1)))
219 // Exactly one possible choice, set the path accordingly
221 for(; (mask && !(mask&1)); mask>>=1, ++path) ;
222 turnouts[tid] = path;
224 else if(!turnouts.count(tid))
225 // More than one possible choice, and no existing entry - set as undecided
229 // Remove any turnouts that do not exist in the route
230 for(map<unsigned, int>::iterator i=turnouts.begin(); i!=turnouts.end();)
232 if(!found.count(i->first))
239 unsigned Route::check_validity(const Track &trk) const
242 for(set<const Track *>::const_iterator i=tracks.begin(); i!=tracks.end(); ++i)
244 int epi=(*i)->get_endpoint_by_link(trk);
247 // Linked to an existing track - good
249 const vector<Endpoint> &endpoints = (*i)->get_type().get_endpoints();
250 if(unsigned tid=(*i)->get_turnout_id())
252 int r = get_turnout(tid);
255 // Linking to a turnout with path set is only good if we're continuing that path
256 if(endpoints[epi].paths&(1<<r))
261 // Linked to a turnout with no path set - find out other linked tracks
263 const vector<Track *> &links = (*i)->get_links();
265 for(unsigned k=0; k<endpoints.size(); ++k)
266 if(tracks.count(links[k]))
272 // Only good if at most one other track is linked to the turnout
276 if(epj>=0 && !(endpoints[epi].paths&endpoints[epj].paths))
277 // Impossible path through the turnout - not good
283 // Linked to something linear - good
291 void Route::track_removed(Track &t)
296 Route *Route::find(const Track &from, unsigned ep, const Track &to)
299 list<const Track *> tracks = dijkstra(from, ep, goal);
301 static unsigned n = 0;
302 Route *route = new Route(from.get_layout(), format("Route::find %d", ++n));
303 for(list<const Track *>::iterator i=tracks.begin(); i!=tracks.end(); ++i)
304 route->add_track(**i);
310 Route::Loader::Loader(Route &r):
311 DataFile::BasicLoader<Route>(r)
313 add("turnout", &Loader::turnout);
316 void Route::Loader::turnout(unsigned id, unsigned path)
318 obj.turnouts[id] = path;
321 } // namespace Marklin