Skip to content

Overnight: Reversal on first day of timetable.dat goes wrong #29

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Open
koch-t opened this issue Jul 30, 2013 · 8 comments
Open

Overnight: Reversal on first day of timetable.dat goes wrong #29

koch-t opened this issue Jul 30, 2013 · 8 comments

Comments

@koch-t
Copy link
Contributor

koch-t commented Jul 30, 2013

When reversing a request departing at the first possible second in the timetable.dat, the reversal ends up in 1970

CONTEXT
n_stops: 2
n_routes: 1

STOPS
stop 0 at lat 0.000000 lon 0.000000
served by routes 0 
stop 1 at lat 0.000000 lon 0.000000
served by routes 0 

ROUTES
route 0
serves stops 0 1 

STOPIDS
stop 000 has id Stop 2a1 
stop 001 has id Stop 2a2 

ROUTEIDS, TRIPIDS
route 000 has id bus long and first trip id LEV1pL�R 
-- Router Request --
from:  Stop 2a1 [0]
to:    Stop 2a2 [1]
date:  2014-01-01
time:  00:00:00 [1388530800]
speed: 1.500000 m/sec
arrive-by: false
max xfers: 5
max time:     --   
-- Router Request --
from:  Stop 2a1 [0]
to:    Stop 2a2 [1]
date:  2014-01-01
time:  00:00:00 [1388530800]
speed: 1.500000 m/sec
arrive-by: false
max xfers: 5
max time:     --   

origin_time 00:00:00 

CONTEXT
n_stops: 2
n_routes: 1

STOPS
stop 0 at lat 0.000000 lon 0.000000
served by routes 0 
stop 1 at lat 0.000000 lon 0.000000
served by routes 0 

ROUTES
route 0
serves stops 0 1 

STOPIDS
stop 000 has id Stop 2a1 
stop 001 has id Stop 2a2 

ROUTEIDS, TRIPIDS
route 000 has id bus long and first trip id LEV1pL�R 
Initializing router state 
stop 0 was marked as updated 
  applying transfer at 0 (Stop 2a1) 
  flagging route 0 at stop 0
  route running

Router states:
Stop name [sindex]  round 0  round 1  round 2  round 3  round 4  round 5
 Stop 2a1 [     0] 00:00:00    --       --       --       --       --   

round 0
  route 0: bus long

Route details for 'bus long' [0] (n_stops 2, n_trips 4)
stop sequence, stop name (index), departures  
   0                            Stop 2a1 [000000] : 00:01:00 -1D 00:01:00 -1D 00:05:00 -1D 00:05:00 -1D 
   1                            Stop 2a2 [000001] : 00:03:00 -1D 00:02:00 -1D 00:06:00 -1D 00:07:00 -1D 

    stop  0 [0] 00:00:00 Stop 2a1
hit previously-reached stop 0

Route details for 'bus long' [0] (n_stops 2, n_trips 4)
stop sequence, stop name (index), departures  
   0                            Stop 2a1 [000000] : 00:01:00 -1D 00:01:00 -1D 00:05:00 -1D 00:05:00 -1D 
   1                            Stop 2a2 [000001] : 00:03:00 -1D 00:02:00 -1D 00:06:00 -1D 00:07:00 -1D 

    board option 0 at 00:01:00 -1D 
00000000000000000000000000000001
00000000000000000000000000000000

    board option 1 at 00:01:00 -1D 
00000000000000000000000000000001
00000000000000000000000000000000

    board option 2 at 00:05:00 -1D 
00000000000000000000000000000001
00000000000000000000000000000000

    board option 3 at 00:05:00 -1D 
00000000000000000000000000000001
00000000000000000000000000000000

    board option 0 at 00:01:00 -1D 
00000000000000000000000000000001
00000000000000000000000000000001

    board option 1 at 00:01:00 -1D 
00000000000000000000000000000001
00000000000000000000000000000001

    board option 2 at 00:05:00 -1D 
00000000000000000000000000000001
00000000000000000000000000000001

    board option 3 at 00:05:00 -1D 
00000000000000000000000000000001
00000000000000000000000000000001

    board option 0 at 00:01:00 -1D 
00000000000000000000000000000001
00000000000000000000000000000010

    board option 1 at 00:01:00 -1D 
00000000000000000000000000000001
00000000000000000000000000000010

    board option 2 at 00:05:00 -1D 
00000000000000000000000000000001
00000000000000000000000000000010

    board option 3 at 00:05:00 -1D 
