cargopacket.cpp

Go to the documentation of this file.

/*
 * This file is part of OpenTTD.
 * 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.
 * 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.
 * 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 <https://www.gnu.org/licenses/old-licenses/gpl-2.0>.
 */

 
#include "stdafx.h"
#include "station_base.h"
#include "core/pool_func.hpp"
#include "core/random_func.hpp"
#include "economy_base.h"
#include "cargoaction.h"
#include "order_type.h"
 
#include "safeguards.h"
 
/* Initialize the cargopacket-pool */
CargoPacketPool _cargopacket_pool("CargoPacket");
INSTANTIATE_POOL_METHODS(CargoPacket)
 

CargoPacket::CargoPacket(CargoPacketID index) : CargoPacketPool::PoolItem<&_cargopacket_pool>(index)
{
}

CargoPacket::CargoPacket(CargoPacketID index, StationID first_station,uint16_t count, Source source) :
    CargoPacketPool::PoolItem<&_cargopacket_pool>(index),
    count(count),
    source(source),
    first_station(first_station)
{
  assert(count != 0);
}

CargoPacket::CargoPacket(CargoPacketID index, uint16_t count, uint16_t periods_in_transit, StationID first_station, TileIndex source_xy, Money feeder_share) :
    CargoPacketPool::PoolItem<&_cargopacket_pool>(index),
    count(count),
    periods_in_transit(periods_in_transit),
    feeder_share(feeder_share),
    source_xy(source_xy),
    first_station(first_station)
{
  assert(count != 0);
}

CargoPacket::CargoPacket(CargoPacketID index, uint16_t count, Money feeder_share, CargoPacket &original) :
    CargoPacketPool::PoolItem<&_cargopacket_pool>(index),
    count(count),
    periods_in_transit(original.periods_in_transit),
    feeder_share(feeder_share),
    source_xy(original.source_xy),
    travelled(original.travelled),
    source(original.source),
#ifdef WITH_ASSERT
    in_vehicle(original.in_vehicle),
#endif /* WITH_ASSERT */
    first_station(original.first_station),
    next_hop(original.next_hop)
{
  assert(count != 0);
}

CargoPacket *CargoPacket::Split(uint new_size)
{
  if (!CargoPacket::CanAllocateItem()) return nullptr;
 
  Money fs = this->GetFeederShare(new_size);
  CargoPacket *cp_new = CargoPacket::Create(new_size, fs, *this);
  this->feeder_share -= fs;
  this->count -= new_size;
  return cp_new;
}

void CargoPacket::Merge(CargoPacket *cp)
{
  this->count += cp->count;
  this->feeder_share += cp->feeder_share;
  delete cp;
}

void CargoPacket::Reduce(uint count)
{
  assert(count < this->count);
  this->feeder_share -= this->GetFeederShare(count);
  this->count -= count;
}

/* static */ void CargoPacket::InvalidateAllFrom(Source src)
{
  for (CargoPacket *cp : CargoPacket::Iterate()) {
    if (cp->source == src) cp->source.MakeInvalid();
  }
}

/* static */ void CargoPacket::InvalidateAllFrom(StationID sid)
{
  for (CargoPacket *cp : CargoPacket::Iterate()) {
    if (cp->first_station == sid) cp->first_station = StationID::Invalid();
  }
}
 
/*
 *
 * Cargo list implementation
 *
 */

template <class Tinst, class Tcont>
CargoList<Tinst, Tcont>::~CargoList()
{
  for (Iterator it(this->packets.begin()); it != this->packets.end(); ++it) {
    delete *it;
  }
}

template <class Tinst, class Tcont>
void CargoList<Tinst, Tcont>::OnCleanPool()
{
  this->packets.clear();
}

template <class Tinst, class Tcont>
void CargoList<Tinst, Tcont>::RemoveFromCache(const CargoPacket *cp, uint count)
{
  assert(count <= cp->count);
  this->count -= count;
  this->cargo_periods_in_transit -= static_cast<uint64_t>(cp->periods_in_transit) * count;
}

