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