00000000000000000000000000000001
00000000000000000000000000000010

    boarding trip 0 at 00:01:00 
    stop  1 [1]    --    Stop 2a2
    on board trip 0 considering time 00:03:00 
    setting stop to 00:03:00 
stop 1 was marked as updated 
  applying transfer at 1 (Stop 2a2) 
  flagging route 0 at stop 1
  route running
round 1
  route 0: bus long

Route details for 'bus long' [0] (n_stops 2, n_trips 4)
stop sequence, stop name (index), departures  
   0                            Stop 2a1 [000000] : 00:01:00 -1D 00:01:00 -1D 00:05:00 -1D 00:05:00 -1D 
   1                            Stop 2a2 [000001] : 00:03:00 -1D 00:02:00 -1D 00:06:00 -1D 00:07:00 -1D 

    stop  0 [0] 00:00:00 Stop 2a1
hit previously-reached stop 0

Route details for 'bus long' [0] (n_stops 2, n_trips 4)
stop sequence, stop name (index), departures  
   0                            Stop 2a1 [000000] : 00:01:00 -1D 00:01:00 -1D 00:05:00 -1D 00:05:00 -1D 
   1                            Stop 2a2 [000001] : 00:03:00 -1D 00:02:00 -1D 00:06:00 -1D 00:07:00 -1D 

    board option 0 at 00:01:00 -1D 
00000000000000000000000000000001
00000000000000000000000000000000

    board option 1 at 00:01:00 -1D 
00000000000000000000000000000001
00000000000000000000000000000000

    board option 2 at 00:05:00 -1D 
00000000000000000000000000000001
00000000000000000000000000000000

    board option 3 at 00:05:00 -1D 
00000000000000000000000000000001
00000000000000000000000000000000

    board option 0 at 00:01:00 -1D 
00000000000000000000000000000001
00000000000000000000000000000001

    board option 1 at 00:01:00 -1D 
00000000000000000000000000000001
00000000000000000000000000000001

    board option 2 at 00:05:00 -1D 
00000000000000000000000000000001
00000000000000000000000000000001

    board option 3 at 00:05:00 -1D 
00000000000000000000000000000001
00000000000000000000000000000001

    board option 0 at 00:01:00 -1D 
00000000000000000000000000000001
00000000000000000000000000000010

    board option 1 at 00:01:00 -1D 
00000000000000000000000000000001
00000000000000000000000000000010

    board option 2 at 00:05:00 -1D 
00000000000000000000000000000001
00000000000000000000000000000010

    board option 3 at 00:05:00 -1D 
00000000000000000000000000000001
00000000000000000000000000000010

    boarding trip 0 at 00:01:00 
    stop  1 [1] 00:03:00 Stop 2a2
    on board trip 0 considering time 00:03:00 
    (no improvement)
round 2
round 3
round 4
round 5
State present at round 0 
-- Router State --
time:         00:03:00 
board time:   00:01:00 
back trip id: bus long 
back route:   0
back stop     0 
Repeating search with reversed request: 
-- Router Request --
from:  Stop 2a1 [0]
to:    Stop 2a2 [1]
date:  1970-01-01
time:  00:03:00 [180]
speed: 1.500000 m/sec
arrive-by: true
max xfers: 0
max time:  12:02:56 +1D
-- Router Request --
from:  Stop 2a1 [0]
to:    Stop 2a2 [1]
date:  1970-01-01
time:  00:03:00 [180]
speed: 1.500000 m/sec
arrive-by: true
max xfers: 0
max time:  12:02:56 +1D

origin_time 00:03:00 

CONTEXT
n_stops: 2
n_routes: 1

STOPS
stop 0 at lat 0.000000 lon 0.000000
served by routes 0 
stop 1 at lat 0.000000 lon 0.000000
served by routes 0 

ROUTES
route 0
serves stops 0 1 

STOPIDS
stop 000 has id Stop 2a1 
stop 001 has id Stop 2a2 

ROUTEIDS, TRIPIDS
route 000 has id bus long and first trip id LEV1pL�R 
Initializing router state 
stop 1 was marked as updated 
  applying transfer at 1 (Stop 2a2) 
  flagging route 0 at stop 1

Router states:
Stop name [sindex]  round 0  round 1  round 2  round 3  round 4  round 5
 Stop 2a2 [     1] 00:03:00    --       --       --       --       --   

round 0
round 1
round 2
round 3
round 4
round 5
Repeating search with reversed request: 
-- Router Request --
from:  Stop 2a1 [0]
to:    Stop 2a2 [1]
date:  1970-01-01
time:  00:03:00 [180]
speed: 1.500000 m/sec
arrive-by: true
max xfers: 0
max time:  12:02:56 +1D
-- Router Request --
from:  Stop 2a1 [0]
to:    Stop 2a2 [1]
date:  1970-01-01
time:  00:03:00 [180]
speed: 1.500000 m/sec
arrive-by: true
max xfers: 0
max time:  12:02:56 +1D

