home *** CD-ROM | disk | FTP | other *** search
/ linuxmafia.com 2016 / linuxmafia.com.tar / linuxmafia.com / pub / palmos / bart-1.3b2.tar.gz / bart-1.3b2.tar / bart-1.3b2 / find.c < prev    next >
C/C++ Source or Header  |  2000-01-12  |  32KB  |  971 lines
  1. /* BART Scheduler Palm Pilot App
  2.  *    
  3.  * Copyright (c) 1999, 2000 Michael Wittman
  4.  * 
  5.  * Permission is hereby granted, free of charge, to any person obtaining a
  6.  * copy of this software and associated documentation files (the "Software"),
  7.  * to deal in the Software without restriction, including without limitation
  8.  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
  9.  * and/or sell copies of the Software, and to permit persons to whom the
  10.  * Software is furnished to do so, subject to the following conditions:
  11.  * 
  12.  * The above copyright notice and this permission notice shall be included
  13.  * in all copies or substantial portions of the Software.
  14.  * 
  15.  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16.  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17.  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
  18.  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
  19.  * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
  20.  * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
  21.  * OTHER DEALINGS IN THE SOFTWARE.
  22.  *    
  23.  */
  24.  
  25. /* Generic code specific to finding the desired trains.  The only function
  26.    visible outside this file is FindTrips */
  27.  
  28. #include <Pilot.h>
  29. #include "callback.h"
  30. #include "bart.h"
  31.  
  32.  
  33. #define SEGMENT_FIRST    0x1
  34. #define SEGMENT_LAST    0x2
  35.  
  36. #if TUNING
  37. static ULong tuningNumber[TABLE_ROWS*TABLE_COLUMNS];
  38. static Int tuningNumbers;
  39. Int tuningSetting = 0;
  40. Int miscSetting = 0;
  41.  
  42. static ULong timerStartValue;
  43.  
  44. inline void TimerReset()
  45. {
  46.    timerStartValue = TimGetTicks();
  47. }
  48.  
  49. inline ULong TimerElapsedTicks()
  50. {
  51.    return TimGetTicks() - timerStartValue;
  52. }
  53. #endif
  54.  
  55. Int useSourceForDestination = 0;
  56.  
  57.  
  58. /* This structure is used to cache pointers corresponding to the
  59.    associated handles in LineDataType, so we don't have to do repeated
  60.    MemHandleLock's and MemHandleUnlock's. */
  61. typedef struct {
  62.    UInt *departure_time;
  63.    Byte *inc_vector_idx;
  64.    Byte *nobike_pair_idx;
  65.  
  66.    /* We use inc_vector to cache all inc_vector's for a line so we can
  67.       avoid the multiplications that we would need to do to find them
  68.       one at a time. */
  69.    Byte **inc_vector;
  70. } LineDataCache;
  71.  
  72. static LineDataCache dataCache[MAX_TRANSFERS+1];
  73.  
  74. /* for recording paths between two stations */
  75. typedef struct {
  76.    Byte station_idxs;
  77.    Byte station_idx[2*MAX_TRANSFERS+2];
  78.    Byte lines;
  79.    Byte line[MAX_TRANSFERS+1];
  80.    Int transfer_time[MAX_TRANSFERS];
  81. } RouteType;
  82.  
  83. static RouteType routeArray[MAX_TRIP_TYPES];
  84.  
  85. /* for recording trip time and destination information for individual trips */
  86. typedef struct {
  87.    /* a 1D array of times for the trip */
  88.    UInt time[2*MAX_TRANSFERS+2];
  89.    /* destination stations for each train */
  90.    Byte dest[MAX_TRANSFERS+1];
  91.    /* the number of times for the trip */
  92.    Byte times;
  93.    /* number of the route associated with each trip's times */
  94.    Byte route;
  95. } TripInfoType;
  96.  
  97.  
  98. /* Find station number given an route and an index in the station
  99.    index array. */
  100. static Byte station_number(RouteType *route, Byte idx)
  101. {
  102.    return lineInfo[route->line[idx/2]].station[route->station_idx[idx]];
  103. }
  104.  
  105. /* Find the index of the first transfer data pair for this station on
  106.    this line (or INVALID_TRANSFER if no transfers), and return number
  107.    of transfers. */
  108. static Byte FindTransfers(LineDataType *line, Byte station, Byte *index)
  109. {
  110.    Byte i = 0;
  111.    Byte count = 0;
  112.  
  113.    *index = INVALID_TRANSFER;
  114.  
  115.    while (i < line->transfers && line->transfer[i].station != station) {
  116.       i++;
  117.    }
  118.    if (i < line->transfers) *index = i;
  119.    while (i < line->transfers && line->transfer[i].station == station) {
  120.       i++; count++;
  121.    }
  122.    return count;
  123. }
  124.  
  125. /* Search for a path between source and destination stations on this
  126.    line, then recursively look for continuations of paths starting on
  127.    this line and transferring to a different line. */
  128. static void FindRoute(Byte line_num, Byte source, Byte dest,
  129.               RouteType *curr_route,
  130.               RouteType route[MAX_TRIP_TYPES],
  131.               Byte *trip,
  132.               Byte allowed_transfers)
  133. {
  134.    Byte s = 0;
  135.    Byte i;
  136.  
  137.    LineDataType *line = &lineInfo[line_num];
  138.  
  139.    /* find source station on this line, if it exists */
  140.    while (s < line->stations && line->station[s] != source)
  141.       s++;
  142.    if (s < line->stations) {
  143.       Byte d = s+1;
  144.       /* find destination station on this line, if it exists */
  145.       while (d < line->stations && line->station[d] != dest)
  146.          d++;
  147.       /* copy previously recorded stations in current route to this trip */
  148.       if (d < line->stations) {
  149.          RouteType *new_route;
  150.  
  151.      ErrFatalDisplayIf(*trip >= MAX_TRIP_TYPES,"MAX_TRIP_TYPES is too small!");
  152.      new_route = &route[*trip];
  153.      MemMove((VoidPtr)new_route,(VoidPtr)curr_route,sizeof(RouteType));
  154.          new_route->line[new_route->lines++] = line_num;
  155.          new_route->station_idx[new_route->station_idxs++] = s;
  156.          new_route->station_idx[new_route->station_idxs++] = d;
  157.          (*trip)++;
  158.       }
  159.       /* look for transfers, even if we can get there directly on this line */
  160.       if (allowed_transfers > 0) {
  161.      Byte possible_transfers, index;
  162.          /* search for possible transfer stations */
  163.          d = s+1;
  164.          while (d < line->stations) {
  165.             while (d < line->stations &&
  166.                    (possible_transfers = FindTransfers(line,line->station[d],&index)) == 0) {
  167.                d++;
  168.             }
  169.             if (d < line->stations) {
  170.                for (i = 0; i < possible_transfers; i++) {
  171.           /* we may be using a single transfer record for all
  172.              categories, so check that the line given is valid */
  173.           if (line->transfer[index+i].new_line < currentLines) {
  174.              curr_route->transfer_time[curr_route->lines] = line->transfer[index+i].time;
  175.              curr_route->line[curr_route->lines++] = line_num;
  176.              curr_route->station_idx[curr_route->station_idxs++] = s;
  177.              curr_route->station_idx[curr_route->station_idxs++] = d;
  178.              FindRoute(line->transfer[index+i].new_line,
  179.                    line->station[d],dest,
  180.                    curr_route, route, trip,
  181.                    allowed_transfers-1);
  182.              curr_route->lines--;
  183.              curr_route->station_idxs -= 2;
  184.           }
  185.                }
  186.                d++;
  187.             }
  188.          }
  189.       }
  190.    }
  191. }
  192.  
  193. /* Mark as eliminated trips in time1 that leave earlier and get in
  194.    later than a trip in time2. */
  195. static void EliminateTrips(TripInfoType trip1[MAX_TRIPS],
  196.                TripInfoType trip2[MAX_TRIPS],
  197.                Byte trip1_trips, Byte trip2_trips,
  198.                Boolean trip1_eliminated[MAX_TRIPS])
  199. {
  200.    Int trip1_idx = 0, trip2_idx = 0;
  201.    TripInfoType *t1 = &trip1[trip1_idx];
  202.    TripInfoType *t2 = &trip2[trip2_idx];
  203.    
  204.    while (trip2_idx < trip2_trips) {
  205.       while (trip1_idx < trip1_trips &&
  206.          t1->time[0] < t2->time[0]) {
  207.      if (t1->time[t1->times-1] >= t2->time[t2->times-1])
  208.         trip1_eliminated[trip1_idx] = true;
  209.      else
  210.         trip1_eliminated[trip1_idx] = false;
  211.      trip1_idx++; t1++;
  212.       }
  213.       if (trip1_idx < trip1_trips &&
  214.       t1->time[0] == t2->time[0]) {
  215.      if (t1->time[t1->times-1] > t2->time[t2->times-1])
  216.         trip1_eliminated[trip1_idx] = true;
  217.      else
  218.         trip1_eliminated[trip1_idx] = false;
  219.      trip1_idx++; t1++;
  220.       }
  221.       trip2_idx++; t2++;
  222.    }
  223.    while (trip1_idx < trip1_trips)
  224.       trip1_eliminated[trip1_idx++] = false;
  225. }
  226.  
  227. /* find next trip that is not marked eliminated and return it, or
  228.    return max_idx if none */
  229. inline static Byte NextValidTrip(Boolean eliminated[MAX_TRIPS], Byte idx,
  230.                  Byte max_idx)
  231. {
  232.    for (; idx < max_idx; idx++)
  233.       if (!eliminated[idx])
  234.      break;
  235.    return(idx);
  236. }
  237.  
  238. /* return the time with which we evaluate the trip */
  239. inline static UInt TripEvalTime(TripInfoType *trip, Boolean leaving)
  240. {
  241.    return(leaving ? trip->time[0] : trip->time[trip->times-1]);
  242. }
  243.  
  244. /* Given two sets of trips (in merged and new), we merge the two sets
  245.    into one, which has desired_trips trips.  We try to maintain the
  246.    desired split of trains before/at/after the desired time, and we
  247.    prune the extra before and after trips based on how far they are
  248.    from the desired time. */
  249. static void MergeTimes(TripInfoType merged[MAX_TRIPS],
  250.                TripInfoType new[MAX_TRIPS],
  251.                Byte *num_merged_trips, Byte new_trips,
  252.                UInt desired_time, UInt desired_trips, Boolean leaving)
  253. {
  254.    Int i;
  255.    Byte merged_trips = *num_merged_trips;
  256.    Byte new_merged_trips;
  257.    Boolean merged_eliminated[MAX_TRIPS], new_eliminated[MAX_TRIPS];
  258.    Byte merged_idx, new_idx, new_merged_idx;
  259.    Byte desired_before, desired_after;
  260.    Byte before_idx, at_idx, after_idx;
  261.    Byte num_before, num_at, num_after;
  262.    TripInfoType new_merged[2*MAX_TRIPS];
  263.  
  264.    /* mark as eliminated trips in one array whose start and end times
  265.       are completely within the start and end times of a trip in the
  266.       other array */
  267.    EliminateTrips(new,merged,new_trips,merged_trips,new_eliminated);
  268.    EliminateTrips(merged,new,merged_trips,new_trips,merged_eliminated);
  269.  
  270.    /* copy trips to new_merged in order of time */
  271.    merged_idx = NextValidTrip(merged_eliminated,0,merged_trips);
  272.    new_idx = NextValidTrip(new_eliminated,0,new_trips);
  273.    new_merged_idx = 0;
  274.    while (merged_idx < merged_trips && new_idx < new_trips) {
  275.       UInt merged_time = TripEvalTime(&merged[merged_idx],leaving);
  276.       UInt new_time = TripEvalTime(&new[new_idx],leaving);
  277.       if (new_time < merged_time) {
  278.      MemMove((VoidPtr)&new_merged[new_merged_idx],
  279.          (VoidPtr)&new[new_idx],sizeof(TripInfoType));
  280.      new_idx = NextValidTrip(new_eliminated,new_idx+1,new_trips);
  281.       }
  282.       else {
  283.      /* merged_time <= new_time: if they are equal, the times at
  284.             the other end of the trip must also be equal (or one would
  285.             have been eliminated earlier).  We default to the merged
  286.             time first in that case. */
  287.      MemMove((VoidPtr)&new_merged[new_merged_idx],
  288.          (VoidPtr)&merged[merged_idx],sizeof(TripInfoType));
  289.      merged_idx = NextValidTrip(merged_eliminated,merged_idx+1,merged_trips);
  290.       }
  291.       new_merged_idx++;
  292.    }
  293.    
  294.    /* copy remaining trips */
  295.    while (merged_idx < merged_trips) {
  296.       MemMove((VoidPtr)&new_merged[new_merged_idx],
  297.           (VoidPtr)&merged[merged_idx],sizeof(TripInfoType));
  298.       merged_idx = NextValidTrip(merged_eliminated,merged_idx+1,merged_trips);
  299.       new_merged_idx++;
  300.    }
  301.    while (new_idx < new_trips) {
  302.       MemMove((VoidPtr)&new_merged[new_merged_idx],
  303.           (VoidPtr)&new[new_idx],sizeof(TripInfoType));
  304.       new_idx = NextValidTrip(new_eliminated,new_idx+1,new_trips);
  305.       new_merged_idx++;
  306.    }
  307.    
  308.    new_merged_trips = new_merged_idx;
  309.  
  310.    
  311.    /* record start index of trips before, at, and after the desired time */
  312.    before_idx = 0;
  313.    i = 0;
  314.    while (i < new_merged_trips &&
  315.       TripEvalTime(&new_merged[i],leaving) < desired_time)
  316.       i++;
  317.    at_idx = i;
  318.    while (i < new_merged_trips &&
  319.       TripEvalTime(&new_merged[i],leaving) == desired_time)
  320.       i++;
  321.    after_idx = i;
  322.  
  323.    /* calculate number of trips before, at, after */
  324.    num_before = at_idx - before_idx;
  325.    num_at = after_idx - at_idx;
  326.    num_after = new_merged_trips - after_idx;
  327.  
  328.  
  329.    /* calculate "ideal" desired number of before and after trips; we
  330.       always use all "at" trips */
  331.    if (leaving)
  332.       desired_after = (desired_trips-num_at+1)/2;
  333.    else
  334.       desired_after = (desired_trips-num_at)/2;
  335.    desired_before = desired_trips - desired_after - num_at;
  336.  
  337.    /* redistribute excess desired trips if possible, and ensure that
  338.       desired_before <= num_before && desired_after <= num_after */
  339.    if (num_before > desired_before && num_after < desired_after) {
  340.       desired_before += min(num_before-desired_before,desired_after-num_after);
  341.       desired_after = num_after;
  342.    }
  343.    else if (num_before < desired_before && num_after > desired_after) {
  344.       desired_after += min(num_after-desired_after,desired_before-num_before);
  345.       desired_before = num_before;
  346.    }
  347.    else {
  348.       if (num_before < desired_before)
  349.      desired_before = num_before;
  350.       if (num_after < desired_after)
  351.      desired_after = num_after;
  352.    }
  353.  
  354.    /* finally, copy those trips in the new_merged array that we want
  355.       to the merged array */
  356.    *num_merged_trips = desired_before + desired_after + num_at;
  357.    MemMove((VoidPtr)merged,
  358.        (VoidPtr)&new_merged[before_idx+(num_before-desired_before)],
  359.        *num_merged_trips*sizeof(TripInfoType));
  360. }
  361.  
  362. /* Lock handles and allocate memory for the LineDataCache
  363.    corresponding to each line in the route.  Assumes that we have
  364.    called AllocateDepartureTimes prior to calling this function. */
  365. static void AllocateDataCache(RouteType *route)
  366. {
  367.    Int i, j;
  368.  
  369.    for (i = 0; i < route->lines; i++) {
  370.       LineDataType *line = &lineInfo[route->line[i]];
  371.       dataCache[i].departure_time = MemHandleLock(line->departure_time_handle);
  372.       dataCache[i].inc_vector_idx = MemHandleLock(line->inc_vector_idx_handle);
  373.       dataCache[i].nobike_pair_idx = MemHandleLock(line->nobike_pair_idx_handle);
  374.  
  375.       dataCache[i].inc_vector = MemPtrNew(line->inc_vectors*sizeof(Byte *));
  376.       dataCache[i].inc_vector[0] = line->inc_vector;
  377.       for (j = 1; j < line->inc_vectors; j++)
  378.      dataCache[i].inc_vector[j] = dataCache[i].inc_vector[j-1]+line->stations;
  379.    }
  380. }
  381.  
  382. /* Unlock handles and free memory for the LineDataCache corresponding
  383.    to each line in the route.  Assumes that we have called
  384.    AllocateDepartureTimes prior to calling this function. */
  385. static void FreeDataCache(RouteType *route)
  386. {
  387.    Int i;
  388.  
  389.    for (i = 0; i < route->lines; i++) {
  390.       LineDataType *line = &lineInfo[route->line[i]];
  391.       MemHandleUnlock(line->departure_time_handle);
  392.       MemHandleUnlock(line->inc_vector_idx_handle);
  393.       MemHandleUnlock(line->nobike_pair_idx_handle);
  394.  
  395.       MemPtrFree(dataCache[i].inc_vector);
  396.  
  397.       dataCache[i].departure_time = NULL;
  398.       dataCache[i].inc_vector_idx = NULL;
  399.       dataCache[i].nobike_pair_idx = NULL;
  400.  
  401.       dataCache[i].inc_vector = NULL;
  402.    }
  403. }
  404.  
  405. /* For each train t in the line, set valid[t] = 0 if the train goes to
  406.    both the stations at src_idx and dst_idx and satisfies bike
  407.    restrictions (if applicable), else set to INVALID_TRAIN. */
  408. static void FindValidTrains(LineDataType *line, LineDataCache *cache,
  409.                 Byte src_idx, Byte dst_idx,
  410.                 Boolean bike_trains_only, Byte segment,
  411.                 Byte *valid)
  412. {
  413.    UInt *departure_time;
  414.    Byte *inc_vector_idx;
  415.    Byte *nobike_pair_idx;
  416.    Int train;
  417.    Int i, j;
  418.  
  419.    Byte segment_test[2] = { SEGMENT_FIRST, SEGMENT_LAST };
  420.    Byte stn_idx[2];
  421.  
  422.    stn_idx[0] = src_idx;
  423.    stn_idx[1] = dst_idx;
  424.    
  425.    departure_time = cache->departure_time;
  426.    inc_vector_idx = cache->inc_vector_idx;
  427.    nobike_pair_idx = cache->nobike_pair_idx;
  428.  
  429.    for (train = 0; train < line->trains; train++) {
  430.       Byte *inc_vector = cache->inc_vector[inc_vector_idx[train]];
  431.       if (inc_vector[src_idx] == INVALID_INC || inc_vector[dst_idx] == INVALID_INC)
  432.      valid[train] = INVALID_TRAIN;
  433.       else
  434.      valid[train] = 0;        /* 0 for valid as far as we know */
  435.    }
  436.  
  437.    if (bike_trains_only) {
  438.       /* check this train's bike restrictions */
  439.       for (train = 0; train < line->trains; train++) {
  440.      if (valid[train] != INVALID_TRAIN && nobike_pair_idx[train] != INVALID_BIKEPAIR) {
  441.         Byte *pair = line->nobike_pair[nobike_pair_idx[train]];
  442.         if ((src_idx >= pair[0] && src_idx <= pair[1]) ||
  443.         (dst_idx >= pair[0] && dst_idx <= pair[1]) ||
  444.         (src_idx <= pair[0] && dst_idx >= pair[1]))
  445.            valid[train] = INVALID_TRAIN;
  446.      }
  447.       }
  448.  
  449.       /* check one of the stations' bike restrictions, if necessary */
  450.       if (segment & (SEGMENT_FIRST | SEGMENT_LAST)) {
  451.      for (j = 0; j < 2; j++) {
  452.         if (segment & segment_test[j]) {
  453.            Byte station_idx = stn_idx[j];
  454.            Byte station = line->station[station_idx];
  455.  
  456.            Boolean station_affected = false;
  457.            for (i = 0; i < station_bike_restrictions; i++) {
  458.           StationBikeRestrictionType *sbr = &station_bike_restriction[i];
  459.           if (station == sbr->station) {
  460.              station_affected = true;
  461.              break;
  462.           }
  463.            }
  464.  
  465.            if (station_affected) {
  466.           for (train = 0; train < line->trains; train++) {
  467.              Byte *inc_vector = cache->inc_vector[inc_vector_idx[train]];
  468.              if (valid[train] != INVALID_TRAIN) {
  469.             UInt station_time = departure_time[train]+inc_vector[station_idx];
  470.             for (i = 0; i < station_bike_restrictions; i++) {
  471.                StationBikeRestrictionType *sbr = &station_bike_restriction[i];
  472.                if (station == sbr->station &&
  473.                    station_time >= sbr->time_start &&
  474.                    station_time <= sbr->time_end) {
  475.                   valid[train] = INVALID_TRAIN;
  476.                   break;
  477.                }
  478.             }
  479.              }
  480.           }
  481.            }
  482.         }
  483.      }
  484.       }
  485.       
  486.    }
  487. }
  488.  
  489. /* Find the next valid train in the transfer_train array, or return
  490.    max_idx if none.  Inlining this function gives 30% speedup in my
  491.    testing(!). */
  492. inline static Int NextValidTrain(Byte *transfer_train, Int idx, Int max_idx)
  493. {
  494.    while (idx < max_idx && transfer_train[idx] == INVALID_TRAIN)
  495.       idx++;
  496.    return idx;
  497. }
  498.  
  499. /* Evaluate transfers from line1 to line2 at the station
  500.    line1->station[station_idx1] (== line2->station[station_idx2]): for
  501.    each train t1 in line1, set transfer_train1[t1] to the next valid
  502.    train in line2 on which a transfer can be made (or INVALID_TRAIN if
  503.    none).  We assume that the transfer_train arrays passed in have
  504.    invalid trains assigned the value INVALID_TRAIN. */
  505. static void FindTransferTrains(LineDataType *line1, LineDataType *line2,
  506.                    LineDataCache *cache1, LineDataCache *cache2,
  507.                    Byte station_idx1, Byte station_idx2,
  508.                    Byte *transfer_train1, Byte *transfer_train2,
  509.                    UInt transfer_time)
  510. {
  511.    Int train1, train2;
  512.    Byte max_train1, max_train2;
  513.  
  514.    UInt *departure_time1, *departure_time2;
  515.    Byte *inc_vector_idx1, *inc_vector_idx2;
  516.  
  517. #define station_time1 \
  518. (cache1->inc_vector[inc_vector_idx1[train1]][station_idx1]+departure_time1[train1])
  519. #define station_time2 \
  520. (cache2->inc_vector[inc_vector_idx2[train2]][station_idx2]+departure_time2[train2])
  521.  
  522.    departure_time1 = cache1->departure_time;
  523.    departure_time2 = cache2->departure_time;
  524.    inc_vector_idx1 = cache1->inc_vector_idx;
  525.    inc_vector_idx2 = cache2->inc_vector_idx;
  526.  
  527.    max_train1 = line1->trains;
  528.    max_train2 = line2->trains;
  529.  
  530.    train1 = 0;
  531.    train2 = NextValidTrain(transfer_train2,0,max_train2);
  532.  
  533.    /* for each train2, record it for all train1's that are before it */
  534.    while (train2 < max_train2) {
  535.       UInt stime2 = station_time2;
  536.       
  537.       while ((train1 = NextValidTrain(transfer_train1,train1,max_train1)) < max_train1 &&
  538.          station_time1+transfer_time <= stime2)
  539.      transfer_train1[train1++] = train2;
  540.  
  541.       train2 = NextValidTrain(transfer_train2,train2+1,max_train2);
  542.    }
  543.    /* mark invalid all extra train1's after the last train2 */
  544.    while (train1 < max_train1)
  545.       transfer_train1[train1++] = INVALID_TRAIN;
  546.  
  547. #undef station_time1
  548. #undef station_time2
  549. }
  550.  
  551. /* Mark as invalid all but the last trip in each set of trips that
  552.    shares a common last train.  In other words, we want to throw out a
  553.    trip if another trip with a later starting train will get you there
  554.    at the same time. */
  555. static void KillDuplicateTransferTrains(RouteType *route,
  556.                     Byte *transfer_train[MAX_TRANSFERS])
  557. {
  558.    Int i, j;
  559.    Int initial_trains = lineInfo[route->line[0]].trains;
  560.    /* the trains represented by the last transfer train array have
  561.       been incorporated into the second to last, so we don't need to
  562.       use it */
  563.    Int transfer_train_arrays = route->lines-1;
  564.    /* prev_last_train_num represents the number of the train on the
  565.       last segment of the route, which was previously found to be the
  566.       last train in the previous trip we evaluated. */
  567.    Byte prev_last_train_num = INVALID_TRAIN;
  568.  
  569.    for (i = initial_trains-1; i >= 0; i--) {
  570.       Byte train_num = transfer_train[0][i];
  571.       for (j = 1; j < transfer_train_arrays; j++) {
  572.      train_num = transfer_train[j][train_num];
  573.      ErrFatalDisplayIf(train_num == INVALID_TRAIN,"got train_num == INVALID_TRAIN");
  574.       }
  575.       if (train_num == prev_last_train_num)
  576.      transfer_train[0][i] = INVALID_TRAIN;
  577.       else 
  578.      prev_last_train_num = train_num;
  579.    }
  580. }
  581.  
  582. /* Find the trains leaving or arriving closest to desired_time.  The
  583.    desired number of trains to find is passed in in *trains. */
  584. static void FindBestRouteTrains(RouteType *route,
  585.                 Byte *transfer_train[MAX_TRANSFERS+1],
  586.                 UInt desired_time,
  587.                 Byte train[MAX_TRIPS],
  588.                 Byte *trains, Boolean leaving)
  589. {
  590.    Int i, j;
  591.    Int initial_trains = lineInfo[route->line[0]].trains;
  592.    /* the trains represented by the last transfer train array have
  593.       been incorporated into the second to last, so we don't need to
  594.       use it */
  595.    Int transfer_train_arrays = route->lines-1;
  596.  
  597.    Int train_idx = 0, recorded_trains = 0;
  598.    Byte desired_trains = *trains;
  599.    Byte desired_after_trains;
  600.    Byte after_trains;
  601.  
  602.    LineDataType *time_eval_line;
  603.    LineDataCache *time_eval_cache;
  604.    Byte time_eval_station_idx;
  605.    UInt *departure_time;
  606.    Byte *inc_vector_idx;
  607.  
  608. #define station_time(train) \
  609. (time_eval_cache->inc_vector[inc_vector_idx[train]][time_eval_station_idx]+departure_time[train])
  610.  
  611.  
  612.    if (leaving) {
  613.       time_eval_line = &lineInfo[route->line[0]];
  614.       time_eval_cache = &dataCache[0];
  615.       time_eval_station_idx = route->station_idx[0];
  616.       desired_after_trains = (desired_trains+1)/2;
  617.    }
  618.    else {
  619.       time_eval_line = &lineInfo[route->line[route->lines-1]];
  620.       time_eval_cache = &dataCache[route->lines-1];
  621.       time_eval_station_idx = route->station_idx[route->station_idxs-1];
  622.       desired_after_trains = desired_trains/2;
  623.    }
  624.    departure_time = time_eval_cache->departure_time;
  625.    inc_vector_idx = time_eval_cache->inc_vector_idx;
  626.  
  627.  
  628.    /* We record the initial train in each trip in a circular buffer,
  629.       which we reorder later. */
  630.  
  631. #define ASSIGN_BEFORE    0
  632. #define ASSIGN_AFTER    1
  633.    
  634.    after_trains = 0;
  635.    for (i = 0; i < initial_trains; i++) {
  636.       if (transfer_train[0][i] != INVALID_TRAIN) {
  637.      Boolean end_loop = false;
  638.      Byte action;
  639.      Byte train_num = i;
  640.      UInt stime;
  641.  
  642.      if (!leaving) {
  643.         for (j = 0; j < transfer_train_arrays; j++) {
  644.            train_num = transfer_train[j][train_num];
  645.            ErrFatalDisplayIf(train_num == INVALID_TRAIN,"got train_num == INVALID_TRAIN");
  646.         }
  647.      }
  648.      
  649.      stime = station_time(train_num);
  650.      if (stime < desired_time)
  651.         action = ASSIGN_BEFORE;
  652.      else if (stime > desired_time)
  653.         action = ASSIGN_AFTER;
  654.      else {
  655.         /* stime == desired_time */
  656.         if ((leaving && desired_trains % 2 == 0) ||
  657.         (!leaving && desired_trains % 2 == 1))
  658.            action = ASSIGN_BEFORE;
  659.         else
  660.            action = ASSIGN_AFTER;
  661.      }
  662.  
  663.      train[train_idx] = i;
  664.      train_idx = (train_idx+1) % desired_trains;
  665.      recorded_trains++;
  666.      
  667.      switch (action) {
  668.      case ASSIGN_BEFORE:
  669.         /* don't need to do anything extra */
  670.         break;
  671.      case ASSIGN_AFTER:
  672.         after_trains++;
  673.         if (after_trains >= desired_after_trains &&
  674.         recorded_trains >= desired_trains)
  675.            end_loop = true;
  676.         break;
  677.      }
  678.  
  679.      if (end_loop)
  680.         break;
  681.       }
  682.    }
  683.    
  684. #undef ASSIGN_BEFORE
  685. #undef ASSIGN_AFTER
  686.    
  687.    {
  688.       /* reorder trains in circular buffer so first is in position 0 */
  689.       Byte temp[MAX_TRIPS];
  690.       if (recorded_trains < desired_trains) {
  691.      train_idx = (train_idx+desired_trains-recorded_trains) % desired_trains;
  692.      *trains = recorded_trains;
  693.       }
  694.       else {
  695.      *trains = desired_trains;
  696.       }
  697.       for (i = 0; i < min(recorded_trains,desired_trains); i++) {
  698.      temp[i] = train[train_idx];
  699.      train_idx = (train_idx+1) % desired_trains;
  700.       }
  701.       for (i = 0; i < min(recorded_trains,desired_trains); i++)
  702.      train[i] = temp[i];
  703.    }
  704.  
  705. #undef station_time
  706. }
  707.  
  708. /* Find the destination station of a given train.  Inlining this
  709.    function gives a little speedup in my testing. */
  710. inline static Byte FindTrainDestination(Byte *inc_vector, Byte *station, Byte stations)
  711. {
  712.    Int s;
  713.  
  714.    if (!useSourceForDestination) {
  715.       s = stations-1;
  716.       while (inc_vector[s] == INVALID_INC)
  717.      s--;
  718.    }
  719.    else {
  720.       s = 0;
  721.       while (inc_vector[s] == INVALID_INC)
  722.      s++;
  723.    }
  724.    return(station[s]);
  725. }
  726.  
  727. /* For the starting trains in train[MAX_TRIPS], find the times for the
  728.    trips associated with them in the transfer_train arrays. */
  729. static void FindRouteTrainTimes(RouteType *route,
  730.                 Byte *transfer_train[MAX_TRANSFERS],
  731.                 Byte train[MAX_TRIPS], Byte trains,
  732.                 TripInfoType trip[MAX_TRIPS], Byte *trips)
  733. {
  734.    Int i, j;
  735.    
  736.    LineDataType *line[MAX_TRANSFERS+1];
  737.    UInt *departure_time[MAX_TRANSFERS+1];
  738.    Byte *inc_vector_idx[MAX_TRANSFERS+1];
  739.  
  740. #define station_time(segment,train,station_idx) \
  741. (dataCache[segment].inc_vector[inc_vector_idx[segment][train]][station_idx]+departure_time[segment][train])
  742.  
  743.    for (i = 0; i < route->lines; i++) {
  744.       line[i] = &lineInfo[route->line[i]];
  745.       departure_time[i] = dataCache[i].departure_time;
  746.       inc_vector_idx[i] = dataCache[i].inc_vector_idx;
  747.    }
  748.  
  749.    *trips = trains;
  750.    for (i = 0; i < trains; i++) {
  751.       Byte train_num = train[i];
  752.       TripInfoType *current_trip = &trip[i];
  753.  
  754.       current_trip->times = 0;
  755.  
  756.       j = 0;
  757.       while (1) {
  758.      Byte *inc_vector = dataCache[j].inc_vector[inc_vector_idx[j][train_num]];
  759.      current_trip->time[current_trip->times++] = station_time(j,train_num,route->station_idx[2*j]);
  760.      current_trip->time[current_trip->times++] = station_time(j,train_num,route->station_idx[2*j+1]);
  761.      current_trip->dest[j] = FindTrainDestination(inc_vector,line[j]->station,line[j]->stations);
  762.  
  763.      if (++j >= route->lines)
  764.         break;
  765.      
  766.      train_num = transfer_train[j-1][train_num];
  767.       }
  768.    }
  769.  
  770. #undef station_time
  771. }
  772.  
  773. /* For the given route, find up to max_times times leaving or
  774.    arriving around desired_time. */
  775. static void FindTimes(Byte route_idx, UInt desired_time,
  776.               Byte max_times, Boolean leaving,
  777.               Boolean bike_trains_only, TripInfoType trip[MAX_TRIPS],
  778.               Byte *trips)
  779. {
  780.    RouteType *route = &routeArray[route_idx];
  781.    Byte *transfer_train[MAX_TRANSFERS+1];
  782.    Byte train[MAX_TRIPS], trains;
  783.    Int i;
  784.  
  785.    /* allocate and fill necessary temporary data that we will use */
  786.    for (i = 0; i < route->lines; i++) {
  787.       LineDataType *line = &lineInfo[route->line[i]];
  788.       if (!line->departure_time_handle)
  789.      AllocateDepartureTimes(line);
  790.       transfer_train[i] = MemPtrNew(line->trains*sizeof(Byte));
  791.       ErrFatalDisplayIf(transfer_train[i] == NULL,"failed to allocate memory for transfer_train[i]");
  792.    }
  793.    AllocateDataCache(route);
  794.  
  795.    /* for each line in the route, mark its trains valid or invalid
  796.       in its transfer_train array */
  797.    for (i = 0; i < route->lines; i++) {
  798.       Byte segment = 0;
  799.       if (i == 0)
  800.      segment |= SEGMENT_FIRST;
  801.       if (i == route->lines-1)
  802.      segment |= SEGMENT_LAST;
  803.       
  804.       FindValidTrains(&lineInfo[route->line[i]],
  805.               &dataCache[i],
  806.               route->station_idx[2*i],
  807.               route->station_idx[2*i+1],
  808.               bike_trains_only, segment, transfer_train[i]);
  809.    }
  810.  
  811.    /* find transfers between adjacent pairs of trains: sets each train
  812.       in the transfer_train array for the first line to the train in
  813.       the second line on which a transfer would be made */
  814.    for (i = route->lines-2; i >= 0; i--) {
  815.       FindTransferTrains(&lineInfo[route->line[i]],
  816.              &lineInfo[route->line[i+1]],
  817.              &dataCache[i], &dataCache[i+1],
  818.              route->station_idx[2*i+1],
  819.              route->station_idx[2*i+2],
  820.              transfer_train[i], transfer_train[i+1],
  821.              route->transfer_time[i]);
  822.    }
  823.  
  824.    /* mark invalid any earlier starting trains that wind up taking the
  825.       same final train as a later starting train */
  826.    if (route->lines > 1)
  827.       KillDuplicateTransferTrains(route,transfer_train);
  828.  
  829.    /* find the starting trains that are near the desired time condition */
  830.    trains = max_times;
  831.    FindBestRouteTrains(route,transfer_train,desired_time,train,&trains,
  832.                leaving);
  833.  
  834.    /* find the times for the trips associated with the previously
  835.       found trains */
  836.    FindRouteTrainTimes(route,transfer_train,train,trains,trip,trips);
  837.    for (i = 0; i < *trips; i++)
  838.       trip[i].route = route_idx;
  839.  
  840.    /* get rid of the temporary data that we used.  note that we don't
  841.       call FreeDepartureTimes because we may use that data for another
  842.       route */
  843.    FreeDataCache(route);
  844.    for (i = 0; i < route->lines; i++) {
  845.       MemPtrFree(transfer_train[i]);
  846.    }
  847. }
  848.  
  849. /* This is the only function visible outside this file.  We first find
  850.    potential routes, then find times for the routes and merge them
  851.    down to a single set of times.  We then fill in the results
  852.    table.*/
  853. void FindTrips(Byte source, Byte dest, UInt time, Boolean leaving,
  854.            Boolean bike_trains_only,
  855.            ResultsCellType resultsInfo[TABLE_ROWS][TABLE_COLUMNS],
  856.            Byte destination[TABLE_ROWS][TABLE_COLUMNS/2])
  857. {
  858.    RouteType temp;        /* for use in FindRoute() */
  859.    Byte trips = 0;
  860.    TripInfoType merged_trip[MAX_TRIPS];
  861.    Byte merged_trips;
  862.    TripInfoType tripinfo[MAX_TRIPS];
  863.    Byte tripinfo_trips;
  864.    RouteType *stations_route = NULL;
  865.    Byte curr_row;
  866.    Byte i, j;
  867.  
  868.    ErrFatalDisplayIf(currentLines <= 0,"currentLines <= 0");
  869.  
  870. #if TUNING
  871.    tuningNumbers = 0;
  872.    for (i = 0; i < TABLE_ROWS*TABLE_COLUMNS; i++)
  873.       tuningNumber[i] = 0;
  874. #endif
  875.    
  876. #if TUNING
  877.    if (tuningSetting == 1)
  878.       TimerReset();
  879. #endif
  880.    temp.station_idxs = 0;
  881.    temp.lines = 0;
  882.    for (i = 0; i < currentLines; i++) {
  883.       FindRoute(i,source,dest,&temp,routeArray,&trips,MAX_TRANSFERS);
  884.    }
  885. #if TUNING
  886.    if (tuningSetting == 1) {
  887.       tuningNumber[tuningNumbers++] = TimerElapsedTicks();
  888.       tuningNumber[tuningNumbers++] = (ULong)trips;
  889.    }
  890. #endif
  891.  
  892. #if TUNING
  893.    if (tuningSetting == 1)
  894.       TimerReset();
  895. #endif
  896.    merged_trips = 0;
  897.    for (i = 0; i < trips; i++) {
  898. #if TUNING
  899.       if (tuningSetting == 2)
  900.      TimerReset();
  901. #endif
  902.       FindTimes(i,time,MAX_TRIPS,leaving,bike_trains_only,tripinfo,
  903.         &tripinfo_trips);
  904.       MergeTimes(merged_trip,tripinfo,&merged_trips,tripinfo_trips,time,MAX_TRIPS,leaving);
  905. #if TUNING
  906.       if (tuningSetting == 2) {
  907.      ULong lineNums = 0;
  908.      tuningNumber[tuningNumbers++] = TimerElapsedTicks();
  909.      for (j = 0; j < routeArray[i].lines; j++)
  910.         lineNums = lineNums*10 + routeArray[i].line[j];
  911.      tuningNumber[tuningNumbers++] = lineNums;
  912.       }
  913. #endif
  914.    }
  915. #if TUNING
  916.    if (tuningSetting == 1)
  917.       tuningNumber[tuningNumbers++] = TimerElapsedTicks();
  918. #endif
  919.  
  920.    /* eliminate extra trips here */
  921.    tripinfo_trips = 0;
  922.    MergeTimes(merged_trip,tripinfo,&merged_trips,tripinfo_trips,time,MAX_TRIPS_DISPLAYED,leaving);
  923.  
  924.    curr_row = 0;
  925.    for (i = 0; i < merged_trips; i++) {
  926.       RouteType *route = &routeArray[merged_trip[i].route];
  927.       Boolean same_stations = true;
  928.  
  929.       if (stations_route == NULL || stations_route->station_idxs != route->station_idxs) {
  930.      same_stations = false;
  931.       }
  932.       else {
  933.      /* We don't bother checking the first or last stations, since
  934.         they must be the same. */
  935.      for (j = 1; j < route->lines; j++) {
  936.         if (station_number(stations_route,2*j) !=
  937.         station_number(route,2*j)) {
  938.            same_stations = false;
  939.            break;
  940.         }
  941.      }
  942.       }
  943.  
  944.       if (!same_stations) {
  945.      /* fill in station abbrevs */
  946.      for (j = 0; j < routeArray[merged_trip[i].route].lines; j++) {
  947.         resultsInfo[curr_row][2*j].type = resultsCellStation;
  948.         resultsInfo[curr_row][2*j].data.station.number = station_number(route,2*j);
  949.         resultsInfo[curr_row][2*j+1].type = resultsCellStation;
  950.         resultsInfo[curr_row][2*j+1].data.station.number = station_number(route,2*j+1);
  951.      }
  952.      curr_row++;
  953.      stations_route = route;
  954.       }
  955.       
  956.       for (j = 0; j < merged_trip[i].times; j++) {
  957.      resultsInfo[curr_row][j].type = resultsCellTime;
  958.      resultsInfo[curr_row][j].data.time.time = merged_trip[i].time[j];
  959.      destination[curr_row][j/2] = merged_trip[i].dest[j/2];
  960.       }
  961.       curr_row++;
  962.    }
  963.  
  964. #if TUNING
  965.    for (i = 0; i < min(tuningNumbers,TABLE_ROWS*TABLE_COLUMNS); i++) {
  966.       resultsInfo[i/TABLE_COLUMNS][i%TABLE_COLUMNS].type = resultsCellNumber;
  967.       resultsInfo[i/TABLE_COLUMNS][i%TABLE_COLUMNS].data.number.number = tuningNumber[i];
  968.    }
  969. #endif
  970. }
  971.