template <class Tinst, class Tcont>
void CargoList<Tinst, Tcont>::AddToCache(const CargoPacket *cp)
{
  this->count += cp->count;
  this->cargo_periods_in_transit += static_cast<uint64_t>(cp->periods_in_transit) * cp->count;
}

template <class Tinst, class Tcont>
void CargoList<Tinst, Tcont>::InvalidateCache()
{
  this->count = 0;
  this->cargo_periods_in_transit = 0;
 
  for (ConstIterator it(this->packets.begin()); it != this->packets.end(); it++) {
    static_cast<Tinst *>(this)->AddToCache(*it);
  }
}

template <class Tinst, class Tcont>
/* static */ bool CargoList<Tinst, Tcont>::TryMerge(CargoPacket *icp, CargoPacket *cp)
{
  if (Tinst::AreMergable(icp, cp) &&
      icp->count + cp->count <= CargoPacket::MAX_COUNT) {
    icp->Merge(cp);
    return true;
  } else {
    return false;
  }
}
 
/*
 *
 * Vehicle cargo list implementation.
 *
 */

void VehicleCargoList::Append(CargoPacket *cp, MoveToAction action)
{
  assert(cp != nullptr);
  assert(action == MTA_LOAD ||
      (action == MTA_KEEP && this->action_counts[MTA_LOAD] == 0));
  this->AddToMeta(cp, action);
 
  if (this->count == cp->count) {
    this->packets.push_back(cp);
    return;
  }
 
  uint sum = cp->count;
  for (ReverseIterator it(this->packets.rbegin()); it != this->packets.rend(); it++) {
    CargoPacket *icp = *it;
    if (VehicleCargoList::TryMerge(icp, cp)) return;
    sum += icp->count;
    if (sum >= this->action_counts[action]) {
      this->packets.push_back(cp);
      return;
    }
  }
 
  NOT_REACHED();
}

template <class Taction>
void VehicleCargoList::ShiftCargo(Taction action)
{
  Iterator it(this->packets.begin());
  while (it != this->packets.end() && action.MaxMove() > 0) {
    CargoPacket *cp = *it;
    if (action(cp)) {
      it = this->packets.erase(it);
    } else {
      break;
    }
  }
}

template <class Taction>
void VehicleCargoList::PopCargo(Taction action)
{
  if (this->packets.empty()) return;
  Iterator it(--(this->packets.end()));
  Iterator begin(this->packets.begin());
  while (action.MaxMove() > 0) {
    CargoPacket *cp = *it;
    if (action(cp)) {
      if (it != begin) {
        this->packets.erase(it--);
      } else {
        this->packets.erase(it);
        break;
      }
    } else {
      break;
    }
  }
}

void VehicleCargoList::RemoveFromCache(const CargoPacket *cp, uint count)
{
  this->feeder_share -= cp->GetFeederShare(count);
  this->Parent::RemoveFromCache(cp, count);
}

void VehicleCargoList::AddToCache(const CargoPacket *cp)
{
  this->feeder_share += cp->feeder_share;
  this->Parent::AddToCache(cp);
}

void VehicleCargoList::RemoveFromMeta(const CargoPacket *cp, MoveToAction action, uint count)
{
  assert(count <= this->action_counts[action]);
  this->AssertCountConsistency();
  this->RemoveFromCache(cp, count);
  this->action_counts[action] -= count;
  this->AssertCountConsistency();
}

void VehicleCargoList::AddToMeta(const CargoPacket *cp, MoveToAction action)
{
  this->AssertCountConsistency();
  this->AddToCache(cp);
  this->action_counts[action] += cp->count;
  this->AssertCountConsistency();
}

void VehicleCargoList::AgeCargo()
{
  for (const auto &cp : this->packets) {
    /* If we're at the maximum, then we can't increase no more. */
    if (cp->periods_in_transit == UINT16_MAX) continue;
 
    cp->periods_in_transit++;
    this->cargo_periods_in_transit += cp->count;
  }
}

/* static */ VehicleCargoList::MoveToAction VehicleCargoList::ChooseAction(const CargoPacket *cp, StationID cargo_next,
    StationID current_station, bool accepted, std::span<const StationID> next_station)
{
  if (cargo_next == StationID::Invalid()) {
    return (accepted && cp->first_station != current_station) ? MTA_DELIVER : MTA_KEEP;
  } else if (cargo_next == current_station) {
    return MTA_DELIVER;
  } else if (std::ranges::find(next_station, cargo_next) != std::end(next_station)) {
    return MTA_KEEP;
  } else {
    return MTA_TRANSFER;
  }
}

