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