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 / README.src < prev    next >
Text File  |  2000-03-12  |  12KB  |  243 lines
  1. This file is intended for people interested in porting this code for
  2. use with other transit systems.  To do so requires knowledge of both C
  3. and Perl, but should not be too difficult if you've got that.  At a
  4. minimum, a port will require a small amounts of modification to the C
  5. code, and a fair amount of modification to the Perl code.  I've tried
  6. to keep most transit system and schedule-specific data in the pdb file
  7. so that the C code is fairly general and can serve as a base for
  8. others' efforts.
  9.  
  10. Changes vs. Version 1.21
  11. ------------------------
  12.    - user interface enhancements mentioned in README
  13.    - renamed itineraries to routes, which better describes what they
  14.      are
  15.    - time is now updated when the device is powered on, eliminating
  16.      the need for TIME_UPDATE_INTERVAL.  this should save a small
  17.      amount of power.
  18.    - removed preferences form, but left preferences form code intact
  19.      and #if 0'd out.
  20.    - DB_ID is now uniquely defined in bartdata.h, written by
  21.      make-pdb-file
  22.    - moved some initialization code from MainFormInit() to
  23.      StartApplication(), revised locking/unlocking of StationNameArray
  24.      to minimize time holding the handle locked
  25.  
  26.  
  27. Changes vs. Version 1.01
  28. ------------------------
  29.  
  30.    - user visible changes: see the README file
  31.    - completely rewrote the code that finds train times; it is now
  32.      much faster, cleaner, more predictable in its running time, and
  33.      (IMHO) simpler and easier to understand.
  34.    - rewrote the MergeTimes function
  35.    - changed TimeInfoType struct to array of TripInfoType, which is a
  36.      bit more manageable
  37.    - got rid of yucky (Byte)-1's and replaced with symbolic constants
  38.    - added a LineDataCache struct to cache pointers frequently needed
  39.      by the train time finding code
  40.    - added TUNING #define; if you set this to 1 you can easily time
  41.      sections of the code, run alternate implementations of parts of
  42.      the code, and display results
  43.    - increased MAX_TRIPS from 5 to 8 (it's only slightly slower, but
  44.      gives better results)
  45.    - now record two station indices for each line in the route,
  46.      instead of a station number; this way we don't have to search for
  47.      the station indices each time we need them.  this should also
  48.      make support easier for stations appearing multiple times on a
  49.      single line
  50.    - got rid of duplication of time printing functionality
  51.    - database format changes: added "time necessary to make transfer"
  52.      field for each transfer, added database creation date to general
  53.      info record
  54.    - make-pdb-file: now constructs the pdb file in memory by printing
  55.      everything to buffers, obviating the need for a temp file; also
  56.      got rid of unused line-abbrevs file
  57.    - there is now a single unique version string in bart.prc which is
  58.      propagated everywhere else it is needed (including the "About"
  59.      form)
  60.    - added much inline documentation
  61.    - other changes I've probably forgotten...
  62.  
  63.  
  64. How the code works
  65. ------------------
  66.  
  67. Initialization:
  68.  
  69. On starting, the application reads from the database the schedule
  70. category names (e.g. Weekday, Saturday, Sunday), the station names,
  71. prior user interface settings, and other miscellaneous info that is
  72. needed for the user interface.  In the main form initialization
  73. function the user interface is actually set up.
  74.  
  75. Other "Front End" Code:
  76.  
  77. The remainder of the bart.c file deals with the necessary manipulation
  78. of the user interface, with the exception of the ResultsFormInit and
  79. ResultsFormUnInit functions.  ResultsFormInit sets up the results form
  80. and calls functions to set up the lineInfo array for the lines in the
  81. desired schedule category.  It also finds the fare and sets the fare
  82. label, and calls the FindTrips function, which actually finds the
  83. desired trips.  ResultsFormUnInit undoes the work of ResultsFormInit
  84. by deallocating memory and unlocking handles.
  85.  
  86. "Back End" Code:
  87.  
  88. The find.c file consists entirely of the back end code that finds the
  89. desired trips, given that the lineInfo array is properly initialized.
  90. The trips are found in two stages.  First, all possible routes (ways
  91. to get from the source station to the destination station by taking
  92. different lines) are found in the FindRoute function.  This is done,
  93. by checking for each line, if the source stations appears before the
  94. destination station in that line.  If so, we record that route.  We
  95. then check all transfer stations after the source station and call
  96. FindRoute recursively on the lines that we would transfer to at each
  97. one, up to a recursion level of MAX_TRANSFERS+1.  In this way, we find
  98. all routes that take at most MAX_TRANSFERS transfers.
  99.  
  100. The second stage of finding trips consists of finding and evaluating
  101. times of the possible trips for each route.  This stage is performed
  102. by the FindTimes function.  In that function, we perform the following
  103. steps.
  104.  
  105. 1. Lock handle pointers to data we need for each line in the
  106.    route, allocate a transfer_train array for each line, and
  107.    allocate a data cache for each line.
  108.  
  109. 2. In the FindValidTrains function, set transfer_train[segment][t] to
  110.    zero if train t on line route->line[segment] stops at both the
  111.    source and destination stations.  If not, or if we are using bike
  112.    restrictions and the train fails any of them, we set
  113.    transfer_train[segment][t] to INVALID_TRAIN (0xff).  We call this
  114.    function for each line in the route.
  115.  
  116. 3. If there is more than one line used in the trip, for all but the
  117.    last line, calculate the "transfer train" in the next line on which
  118.    a transfer would be made for each train in current line.  In doing
  119.    this we ignore trains in the next line already marked invalid in
  120.    step 2.  This is done by the FindTransferTrains function, and sets
  121.    transfer_train[segment][t] to the index of the train in line
  122.    route->line[segment+1] on which the transfer would be made.  If
  123.    there is no valid train on which to make a transfer, we set
  124.    transfer_train[segment][t] to INVALID_TRAIN.  By doing this
  125.    backward from the last pair of lines in the trip to the first pair,
  126.    we are guaranteed that transfer_train[0][t] is valid if and only if
  127.    there is a series of valid trains starting with train t on line
  128.    route->line[0] that gets us to the destination.  Moreover, we
  129.    can follow the indices in the transfer_train arrays to find the
  130.    necessary trains to take on that trip.
  131.  
  132. 4. Use KillDuplicateTransferTrains to follow the indices in the
  133.    transfer_train arrays and find the number of the train on the last
  134.    line that corresponds to each train on the first line.  We then
  135.    mark invalid transfer_train[0][t1] if there exists a train t2 > t1
  136.    that has the same final train number.  In this way, we eliminate
  137.    any trips on this route that take longer than necessary to get
  138.    to the destination.
  139.  
  140. 5. Use FindBestRouteTrains to find the "best" MAX_TRIPS trips
  141.    around the desired time of all the valid trips we found for this
  142.    route.  This function assumes there is at most one trip that
  143.    exactly meets the desired time condition.  Let e be that number of
  144.    "exact" trips.  If the time condition is leaving, we try to find
  145.    (MAX_TRIPS-e)/2 trips before the desired time, and
  146.    (MAX_TRIPS-e+1)/2 trips after the desired time.  If the time
  147.    condition is arriving, we try to find (MAX_TRIPS-e+1)/2 trips
  148.    before the desired time and (MAX_TRIPS-e)/2 trips after the desired
  149.    time.  The logic thus gives preference to trips after the desired
  150.    time if we are leaving, or preference to trips before the desired
  151.    time if we are arriving.  If there are insufficient trips either
  152.    before or after, we take whatever extra trips we can get in the
  153.    opposite direction to fill up to MAX_TRIPS trips.
  154.  
  155. 6. Use FindRouteTrainTimes to find times for the trains in the
  156.    trips found in step 5.
  157.  
  158. 7. Deallocate the data cache for each line and unlock handles.
  159.  
  160. After finding the trips for each route, we use MergeTimes to merge
  161. those trips into the list previously found trips.  We try to maintain
  162. the same before/exact/after split as in step 5 of FindTimes, but here
  163. e may be greater than one.  Finally, we take the list of MAX_TRIPS
  164. trips merged from all routes and use MergeTimes to pare the list down
  165. to MAX_TRIPS_DISPLAYED trips.  This list is then used to fill the
  166. resultsInfo table which in turn is used by the user interface
  167. functions to display the results in the results form.
  168.  
  169. On Exit:
  170.  
  171. User interface settings are saved, and memory is freed.
  172.  
  173.  
  174. Notes on the Database Format
  175. ----------------------------
  176.  
  177. The database format was designed for maximum compression of the
  178. schedule data so that as little space as possible is taken up on the
  179. pilot.  Other than using Bytes instead of Ints everywhere possible,
  180. the compression is largely due to a run length encoding of train
  181. properties for the trains on each line.  These properties are the
  182. difference in starting time from the last train, the bike restriction
  183. stations, and the increment vector.  The increment vector needs some
  184. explanation: it is a vector of the increments to the starting time of
  185. the train to get the time at subsequent stations.  For BART (and I
  186. would think for other systems with decent schedules) there is a small
  187. number of unique increment vectors for each line.  In the
  188. make-pdb-file code, each set of trains with the same properties is
  189. referred to as a block.
  190.  
  191. Although the application supports both per-day and default transfer
  192. records, make-pdb-file creates only a default transfer record.  (The
  193. application will first check if a per-day transfer record exists for
  194. the selected day, and if not, use the default transfer record.)  We
  195. can get away with a single transfer record because BART uses the same
  196. 10 lines for weekdays and Saturdays, and only 6 of those lines for
  197. Sundays.  By ordering lines 0-5 the same for each of the three day
  198. categories, and ensuring that the order of lines 6-9 are the same for
  199. weekdays and Saturdays, the line information for transfers is
  200. consistent across all days.  When searching for valid transfers, the
  201. application simply rejects those transfers to or from a line greater
  202. than the number of lines for the current day.
  203.  
  204.  
  205. Other Miscellaneous Notes
  206. -------------------------
  207.  
  208. Restrictions/Limitations:
  209.  
  210. The fact that some quantities in the code and pdb file are represented
  211. as Bytes or SBytes, and the fact that we use the value 0xff in some
  212. cases to mean invalid, imposes the following restrictions on the data:
  213.  
  214. - at most 255 stations
  215. - at most 254 minutes difference between a train's first stop on its
  216.   line and its last stop on its line
  217. - between -128 and 127 minutes difference between successive trains'
  218.   first stops
  219. - at most 15 schedule day categories (due to catgory representation on
  220.   the pilot)
  221. - at most 248 lines (due to record numbering)
  222. - at most 255 trains on a line per day
  223. - at most 256 stops on each line
  224. - at most 256 increment vectors per line per day
  225. - in cents, min fare = M*m, max fare = M*(m+x), for M, m, x <= 255.
  226.   (see make-pdb-file:gen_fares_info)
  227.  
  228. Most of these limitations can be removed by changing the necessary
  229. variables in the *.[ch] files from Byte to Int, and changing the
  230. necessary pack call in make-pdb-file to pack a "n" instead of a "c" or
  231. "C".  If you do this, be careful about iteration variables as well as
  232. alignment issues!
  233.  
  234. One other limitation is imposed by the table in which the results are
  235. displayed.  Since there are only six columns, we can only display
  236. trips with two transfers.  It would be possible (and probably not too
  237. difficult), to add a horizontal scroll feature to the table to present
  238. more than six columns, if one needed to show trips with more than two
  239. transfers.
  240.  
  241.  
  242. Send questions, comments, or suggestions to wittman@cs.berkeley.edu.
  243.