Make deadlock detection more robust

Deadlock cycles involving more than two trains can now be detected.

diff --git a/source/libr2c2/trainrouteplanner.cpp b/source/libr2c2/trainrouteplanner.cpp
index 45e83e267fb2b37e8b260630442e4a055089f667..e8b5d90107b59b7dad25a455d0f7d4bc678c2a5b 100644 (file)
--- a/source/libr2c2/trainrouteplanner.cpp
+++ b/source/libr2c2/trainrouteplanner.cpp
@@ -336,17 +336,24 @@ bool TrainRoutePlanner::RoutingStep::update_states()
 
 bool TrainRoutePlanner::RoutingStep::check_deadlocks() const
 {
-       for(unsigned i=0; i<trains.size(); ++i)
+       for(vector<TrainRoutingState>::const_iterator i=trains.begin(); i!=trains.end(); ++i)
        {
-               const TrainRoutingState &train = trains[i];
-               if(train.state!=BLOCKED)
+               if(i->state!=BLOCKED)
                        continue;
 
-               if(train.blocked_by<0)
+               if(i->blocked_by<0)
                        return true;
 
-               if(trains[train.blocked_by].blocked_by==static_cast<int>(i))
-                       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;