origin_time 00:03:00 

CONTEXT
n_stops: 2
n_routes: 1

STOPS
stop 0 at lat 0.000000 lon 0.000000
served by routes 0 
stop 1 at lat 0.000000 lon 0.000000
served by routes 0 

ROUTES
route 0
serves stops 0 1 

STOPIDS
stop 000 has id Stop 2a1 
stop 001 has id Stop 2a2 

ROUTEIDS, TRIPIDS
route 000 has id bus long and first trip id LEV1pL�R 
Initializing router state 
stop 1 was marked as updated 
  applying transfer at 1 (Stop 2a2) 
  flagging route 0 at stop 1

Router states:
Stop name [sindex]  round 0  round 1  round 2  round 3  round 4  round 5
 Stop 2a2 [     1] 00:03:00    --       --       --       --       --   

round 0
round 1
round 2
round 3
round 4
round 5

@koch-t
Copy link
Contributor Author

koch-t commented Jul 30, 2013

Same one but without t_data_dump at each route_route. This might not just be the first second of the timetable.dat related but more with departing at midnight...

./testerrrr 0 1 2014-01-01T00:00:00 timetable.dat

CONTEXT
n_stops: 2
n_routes: 1

STOPS
stop 0 at lat 0.000000 lon 0.000000
served by routes 0 
stop 1 at lat 0.000000 lon 0.000000
served by routes 0 

ROUTES
route 0
serves stops 0 1 

STOPIDS
stop 000 has id Stop 2a1 
stop 001 has id Stop 2a2 

ROUTEIDS, TRIPIDS
route 000 has id bus long and first trip id LEV1���R 
-- Router Request --
from:  Stop 2a1 [0]
to:    Stop 2a2 [1]
date:  2014-01-01
time:  00:00:00 [1388530800]
speed: 1.500000 m/sec
arrive-by: false
max xfers: 5
max time:     --   
-- Router Request --
from:  Stop 2a1 [0]
to:    Stop 2a2 [1]
date:  2014-01-01
time:  00:00:00 [1388530800]
speed: 1.500000 m/sec
arrive-by: false
max xfers: 5
max time:     --   

origin_time 00:00:00 
Initializing router state 
stop 0 was marked as updated 
  applying transfer at 0 (Stop 2a1) 
  flagging route 0 at stop 0
  route running

Router states:
Stop name [sindex]  round 0  round 1  round 2  round 3  round 4  round 5
 Stop 2a1 [     0] 00:00:00    --       --       --       --       --   

round 0
  route 0: bus long

Route details for 'bus long' [0] (n_stops 2, n_trips 4)
stop sequence, stop name (index), departures  
   0                            Stop 2a1 [000000] : 00:01:00 -1D 00:01:00 -1D 00:05:00 -1D 00:05:00 -1D 
   1                            Stop 2a2 [000001] : 00:03:00 -1D 00:02:00 -1D 00:06:00 -1D 00:07:00 -1D 

    stop  0 [0] 00:00:00 Stop 2a1
hit previously-reached stop 0

Route details for 'bus long' [0] (n_stops 2, n_trips 4)
stop sequence, stop name (index), departures  
   0                            Stop 2a1 [000000] : 00:01:00 -1D 00:01:00 -1D 00:05:00 -1D 00:05:00 -1D 
   1                            Stop 2a2 [000001] : 00:03:00 -1D 00:02:00 -1D 00:06:00 -1D 00:07:00 -1D 

    board option 0 at 00:01:00 -1D 
00000000000000000000000000000010
00000000000000000000000000000001

    board option 1 at 00:01:00 -1D 
00000000000000000000000000000010
00000000000000000000000000000001

    board option 2 at 00:05:00 -1D 
00000000000000000000000000000010
00000000000000000000000000000001

    board option 3 at 00:05:00 -1D 
00000000000000000000000000000010
00000000000000000000000000000001

    board option 0 at 00:01:00 -1D 
00000000000000000000000000000010
00000000000000000000000000000010

    board option 1 at 00:01:00 -1D 
00000000000000000000000000000010
00000000000000000000000000000010

    board option 2 at 00:05:00 -1D 
00000000000000000000000000000010
00000000000000000000000000000010

    board option 3 at 00:05:00 -1D 