bool VehicleCargoList::Stage(bool accepted, StationID current_station, std::span<const StationID> next_station, OrderUnloadType unload_type, const GoodsEntry *ge, CargoType cargo, CargoPayment *payment, TileIndex current_tile)
{
  this->AssertCountConsistency();
  assert(this->action_counts[MTA_LOAD] == 0);
  this->action_counts[MTA_TRANSFER] = this->action_counts[MTA_DELIVER] = this->action_counts[MTA_KEEP] = 0;
  Iterator deliver = this->packets.end();
  Iterator it = this->packets.begin();
  uint sum = 0;
 
  static const FlowStatMap EMPTY_FLOW_STAT_MAP = {};
  const FlowStatMap &flows = ge->HasData() ? ge->GetData().flows : EMPTY_FLOW_STAT_MAP;
 
  bool force_keep = unload_type == OrderUnloadType::NoUnload;
  bool force_unload = unload_type == OrderUnloadType::Unload;
  bool force_transfer = unload_type == OrderUnloadType::Transfer || unload_type == OrderUnloadType::Unload;
  assert(this->count > 0 || it == this->packets.end());
  while (sum < this->count) {
    CargoPacket *cp = *it;
 
    this->packets.erase(it++);
    StationID cargo_next = StationID::Invalid();
    MoveToAction action = MTA_LOAD;
    if (force_keep) {
      action = MTA_KEEP;
    } else if (force_unload && accepted && cp->first_station != current_station) {
      action = MTA_DELIVER;
    } else if (force_transfer) {
      action = MTA_TRANSFER;
      /* We cannot send the cargo to any of the possible next hops and
       * also not to the current station. */
      FlowStatMap::const_iterator flow_it(flows.find(cp->first_station));
      if (flow_it == flows.end()) {
        cargo_next = StationID::Invalid();
      } else {
        FlowStat new_shares = flow_it->second;
        new_shares.ChangeShare(current_station, INT_MIN);
        for (auto station_it = next_station.rbegin(); station_it != next_station.rend(); ++station_it) {
          if (new_shares.GetShares()->empty()) break;
          new_shares.ChangeShare(*station_it, INT_MIN);
        }
        if (new_shares.GetShares()->empty()) {
          cargo_next = StationID::Invalid();
        } else {
          cargo_next = new_shares.GetVia();
        }
      }
    } else {
      /* Rewrite an invalid source station to some random other one to
       * avoid keeping the cargo in the vehicle forever. */
      if (cp->first_station == StationID::Invalid() && !flows.empty()) {
        cp->first_station = flows.begin()->first;
      }
      bool restricted = false;
      FlowStatMap::const_iterator flow_it(flows.find(cp->first_station));
      if (flow_it == flows.end()) {
        cargo_next = StationID::Invalid();
      } else {
        cargo_next = flow_it->second.GetViaWithRestricted(restricted);
      }
      action = VehicleCargoList::ChooseAction(cp, cargo_next, current_station, accepted, next_station);
      if (restricted && action == MTA_TRANSFER) {
        /* If the flow is restricted we can't transfer to it. Choose an
         * unrestricted one instead. */
        cargo_next = flow_it->second.GetVia();
        action = VehicleCargoList::ChooseAction(cp, cargo_next, current_station, accepted, next_station);
      }
    }
    Money share;
    switch (action) {
      case MTA_KEEP:
        this->packets.push_back(cp);
        if (deliver == this->packets.end()) --deliver;
        break;
      case MTA_DELIVER:
        this->packets.insert(deliver, cp);
        break;
      case MTA_TRANSFER:
        this->packets.push_front(cp);
        /* Add feeder share here to allow reusing field for next station. */
        share = payment->PayTransfer(cargo, cp, cp->count, current_tile);
        cp->AddFeederShare(share);
        this->feeder_share += share;
        cp->next_hop = cargo_next;
        break;
      default:
        NOT_REACHED();
    }
    this->action_counts[action] += cp->count;
    sum += cp->count;
  }
  this->AssertCountConsistency();
  return this->action_counts[MTA_DELIVER] > 0 || this->action_counts[MTA_TRANSFER] > 0;
}

