X-Git-Url: http://git.tdb.fi/?a=blobdiff_plain;f=source%2Flibmarklin%2Froute.cpp;h=befaa6de9245a9dbe5d36f02a3a333f265c14fc1;hb=9def58c4bbec8788430740a1e9afce64a496231f;hp=364509c8714d4b1aa94fc1340e3f4cbf993181ea;hpb=1ba0bd68483b900a702c7a38f41250b33770503d;p=r2c2.git diff --git a/source/libmarklin/route.cpp b/source/libmarklin/route.cpp index 364509c..befaa6d 100644 --- a/source/libmarklin/route.cpp +++ b/source/libmarklin/route.cpp @@ -1,26 +1,227 @@ /* $Id$ This file is part of the MSP Märklin suite -Copyright © 2007-2009 Mikkosoft Productions, Mikko Rasa +Copyright © 2007-2010 Mikkosoft Productions, Mikko Rasa Distributed under the GPL */ +#include +#include #include "layout.h" #include "route.h" #include "track.h" +#include "trackiter.h" #include "tracktype.h" using namespace std; using namespace Msp; +namespace { + +using namespace Marklin; + +typedef std::pair 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 &tracks; + + TrackInSet(const set &t): tracks(t) { } + + bool operator()(Track &t) const { return tracks.count(&t); } +}; + +template +list dijkstra(const TrackIter &from, const Pred &goal) +{ + map track_nodes; + priority_queue 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.endpoint().paths; + for(unsigned i=0; paths>>i; ++i) + if(paths&(1<get_type().get_path_length(i))); + } + } + + list result; + for(Node *node=final; node; node=node->prev) + result.push_front(&*node->track); + + return result; +} + +template +Route *create_route(const TrackIter &from, const Pred &goal) +{ + list tracks = dijkstra(from, goal); + + if(tracks.empty()) + return 0; + + Route *route = new Route(from->get_layout()); + for(list::iterator i=tracks.begin(); i!=tracks.end(); ++i) + route->add_track(**i); + + route->set_name("Pathfinder"); + route->set_temporary(true); + + return route; +} + +} + + namespace Marklin { -Route::Route(Layout &layout, const string &n): - name(n) +Route::Route(Layout &l): + layout(l), + temporary(false) { + layout.add_route(*this); layout.signal_track_removed.connect(sigc::mem_fun(this, &Route::track_removed)); } +Route::~Route() +{ + layout.remove_route(*this); +} + +void Route::set_name(const string &n) +{ + name = n; + signal_name_changed.emit(name); +} + +void Route::set_temporary(bool t) +{ + temporary = t; +} + +void Route::set_turnout(unsigned addr, unsigned path) +{ + if(!addr) + throw InvalidParameterValue("Invalid turnout address"); + map::iterator i = turnouts.find(addr); + if(i==turnouts.end()) + throw KeyError("Turnout is not in this route"); + if(i->second>=0 && path!=static_cast(i->second)) + throw InvalidState("Setting conflicts with route"); + i->second = path; +} + +void Route::update_turnouts() +{ + set found; + for(set::const_iterator i=tracks.begin(); i!=tracks.end(); ++i) + if(unsigned tid = (*i)->get_turnout_id()) + { + found.insert(tid); + + const vector &endpoints = (*i)->get_type().get_endpoints(); + const vector &links = (*i)->get_links(); + + // Build a combined path mask from linked endpoints + unsigned mask = 15; + for(unsigned j=0; jget_turnout_id()) + { + const TrackType::Endpoint &ep = links[j]->get_type().get_endpoint(links[j]->get_endpoint_by_link(**i)); + int p = get_turnout(tid2); + if(p>=0 && !(ep.paths&(1<>=1, ++path) ; + turnouts[tid] = path; + } + else if(!turnouts.count(tid)) + // More than one possible choice, and no existing entry - set as undecided + turnouts[tid] = -1; + } + + // Remove any turnouts that do not exist in the route + for(map::iterator i=turnouts.begin(); i!=turnouts.end();) + { + if(!found.count(i->first)) + turnouts.erase(i++); + else + ++i; + } +} + int Route::get_turnout(unsigned id) const { map::const_iterator i = turnouts.find(id); @@ -29,7 +230,18 @@ int Route::get_turnout(unsigned id) const return -1; } -void Route::add_track(const Track &trk) +unsigned Route::get_path(Track &trk) const +{ + if(unsigned tid = trk.get_turnout_id()) + { + map::const_iterator i = turnouts.find(tid); + if(i!=turnouts.end()) + return i->second; + } + return trk.get_active_path(); +} + +void Route::add_track(Track &trk) { if(tracks.count(&trk)) return; @@ -49,17 +261,17 @@ void Route::add_track(const Track &trk) update_turnouts(); } -void Route::add_tracks(const set &trks) +void Route::add_tracks(const set &trks) { - set pending; - for(set::const_iterator i=trks.begin(); i!=trks.end(); ++i) + set pending; + for(set::const_iterator i=trks.begin(); i!=trks.end(); ++i) if(!tracks.count(*i)) pending.insert(*i); while(!pending.empty()) { bool found = false; - for(set::const_iterator i=pending.begin(); i!=pending.end(); ++i) + for(set::const_iterator i=pending.begin(); i!=pending.end(); ++i) if(tracks.empty() || check_validity(**i)==7) { tracks.insert(*i); @@ -75,80 +287,68 @@ void Route::add_tracks(const set &trks) update_turnouts(); } -void Route::save(list &st) const -{ - for(map::const_iterator i=turnouts.begin(); i!=turnouts.end(); ++i) - st.push_back((DataFile::Statement("turnout"), i->first, i->second)); -} - -void Route::update_turnouts() +void Route::add_track_chain(Track &start, unsigned ep, const TurnoutMap &trnts) { - set found; - for(set::const_iterator i=tracks.begin(); i!=tracks.end(); ++i) - if(unsigned tid=(*i)->get_turnout_id()) - { - found.insert(tid); + TrackIter iter(&start, ep); + while(iter) + { + if(iter->get_type().is_dead_end()) + break; - const vector &endpoints = (*i)->get_type().get_endpoints(); - const vector &links = (*i)->get_links(); + if(has_track(*iter)) + break; - unsigned mask = 15; - for(unsigned j=0; jget_turnout_id()) - { - const Endpoint &ep = links[j]->get_type().get_endpoints()[links[j]->get_endpoint_by_link(**i)]; - int r = get_turnout(tid2); - if(r>=0 && !(ep.routes&(1<get_turnout_id()) + { + TurnoutMap::const_iterator i = trnts.find(iter->get_turnout_id()); + if(i==trnts.end()) + break; - if(!(mask&(mask-1))) - { - unsigned route = 0; - for(; (mask && !(mask&1)); mask>>=1, ++route) ; - turnouts[tid] = route; - } - else - turnouts[tid] = -1; + path = i->second; } - for(map::iterator i=turnouts.begin(); i!=turnouts.end();) - { - if(!found.count(i->first)) - turnouts.erase(i++); - else - ++i; + add_track(*iter); + + iter = iter.next(path); } } -unsigned Route::check_validity(const Track &trk) const +bool Route::has_track(Track &t) const +{ + return tracks.count(&t); +} + +void Route::save(list &st) const +{ + st.push_back((DataFile::Statement("name"), name)); + for(map::const_iterator i=turnouts.begin(); i!=turnouts.end(); ++i) + st.push_back((DataFile::Statement("turnout"), i->first, i->second)); +} + +unsigned Route::check_validity(Track &trk) const { unsigned result = 4; - for(set::const_iterator i=tracks.begin(); i!=tracks.end(); ++i) + for(set::const_iterator i=tracks.begin(); i!=tracks.end(); ++i) { int epi=(*i)->get_endpoint_by_link(trk); if(epi>=0) { + // Linked to an existing track - good result |= 1; - const vector &endpoints = (*i)->get_type().get_endpoints(); + const vector &endpoints = (*i)->get_type().get_endpoints(); if(unsigned tid=(*i)->get_turnout_id()) { int r = get_turnout(tid); if(r>=0) { - if(endpoints[epi].routes&(1< &links = (*i)->get_links(); int epj = -1; @@ -158,15 +358,19 @@ unsigned Route::check_validity(const Track &trk) const ++count; epj = k; } + + // Only good if at most one other track is linked to the turnout if(count<=1) { result |= 2; - if(epj>=0 && !(endpoints[epi].routes&endpoints[epj].routes)) + if(epj>=0 && !(endpoints[epi].paths&endpoints[epj].paths)) + // Impossible path through the turnout - not good result &= 3; } } } else + // Linked to something linear - good result |= 2; } } @@ -179,16 +383,62 @@ void Route::track_removed(Track &t) tracks.erase(&t); } +Route *Route::find(const TrackIter &from, Track &to) +{ + return create_route(from, TrackMatch(to)); +} + +Route *Route::find(const TrackIter &from, const Route &to) +{ + return create_route(from, TrackInSet(to.get_tracks())); +} + +Route *Route::find(const TrackIter &from, const set &to) +{ + return create_route(from, TrackInSet(to)); +} + Route::Loader::Loader(Route &r): DataFile::BasicLoader(r) { + add("name", &Route::name); add("turnout", &Loader::turnout); } -void Route::Loader::turnout(unsigned id, unsigned route) +void Route::Loader::finish() +{ + const set <racks = obj.layout.get_tracks(); + for(set::const_iterator i=ltracks.begin(); i!=ltracks.end(); ++i) + { + unsigned tid = (*i)->get_turnout_id(); + if(!tid) + continue; + + TurnoutMap::iterator j = turnouts.find(tid); + if(j==turnouts.end()) + continue; + + unsigned path_mask = 1<second; + const vector &eps = (*i)->get_type().get_endpoints(); + for(unsigned k=0; kget_link(k); + if(!obj.tracks.count(link)) + obj.add_track_chain(*link, link->get_endpoint_by_link(**i), turnouts); + if(!obj.tracks.count(*i)) + obj.add_track_chain(**i, k, turnouts); + break; + } + + break; + } +} + +void Route::Loader::turnout(unsigned id, unsigned path) { - obj.turnouts[id] = route; + turnouts[id] = path; } } // namespace Marklin