00000000000000000000000000000010
00000000000000000000000000000010

    board option 0 at 00:01:00 -1D 
00000000000000000000000000000010
00000000000000000000000000000100

    board option 1 at 00:01:00 -1D 
00000000000000000000000000000010
00000000000000000000000000000100

    board option 2 at 00:05:00 -1D 
00000000000000000000000000000010
00000000000000000000000000000100

    board option 3 at 00:05:00 -1D 
00000000000000000000000000000010
00000000000000000000000000000100

    boarding trip 0 at 00:01:00 
    stop  1 [1]    --    Stop 2a2
    on board trip 0 considering time 00:03:00 
    setting stop to 00:03:00 
stop 1 was marked as updated 
  applying transfer at 1 (Stop 2a2) 
  flagging route 0 at stop 1
  route running
round 1
  route 0: bus long

Route details for 'bus long' [0] (n_stops 2, n_trips 4)
stop sequence, stop name (index), departures  
   0                            Stop 2a1 [000000] : 00:01:00 -1D 00:01:00 -1D 00:05:00 -1D 00:05:00 -1D 
   1                            Stop 2a2 [000001] : 00:03:00 -1D 00:02:00 -1D 00:06:00 -1D 00:07:00 -1D 

    stop  0 [0] 00:00:00 Stop 2a1
hit previously-reached stop 0

Route details for 'bus long' [0] (n_stops 2, n_trips 4)
stop sequence, stop name (index), departures  
   0                            Stop 2a1 [000000] : 00:01:00 -1D 00:01:00 -1D 00:05:00 -1D 00:05:00 -1D 
   1                            Stop 2a2 [000001] : 00:03:00 -1D 00:02:00 -1D 00:06:00 -1D 00:07:00 -1D 

    board option 0 at 00:01:00 -1D 
00000000000000000000000000000010
00000000000000000000000000000001

    board option 1 at 00:01:00 -1D 
00000000000000000000000000000010
00000000000000000000000000000001

    board option 2 at 00:05:00 -1D 
00000000000000000000000000000010
00000000000000000000000000000001

    board option 3 at 00:05:00 -1D 
00000000000000000000000000000010
00000000000000000000000000000001

    board option 0 at 00:01:00 -1D 
00000000000000000000000000000010
00000000000000000000000000000010

    board option 1 at 00:01:00 -1D 
00000000000000000000000000000010
00000000000000000000000000000010

    board option 2 at 00:05:00 -1D 
00000000000000000000000000000010
00000000000000000000000000000010

    board option 3 at 00:05:00 -1D 
00000000000000000000000000000010
00000000000000000000000000000010

    board option 0 at 00:01:00 -1D 
00000000000000000000000000000010
00000000000000000000000000000100

    board option 1 at 00:01:00 -1D 
00000000000000000000000000000010
00000000000000000000000000000100

    board option 2 at 00:05:00 -1D 
00000000000000000000000000000010
00000000000000000000000000000100

    board option 3 at 00:05:00 -1D 
00000000000000000000000000000010
00000000000000000000000000000100

    boarding trip 0 at 00:01:00 
    stop  1 [1] 00:03:00 Stop 2a2
    on board trip 0 considering time 00:03:00 
    (no improvement)
round 2
round 3
round 4
round 5
State present at round 0 
-- Router State --
time:         00:03:00 
board time:   00:01:00 
back trip id: bus long 
back route:   0
back stop     0 
Repeating search with reversed request: 
-- Router Request --
from:  Stop 2a1 [0]
to:    Stop 2a2 [1]
date:  1970-01-01
time:  00:03:00 [180]
speed: 1.500000 m/sec
arrive-by: true
max xfers: 0
max time:  12:02:56 +1D
-- Router Request --
from:  Stop 2a1 [0]
to:    Stop 2a2 [1]
date:  1970-01-01
time:  00:03:00 [180]
speed: 1.500000 m/sec
arrive-by: true
max xfers: 0
max time:  12:02:56 +1D

origin_time 00:03:00 
Initializing router state 
stop 1 was marked as updated 
  applying transfer at 1 (Stop 2a2) 
  flagging route 0 at stop 1

Router states:
Stop name [sindex]  round 0  round 1  round 2  round 3  round 4  round 5
 Stop 2a2 [     1] 00:03:00    --       --       --       --       --   