void VehicleCargoList::InvalidateCache()
{
  this->feeder_share = 0;
  this->Parent::InvalidateCache();
}

template <VehicleCargoList::MoveToAction Tfrom, VehicleCargoList::MoveToAction Tto>
uint VehicleCargoList::Reassign(uint max_move)
{
  static_assert(Tfrom != MTA_TRANSFER && Tto != MTA_TRANSFER);
  static_assert(Tfrom - Tto == 1 || Tto - Tfrom == 1);
  max_move = std::min(this->action_counts[Tfrom], max_move);
  this->action_counts[Tfrom] -= max_move;
  this->action_counts[Tto] += max_move;
  return max_move;
}

template <>
uint VehicleCargoList::Reassign<VehicleCargoList::MTA_DELIVER, VehicleCargoList::MTA_TRANSFER>(uint max_move)
{
  max_move = std::min(this->action_counts[MTA_DELIVER], max_move);
 
  uint sum = 0;
  for (Iterator it(this->packets.begin()); sum < this->action_counts[MTA_TRANSFER] + max_move;) {
    CargoPacket *cp = *it++;
    sum += cp->Count();
    if (sum <= this->action_counts[MTA_TRANSFER]) continue;
    if (sum > this->action_counts[MTA_TRANSFER] + max_move) {
      CargoPacket *cp_split = cp->Split(sum - this->action_counts[MTA_TRANSFER] + max_move);
      sum -= cp_split->Count();
      this->packets.insert(it, cp_split);
    }
    cp->next_hop = StationID::Invalid();
  }
 
  this->action_counts[MTA_DELIVER] -= max_move;
  this->action_counts[MTA_TRANSFER] += max_move;
  return max_move;
}

uint VehicleCargoList::Return(uint max_move, StationCargoList *dest, StationID next, TileIndex current_tile)
{
  max_move = std::min(this->action_counts[MTA_LOAD], max_move);
  this->PopCargo(CargoReturn(this, dest, max_move, next, current_tile));
  return max_move;
}

uint VehicleCargoList::Shift(uint max_move, VehicleCargoList *dest)
{
  max_move = std::min(this->count, max_move);
  this->PopCargo(CargoShift(this, dest, max_move));
  return max_move;
}

uint VehicleCargoList::Unload(uint max_move, StationCargoList *dest, CargoType cargo, CargoPayment *payment, TileIndex current_tile)
{
  uint moved = 0;
  if (this->action_counts[MTA_TRANSFER] > 0) {
    uint move = std::min(this->action_counts[MTA_TRANSFER], max_move);
    this->ShiftCargo(CargoTransfer(this, dest, move, current_tile));
    moved += move;
  }
  if (this->action_counts[MTA_TRANSFER] == 0 && this->action_counts[MTA_DELIVER] > 0 && moved < max_move) {
    uint move = std::min(this->action_counts[MTA_DELIVER], max_move - moved);
    this->ShiftCargo(CargoDelivery(this, move, cargo, payment, current_tile));
    moved += move;
  }
  return moved;
}

uint VehicleCargoList::Truncate(uint max_move)
{
  max_move = std::min(this->count, max_move);
  this->PopCargo(CargoRemoval<VehicleCargoList>(this, max_move));
  return max_move;
}

uint VehicleCargoList::Reroute(uint max_move, VehicleCargoList *dest, StationID avoid, StationID avoid2, const GoodsEntry *ge)
{
  max_move = std::min(this->action_counts[MTA_TRANSFER], max_move);
  this->ShiftCargo(VehicleCargoReroute(this, dest, max_move, avoid, avoid2, ge));
  return max_move;
}
 
/*
 *
 * Station cargo list implementation.
 *
 */

