+
+ return changes;
+}
+
+bool TrainRoutePlanner::RoutingStep::check_deadlocks() const
+{
+ for(vector<TrainRoutingState>::const_iterator i=trains.begin(); i!=trains.end(); ++i)
+ {
+ if(i->state!=BLOCKED)
+ continue;
+
+ if(i->blocked_by<0)
+ return true;
+
+ int slow = i->blocked_by;
+ int fast = trains[slow].blocked_by;
+ while(fast>=0 && trains[fast].blocked_by>=0)
+ {
+ if(fast==slow)
+ return true;
+
+ slow = trains[slow].blocked_by;
+ fast = trains[trains[fast].blocked_by].blocked_by;
+ }
+ }
+
+ return false;
+}
+
+int TrainRoutePlanner::RoutingStep::get_occupant(Track &track) const
+{
+ for(unsigned i=0; i<trains.size(); ++i)
+ if(trains[i].is_occupying(track))
+ return i;
+
+ return -1;
+}
+
+int TrainRoutePlanner::RoutingStep::find_next_train() const
+{
+ Time::TimeDelta min_dt;
+ int next_train = -1;
+ for(unsigned i=0; i<trains.size(); ++i)
+ if(trains[i].state==MOVING)
+ {
+ Time::TimeDelta dt = trains[i].get_time_to_next_track();
+ if(dt<min_dt || next_train<0)
+ {
+ min_dt = dt;
+ next_train = i;
+ }
+ }
+
+ return next_train;
+}
+
+void TrainRoutePlanner::RoutingStep::advance(const Time::TimeDelta &dt)
+{
+ time += dt;
+ for(vector<TrainRoutingState>::iterator i=trains.begin(); i!=trains.end(); ++i)
+ i->advance(dt);
+}
+
+void TrainRoutePlanner::RoutingStep::update_estimate()
+{
+ cost_estimate = Time::zero;
+ for(vector<TrainRoutingState>::const_iterator i=trains.begin(); i!=trains.end(); ++i)
+ if(i->remaining_estimate>=0)
+ cost_estimate += i->wait_time+((i->distance_traveled+i->remaining_estimate)/i->info->speed)*Time::sec;
+}
+
+bool TrainRoutePlanner::RoutingStep::is_viable() const
+{
+ for(vector<TrainRoutingState>::const_iterator i=trains.begin(); i!=trains.end(); ++i)
+ if(i->remaining_estimate<0)
+ return false;
+
+ for(vector<TrainRoutingState>::const_iterator i=trains.begin(); i!=trains.end(); ++i)
+ if(i->state==MOVING)
+ return true;
+
+ return false;