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                         DepartureStatus status = D_TRAVELLING;
 149
 150                         /* If the vehicle is stopped in a depot, ignore it. */
 151                         if ((*v)->IsStoppedInDepot()) {
 152                                 continue;
 153                         }
 154
 155                         /* If the vehicle is heading for a depot to stop there, then its departures are cancelled. */
 156                         if ((*v)->current_order.IsType(OT_GOTO_DEPOT) && (*v)->current_order.GetDepotActionType() & ODATFB_HALT) {
 157                                 status = D_CANCELLED;
 158                         }
 159
 160                         if ((*v)->current_order.IsType(OT_LOADING)) {
 161                                 /* Account for the vehicle having reached the current order and being in the loading phase. */
 162                                 status = D_ARRIVED;
 163                                 start_date -= order->GetTravelTime() + (((*v)->lateness_counter < 0) ? (*v)->lateness_counter : 0);
 164                         }
 165
 166                         /* Loop through the vehicle's orders until we've found a suitable order or we've determined that no such order exists. */
 167                         /* We only need to consider each order at most once. */
 168                         for (int i = (*v)->GetNumOrders(); i > 0; --i) {
 169                                 start_date += order->GetTravelTime() + order->GetWaitTime();
 170
 171                                 /* If the scheduled departure date is too far in the future, stop. */
 172                                 if (start_date - (*v)->lateness_counter > max_date) {
 173                                         break;
 174                                 }
 175
 176                                 /* If the order is a conditional branch, handle it. */
 177                                 if (order->IsType(OT_CONDITIONAL)) {
 178                                         switch(_settings_client.gui.departure_conditionals) {
 179                                                         case 0: {
 180                                                                 /* Give up */
 181                                                                 break;
 182                                                         }
 183                                                         case 1: {
 184                                                                 /* Take the branch */
 185                                                                 if (status != D_CANCELLED) {
 186                                                                         status = D_TRAVELLING;
 187                                                                 }
 188                                                                 order = (*v)->GetOrder(order->GetConditionSkipToOrder());
 189                                                                 if (order == NULL) {
 190                                                                         break;
 191                                                                 }
 192
 193                                                                 start_date -= order->GetTravelTime();
 194
 195                                                                 continue;
 196                                                         }
 197                                                         case 2: {
 198                                                                 /* Do not take the branch */
 199                                                                 if (status != D_CANCELLED) {
 200                                                                         status = D_TRAVELLING;
 201                                                                 }
 202                                                                 order = (order->next == NULL) ? (*v)->GetFirstOrder() : order->next;
 203                                                                 continue;
 204                                                         }
 205                                         }
 206                                 }
 207
 208                                 /* Skip it if it's an automatic order. */
 209                                 if (order->IsType(OT_IMPLICIT)) {
 210                                         order = (order->next == NULL) ? (*v)->GetFirstOrder() : order->next;
 211                                         continue;
 212                                 }
 213
 214                                 /* If an order has a 0 travel time, and it's not explictly set, then stop. */
 215                                 if (order->GetTravelTime() == 0 && !order->IsTravelTimetabled()) {
 216                                         break;
 217                                 }
 218
 219                                 /* If the vehicle will be stopping at and loading from this station, and its wait time is not zero, then it is a departure. */
 220                                 /* If the vehicle will be stopping at and unloading at this station, and its wait time is not zero, then it is an arrival. */
 221                                 if ((type == D_DEPARTURE && IsDeparture(order, station)) ||
 222                                                 (type == D_DEPARTURE && show_vehicles_via && IsVia(order, station)) ||
 223                                                 (type == D_ARRIVAL && IsArrival(order, station))) {
 224                                         /* If the departure was scheduled to have already begun and has been cancelled, do not show it. */
 225                                         if (start_date < 0 && status == D_CANCELLED) {
 226                                                 break;
 227                                         }
 228
 229                                         OrderDate *od = new OrderDate();
 230                                         od->order = order;
 231                                         od->v = *v;
 232                                         /* We store the expected date for now, so that vehicles will be shown in order of expected time. */
 233                                         od->expected_date = start_date;
 234                                         od->lateness = (*v)->lateness_counter > 0 ? (*v)->lateness_counter : 0;
 235                                         od->status = status;
 236
 237                                         /* If we are early, use the scheduled date as the expected date. We also take lateness to be zero. */
 238                                         if ((*v)->lateness_counter < 0 && !(*v)->current_order.IsType(OT_LOADING)) {
 239                                                 od->expected_date -= (*v)->lateness_counter;
 240                                         }
 241
 242                                         /* Update least_order if this is the current least order. */
 243                                         if (least_order == NULL) {
 244                                                 least_order = od;
 245                                         } 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)) {
 246                                                 least_order = od;
 247                                         }
 248
 249                                         *(next_orders.Append(1)) = od;
 250
 251                                         /* We're done with this vehicle. */
 252                                         break;
 253                                 } else {
 254                                         /* Go to the next order in the list. */
 255                                         if (status != D_CANCELLED) {
 256                                                 status = D_TRAVELLING;
 257                                         }
 258                                         order = (order->next == NULL) ? (*v)->GetFirstOrder() : order->next;
 259                                 }
 260                         }
 261                 }
 262         }
 263
 264         /* No suitable orders found? Then stop. */
 265         if (next_orders.Length() == 0) {
 266                 return result;
 267         }
 268
 269         /* We now find as many departures as we can. It's a little involved so I'll try to explain each major step. */
 270         /* The countdown from 10000 is a safeguard just in case something nasty happens. 10000 seemed large enough. */
 271         for(int i = 10000; i > 0; --i) {
 272                 /* I should probably try to convince you that this loop always terminates regardless of the safeguard. */
 273                 /* 1. next_orders contains at least one element. */
 274                 /* 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. */
 275                 /*    (We ignore the case that the least order's scheduled date has overflown, as it is a relative rather than absolute date.) */
 276                 /* 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. */
 277                 /* 4. Therefore the loop must eventually terminate. */
 278
 279                 /* least_order is the best candidate for the next departure. */
 280
 281                 /* First, we check if we can stop looking for departures yet. */
 282                 if (result->Length() >= _settings_client.gui.max_departures ||
 283                                 least_order->expected_date - least_order->lateness > max_date) {
 284                         break;
 285                 }
 286
 287                 /* We already know the least order and that it's a suitable departure, so make it into a departure. */
 288                 Departure *d = new Departure();
 289                 d->scheduled_date = least_order->expected_date - least_order->lateness;
 290                 d->lateness = least_order->lateness;
 291                 d->status = least_order->status;
 292                 d->vehicle = least_order->v->index;
 293                 d->type = type;
 294                 d->order = least_order->order->index;
 295
 296                 /* We'll be going through the order list later, so we need a separate variable for it. */
 297                 const Order *order = least_order->order;
 298
 299                 if (type == D_DEPARTURE) {
 300                         /* Computing departures: */
 301                         /* We want to find out where it will terminate, making a list of the stations it calls at along the way. */
 302                         /* We only count stations where unloading happens as being called at - i.e. pickup-only stations are ignored. */
 303                         /* Where the vehicle terminates is defined as the last unique station called at by the vehicle from the current order. */
 304
 305                         /* If the vehicle loops round to the current order without a terminus being found, then it terminates upon reaching its current order again. */
 306
 307                         /* We also determine which station this departure is going via, if any. */
 308                         /* 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. */
 309                         /* Multiple departures on the same journey may go via different stations. That a departure can go via at most one station is intentional. */
 310
 311                         /* 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. */
 312                         StationID candidate_via = INVALID_STATION;
 313
 314                         /* Go through the order list, looping if necessary, to find a terminus. */
 315                         /* Get the next order, which may be the vehicle's first order. */
 316                         order = (order->next == NULL) ? least_order->v->GetFirstOrder() : order->next;
 317                         /* We only need to consider each order at most once. */
 318                         bool found_terminus = false;
 319                         CallAt c = CallAt((StationID)order->GetDestination(), d->scheduled_date);
 320                         for (int i = least_order->v->GetNumOrders(); i > 0; --i) {
 321                                 /* If we reach the order at which the departure occurs again, then use the departure station as the terminus. */
 322                                 if (order == least_order->order) {
 323                                         /* If we're not calling anywhere, then skip this departure. */
 324                                         found_terminus = (d->calling_at.Length() > 0);
 325                                         break;
 326                                 }
 327
 328                                 /* If the order is a conditional branch, handle it. */
 329                                 if (order->IsType(OT_CONDITIONAL)) {
 330                                         switch(_settings_client.gui.departure_conditionals) {
 331                                                         case 0: {
 332                                                                 /* Give up */
 333                                                                 break;
 334                                                         }
 335                                                         case 1: {
 336                                                                 /* Take the branch */
 337                                                                 order = least_order->v->GetOrder(order->GetConditionSkipToOrder());
 338                                                                 if (order == NULL) {
 339                                                                         break;
 340                                                                 }
 341                                                                 continue;
 342                                                         }
 343                                                         case 2: {
 344                                                                 /* Do not take the branch */
 345                                                                 order = (order->next == NULL) ? least_order->v->GetFirstOrder() : order->next;
 346                                                                 continue;
 347                                                         }
 348                                         }
 349                                 }
 350
 351                                 /* If we reach the original station again, then use it as the terminus. */
 352                                 if (order->GetType() == OT_GOTO_STATION &&
 353                                                 (StationID)order->GetDestination() == station &&
 354                                                 (order->GetUnloadType() != OUFB_NO_UNLOAD ||
 355                                                 _settings_client.gui.departure_show_all_stops) &&
 356                                                 order->GetNonStopType() != ONSF_NO_STOP_AT_ANY_STATION &&
 357                                                 order->GetNonStopType() != ONSF_NO_STOP_AT_DESTINATION_STATION) {
 358                                         /* If we're not calling anywhere, then skip this departure. */
 359                                         found_terminus = (d->calling_at.Length() > 0);
 360                                         break;
 361                                 }
 362
 363                                 /* Check if we're going via this station. */
 364                                 if ((order->GetNonStopType() == ONSF_NO_STOP_AT_ANY_STATION ||
 365                                                 order->GetNonStopType() == ONSF_NO_STOP_AT_DESTINATION_STATION) &&
 366                                                 order->GetType() == OT_GOTO_STATION &&
 367                                                 d->via == INVALID_STATION) {
 368                                         candidate_via = (StationID)order->GetDestination();
 369                                 }
 370
 371                                 if (c.scheduled_date != 0 && (order->GetTravelTime() != 0 || order->IsTravelTimetabled())) {
 372                                         c.scheduled_date += order->GetTravelTime();
 373                                 } else {
 374                                         c.scheduled_date = 0;
 375                                 }
 376
 377                                 c.station = (StationID)order->GetDestination();
 378
 379                                 /* We're not interested in this order any further if we're not calling at it. */
 380                                 if ((order->GetUnloadType() == OUFB_NO_UNLOAD &&
 381                                                 !_settings_client.gui.departure_show_all_stops) ||
 382                                                 (order->GetType() != OT_GOTO_STATION &&
 383                                                 order->GetType() != OT_IMPLICIT) ||
 384                                                 order->GetNonStopType() == ONSF_NO_STOP_AT_ANY_STATION ||
 385                                                 order->GetNonStopType() == ONSF_NO_STOP_AT_DESTINATION_STATION) {
 386                                         c.scheduled_date += order->GetWaitTime();
 387                                         order = (order->next == NULL) ? least_order->v->GetFirstOrder() : order->next;
 388                                         continue;
 389                                 }
 390
 391                                 /* If this order's station is already in the calling, then the previous called at station is the terminus. */
 392                                 if (d->calling_at.Contains(c)) {
 393                                         found_terminus = true;
 394                                         break;
 395                                 }
 396
 397                                 /* If appropriate, add the station to the calling at list and make it the candidate terminus. */
 398                                 if ((order->GetType() == OT_GOTO_STATION ||
 399                                                 order->GetType() == OT_IMPLICIT) &&
 400                                                 order->GetNonStopType() != ONSF_NO_STOP_AT_ANY_STATION &&
 401                                                 order->GetNonStopType() != ONSF_NO_STOP_AT_DESTINATION_STATION) {
 402                                         if (d->via == INVALID_STATION && candidate_via == (StationID)order->GetDestination()) {
 403                                                 d->via = (StationID)order->GetDestination();
 404                                         }
 405                                         d->terminus = c;
 406                                         *(d->calling_at.Append(1)) = c;
 407                                 }
 408
 409                                 /* If we unload all at this station, then it is the terminus. */
 410                                 if (order->GetType() == OT_GOTO_STATION &&
 411                                                 order->GetUnloadType() == OUFB_UNLOAD) {
 412                                         if (d->calling_at.Length() > 0) {
 413                                                 found_terminus = true;
 414                                         }
 415                                         break;
 416                                 }
 417
 418                                 c.scheduled_date += order->GetWaitTime();
 419
 420                                 /* Get the next order, which may be the vehicle's first order. */
 421                                 order = (order->next == NULL) ? least_order->v->GetFirstOrder() : order->next;
 422                         }
 423
 424                         if (found_terminus) {
 425                                 /* Add the departure to the result list. */
 426                 bool duplicate = false;
 427
 428                 if (_settings_client.gui.departure_merge_identical) {
 429                     for (uint i = 0; i < result->Length(); ++i) {
 430                         if (*d == **(result->Get(i))) {
 431                             duplicate = true;
 432                             break;
 433                         }
 434                     }
 435                 }
 436
 437                 if (!duplicate) {
 438                     *(result->Append(1)) = d;
 439
 440                     if (_settings_client.gui.departure_smart_terminus && type == D_DEPARTURE) {
 441                         for (uint i = 0; i < result->Length()-1; ++i) {
 442                             Departure *d_first = *(result->Get(i));
 443                             uint k = d_first->calling_at.Length()-2;
 444                             for (uint j = d->calling_at.Length(); j > 0; --j) {
 445                                 CallAt c = CallAt(*(d->calling_at.Get(j-1)));
 446
 447                                 if (d_first->terminus >= c && d_first->calling_at.Length() >= 2) {
 448                                     d_first->terminus = CallAt(*(d_first->calling_at.Get(k)));
 449
 450                                     if (k == 0) break;
 451
 452                                     k--;
 453                                 }
 454                             }
 455                         }
 456                     }
 457
 458                     /* If the vehicle is expected to be late, we want to know what time it will arrive rather than depart. */
 459                     /* 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. */
 460                     if (d->status != D_ARRIVED &&
 461                             d->lateness > 0) {
 462                         d->lateness -= least_order->order->GetWaitTime();
 463                     }
 464                 }
 465                         }
 466                 } else {
 467                         /* Computing arrivals: */
 468                         /* 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. */
 469                         /* The next stage is simpler. We just need to add all the stations called at on the way to the current station. */
 470                         /* Again, we define a station as being called at if the vehicle loads from it. */
 471
 472                         /* However, the very first thing we do is use the arrival time as the scheduled time instead of the departure time. */
 473                         d->scheduled_date -= order->GetWaitTime();
 474
 475                         const Order *candidate_origin = (order->next == NULL) ? least_order->v->GetFirstOrder() : order->next;
 476                         bool found_origin = false;
 477
 478                         while (candidate_origin != least_order->order) {
 479                                 if ((candidate_origin->GetLoadType() != OLFB_NO_LOAD ||
 480                                                 _settings_client.gui.departure_show_all_stops) &&
 481                                                 (candidate_origin->GetType() == OT_GOTO_STATION ||
 482                                                 candidate_origin->GetType() == OT_IMPLICIT) &&
 483                                                 candidate_origin->GetDestination() != station) {
 484                                         const Order *o = (candidate_origin->next == NULL) ? least_order->v->GetFirstOrder() : candidate_origin->next;
 485                                         bool found_collision = false;
 486
 487                                         /* Check if the candidate origin's destination appears again before the original order or the station does. */
 488                                         while (o != least_order->order) {
 489                                                 if (o->GetUnloadType() == OUFB_UNLOAD) {
 490                                                         found_collision = true;
 491                                                         break;
 492                                                 }
 493
 494                                                 if ((o->GetType() == OT_GOTO_STATION ||
 495                                                                 o->GetType() == OT_IMPLICIT) &&
 496                                                                 (o->GetDestination() == candidate_origin->GetDestination() ||
 497                                                                 o->GetDestination() == station)) {
 498                                                         found_collision = true;
 499                                                         break;
 500                                                 }
 501
 502                                                 o = (o->next == NULL) ? least_order->v->GetFirstOrder() : o->next;
 503                                         }
 504
 505                                         /* If it doesn't, then we have found the origin. */
 506                                         if (!found_collision) {
 507                                                 found_origin = true;
 508                                                 break;
 509                                         }
 510                                 }
 511
 512                                 candidate_origin = (candidate_origin->next == NULL) ? least_order->v->GetFirstOrder() : candidate_origin->next;
 513                         }
 514
 515                         order = (candidate_origin->next == NULL) ? least_order->v->GetFirstOrder() : candidate_origin->next;
 516
 517                         while (order != least_order->order) {
 518                                 if (order->GetType() == OT_GOTO_STATION &&
 519                                                 (order->GetLoadType() != OLFB_NO_LOAD ||
 520                                                 _settings_client.gui.departure_show_all_stops)) {
 521                                         *(d->calling_at.Append(1)) = CallAt((StationID)order->GetDestination());
 522                                 }
 523
 524                                 order = (order->next == NULL) ? least_order->v->GetFirstOrder() : order->next;
 525                         }
 526
 527                         d->terminus = CallAt((StationID)candidate_origin->GetDestination());
 528
 529                         if (found_origin) {
 530                 bool duplicate = false;
 531
 532                 if (_settings_client.gui.departure_merge_identical) {
 533                     for (uint i = 0; i < result->Length(); ++i) {
 534                         if (*d == **(result->Get(i))) {
 535                             duplicate = true;
 536                             break;
 537                         }
 538                     }
 539                 }
 540
 541                 if (!duplicate) {
 542                     *(result->Append(1)) = d;
 543                 }
 544                         }
 545                 }
 546
 547                 /* Save on pointer dereferences in the coming loop. */
 548                 order = least_order->order;
 549
 550                 /* Now we find the next suitable order for being a departure for this vehicle. */
 551                 /* We do this in a similar way to finding the first suitable order for the vehicle. */
 552
 553                 /* Go to the next order so we don't add the current order again. */
 554                 order = (order->next == NULL) ? least_order->v->GetFirstOrder() : order->next;
 555                 least_order->expected_date += order->GetTravelTime() + order->GetWaitTime();
 556
 557                 /* Go through the order list to find the next candidate departure. */
 558                 /* We only need to consider each order at most once. */
 559                 bool found_next_order = false;
 560                 for (int i = least_order->v->GetNumOrders(); i > 0; --i) {
 561                         /* If the order is a conditional branch, handle it. */
 562                         if (order->IsType(OT_CONDITIONAL)) {
 563                                 switch(_settings_client.gui.departure_conditionals) {
 564                                                 case 0: {
 565                                                         /* Give up */
 566                                                         break;
 567                                                 }
 568                                                 case 1: {
 569                                                         /* Take the branch */
 570                                                         order = least_order->v->GetOrder(order->GetConditionSkipToOrder());
 571                                                         if (order == NULL) {
 572                                                                 break;
 573                                                         }
 574
 575                                                         least_order->expected_date += order->GetWaitTime();
 576
 577                                                         continue;
 578                                                 }
 579                                                 case 2: {
 580                                                         /* Do not take the branch */
 581                                                         order = (order->next == NULL) ? least_order->v->GetFirstOrder() : order->next;
 582                                                         least_order->expected_date += order->GetTravelTime() + order->GetWaitTime();
 583                                                         continue;
 584                                                 }
 585                                 }
 586                         }
 587
 588                         /* Skip it if it's an automatic order. */
 589                         if (order->IsType(OT_IMPLICIT)) {
 590                                 order = (order->next == NULL) ? least_order->v->GetFirstOrder() : order->next;
 591                                 continue;
 592                         }
 593
 594                         /* If an order has a 0 travel time, and it's not explictly set, then stop. */
 595                         if (order->GetTravelTime() == 0 && !order->IsTravelTimetabled()) {
 596                                 break;
 597                         }
 598
 599                         /* If the departure is scheduled to be too late, then stop. */
 600                         if (least_order->expected_date - least_order->lateness > max_date) {
 601                                 break;
 602                         }
 603
 604                         /* 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. */
 605                         if ((type == D_DEPARTURE && IsDeparture(order, station)) ||
 606                                                 (type == D_DEPARTURE && show_vehicles_via && IsVia(order, station)) ||
 607                                                 (type == D_ARRIVAL && IsArrival(order, station))) {
 608                                 least_order->order = order;
 609                                 found_next_order = true;
 610                                 break;
 611                         }
 612
 613                         order = (order->next == NULL) ? least_order->v->GetFirstOrder() : order->next;
 614                         least_order->expected_date += order->GetTravelTime() + order->GetWaitTime();
 615                 }
 616
 617                 /* If we didn't find a suitable order for being a departure, then we can ignore this vehicle from now on. */
 618                 if (!found_next_order) {
 619                         /* Make sure we don't try to get departures out of this order. */
 620                         /* This is cheaper than deleting it from next_orders. */
 621                         /* 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. */
 622                         least_order->expected_date = INT32_MAX;
 623                 }
 624
 625                 /* The vehicle can't possibly have arrived at its next candidate departure yet. */
 626                 if (least_order->status == D_ARRIVED) {
 627                         least_order->status = D_TRAVELLING;
 628                 }
 629
 630                 /* Find the new least order. */
 631                 for (uint i = 0; i < next_orders.Length(); ++i) {
 632                         OrderDate *od = *(next_orders.Get(i));
 633
 634                         Ticks lod = least_order->expected_date - least_order->lateness;
 635                         Ticks odd = od->expected_date - od->lateness;
 636
 637                         if (type == D_ARRIVAL) {
 638                                 lod -= least_order->order->GetWaitTime();
 639                                 odd -= od->order->GetWaitTime();
 640                         }
 641
 642                         if (lod > odd && od->expected_date - od->lateness < max_date) {
 643                                 least_order = od;
 644                         }
 645                 }
 646         }
 647
 648         /* Avoid leaking OrderDate structs */
 649         for (uint i = 0; i < next_orders.Length(); ++i) {
 650                 OrderDate *od = *(next_orders.Get(i));
 651                 delete od;
 652         }
 653
 654         /* Done. Phew! */
 655         return result;
 656 }