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 >
Wrap
C/C++ Source or Header
|
2000-01-12
|
32KB
|
971 lines
/* BART Scheduler Palm Pilot App
*
* Copyright (c) 1999, 2000 Michael Wittman
*
* Permission is hereby granted, free of charge, to any person obtaining a
* copy of this software and associated documentation files (the "Software"),
* to deal in the Software without restriction, including without limitation
* the rights to use, copy, modify, merge, publish, distribute, sublicense,
* and/or sell copies of the Software, and to permit persons to whom the
* Software is furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included
* in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
* OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
* ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
* OTHER DEALINGS IN THE SOFTWARE.
*
*/
/* Generic code specific to finding the desired trains. The only function
visible outside this file is FindTrips */
#include <Pilot.h>
#include "callback.h"
#include "bart.h"
#define SEGMENT_FIRST 0x1
#define SEGMENT_LAST 0x2
#if TUNING
static ULong tuningNumber[TABLE_ROWS*TABLE_COLUMNS];
static Int tuningNumbers;
Int tuningSetting = 0;
Int miscSetting = 0;
static ULong timerStartValue;
inline void TimerReset()
{
timerStartValue = TimGetTicks();
}
inline ULong TimerElapsedTicks()
{
return TimGetTicks() - timerStartValue;
}
#endif
Int useSourceForDestination = 0;
/* This structure is used to cache pointers corresponding to the
associated handles in LineDataType, so we don't have to do repeated
MemHandleLock's and MemHandleUnlock's. */
typedef struct {
UInt *departure_time;
Byte *inc_vector_idx;
Byte *nobike_pair_idx;
/* We use inc_vector to cache all inc_vector's for a line so we can
avoid the multiplications that we would need to do to find them
one at a time. */
Byte **inc_vector;
} LineDataCache;
static LineDataCache dataCache[MAX_TRANSFERS+1];
/* for recording paths between two stations */
typedef struct {
Byte station_idxs;
Byte station_idx[2*MAX_TRANSFERS+2];
Byte lines;
Byte line[MAX_TRANSFERS+1];
Int transfer_time[MAX_TRANSFERS];
} RouteType;
static RouteType routeArray[MAX_TRIP_TYPES];
/* for recording trip time and destination information for individual trips */
typedef struct {
/* a 1D array of times for the trip */
UInt time[2*MAX_TRANSFERS+2];
/* destination stations for each train */
Byte dest[MAX_TRANSFERS+1];
/* the number of times for the trip */
Byte times;
/* number of the route associated with each trip's times */
Byte route;
} TripInfoType;
/* Find station number given an route and an index in the station
index array. */
static Byte station_number(RouteType *route, Byte idx)
{
return lineInfo[route->line[idx/2]].station[route->station_idx[idx]];
}
/* Find the index of the first transfer data pair for this station on
this line (or INVALID_TRANSFER if no transfers), and return number
of transfers. */
static Byte FindTransfers(LineDataType *line, Byte station, Byte *index)
{
Byte i = 0;
Byte count = 0;
*index = INVALID_TRANSFER;
while (i < line->transfers && line->transfer[i].station != station) {
i++;
}
if (i < line->transfers) *index = i;
while (i < line->transfers && line->transfer[i].station == station) {
i++; count++;
}
return count;
}
/* Search for a path between source and destination stations on this
line, then recursively look for continuations of paths starting on
this line and transferring to a different line. */
static void FindRoute(Byte line_num, Byte source, Byte dest,
RouteType *curr_route,
RouteType route[MAX_TRIP_TYPES],
Byte *trip,
Byte allowed_transfers)
{
Byte s = 0;
Byte i;
LineDataType *line = &lineInfo[line_num];
/* find source station on this line, if it exists */
while (s < line->stations && line->station[s] != source)
s++;
if (s < line->stations) {
Byte d = s+1;
/* find destination station on this line, if it exists */
while (d < line->stations && line->station[d] != dest)
d++;
/* copy previously recorded stations in current route to this trip */
if (d < line->stations) {
RouteType *new_route;
ErrFatalDisplayIf(*trip >= MAX_TRIP_TYPES,"MAX_TRIP_TYPES is too small!");
new_route = &route[*trip];
MemMove((VoidPtr)new_route,(VoidPtr)curr_route,sizeof(RouteType));
new_route->line[new_route->lines++] = line_num;
new_route->station_idx[new_route->station_idxs++] = s;
new_route->station_idx[new_route->station_idxs++] = d;
(*trip)++;
}
/* look for transfers, even if we can get there directly on this line */
if (allowed_transfers > 0) {
Byte possible_transfers, index;
/* search for possible transfer stations */
d = s+1;
while (d < line->stations) {
while (d < line->stations &&
(possible_transfers = FindTransfers(line,line->station[d],&index)) == 0) {
d++;
}
if (d < line->stations) {
for (i = 0; i < possible_transfers; i++) {
/* we may be using a single transfer record for all
categories, so check that the line given is valid */
if (line->transfer[index+i].new_line < currentLines) {
curr_route->transfer_time[curr_route->lines] = line->transfer[index+i].time;
curr_route->line[curr_route->lines++] = line_num;
curr_route->station_idx[curr_route->station_idxs++] = s;
curr_route->station_idx[curr_route->station_idxs++] = d;
FindRoute(line->transfer[index+i].new_line,
line->station[d],dest,
curr_route, route, trip,
allowed_transfers-1);
curr_route->lines--;
curr_route->station_idxs -= 2;
}
}
d++;
}
}
}
}
}
/* Mark as eliminated trips in time1 that leave earlier and get in
later than a trip in time2. */
static void EliminateTrips(TripInfoType trip1[MAX_TRIPS],
TripInfoType trip2[MAX_TRIPS],
Byte trip1_trips, Byte trip2_trips,
Boolean trip1_eliminated[MAX_TRIPS])
{
Int trip1_idx = 0, trip2_idx = 0;
TripInfoType *t1 = &trip1[trip1_idx];
TripInfoType *t2 = &trip2[trip2_idx];
while (trip2_idx < trip2_trips) {
while (trip1_idx < trip1_trips &&
t1->time[0] < t2->time[0]) {
if (t1->time[t1->times-1] >= t2->time[t2->times-1])
trip1_eliminated[trip1_idx] = true;
else
trip1_eliminated[trip1_idx] = false;
trip1_idx++; t1++;
}
if (trip1_idx < trip1_trips &&
t1->time[0] == t2->time[0]) {
if (t1->time[t1->times-1] > t2->time[t2->times-1])
trip1_eliminated[trip1_idx] = true;
else
trip1_eliminated[trip1_idx] = false;
trip1_idx++; t1++;
}
trip2_idx++; t2++;
}
while (trip1_idx < trip1_trips)
trip1_eliminated[trip1_idx++] = false;
}
/* find next trip that is not marked eliminated and return it, or
return max_idx if none */
inline static Byte NextValidTrip(Boolean eliminated[MAX_TRIPS], Byte idx,
Byte max_idx)
{
for (; idx < max_idx; idx++)
if (!eliminated[idx])
break;
return(idx);
}
/* return the time with which we evaluate the trip */
inline static UInt TripEvalTime(TripInfoType *trip, Boolean leaving)
{
return(leaving ? trip->time[0] : trip->time[trip->times-1]);
}
/* Given two sets of trips (in merged and new), we merge the two sets
into one, which has desired_trips trips. We try to maintain the
desired split of trains before/at/after the desired time, and we
prune the extra before and after trips based on how far they are
from the desired time. */
static void MergeTimes(TripInfoType merged[MAX_TRIPS],
TripInfoType new[MAX_TRIPS],
Byte *num_merged_trips, Byte new_trips,
UInt desired_time, UInt desired_trips, Boolean leaving)
{
Int i;
Byte merged_trips = *num_merged_trips;
Byte new_merged_trips;
Boolean merged_eliminated[MAX_TRIPS], new_eliminated[MAX_TRIPS];
Byte merged_idx, new_idx, new_merged_idx;
Byte desired_before, desired_after;
Byte before_idx, at_idx, after_idx;
Byte num_before, num_at, num_after;
TripInfoType new_merged[2*MAX_TRIPS];
/* mark as eliminated trips in one array whose start and end times
are completely within the start and end times of a trip in the
other array */
EliminateTrips(new,merged,new_trips,merged_trips,new_eliminated);
EliminateTrips(merged,new,merged_trips,new_trips,merged_eliminated);
/* copy trips to new_merged in order of time */
merged_idx = NextValidTrip(merged_eliminated,0,merged_trips);
new_idx = NextValidTrip(new_eliminated,0,new_trips);
new_merged_idx = 0;
while (merged_idx < merged_trips && new_idx < new_trips) {
UInt merged_time = TripEvalTime(&merged[merged_idx],leaving);
UInt new_time = TripEvalTime(&new[new_idx],leaving);
if (new_time < merged_time) {
MemMove((VoidPtr)&new_merged[new_merged_idx],
(VoidPtr)&new[new_idx],sizeof(TripInfoType));
new_idx = NextValidTrip(new_eliminated,new_idx+1,new_trips);
}
else {
/* merged_time <= new_time: if they are equal, the times at
the other end of the trip must also be equal (or one would
have been eliminated earlier). We default to the merged
time first in that case. */
MemMove((VoidPtr)&new_merged[new_merged_idx],
(VoidPtr)&merged[merged_idx],sizeof(TripInfoType));
merged_idx = NextValidTrip(merged_eliminated,merged_idx+1,merged_trips);
}
new_merged_idx++;
}
/* copy remaining trips */
while (merged_idx < merged_trips) {
MemMove((VoidPtr)&new_merged[new_merged_idx],
(VoidPtr)&merged[merged_idx],sizeof(TripInfoType));
merged_idx = NextValidTrip(merged_eliminated,merged_idx+1,merged_trips);
new_merged_idx++;
}
while (new_idx < new_trips) {
MemMove((VoidPtr)&new_merged[new_merged_idx],
(VoidPtr)&new[new_idx],sizeof(TripInfoType));
new_idx = NextValidTrip(new_eliminated,new_idx+1,new_trips);
new_merged_idx++;
}
new_merged_trips = new_merged_idx;
/* record start index of trips before, at, and after the desired time */
before_idx = 0;
i = 0;
while (i < new_merged_trips &&
TripEvalTime(&new_merged[i],leaving) < desired_time)
i++;
at_idx = i;
while (i < new_merged_trips &&
TripEvalTime(&new_merged[i],leaving) == desired_time)
i++;
after_idx = i;
/* calculate number of trips before, at, after */
num_before = at_idx - before_idx;
num_at = after_idx - at_idx;
num_after = new_merged_trips - after_idx;
/* calculate "ideal" desired number of before and after trips; we
always use all "at" trips */
if (leaving)
desired_after = (desired_trips-num_at+1)/2;
else
desired_after = (desired_trips-num_at)/2;
desired_before = desired_trips - desired_after - num_at;
/* redistribute excess desired trips if possible, and ensure that
desired_before <= num_before && desired_after <= num_after */
if (num_before > desired_before && num_after < desired_after) {
desired_before += min(num_before-desired_before,desired_after-num_after);
desired_after = num_after;
}
else if (num_before < desired_before && num_after > desired_after) {
desired_after += min(num_after-desired_after,desired_before-num_before);
desired_before = num_before;
}
else {
if (num_before < desired_before)
desired_before = num_before;
if (num_after < desired_after)
desired_after = num_after;
}
/* finally, copy those trips in the new_merged array that we want
to the merged array */
*num_merged_trips = desired_before + desired_after + num_at;
MemMove((VoidPtr)merged,
(VoidPtr)&new_merged[before_idx+(num_before-desired_before)],
*num_merged_trips*sizeof(TripInfoType));
}
/* Lock handles and allocate memory for the LineDataCache
corresponding to each line in the route. Assumes that we have
called AllocateDepartureTimes prior to calling this function. */
static void AllocateDataCache(RouteType *route)
{
Int i, j;
for (i = 0; i < route->lines; i++) {
LineDataType *line = &lineInfo[route->line[i]];
dataCache[i].departure_time = MemHandleLock(line->departure_time_handle);
dataCache[i].inc_vector_idx = MemHandleLock(line->inc_vector_idx_handle);
dataCache[i].nobike_pair_idx = MemHandleLock(line->nobike_pair_idx_handle);
dataCache[i].inc_vector = MemPtrNew(line->inc_vectors*sizeof(Byte *));
dataCache[i].inc_vector[0] = line->inc_vector;
for (j = 1; j < line->inc_vectors; j++)
dataCache[i].inc_vector[j] = dataCache[i].inc_vector[j-1]+line->stations;
}
}
/* Unlock handles and free memory for the LineDataCache corresponding
to each line in the route. Assumes that we have called
AllocateDepartureTimes prior to calling this function. */
static void FreeDataCache(RouteType *route)
{
Int i;
for (i = 0; i < route->lines; i++) {
LineDataType *line = &lineInfo[route->line[i]];
MemHandleUnlock(line->departure_time_handle);
MemHandleUnlock(line->inc_vector_idx_handle);
MemHandleUnlock(line->nobike_pair_idx_handle);
MemPtrFree(dataCache[i].inc_vector);
dataCache[i].departure_time = NULL;
dataCache[i].inc_vector_idx = NULL;
dataCache[i].nobike_pair_idx = NULL;
dataCache[i].inc_vector = NULL;
}
}
/* For each train t in the line, set valid[t] = 0 if the train goes to
both the stations at src_idx and dst_idx and satisfies bike
restrictions (if applicable), else set to INVALID_TRAIN. */
static void FindValidTrains(LineDataType *line, LineDataCache *cache,
Byte src_idx, Byte dst_idx,
Boolean bike_trains_only, Byte segment,
Byte *valid)
{
UInt *departure_time;
Byte *inc_vector_idx;
Byte *nobike_pair_idx;
Int train;
Int i, j;
Byte segment_test[2] = { SEGMENT_FIRST, SEGMENT_LAST };
Byte stn_idx[2];
stn_idx[0] = src_idx;
stn_idx[1] = dst_idx;
departure_time = cache->departure_time;
inc_vector_idx = cache->inc_vector_idx;
nobike_pair_idx = cache->nobike_pair_idx;
for (train = 0; train < line->trains; train++) {
Byte *inc_vector = cache->inc_vector[inc_vector_idx[train]];
if (inc_vector[src_idx] == INVALID_INC || inc_vector[dst_idx] == INVALID_INC)
valid[train] = INVALID_TRAIN;
else
valid[train] = 0; /* 0 for valid as far as we know */
}
if (bike_trains_only) {
/* check this train's bike restrictions */
for (train = 0; train < line->trains; train++) {
if (valid[train] != INVALID_TRAIN && nobike_pair_idx[train] != INVALID_BIKEPAIR) {
Byte *pair = line->nobike_pair[nobike_pair_idx[train]];
if ((src_idx >= pair[0] && src_idx <= pair[1]) ||
(dst_idx >= pair[0] && dst_idx <= pair[1]) ||
(src_idx <= pair[0] && dst_idx >= pair[1]))
valid[train] = INVALID_TRAIN;
}
}
/* check one of the stations' bike restrictions, if necessary */
if (segment & (SEGMENT_FIRST | SEGMENT_LAST)) {
for (j = 0; j < 2; j++) {
if (segment & segment_test[j]) {
Byte station_idx = stn_idx[j];
Byte station = line->station[station_idx];
Boolean station_affected = false;
for (i = 0; i < station_bike_restrictions; i++) {
StationBikeRestrictionType *sbr = &station_bike_restriction[i];
if (station == sbr->station) {
station_affected = true;
break;
}
}
if (station_affected) {
for (train = 0; train < line->trains; train++) {
Byte *inc_vector = cache->inc_vector[inc_vector_idx[train]];
if (valid[train] != INVALID_TRAIN) {
UInt station_time = departure_time[train]+inc_vector[station_idx];
for (i = 0; i < station_bike_restrictions; i++) {
StationBikeRestrictionType *sbr = &station_bike_restriction[i];
if (station == sbr->station &&
station_time >= sbr->time_start &&
station_time <= sbr->time_end) {
valid[train] = INVALID_TRAIN;
break;
}
}
}
}
}
}
}
}
}
}
/* Find the next valid train in the transfer_train array, or return
max_idx if none. Inlining this function gives 30% speedup in my
testing(!). */
inline static Int NextValidTrain(Byte *transfer_train, Int idx, Int max_idx)
{
while (idx < max_idx && transfer_train[idx] == INVALID_TRAIN)
idx++;
return idx;
}
/* Evaluate transfers from line1 to line2 at the station
line1->station[station_idx1] (== line2->station[station_idx2]): for
each train t1 in line1, set transfer_train1[t1] to the next valid
train in line2 on which a transfer can be made (or INVALID_TRAIN if
none). We assume that the transfer_train arrays passed in have
invalid trains assigned the value INVALID_TRAIN. */
static void FindTransferTrains(LineDataType *line1, LineDataType *line2,
LineDataCache *cache1, LineDataCache *cache2,
Byte station_idx1, Byte station_idx2,
Byte *transfer_train1, Byte *transfer_train2,
UInt transfer_time)
{
Int train1, train2;
Byte max_train1, max_train2;
UInt *departure_time1, *departure_time2;
Byte *inc_vector_idx1, *inc_vector_idx2;
#define station_time1 \
(cache1->inc_vector[inc_vector_idx1[train1]][station_idx1]+departure_time1[train1])
#define station_time2 \
(cache2->inc_vector[inc_vector_idx2[train2]][station_idx2]+departure_time2[train2])
departure_time1 = cache1->departure_time;
departure_time2 = cache2->departure_time;
inc_vector_idx1 = cache1->inc_vector_idx;
inc_vector_idx2 = cache2->inc_vector_idx;
max_train1 = line1->trains;
max_train2 = line2->trains;
train1 = 0;
train2 = NextValidTrain(transfer_train2,0,max_train2);
/* for each train2, record it for all train1's that are before it */
while (train2 < max_train2) {
UInt stime2 = station_time2;
while ((train1 = NextValidTrain(transfer_train1,train1,max_train1)) < max_train1 &&
station_time1+transfer_time <= stime2)
transfer_train1[train1++] = train2;
train2 = NextValidTrain(transfer_train2,train2+1,max_train2);
}
/* mark invalid all extra train1's after the last train2 */
while (train1 < max_train1)
transfer_train1[train1++] = INVALID_TRAIN;
#undef station_time1
#undef station_time2
}
/* Mark as invalid all but the last trip in each set of trips that
shares a common last train. In other words, we want to throw out a
trip if another trip with a later starting train will get you there
at the same time. */
static void KillDuplicateTransferTrains(RouteType *route,
Byte *transfer_train[MAX_TRANSFERS])
{
Int i, j;
Int initial_trains = lineInfo[route->line[0]].trains;
/* the trains represented by the last transfer train array have
been incorporated into the second to last, so we don't need to
use it */
Int transfer_train_arrays = route->lines-1;
/* prev_last_train_num represents the number of the train on the
last segment of the route, which was previously found to be the
last train in the previous trip we evaluated. */
Byte prev_last_train_num = INVALID_TRAIN;
for (i = initial_trains-1; i >= 0; i--) {
Byte train_num = transfer_train[0][i];
for (j = 1; j < transfer_train_arrays; j++) {
train_num = transfer_train[j][train_num];
ErrFatalDisplayIf(train_num == INVALID_TRAIN,"got train_num == INVALID_TRAIN");
}
if (train_num == prev_last_train_num)
transfer_train[0][i] = INVALID_TRAIN;
else
prev_last_train_num = train_num;
}
}
/* Find the trains leaving or arriving closest to desired_time. The
desired number of trains to find is passed in in *trains. */
static void FindBestRouteTrains(RouteType *route,
Byte *transfer_train[MAX_TRANSFERS+1],
UInt desired_time,
Byte train[MAX_TRIPS],
Byte *trains, Boolean leaving)
{
Int i, j;
Int initial_trains = lineInfo[route->line[0]].trains;
/* the trains represented by the last transfer train array have
been incorporated into the second to last, so we don't need to
use it */
Int transfer_train_arrays = route->lines-1;
Int train_idx = 0, recorded_trains = 0;
Byte desired_trains = *trains;
Byte desired_after_trains;
Byte after_trains;
LineDataType *time_eval_line;
LineDataCache *time_eval_cache;
Byte time_eval_station_idx;
UInt *departure_time;
Byte *inc_vector_idx;
#define station_time(train) \
(time_eval_cache->inc_vector[inc_vector_idx[train]][time_eval_station_idx]+departure_time[train])
if (leaving) {
time_eval_line = &lineInfo[route->line[0]];
time_eval_cache = &dataCache[0];
time_eval_station_idx = route->station_idx[0];
desired_after_trains = (desired_trains+1)/2;
}
else {
time_eval_line = &lineInfo[route->line[route->lines-1]];
time_eval_cache = &dataCache[route->lines-1];
time_eval_station_idx = route->station_idx[route->station_idxs-1];
desired_after_trains = desired_trains/2;
}
departure_time = time_eval_cache->departure_time;
inc_vector_idx = time_eval_cache->inc_vector_idx;
/* We record the initial train in each trip in a circular buffer,
which we reorder later. */
#define ASSIGN_BEFORE 0
#define ASSIGN_AFTER 1
after_trains = 0;
for (i = 0; i < initial_trains; i++) {
if (transfer_train[0][i] != INVALID_TRAIN) {
Boolean end_loop = false;
Byte action;
Byte train_num = i;
UInt stime;
if (!leaving) {
for (j = 0; j < transfer_train_arrays; j++) {
train_num = transfer_train[j][train_num];
ErrFatalDisplayIf(train_num == INVALID_TRAIN,"got train_num == INVALID_TRAIN");
}
}
stime = station_time(train_num);
if (stime < desired_time)
action = ASSIGN_BEFORE;
else if (stime > desired_time)
action = ASSIGN_AFTER;
else {
/* stime == desired_time */
if ((leaving && desired_trains % 2 == 0) ||
(!leaving && desired_trains % 2 == 1))
action = ASSIGN_BEFORE;
else
action = ASSIGN_AFTER;
}
train[train_idx] = i;
train_idx = (train_idx+1) % desired_trains;
recorded_trains++;
switch (action) {
case ASSIGN_BEFORE:
/* don't need to do anything extra */
break;
case ASSIGN_AFTER:
after_trains++;
if (after_trains >= desired_after_trains &&
recorded_trains >= desired_trains)
end_loop = true;
break;
}
if (end_loop)
break;
}
}
#undef ASSIGN_BEFORE
#undef ASSIGN_AFTER
{
/* reorder trains in circular buffer so first is in position 0 */
Byte temp[MAX_TRIPS];
if (recorded_trains < desired_trains) {
train_idx = (train_idx+desired_trains-recorded_trains) % desired_trains;
*trains = recorded_trains;
}
else {
*trains = desired_trains;
}
for (i = 0; i < min(recorded_trains,desired_trains); i++) {
temp[i] = train[train_idx];
train_idx = (train_idx+1) % desired_trains;
}
for (i = 0; i < min(recorded_trains,desired_trains); i++)
train[i] = temp[i];
}
#undef station_time
}
/* Find the destination station of a given train. Inlining this
function gives a little speedup in my testing. */
inline static Byte FindTrainDestination(Byte *inc_vector, Byte *station, Byte stations)
{
Int s;
if (!useSourceForDestination) {
s = stations-1;
while (inc_vector[s] == INVALID_INC)
s--;
}
else {
s = 0;
while (inc_vector[s] == INVALID_INC)
s++;
}
return(station[s]);
}
/* For the starting trains in train[MAX_TRIPS], find the times for the
trips associated with them in the transfer_train arrays. */
static void FindRouteTrainTimes(RouteType *route,
Byte *transfer_train[MAX_TRANSFERS],
Byte train[MAX_TRIPS], Byte trains,
TripInfoType trip[MAX_TRIPS], Byte *trips)
{
Int i, j;
LineDataType *line[MAX_TRANSFERS+1];
UInt *departure_time[MAX_TRANSFERS+1];
Byte *inc_vector_idx[MAX_TRANSFERS+1];
#define station_time(segment,train,station_idx) \
(dataCache[segment].inc_vector[inc_vector_idx[segment][train]][station_idx]+departure_time[segment][train])
for (i = 0; i < route->lines; i++) {
line[i] = &lineInfo[route->line[i]];
departure_time[i] = dataCache[i].departure_time;
inc_vector_idx[i] = dataCache[i].inc_vector_idx;
}
*trips = trains;
for (i = 0; i < trains; i++) {
Byte train_num = train[i];
TripInfoType *current_trip = &trip[i];
current_trip->times = 0;
j = 0;
while (1) {
Byte *inc_vector = dataCache[j].inc_vector[inc_vector_idx[j][train_num]];
current_trip->time[current_trip->times++] = station_time(j,train_num,route->station_idx[2*j]);
current_trip->time[current_trip->times++] = station_time(j,train_num,route->station_idx[2*j+1]);
current_trip->dest[j] = FindTrainDestination(inc_vector,line[j]->station,line[j]->stations);
if (++j >= route->lines)
break;
train_num = transfer_train[j-1][train_num];
}
}
#undef station_time
}
/* For the given route, find up to max_times times leaving or
arriving around desired_time. */
static void FindTimes(Byte route_idx, UInt desired_time,
Byte max_times, Boolean leaving,
Boolean bike_trains_only, TripInfoType trip[MAX_TRIPS],
Byte *trips)
{
RouteType *route = &routeArray[route_idx];
Byte *transfer_train[MAX_TRANSFERS+1];
Byte train[MAX_TRIPS], trains;
Int i;
/* allocate and fill necessary temporary data that we will use */
for (i = 0; i < route->lines; i++) {
LineDataType *line = &lineInfo[route->line[i]];
if (!line->departure_time_handle)
AllocateDepartureTimes(line);
transfer_train[i] = MemPtrNew(line->trains*sizeof(Byte));
ErrFatalDisplayIf(transfer_train[i] == NULL,"failed to allocate memory for transfer_train[i]");
}
AllocateDataCache(route);
/* for each line in the route, mark its trains valid or invalid
in its transfer_train array */
for (i = 0; i < route->lines; i++) {
Byte segment = 0;
if (i == 0)
segment |= SEGMENT_FIRST;
if (i == route->lines-1)
segment |= SEGMENT_LAST;
FindValidTrains(&lineInfo[route->line[i]],
&dataCache[i],
route->station_idx[2*i],
route->station_idx[2*i+1],
bike_trains_only, segment, transfer_train[i]);
}
/* find transfers between adjacent pairs of trains: sets each train
in the transfer_train array for the first line to the train in
the second line on which a transfer would be made */
for (i = route->lines-2; i >= 0; i--) {
FindTransferTrains(&lineInfo[route->line[i]],
&lineInfo[route->line[i+1]],
&dataCache[i], &dataCache[i+1],
route->station_idx[2*i+1],
route->station_idx[2*i+2],
transfer_train[i], transfer_train[i+1],
route->transfer_time[i]);
}
/* mark invalid any earlier starting trains that wind up taking the
same final train as a later starting train */
if (route->lines > 1)
KillDuplicateTransferTrains(route,transfer_train);
/* find the starting trains that are near the desired time condition */
trains = max_times;
FindBestRouteTrains(route,transfer_train,desired_time,train,&trains,
leaving);
/* find the times for the trips associated with the previously
found trains */
FindRouteTrainTimes(route,transfer_train,train,trains,trip,trips);
for (i = 0; i < *trips; i++)
trip[i].route = route_idx;
/* get rid of the temporary data that we used. note that we don't
call FreeDepartureTimes because we may use that data for another
route */
FreeDataCache(route);
for (i = 0; i < route->lines; i++) {
MemPtrFree(transfer_train[i]);
}
}
/* This is the only function visible outside this file. We first find
potential routes, then find times for the routes and merge them
down to a single set of times. We then fill in the results
table.*/
void FindTrips(Byte source, Byte dest, UInt time, Boolean leaving,
Boolean bike_trains_only,
ResultsCellType resultsInfo[TABLE_ROWS][TABLE_COLUMNS],
Byte destination[TABLE_ROWS][TABLE_COLUMNS/2])
{
RouteType temp; /* for use in FindRoute() */
Byte trips = 0;
TripInfoType merged_trip[MAX_TRIPS];
Byte merged_trips;
TripInfoType tripinfo[MAX_TRIPS];
Byte tripinfo_trips;
RouteType *stations_route = NULL;
Byte curr_row;
Byte i, j;
ErrFatalDisplayIf(currentLines <= 0,"currentLines <= 0");
#if TUNING
tuningNumbers = 0;
for (i = 0; i < TABLE_ROWS*TABLE_COLUMNS; i++)
tuningNumber[i] = 0;
#endif
#if TUNING
if (tuningSetting == 1)
TimerReset();
#endif
temp.station_idxs = 0;
temp.lines = 0;
for (i = 0; i < currentLines; i++) {
FindRoute(i,source,dest,&temp,routeArray,&trips,MAX_TRANSFERS);
}
#if TUNING
if (tuningSetting == 1) {
tuningNumber[tuningNumbers++] = TimerElapsedTicks();
tuningNumber[tuningNumbers++] = (ULong)trips;
}
#endif
#if TUNING
if (tuningSetting == 1)
TimerReset();
#endif
merged_trips = 0;
for (i = 0; i < trips; i++) {
#if TUNING
if (tuningSetting == 2)
TimerReset();
#endif
FindTimes(i,time,MAX_TRIPS,leaving,bike_trains_only,tripinfo,
&tripinfo_trips);
MergeTimes(merged_trip,tripinfo,&merged_trips,tripinfo_trips,time,MAX_TRIPS,leaving);
#if TUNING
if (tuningSetting == 2) {
ULong lineNums = 0;
tuningNumber[tuningNumbers++] = TimerElapsedTicks();
for (j = 0; j < routeArray[i].lines; j++)
lineNums = lineNums*10 + routeArray[i].line[j];
tuningNumber[tuningNumbers++] = lineNums;
}
#endif
}
#if TUNING
if (tuningSetting == 1)
tuningNumber[tuningNumbers++] = TimerElapsedTicks();
#endif
/* eliminate extra trips here */
tripinfo_trips = 0;
MergeTimes(merged_trip,tripinfo,&merged_trips,tripinfo_trips,time,MAX_TRIPS_DISPLAYED,leaving);
curr_row = 0;
for (i = 0; i < merged_trips; i++) {
RouteType *route = &routeArray[merged_trip[i].route];
Boolean same_stations = true;
if (stations_route == NULL || stations_route->station_idxs != route->station_idxs) {
same_stations = false;
}
else {
/* We don't bother checking the first or last stations, since
they must be the same. */
for (j = 1; j < route->lines; j++) {
if (station_number(stations_route,2*j) !=
station_number(route,2*j)) {
same_stations = false;
break;
}
}
}
if (!same_stations) {
/* fill in station abbrevs */
for (j = 0; j < routeArray[merged_trip[i].route].lines; j++) {
resultsInfo[curr_row][2*j].type = resultsCellStation;
resultsInfo[curr_row][2*j].data.station.number = station_number(route,2*j);
resultsInfo[curr_row][2*j+1].type = resultsCellStation;
resultsInfo[curr_row][2*j+1].data.station.number = station_number(route,2*j+1);
}
curr_row++;
stations_route = route;
}
for (j = 0; j < merged_trip[i].times; j++) {
resultsInfo[curr_row][j].type = resultsCellTime;
resultsInfo[curr_row][j].data.time.time = merged_trip[i].time[j];
destination[curr_row][j/2] = merged_trip[i].dest[j/2];
}
curr_row++;
}
#if TUNING
for (i = 0; i < min(tuningNumbers,TABLE_ROWS*TABLE_COLUMNS); i++) {
resultsInfo[i/TABLE_COLUMNS][i%TABLE_COLUMNS].type = resultsCellNumber;
resultsInfo[i/TABLE_COLUMNS][i%TABLE_COLUMNS].data.number.number = tuningNumber[i];
}
#endif
}