]> git.tdb.fi Git - r2c2.git/blob - source/libmarklin/route.cpp
Add framework for generating simple meshes for vehicles
[r2c2.git] / source / libmarklin / route.cpp
1 /* $Id$
2
3 This file is part of the MSP Märklin suite
4 Copyright © 2007-2010  Mikkosoft Productions, Mikko Rasa
5 Distributed under the GPL
6 */
7
8 #include <queue>
9 #include <msp/strings/formatter.h>
10 #include "layout.h"
11 #include "route.h"
12 #include "track.h"
13 #include "trackiter.h"
14 #include "tracktype.h"
15
16 using namespace std;
17 using namespace Msp;
18
19 namespace {
20
21 using namespace Marklin;
22
23 typedef std::pair<Track *, unsigned> Key;
24
25 struct Node
26 {
27         TrackIter track;
28         Node *prev;
29         float dist;
30
31         Node():
32                 prev(0), dist(0)
33         { }
34
35         Node(const TrackIter &t):
36                 track(t), prev(0), dist(0)
37         { }
38
39         Node(const TrackIter &t, Node &r, float d):
40                 track(t), prev(&r), dist(prev->dist+d)
41         { }
42
43         bool operator<(const Node &other) const
44         { return dist>other.dist; }
45 };
46
47 struct TrackMatch
48 {
49         Track &track;
50
51         TrackMatch(Track &t): track(t) { }
52
53         bool operator()(Track &t) const { return &t==&track; }
54 };
55
56 struct TrackInSet
57 {
58         const set<Track *> &tracks;
59
60         TrackInSet(const set<Track *> &t): tracks(t) { }
61
62         bool operator()(Track &t) const { return tracks.count(&t); }
63 };
64
65 template<typename Pred>
66 list<Track *> dijkstra(const TrackIter &from, const Pred &goal)
67 {
68         map<Key, Node> track_nodes;
69         priority_queue<Node> nodes;
70         Node *final = 0;
71
72         nodes.push(from);
73
74         while(!nodes.empty())
75         {
76                 Node lowest = nodes.top();
77                 nodes.pop();
78
79                 Key key(lowest.track.track(), lowest.track.entry());
80                 if(track_nodes.count(key))
81                         continue;
82
83                 Node &ref = track_nodes[key] = lowest;
84                 if(goal(*lowest.track))
85                 {
86                         final = &ref;
87                         break;
88                 }
89
90                 unsigned paths = lowest.track.endpoint().paths;
91                 for(unsigned i=0; paths>>i; ++i)
92                         if(paths&(1<<i))
93                         {
94                                 TrackIter next = lowest.track.next(i);
95                                 if(!next)
96                                         continue;
97
98                                 if(track_nodes.count(Key(next.track(), next.entry())))
99                                         continue;
100
101                                 nodes.push(Node(next, ref, lowest.track->get_type().get_path_length(i)));
102                         }
103         }
104
105         list<Track *> result;
106         for(Node *node=final; node; node=node->prev)
107                 result.push_front(&*node->track);
108
109         return result;
110 }
111
112 template<typename Pred>
113 Route *create_route(const TrackIter &from, const Pred &goal)
114 {
115         list<Track *> tracks = dijkstra(from, goal);
116
117         if(tracks.empty())
118                 return 0;
119
120         Route *route = new Route(from->get_layout());
121         for(list<Track *>::iterator i=tracks.begin(); i!=tracks.end(); ++i)
122                 route->add_track(**i);
123
124         route->set_name("Pathfinder");
125         route->set_temporary(true);
126
127         return route;
128 }
129
130 }
131
132
133 namespace Marklin {
134
135 Route::Route(Layout &l):
136         layout(l),
137         temporary(false)
138 {
139         layout.add_route(*this);
140         layout.signal_track_removed.connect(sigc::mem_fun(this, &Route::track_removed));
141 }
142
143 Route::~Route()
144 {
145         layout.remove_route(*this);
146 }
147
148 void Route::set_name(const string &n)
149 {
150         name = n;
151         signal_name_changed.emit(name);
152 }
153
154 void Route::set_temporary(bool t)
155 {
156         temporary = t;
157 }
158
159 void Route::set_turnout(unsigned addr, unsigned path)
160 {
161         if(!addr)
162                 throw InvalidParameterValue("Invalid turnout address");
163         map<unsigned, int>::iterator i = turnouts.find(addr);
164         if(i==turnouts.end())
165                 throw KeyError("Turnout is not in this route");
166         if(i->second>=0 && path!=static_cast<unsigned>(i->second))
167                 throw InvalidState("Setting conflicts with route");
168         i->second = path;
169 }
170
171 void Route::update_turnouts()
172 {
173         set<unsigned> found;
174         for(set<Track *>::const_iterator i=tracks.begin(); i!=tracks.end(); ++i)
175                 if(unsigned tid = (*i)->get_turnout_id())
176                 {
177                         found.insert(tid);
178
179                         const vector<TrackType::Endpoint> &endpoints = (*i)->get_type().get_endpoints();
180                         const vector<Track *> &links = (*i)->get_links();
181
182                         // Build a combined path mask from linked endpoints
183                         unsigned mask = 15;
184                         for(unsigned j=0; j<endpoints.size(); ++j)
185                         {
186                                 if(!tracks.count(links[j]))
187                                         continue;
188
189                                 if(unsigned tid2 = links[j]->get_turnout_id())
190                                 {
191                                         const TrackType::Endpoint &ep = links[j]->get_type().get_endpoint(links[j]->get_endpoint_by_link(**i));
192                                         int p = get_turnout(tid2);
193                                         if(p>=0 && !(ep.paths&(1<<p)))
194                                         {
195                                                 // The linked track is a turnout and has a path which is incompatible with this endpoint
196                                                 mask &= ~endpoints[j].paths;
197                                                 continue;
198                                         }
199                                 }
200                                 mask &= endpoints[j].paths;
201                         }
202
203                         if(mask && !(mask&(mask-1)))
204                         {
205                                 // Exactly one possible choice, set the path accordingly
206                                 unsigned path = 0;
207                                 for(; (mask && !(mask&1)); mask>>=1, ++path) ;
208                                 turnouts[tid] = path;
209                         }
210                         else if(!turnouts.count(tid))
211                                 // More than one possible choice, and no existing entry - set as undecided
212                                 turnouts[tid] = -1;
213                 }
214
215         // Remove any turnouts that do not exist in the route
216         for(map<unsigned, int>::iterator i=turnouts.begin(); i!=turnouts.end();)
217         {
218                 if(!found.count(i->first))
219                         turnouts.erase(i++);
220                 else
221                         ++i;
222         }
223 }
224
225 int Route::get_turnout(unsigned id) const
226 {
227         map<unsigned, int>::const_iterator i = turnouts.find(id);
228         if(i!=turnouts.end())
229                 return i->second;
230         return -1;
231 }
232
233 unsigned Route::get_path(Track &trk) const
234 {
235         if(unsigned tid = trk.get_turnout_id())
236         {
237                 map<unsigned, int>::const_iterator i = turnouts.find(tid);
238                 if(i!=turnouts.end())
239                         return i->second;
240         }
241         return trk.get_active_path();
242 }
243
244 void Route::add_track(Track &trk)
245 {
246         if(tracks.count(&trk))
247                 return;
248
249         if(!tracks.empty())
250         {
251                 unsigned valid = check_validity(trk);
252                 if(!(valid&1))
253                         throw Exception("Not linked to existing tracks");
254                 else if(!(valid&2))
255                         throw Exception("Branching routes not allowed");
256                 else if(!(valid&4))
257                         throw Exception("Route must be smooth");
258         }
259
260         tracks.insert(&trk);
261         update_turnouts();
262 }
263
264 void Route::add_tracks(const set<Track *> &trks)
265 {
266         set<Track *> pending;
267         for(set<Track *>::const_iterator i=trks.begin(); i!=trks.end(); ++i)
268                 if(!tracks.count(*i))
269                         pending.insert(*i);
270
271         while(!pending.empty())
272         {
273                 bool found = false;
274                 for(set<Track *>::const_iterator i=pending.begin(); i!=pending.end(); ++i)
275                         if(tracks.empty() || check_validity(**i)==7)
276                         {
277                                 tracks.insert(*i);
278                                 pending.erase(*i);
279                                 found = true;
280                                 break;
281                         }
282
283                 if(!found)
284                         throw Exception("Could not add all tracks to route");
285         }
286
287         update_turnouts();
288 }
289
290 void Route::add_track_chain(Track &start, unsigned ep, const TurnoutMap &trnts)
291 {
292         TrackIter iter(&start, ep);
293         while(iter)
294         {
295                 if(iter->get_type().is_dead_end())
296                         break;
297
298                 if(has_track(*iter))
299                         break;
300
301                 int path = 0;
302                 if(iter->get_turnout_id())
303                 {
304                         TurnoutMap::const_iterator i = trnts.find(iter->get_turnout_id());
305                         if(i==trnts.end())
306                                 break;
307
308                         path = i->second;
309                 }
310
311                 add_track(*iter);
312
313                 iter = iter.next(path);
314         }
315 }
316
317 bool Route::has_track(Track &t) const
318 {
319         return tracks.count(&t);
320 }
321
322 void Route::save(list<DataFile::Statement> &st) const
323 {
324         st.push_back((DataFile::Statement("name"), name));
325         for(map<unsigned, int>::const_iterator i=turnouts.begin(); i!=turnouts.end(); ++i)
326                 st.push_back((DataFile::Statement("turnout"), i->first, i->second));
327 }
328
329 unsigned Route::check_validity(Track &trk) const
330 {
331         unsigned result = 4;
332         for(set<Track *>::const_iterator i=tracks.begin(); i!=tracks.end(); ++i)
333         {
334                 int epi=(*i)->get_endpoint_by_link(trk);
335                 if(epi>=0)
336                 {
337                         // Linked to an existing track - good
338                         result |= 1;
339                         const vector<TrackType::Endpoint> &endpoints = (*i)->get_type().get_endpoints();
340                         if(unsigned tid=(*i)->get_turnout_id())
341                         {
342                                 int r = get_turnout(tid);
343                                 if(r>=0)
344                                 {
345                                         // Linking to a turnout with path set is only good if we're continuing that path
346                                         if(endpoints[epi].paths&(1<<r))
347                                                 result |= 2;
348                                 }
349                                 else
350                                 {
351                                         // Linked to a turnout with no path set - find out other linked tracks 
352                                         unsigned count = 0;
353                                         const vector<Track *> &links = (*i)->get_links();
354                                         int epj = -1;
355                                         for(unsigned k=0; k<endpoints.size(); ++k)
356                                                 if(tracks.count(links[k]))
357                                                 {
358                                                         ++count;
359                                                         epj = k;
360                                                 }
361
362                                         // Only good if at most one other track is linked to the turnout
363                                         if(count<=1)
364                                         {
365                                                 result |= 2;
366                                                 if(epj>=0 && !(endpoints[epi].paths&endpoints[epj].paths))
367                                                         // Impossible path through the turnout - not good
368                                                         result &= 3;
369                                         }
370                                 }
371                         }
372                         else
373                                 // Linked to something linear - good
374                                 result |= 2;
375                 }
376         }
377
378         return result;
379 }
380
381 void Route::track_removed(Track &t)
382 {
383         tracks.erase(&t);
384 }
385
386 Route *Route::find(const TrackIter &from, Track &to)
387 {
388         return create_route(from, TrackMatch(to));
389 }
390
391 Route *Route::find(const TrackIter &from, const Route &to)
392 {
393         return create_route(from, TrackInSet(to.get_tracks()));
394 }
395
396 Route *Route::find(const TrackIter &from, const set<Track *> &to)
397 {
398         return create_route(from, TrackInSet(to));
399 }
400
401
402 Route::Loader::Loader(Route &r):
403         DataFile::BasicLoader<Route>(r)
404 {
405         add("name",    &Route::name);
406         add("turnout", &Loader::turnout);
407 }
408
409 void Route::Loader::finish()
410 {
411         const set<Track *> &ltracks = obj.layout.get_tracks();
412         for(set<Track *>::const_iterator i=ltracks.begin(); i!=ltracks.end(); ++i)
413         {
414                 unsigned tid = (*i)->get_turnout_id();
415                 if(!tid)
416                         continue;
417
418                 TurnoutMap::iterator j = turnouts.find(tid);
419                 if(j==turnouts.end())
420                         continue;
421
422                 unsigned path_mask = 1<<j->second;
423                 const vector<TrackType::Endpoint> &eps = (*i)->get_type().get_endpoints();
424                 for(unsigned k=0; k<eps.size(); ++k)
425                         if(eps[k].paths&path_mask)
426                         {
427                                 Track *link = (*i)->get_link(k);
428                                 if(!obj.tracks.count(link))
429                                         obj.add_track_chain(*link, link->get_endpoint_by_link(**i), turnouts);
430                                 if(!obj.tracks.count(*i))
431                                         obj.add_track_chain(**i, k, turnouts);
432                                 break;
433                         }
434
435                 break;
436         }
437 }
438
439 void Route::Loader::turnout(unsigned id, unsigned path)
440 {
441         turnouts[id] = path;
442 }
443
444 } // namespace Marklin