src/departures.cpp

   1 /* $Id$ */
   2
   3 /*
   4  * This file is part of OpenTTD.
   5  * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
   6  * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
   7  * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
   8  */
   9
  10 /** @file departures.cpp Scheduled departures from a station. */
  11
  12 #include "stdafx.h"
  13 #include "debug.h"
  14 #include "gui.h"
  15 #include "textbuf_gui.h"
  16 #include "strings_func.h"
  17 #include "window_func.h"
  18 #include "vehicle_func.h"
  19 #include "string_func.h"
  20 #include "window_gui.h"
  21 #include "timetable.h"
  22 #include "vehiclelist.h"
  23 #include "company_base.h"
  24 #include "date_func.h"
  25 #include "departures_gui.h"
  26 #include "station_base.h"
  27 #include "vehicle_gui_base.h"
  28 #include "vehicle_base.h"
  29 #include "vehicle_gui.h"
  30 #include "order_base.h"
  31 #include "settings_type.h"
  32 #include "core/smallvec_type.hpp"
  33 #include "date_type.h"
  34 #include "company_type.h"
  35 #include "cargo_type.h"
  36 #include "departures_func.h"
  37 #include "departures_type.h"
  38
  39 /** A scheduled order. */
  40 typedef struct OrderDate
  41 {
  42         const Order *order;     ///< The order
  43         const Vehicle *v;       ///< The vehicle carrying out the order
  44         Ticks expected_date;    ///< The date on which the order is expected to complete
  45         Ticks lateness;         ///< How late this order is expected to finish
  46         DepartureStatus status; ///< Whether the vehicle has arrived to carry out the order yet
  47 } OrderDate;
  48
  49 static bool IsDeparture(const Order *order, StationID station) {
  50         return (order->GetType() == OT_GOTO_STATION &&
  51                         (StationID)order->GetDestination() == station &&
  52                         (order->GetLoadType() != OLFB_NO_LOAD ||
  53                         _settings_client.gui.departure_show_all_stops) &&
  54                         (order->GetWaitTime() != 0 || order->IsWaitTimetabled()) &&
  55                         !(order->GetNonStopType() & ONSF_NO_STOP_AT_DESTINATION_STATION));
  56 }
  57
  58 static bool IsVia(const Order *order, StationID station) {
  59         return ((order->GetType() == OT_GOTO_STATION ||
  60                         order->GetType() == OT_GOTO_WAYPOINT) &&
  61                         (StationID)order->GetDestination() == station &&
  62                         (order->GetNonStopType() == ONSF_NO_STOP_AT_ANY_STATION ||
  63                         order->GetNonStopType() == ONSF_NO_STOP_AT_DESTINATION_STATION));
  64 }
  65
  66 static bool IsArrival(const Order *order, StationID station) {
  67         return (order->GetType() == OT_GOTO_STATION &&
  68                         (StationID)order->GetDestination() == station &&
  69                         (order->GetUnloadType() != OUFB_NO_UNLOAD ||
  70                         _settings_client.gui.departure_show_all_stops) &&
  71                         (order->GetWaitTime() != 0 || order->IsWaitTimetabled()) &&
  72                         !(order->GetNonStopType() & ONSF_NO_STOP_AT_DESTINATION_STATION));
  73 }
  74
  75 /**
  76  * Compute an up-to-date list of departures for a station.
  77  * @param station the station to compute the departures of
  78  * @param show_vehicle_types the types of vehicles to include in the departure list
  79  * @param type the type of departures to get (departures or arrivals)
  80  * @param show_vehicles_via whether to include vehicles that have this station in their orders but do not stop at it
  81  * @param show_pax whether to include passenger vehicles
  82  * @param show_freight whether to include freight vehicles
  83  * @return a list of departures, which is empty if an error occurred
  84  */
  85 DepartureList* MakeDepartureList(StationID station, bool show_vehicle_types[5], DepartureType type, bool show_vehicles_via, bool show_pax, bool show_freight)
  86 {
  87         /* This function is the meat of the departure boards functionality. */
  88         /* As an overview, it works by repeatedly considering the best possible next departure to show. */
  89         /* By best possible we mean the one expected to arrive at the station first. */
  90         /* However, we do not consider departures whose scheduled time is too far in the future, even if they are expected before some delayed ones. */
  91         /* This code can probably be made more efficient. I haven't done so in order to keep both its (relative) simplicity and my (relative) sanity. */
  92         /* Having written that, it's not exactly slow at the moment. */
  93
  94         /* The list of departures which will be returned as a result. */
  95         SmallVector<Departure*, 32> *result = new SmallVector<Departure*, 32>();
  96
  97         if (!show_pax && !show_freight) return result;
  98
  99         /* A list of the next scheduled orders to be considered for inclusion in the departure list. */
 100         SmallVector<OrderDate*, 32> next_orders;
 101
 102         /* The maximum possible date for departures to be scheduled to occur. */
 103         Ticks max_date = INT_MAX;
 104
 105         /* The scheduled order in next_orders with the earliest expected_date field. */
 106         OrderDate *least_order = NULL;
 107
 108         /* Get all the vehicles stopping at this station. */
 109         /* We do this to get the order which is the first time they will stop at this station. */
 110         /* This order is stored along with some more information. */
 111         /* We keep a pointer to the `least' order (the one with the soonest expected completion time). */
 112         for (uint i = 0; i < 4; ++i) {
 113                 VehicleList vehicles;
 114
 115                 if (!show_vehicle_types[i]) {
 116                         /* Don't show vehicles whose type we're not interested in. */
 117                         continue;
 118                 }
 119
 120         /* MAX_COMPANIES is probably the wrong thing to put here, but it works. GenerateVehicleSortList doesn't check the company when the type of list is VL_STATION_LIST (r20801). */
 121                 if (!GenerateVehicleSortList(&vehicles, VehicleListIdentifier(VL_STATION_LIST, (VehicleType)(VEH_TRAIN + i), MAX_COMPANIES, station))) {
 122                         /* Something went wrong: panic! */
 123                         return result;
 124                 }
 125
 126                 /* Get the first order for each vehicle for the station we're interested in that doesn't have No Loading set. */
 127                 /* We find the least order while we're at it. */
 128                 for (const Vehicle **v = vehicles.Begin(); v != vehicles.End(); v++) {
 129                         if (show_pax != show_freight) {
 130                                 bool carries_passengers = false;
 131
 132                                 const Vehicle *u = *v;
 133                                 while (u != NULL) {
 134                                         if (u->cargo_cap > 0 && IsCargoInClass(u->cargo_type, CC_PASSENGERS)) {
 135                                                 carries_passengers = true;
 136                                                 break;
 137                                         }
 138                                         u = u->Next();
 139                                 }
 140
 141                                 if (carries_passengers != show_pax) {
 142                                         continue;
 143                                 }
 144                         }
 145
 146                         const Order *order = (*v)->GetOrder((*v)->cur_implicit_order_index % (*v)->GetNumOrders());
 147                         Ticks start_date = GetCurrentTickCount() - (*v)->current_order_time;
 148                         if ((*v)->cur_timetable_order_index != INVALID_VEH_ORDER_ID && (*v)->cur_timetable_order_index != (*v)->cur_real_order_index) {
 149                                 // Vehicle is taking a conditional order branch, adjust start time to compensate
 150                                 const Order *real_current_order = (*v)->GetOrder((*v)->cur_real_order_index);
 151                                 const Order *real_timetable_order = (*v)->GetOrder((*v)->cur_timetable_order_index);
 152                                 assert(real_timetable_order->IsType(OT_CONDITIONAL));
 153                                 start_date += (real_timetable_order->GetWaitTime() - real_current_order->GetTravelTime());
 154                         }
 155                         DepartureStatus status = D_TRAVELLING;
 156
 157                         /* If the vehicle is stopped in a depot, ignore it. */
 158                         if ((*v)->IsStoppedInDepot()) {
 159                                 continue;
 160                         }
 161
 162                         /* If the vehicle is heading for a depot to stop there, then its departures are cancelled. */
 163                         if ((*v)->current_order.IsType(OT_GOTO_DEPOT) && (*v)->current_order.GetDepotActionType() & ODATFB_HALT) {
 164                                 status = D_CANCELLED;
 165                         }
 166
 167                         if ((*v)->current_order.IsType(OT_LOADING)) {
 168                                 /* Account for the vehicle having reached the current order and being in the loading phase. */
 169                                 status = D_ARRIVED;
 170                                 start_date -= order->GetTravelTime() + (((*v)->lateness_counter < 0) ? (*v)->lateness_counter : 0);
 171                         }
 172
 173                         /* Loop through the vehicle's orders until we've found a suitable order or we've determined that no such order exists. */
 174                         /* We only need to consider each order at most once. */
 175                         for (int i = (*v)->GetNumOrders(); i > 0; --i) {
 176                                 start_date += order->GetTravelTime() + order->GetWaitTime();
 177
 178                                 /* If the scheduled departure date is too far in the future, stop. */
 179                                 if (start_date - (*v)->lateness_counter > max_date) {
 180                                         break;
 181                                 }
 182
 183                                 /* If the order is a conditional branch, handle it. */
 184                                 if (order->IsType(OT_CONDITIONAL)) {
 185                                         switch(_settings_client.gui.departure_conditionals) {
 186                                                         case 0: {
 187                                                                 /* Give up */
 188                                                                 break;
 189                                                         }
 190                                                         case 1: {
 191                                                                 /* Take the branch */
 192                                                                 if (status != D_CANCELLED) {
 193                                                                         status = D_TRAVELLING;
 194                                                                 }
 195                                                                 order = (*v)->GetOrder(order->GetConditionSkipToOrder());
 196                                                                 if (order == NULL) {
 197                                                                         break;
 198                                                                 }
 199
 200                                                                 start_date -= order->GetTravelTime();
 201
 202                                                                 continue;
 203                                                         }
 204                                                         case 2: {
 205                                                                 /* Do not take the branch */
 206                                                                 if (status != D_CANCELLED) {
 207                                                                         status = D_TRAVELLING;
 208                                                                 }
 209                                                                 order = (order->next == NULL) ? (*v)->GetFirstOrder() : order->next;
 210                                                                 continue;
 211                                                         }
 212                                         }
 213                                 }
 214
 215                                 /* Skip it if it's an automatic order. */
 216                                 if (order->IsType(OT_IMPLICIT)) {
 217                                         order = (order->next == NULL) ? (*v)->GetFirstOrder() : order->next;
 218                                         continue;
 219                                 }
 220
 221                                 /* If an order has a 0 travel time, and it's not explictly set, then stop. */
 222                                 if (order->GetTravelTime() == 0 && !order->IsTravelTimetabled()) {
 223                                         break;
 224                                 }
 225
 226                                 /* If the vehicle will be stopping at and loading from this station, and its wait time is not zero, then it is a departure. */
 227                                 /* If the vehicle will be stopping at and unloading at this station, and its wait time is not zero, then it is an arrival. */
 228                                 if ((type == D_DEPARTURE && IsDeparture(order, station)) ||
 229                                                 (type == D_DEPARTURE && show_vehicles_via && IsVia(order, station)) ||
 230                                                 (type == D_ARRIVAL && IsArrival(order, station))) {
 231                                         /* If the departure was scheduled to have already begun and has been cancelled, do not show it. */
 232                                         if (start_date < 0 && status == D_CANCELLED) {
 233                                                 break;
 234                                         }
 235
 236                                         OrderDate *od = new OrderDate();
 237                                         od->order = order;
 238                                         od->v = *v;
 239                                         /* We store the expected date for now, so that vehicles will be shown in order of expected time. */
 240                                         od->expected_date = start_date;
 241                                         od->lateness = (*v)->lateness_counter > 0 ? (*v)->lateness_counter : 0;
 242                                         od->status = status;
 243
 244                                         /* If we are early, use the scheduled date as the expected date. We also take lateness to be zero. */
 245                                         if ((*v)->lateness_counter < 0 && !(*v)->current_order.IsType(OT_LOADING)) {
 246                                                 od->expected_date -= (*v)->lateness_counter;
 247                                         }
 248
 249                                         /* Update least_order if this is the current least order. */
 250                                         if (least_order == NULL) {
 251                                                 least_order = od;
 252                                         } else if (least_order->expected_date - least_order->lateness - (type == D_ARRIVAL ? least_order->order->GetWaitTime() : 0) > od->expected_date - od->lateness - (type == D_ARRIVAL ? od->order->GetWaitTime() : 0)) {
 253                                                 least_order = od;
 254                                         }
 255
 256                                         *(next_orders.Append(1)) = od;
 257
 258                                         /* We're done with this vehicle. */
 259                                         break;
 260                                 } else {
 261                                         /* Go to the next order in the list. */
 262                                         if (status != D_CANCELLED) {
 263                                                 status = D_TRAVELLING;
 264                                         }
 265                                         order = (order->next == NULL) ? (*v)->GetFirstOrder() : order->next;
 266                                 }
 267                         }
 268                 }
 269         }
 270
 271         /* No suitable orders found? Then stop. */
 272         if (next_orders.Length() == 0) {
 273                 return result;
 274         }
 275
 276         /* We now find as many departures as we can. It's a little involved so I'll try to explain each major step. */
 277         /* The countdown from 10000 is a safeguard just in case something nasty happens. 10000 seemed large enough. */
 278         for(int i = 10000; i > 0; --i) {
 279                 /* I should probably try to convince you that this loop always terminates regardless of the safeguard. */
 280                 /* 1. next_orders contains at least one element. */
 281                 /* 2. The loop terminates if result->Length() exceeds a fixed (for this loop) value, or if the least order's scheduled date is later than max_date. */
 282                 /*    (We ignore the case that the least order's scheduled date has overflown, as it is a relative rather than absolute date.) */
 283                 /* 3. Every time we loop round, either result->Length() will have increased -OR- we will have increased the expected_date of one of the elements of next_orders. */
 284                 /* 4. Therefore the loop must eventually terminate. */
 285
 286                 /* least_order is the best candidate for the next departure. */
 287
 288                 /* First, we check if we can stop looking for departures yet. */
 289                 if (result->Length() >= _settings_client.gui.max_departures ||
 290                                 least_order->expected_date - least_order->lateness > max_date) {
 291                         break;
 292                 }
 293
 294                 /* We already know the least order and that it's a suitable departure, so make it into a departure. */
 295                 Departure *d = new Departure();
 296                 d->scheduled_date = least_order->expected_date - least_order->lateness;
 297                 d->lateness = least_order->lateness;
 298                 d->status = least_order->status;
 299                 d->vehicle = least_order->v->index;
 300                 d->type = type;
 301                 d->order = least_order->order->index;
 302
 303                 /* We'll be going through the order list later, so we need a separate variable for it. */
 304                 const Order *order = least_order->order;
 305
 306                 if (type == D_DEPARTURE) {
 307                         /* Computing departures: */
 308                         /* We want to find out where it will terminate, making a list of the stations it calls at along the way. */
 309                         /* We only count stations where unloading happens as being called at - i.e. pickup-only stations are ignored. */
 310                         /* Where the vehicle terminates is defined as the last unique station called at by the vehicle from the current order. */
 311
 312                         /* If the vehicle loops round to the current order without a terminus being found, then it terminates upon reaching its current order again. */
 313
 314                         /* We also determine which station this departure is going via, if any. */
 315                         /* A departure goes via a station if it is the first station for which the vehicle has an order to go via or non-stop via. */
 316                         /* Multiple departures on the same journey may go via different stations. That a departure can go via at most one station is intentional. */
 317
 318                         /* We keep track of potential via stations along the way. If we call at a station immediately after going via it, then it is the via station. */
 319                         StationID candidate_via = INVALID_STATION;
 320
 321                         /* Go through the order list, looping if necessary, to find a terminus. */
 322                         /* Get the next order, which may be the vehicle's first order. */
 323                         order = (order->next == NULL) ? least_order->v->GetFirstOrder() : order->next;
 324                         /* We only need to consider each order at most once. */
 325                         bool found_terminus = false;
 326                         CallAt c = CallAt((StationID)order->GetDestination(), d->scheduled_date);
 327                         for (int i = least_order->v->GetNumOrders(); i > 0; --i) {
 328                                 /* If we reach the order at which the departure occurs again, then use the departure station as the terminus. */
 329                                 if (order == least_order->order) {
 330                                         /* If we're not calling anywhere, then skip this departure. */
 331                                         found_terminus = (d->calling_at.Length() > 0);
 332                                         break;
 333                                 }
 334
 335                                 /* If the order is a conditional branch, handle it. */
 336                                 if (order->IsType(OT_CONDITIONAL)) {
 337                                         switch(_settings_client.gui.departure_conditionals) {
 338                                                         case 0: {
 339                                                                 /* Give up */
 340                                                                 break;
 341                                                         }
 342                                                         case 1: {
 343                                                                 /* Take the branch */
 344                                                                 order = least_order->v->GetOrder(order->GetConditionSkipToOrder());
 345                                                                 if (order == NULL) {
 346                                                                         break;
 347                                                                 }
 348                                                                 continue;
 349                                                         }
 350                                                         case 2: {
 351                                                                 /* Do not take the branch */
 352                                                                 order = (order->next == NULL) ? least_order->v->GetFirstOrder() : order->next;
 353                                                                 continue;
 354                                                         }
 355                                         }
 356                                 }
 357
 358                                 /* If we reach the original station again, then use it as the terminus. */
 359                                 if (order->GetType() == OT_GOTO_STATION &&
 360                                                 (StationID)order->GetDestination() == station &&
 361                                                 (order->GetUnloadType() != OUFB_NO_UNLOAD ||
 362                                                 _settings_client.gui.departure_show_all_stops) &&
 363                                                 order->GetNonStopType() != ONSF_NO_STOP_AT_ANY_STATION &&
 364                                                 order->GetNonStopType() != ONSF_NO_STOP_AT_DESTINATION_STATION) {
 365                                         /* If we're not calling anywhere, then skip this departure. */
 366                                         found_terminus = (d->calling_at.Length() > 0);
 367                                         break;
 368                                 }
 369
 370                                 /* Check if we're going via this station. */
 371                                 if ((order->GetNonStopType() == ONSF_NO_STOP_AT_ANY_STATION ||
 372                                                 order->GetNonStopType() == ONSF_NO_STOP_AT_DESTINATION_STATION) &&
 373                                                 order->GetType() == OT_GOTO_STATION &&
 374                                                 d->via == INVALID_STATION) {
 375                                         candidate_via = (StationID)order->GetDestination();
 376                                 }
 377
 378                                 if (c.scheduled_date != 0 && (order->GetTravelTime() != 0 || order->IsTravelTimetabled())) {
 379                                         c.scheduled_date += order->GetTravelTime();
 380                                 } else {
 381                                         c.scheduled_date = 0;
 382                                 }
 383
 384                                 c.station = (StationID)order->GetDestination();
 385
 386                                 /* We're not interested in this order any further if we're not calling at it. */
 387                                 if ((order->GetUnloadType() == OUFB_NO_UNLOAD &&
 388                                                 !_settings_client.gui.departure_show_all_stops) ||
 389                                                 (order->GetType() != OT_GOTO_STATION &&
 390                                                 order->GetType() != OT_IMPLICIT) ||
 391                                                 order->GetNonStopType() == ONSF_NO_STOP_AT_ANY_STATION ||
 392                                                 order->GetNonStopType() == ONSF_NO_STOP_AT_DESTINATION_STATION) {
 393                                         c.scheduled_date += order->GetWaitTime();
 394                                         order = (order->next == NULL) ? least_order->v->GetFirstOrder() : order->next;
 395                                         continue;
 396                                 }
 397
 398                                 /* If this order's station is already in the calling, then the previous called at station is the terminus. */
 399                                 if (d->calling_at.Contains(c)) {
 400                                         found_terminus = true;
 401                                         break;
 402                                 }
 403
 404                                 /* If appropriate, add the station to the calling at list and make it the candidate terminus. */
 405                                 if ((order->GetType() == OT_GOTO_STATION ||
 406                                                 order->GetType() == OT_IMPLICIT) &&
 407                                                 order->GetNonStopType() != ONSF_NO_STOP_AT_ANY_STATION &&
 408                                                 order->GetNonStopType() != ONSF_NO_STOP_AT_DESTINATION_STATION) {
 409                                         if (d->via == INVALID_STATION && candidate_via == (StationID)order->GetDestination()) {
 410                                                 d->via = (StationID)order->GetDestination();
 411                                         }
 412                                         d->terminus = c;
 413                                         *(d->calling_at.Append(1)) = c;
 414                                 }
 415
 416                                 /* If we unload all at this station, then it is the terminus. */
 417                                 if (order->GetType() == OT_GOTO_STATION &&
 418                                                 order->GetUnloadType() == OUFB_UNLOAD) {
 419                                         if (d->calling_at.Length() > 0) {
 420                                                 found_terminus = true;
 421                                         }
 422                                         break;
 423                                 }
 424
 425                                 c.scheduled_date += order->GetWaitTime();
 426
 427                                 /* Get the next order, which may be the vehicle's first order. */
 428                                 order = (order->next == NULL) ? least_order->v->GetFirstOrder() : order->next;
 429                         }
 430
 431                         if (found_terminus) {
 432                                 /* Add the departure to the result list. */
 433                 bool duplicate = false;
 434
 435                 if (_settings_client.gui.departure_merge_identical) {
 436                     for (uint i = 0; i < result->Length(); ++i) {
 437                         if (*d == **(result->Get(i))) {
 438                             duplicate = true;
 439                             break;
 440                         }
 441                     }
 442                 }
 443
 444                 if (!duplicate) {
 445                     *(result->Append(1)) = d;
 446
 447                     if (_settings_client.gui.departure_smart_terminus && type == D_DEPARTURE) {
 448                         for (uint i = 0; i < result->Length()-1; ++i) {
 449                             Departure *d_first = *(result->Get(i));
 450                             uint k = d_first->calling_at.Length()-2;
 451                             for (uint j = d->calling_at.Length(); j > 0; --j) {
 452                                 CallAt c = CallAt(*(d->calling_at.Get(j-1)));
 453
 454                                 if (d_first->terminus >= c && d_first->calling_at.Length() >= 2) {
 455                                     d_first->terminus = CallAt(*(d_first->calling_at.Get(k)));
 456
 457                                     if (k == 0) break;
 458
 459                                     k--;
 460                                 }
 461                             }
 462                         }
 463                     }
 464
 465                     /* If the vehicle is expected to be late, we want to know what time it will arrive rather than depart. */
 466                     /* This is done because it looked silly to me to have a vehicle not be expected for another few days, yet it be at the same time pulling into the station. */
 467                     if (d->status != D_ARRIVED &&
 468                             d->lateness > 0) {
 469                         d->lateness -= least_order->order->GetWaitTime();
 470                     }
 471                 }
 472                         }
 473                 } else {
 474                         /* Computing arrivals: */
 475                         /* First we need to find the origin of the order. This is somewhat like finding a terminus, but a little more involved since order lists are singly linked. */
 476                         /* The next stage is simpler. We just need to add all the stations called at on the way to the current station. */
 477                         /* Again, we define a station as being called at if the vehicle loads from it. */
 478
 479                         /* However, the very first thing we do is use the arrival time as the scheduled time instead of the departure time. */
 480                         d->scheduled_date -= order->GetWaitTime();
 481
 482                         const Order *candidate_origin = (order->next == NULL) ? least_order->v->GetFirstOrder() : order->next;
 483                         bool found_origin = false;
 484
 485                         while (candidate_origin != least_order->order) {
 486                                 if ((candidate_origin->GetLoadType() != OLFB_NO_LOAD ||
 487                                                 _settings_client.gui.departure_show_all_stops) &&
 488                                                 (candidate_origin->GetType() == OT_GOTO_STATION ||
 489                                                 candidate_origin->GetType() == OT_IMPLICIT) &&
 490                                                 candidate_origin->GetDestination() != station) {
 491                                         const Order *o = (candidate_origin->next == NULL) ? least_order->v->GetFirstOrder() : candidate_origin->next;
 492                                         bool found_collision = false;
 493
 494                                         /* Check if the candidate origin's destination appears again before the original order or the station does. */
 495                                         while (o != least_order->order) {
 496                                                 if (o->GetUnloadType() == OUFB_UNLOAD) {
 497                                                         found_collision = true;
 498                                                         break;
 499                                                 }
 500
 501                                                 if ((o->GetType() == OT_GOTO_STATION ||
 502                                                                 o->GetType() == OT_IMPLICIT) &&
 503                                                                 (o->GetDestination() == candidate_origin->GetDestination() ||
 504                                                                 o->GetDestination() == station)) {
 505                                                         found_collision = true;
 506                                                         break;
 507                                                 }
 508
 509                                                 o = (o->next == NULL) ? least_order->v->GetFirstOrder() : o->next;
 510                                         }
 511
 512                                         /* If it doesn't, then we have found the origin. */
 513                                         if (!found_collision) {
 514                                                 found_origin = true;
 515                                                 break;
 516                                         }
 517                                 }
 518
 519                                 candidate_origin = (candidate_origin->next == NULL) ? least_order->v->GetFirstOrder() : candidate_origin->next;
 520                         }
 521
 522                         order = (candidate_origin->next == NULL) ? least_order->v->GetFirstOrder() : candidate_origin->next;
 523
 524                         while (order != least_order->order) {
 525                                 if (order->GetType() == OT_GOTO_STATION &&
 526                                                 (order->GetLoadType() != OLFB_NO_LOAD ||
 527                                                 _settings_client.gui.departure_show_all_stops)) {
 528                                         *(d->calling_at.Append(1)) = CallAt((StationID)order->GetDestination());
 529                                 }
 530
 531                                 order = (order->next == NULL) ? least_order->v->GetFirstOrder() : order->next;
 532                         }
 533
 534                         d->terminus = CallAt((StationID)candidate_origin->GetDestination());
 535
 536                         if (found_origin) {
 537                 bool duplicate = false;
 538
 539                 if (_settings_client.gui.departure_merge_identical) {
 540                     for (uint i = 0; i < result->Length(); ++i) {
 541                         if (*d == **(result->Get(i))) {
 542                             duplicate = true;
 543                             break;
 544                         }
 545                     }
 546                 }
 547
 548                 if (!duplicate) {
 549                     *(result->Append(1)) = d;
 550                 }
 551                         }
 552                 }
 553
 554                 /* Save on pointer dereferences in the coming loop. */
 555                 order = least_order->order;
 556
 557                 /* Now we find the next suitable order for being a departure for this vehicle. */
 558                 /* We do this in a similar way to finding the first suitable order for the vehicle. */
 559
 560                 /* Go to the next order so we don't add the current order again. */
 561                 order = (order->next == NULL) ? least_order->v->GetFirstOrder() : order->next;
 562                 least_order->expected_date += order->GetTravelTime() + order->GetWaitTime();
 563
 564                 /* Go through the order list to find the next candidate departure. */
 565                 /* We only need to consider each order at most once. */
 566                 bool found_next_order = false;
 567                 for (int i = least_order->v->GetNumOrders(); i > 0; --i) {
 568                         /* If the order is a conditional branch, handle it. */
 569                         if (order->IsType(OT_CONDITIONAL)) {
 570                                 switch(_settings_client.gui.departure_conditionals) {
 571                                                 case 0: {
 572                                                         /* Give up */
 573                                                         break;
 574                                                 }
 575                                                 case 1: {
 576                                                         /* Take the branch */
 577                                                         order = least_order->v->GetOrder(order->GetConditionSkipToOrder());
 578                                                         if (order == NULL) {
 579                                                                 break;
 580                                                         }
 581
 582                                                         least_order->expected_date += order->GetWaitTime();
 583
 584                                                         continue;
 585                                                 }
 586                                                 case 2: {
 587                                                         /* Do not take the branch */
 588                                                         order = (order->next == NULL) ? least_order->v->GetFirstOrder() : order->next;
 589                                                         least_order->expected_date += order->GetTravelTime() + order->GetWaitTime();
 590                                                         continue;
 591                                                 }
 592                                 }
 593                         }
 594
 595                         /* Skip it if it's an automatic order. */
 596                         if (order->IsType(OT_IMPLICIT)) {
 597                                 order = (order->next == NULL) ? least_order->v->GetFirstOrder() : order->next;
 598                                 continue;
 599                         }
 600
 601                         /* If an order has a 0 travel time, and it's not explictly set, then stop. */
 602                         if (order->GetTravelTime() == 0 && !order->IsTravelTimetabled()) {
 603                                 break;
 604                         }
 605
 606                         /* If the departure is scheduled to be too late, then stop. */
 607                         if (least_order->expected_date - least_order->lateness > max_date) {
 608                                 break;
 609                         }
 610
 611                         /* If the order loads from this station (or unloads if we're computing arrivals) and has a wait time set, then it is suitable for being a departure. */
 612                         if ((type == D_DEPARTURE && IsDeparture(order, station)) ||
 613                                                 (type == D_DEPARTURE && show_vehicles_via && IsVia(order, station)) ||
 614                                                 (type == D_ARRIVAL && IsArrival(order, station))) {
 615                                 least_order->order = order;
 616                                 found_next_order = true;
 617                                 break;
 618                         }
 619
 620                         order = (order->next == NULL) ? least_order->v->GetFirstOrder() : order->next;
 621                         least_order->expected_date += order->GetTravelTime() + order->GetWaitTime();
 622                 }
 623
 624                 /* If we didn't find a suitable order for being a departure, then we can ignore this vehicle from now on. */
 625                 if (!found_next_order) {
 626                         /* Make sure we don't try to get departures out of this order. */
 627                         /* This is cheaper than deleting it from next_orders. */
 628                         /* If we ever get to a state where _date * DAY_TICKS is close to INT_MAX, then we'll have other problems anyway as departures' scheduled dates will wrap around. */
 629                         least_order->expected_date = INT32_MAX;
 630                 }
 631
 632                 /* The vehicle can't possibly have arrived at its next candidate departure yet. */
 633                 if (least_order->status == D_ARRIVED) {
 634                         least_order->status = D_TRAVELLING;
 635                 }
 636
 637                 /* Find the new least order. */
 638                 for (uint i = 0; i < next_orders.Length(); ++i) {
 639                         OrderDate *od = *(next_orders.Get(i));
 640
 641                         Ticks lod = least_order->expected_date - least_order->lateness;
 642                         Ticks odd = od->expected_date - od->lateness;
 643
 644                         if (type == D_ARRIVAL) {
 645                                 lod -= least_order->order->GetWaitTime();
 646                                 odd -= od->order->GetWaitTime();
 647                         }
 648
 649                         if (lod > odd && od->expected_date - od->lateness < max_date) {
 650                                 least_order = od;
 651                         }
 652                 }
 653         }
 654
 655         /* Avoid leaking OrderDate structs */
 656         for (uint i = 0; i < next_orders.Length(); ++i) {
 657                 OrderDate *od = *(next_orders.Get(i));
 658                 delete od;
 659         }
 660
 661         /* Done. Phew! */
 662         return result;
 663 }