void StationCargoList::Append(CargoPacket *cp, StationID next)
{
  assert(cp != nullptr);
  this->AddToCache(cp);
 
  StationCargoPacketMap::List &list = this->packets[next];
  for (StationCargoPacketMap::List::reverse_iterator it(list.rbegin());
      it != list.rend(); it++) {
    if (StationCargoList::TryMerge(*it, cp)) return;
  }
 
  /* The packet could not be merged with another one */
  list.push_back(cp);
}

template <class Taction>
bool StationCargoList::ShiftCargo(Taction &action, StationID next)
{
  std::pair<Iterator, Iterator> range(this->packets.equal_range(next));
  for (Iterator it(range.first); it != range.second && it.GetKey() == next;) {
    if (action.MaxMove() == 0) return false;
    CargoPacket *cp = *it;
    if (action(cp)) {
      it = this->packets.erase(it);
    } else {
      return false;
    }
  }
  return true;
}

template <class Taction>
uint StationCargoList::ShiftCargo(Taction action, std::span<const StationID> next, bool include_invalid)
{
  uint max_move = action.MaxMove();
  for (auto it = next.rbegin(); it != next.rend(); ++it) {
    this->ShiftCargo(action, *it);
    if (action.MaxMove() == 0) break;
  }
  if (include_invalid && action.MaxMove() > 0) {
    this->ShiftCargo(action, StationID::Invalid());
  }
  return max_move - action.MaxMove();
}

uint StationCargoList::Truncate(uint max_move, StationCargoAmountMap *cargo_per_source)
{
  max_move = std::min(max_move, this->count);
  uint prev_count = this->count;
  uint moved = 0;
  uint loop = 0;
  bool do_count = cargo_per_source != nullptr;
  while (max_move > moved) {
    for (Iterator it(this->packets.begin()); it != this->packets.end();) {
      CargoPacket *cp = *it;
      if (prev_count > max_move && RandomRange(prev_count) < prev_count - max_move) {
        if (do_count && loop == 0) {
          (*cargo_per_source)[cp->first_station] += cp->count;
        }
        ++it;
        continue;
      }
      uint diff = max_move - moved;
      if (cp->count > diff) {
        if (diff > 0) {
          this->RemoveFromCache(cp, diff);
          cp->Reduce(diff);
          moved += diff;
        }
        if (loop > 0) {
          if (do_count) (*cargo_per_source)[cp->first_station] -= diff;
          return moved;
        } else {
          if (do_count) (*cargo_per_source)[cp->first_station] += cp->count;
          ++it;
        }
      } else {
        it = this->packets.erase(it);
        if (do_count && loop > 0) {
          (*cargo_per_source)[cp->first_station] -= cp->count;
        }
        moved += cp->count;
        this->RemoveFromCache(cp, cp->count);
        delete cp;
      }
    }
    loop++;
  }
  return moved;
}

uint StationCargoList::Reserve(uint max_move, VehicleCargoList *dest, std::span<const StationID> next_station, TileIndex current_tile)
{
  return this->ShiftCargo(CargoReservation(this, dest, max_move, current_tile), next_station, true);
}

uint StationCargoList::Load(uint max_move, VehicleCargoList *dest, std::span<const StationID> next_station, TileIndex current_tile)
{
  uint move = std::min(dest->ActionCount(VehicleCargoList::MTA_LOAD), max_move);
  if (move > 0) {
    this->reserved_count -= move;
    dest->Reassign<VehicleCargoList::MTA_LOAD, VehicleCargoList::MTA_KEEP>(move);
    return move;
  } else {
    return this->ShiftCargo(CargoLoad{this, dest, max_move, current_tile}, next_station, true);
  }
}

uint StationCargoList::Reroute(uint max_move, StationCargoList *dest, StationID avoid, StationID avoid2, const GoodsEntry *ge)
{
  return this->ShiftCargo(StationCargoReroute(this, dest, max_move, avoid, avoid2, ge), {&avoid, 1}, false);
}
 
/*
 * We have to instantiate everything we want to be usable.
 */
template class CargoList<VehicleCargoList, CargoPacketList>;
template class CargoList<StationCargoList, StationCargoPacketMap>;
template uint VehicleCargoList::Reassign<VehicleCargoList::MTA_DELIVER, VehicleCargoList::MTA_KEEP>(uint);