round 0
round 1
round 2
round 3
round 4
round 5
Repeating search with reversed request: 
-- Router Request --
from:  Stop 2a1 [0]
to:    Stop 2a2 [1]
date:  1970-01-01
time:  00:03:00 [180]
speed: 1.500000 m/sec
arrive-by: true
max xfers: 0
max time:  12:02:56 +1D
-- Router Request --
from:  Stop 2a1 [0]
to:    Stop 2a2 [1]
date:  1970-01-01
time:  00:03:00 [180]
speed: 1.500000 m/sec
arrive-by: true
max xfers: 0
max time:  12:02:56 +1D

origin_time 00:03:00 
Initializing router state 
stop 1 was marked as updated 
  applying transfer at 1 (Stop 2a2) 
  flagging route 0 at stop 1

Router states:
Stop name [sindex]  round 0  round 1  round 2  round 3  round 4  round 5
 Stop 2a2 [     1] 00:03:00    --       --       --       --       --   

round 0
round 1
round 2
round 3
round 4
round 5

@skinkie
Copy link
Contributor

skinkie commented Jul 30, 2013

This fixes the calendar date, but doesn't fix the actual routing problem.

diff --git a/router.c b/router.c
index 6a0ebbd..69b8bae 100644
--- a/router.c
+++ b/router.c
@@ -530,7 +530,11 @@ bool router_request_reverse(router_t *router, router_request_t *req) {
             D router_state_dump (&(states[round][stop]));
             req->max_transfers = round;
             req->time_cutoff = SEC_TO_RTIME(req->time); // fix units situation -- use durations in seconds o
-            req->time = RTIME_TO_SEC(states[round][stop].time - RTIME_ONE_DAY);
+            struct tm origin_tm;
+            rtime_t origin_rtime = epoch_to_rtime (req->time, &origin_tm);
+            origin_tm.tm_min = 0;
+            origin_tm.tm_hour = 0;
+            origin_tm.tm_sec = 0;
+            req->time = RTIME_TO_SEC(states[round][stop].time - RTIME_ONE_DAY) + mktime(&origin_tm);
             req->arrive_by = !(req->arrive_by);
             // router_request_dump(router, req);
             return true;

Final patch.

@abyrd
Copy link
Contributor

abyrd commented Jul 30, 2013

This is indeed part of the problem, but a deeper problem here is the mixing of internal r(outer)times and epoch times. The epoch time thing seemed like a good idea (especially since I just wanted to test out the date masks) but it's time zone sensitive, and prone to weirdness like this. We should instead store the date and time as separate fields in requests, and only perform math on dates to determine on which day of the internal calendar a request is made. There, in most cases it doesn't matter in which time zone the problem is evaluated because only the relative number of days is important. Daylight saving time problems could be eliminated by evaluating at noon instead of midnight.

@skinkie
Copy link
Contributor

skinkie commented Jul 30, 2013

I think you should start thinking on a private structure for the request and the public structure. The private structure could contain the rtime and cal_day, while the public part only does have epoch (or struct tm).

@abyrd
Copy link
Contributor

abyrd commented Jul 30, 2013

But epoch time is not "in a timezone". We might as well avoid that trap and do everything timezone-agnostic. C does easily allow a public and private structure: by including the smaller public structure as the first element of the larger private structure, you should be able to use them somewhat interchangeably.

@abyrd
Copy link
Contributor

abyrd commented Sep 26, 2013

This is probably partially fixed since we use rtimes now. There is a remaining edge case though: an arrive-by search early on the first day of the schedule may go past midnight into a day where no services are running (its mask is 0). In this case, the search should just fail with no result if the destination cannot be reached. Still, this case should be tested.

TODO check that no-trip-found does not crash but fails gracefully.

Depart-after searches should not encounter this problem during reversal, since the reversed search should be bounded by the original search's departure time.

@abyrd
Copy link
Contributor

abyrd commented Sep 26, 2013

This does imply a "business rule" though: we should always publish timetables including at least yesterday, today, and tomorrow relative to the date of issue.

@koch-t
Copy link
Contributor Author

koch-t commented Sep 26, 2013

If this is a problem, i have no issues at all to just set up as design that
"yesterday" should always be exported. Thus that if you export for
2013-09-26, 2013-09-25 is included.

On Thu, Sep 26, 2013 at 6:12 PM, Andrew Byrd notifications@github.comwrote:

This is probably partially fixed since we use rtimes now. There is a
remaining edge case though: an arrive-by search early on the first day of
the schedule may go past midnight into a day where no services are running
(its mask is 0). In this case, the search should just fail with no result
if the destination cannot be reached. Still, this case should be tested.

Depart-after searches should not have this problem at reversal, since the
reversed search should be bounded by the original search's departure time.


Reply to this email directly or view it on GitHubhttps://github.com//issues/29#issuecomment-25180962
.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants