source/libr2c2/trainroutemetric.cpp

   1 #include <list>
   2 #include "track.h"
   3 #include "trackchain.h"
   4 #include "trainroutemetric.h"
   5
   6 using namespace std;
   7
   8 namespace R2C2 {
   9
  10 TrainRouteMetric::TrainRouteMetric(const TrackChain &tc, TrackChain::Direction dir)
  11 {
  12         /* Initialize goals for tracks in the target chain.  We travel outwards from
  13         the target in the search phase so the iters appear to point the wrong way. */
  14         TrackChain::Direction reverse_dir = (dir==TrackChain::DOWN ? TrackChain::UP : TrackChain::DOWN);
  15         const TrackChain::TrackSet &ctracks = tc.get_tracks();
  16         for(TrackChain::TrackSet::const_iterator i=ctracks.begin(); i!=ctracks.end(); ++i)
  17         {
  18                 if(dir==TrackChain::UNSPECIFIED)
  19                 {
  20                         unsigned nls = (*i)->get_n_link_slots();
  21                         for(unsigned j=0; j<nls; ++j)
  22                                 if(Track *link = (*i)->get_link(j))
  23                                         if(!ctracks.count(link))
  24                                                 goals.push_back(TrackIter(*i, j));
  25                 }
  26                 else if(TrackIter iter = tc.iter_for(**i, reverse_dir))
  27                         goals.push_back(iter);
  28         }
  29
  30         list<TrackIter> queue;
  31         for(vector<Goal>::iterator i=goals.begin(); i!=goals.end(); ++i)
  32         {
  33                 tracks[Key(i->track.track(), i->track.entry())] = Data(0, &*i);
  34                 queue.push_back(i->track);
  35         }
  36
  37         /* Use Dijkstra's algorithm to find the shortest distance from the goal to
  38         every reachable track in the layout.  Entry points here become exit points
  39         when looking up distances to the goal. */
  40         while(!queue.empty())
  41         {
  42                 TrackIter track = queue.front();
  43                 queue.pop_front();
  44                 const Data &data = tracks[Key(track.track(), track.entry())];
  45
  46                 const TrackType::Endpoint &ep = track.endpoint();
  47                 for(unsigned i=0; ep.paths>>i; ++i)
  48                         if(ep.has_path(i))
  49                         {
  50                                 TrackIter next = track.next(i);
  51                                 if(!next)
  52                                         continue;
  53
  54                                 Data &target = tracks[Key(next.track(), next.entry())];
  55                                 float dist = data.distance+track->get_type().get_path_length(i);
  56                                 if(target.distance<0 || target.distance>dist)
  57                                 {
  58                                         target = Data(dist, data.goal);
  59                                         queue.push_back(next);
  60                                 }
  61                         }
  62         }
  63 }
  64
  65 void TrainRouteMetric::chain_to(const TrainRouteMetric &metric)
  66 {
  67         for(vector<Goal>::iterator i=goals.begin(); i!=goals.end(); ++i)
  68                 i->base_distance = metric.get_distance_from(*i->track.track(), i->track.entry());
  69 }
  70
  71 float TrainRouteMetric::get_distance_from(const Track &track) const
  72 {
  73         map<Key, Data>::const_iterator i = tracks.lower_bound(Key(&track, 0));
  74         map<Key, Data>::const_iterator j = tracks.upper_bound(Key(&track, 255));
  75
  76         float result = -1;
  77         for(; i!=j; ++i)
  78         {
  79                 float d = i->second.distance+i->second.goal->base_distance;
  80                 if(result<0 || d<result)
  81                         result = d;
  82         }
  83
  84         return result;
  85 }
  86
  87 float TrainRouteMetric::get_distance_from(const Track &track, unsigned exit) const
  88 {
  89         map<Key, Data>::const_iterator i = tracks.find(Key(&track, exit));
  90         if(i==tracks.end())
  91                 return -1;
  92
  93         return i->second.distance+i->second.goal->base_distance;
  94 }
  95
  96
  97 TrainRouteMetric::Goal::Goal():
  98         base_distance(0)
  99 { }
 100
 101 TrainRouteMetric::Goal::Goal(const TrackIter &t):
 102         track(t),
 103         base_distance(0)
 104 { }
 105
 106
 107 TrainRouteMetric::Data::Data():
 108         distance(-1),
 109         goal(0)
 110 { }
 111
 112 TrainRouteMetric::Data::Data(float d, const Goal *g):
 113         distance(d),
 114         goal(g)
 115 { }
 116
 117 } // namespace R2C2