<commit_before>/*

This file is part of VROOM.

Copyright (c) 2015-2020, <NAME>.
All rights reserved (see LICENSE).

*/

#include "structures/vroom/tw_route.h"
#include "utils/exception.h"

namespace vroom {

TWRoute::TWRoute(const Input& input, Index v)
  : RawRoute(input, v),
    v_start(input.vehicles[v].tw.start),
    v_end(input.vehicles[v].tw.end),
    breaks_at_rank({static_cast<unsigned>(input.vehicles[v].breaks.size())}),
    breaks_counts({static_cast<unsigned>(input.vehicles[v].breaks.size())}),
    break_earliest(input.vehicles[v].breaks.size()),
    break_latest(input.vehicles[v].breaks.size()),
    breaks_travel_margin_before(input.vehicles[v].breaks.size()),
    breaks_travel_margin_after(input.vehicles[v].breaks.size()) {
  std::string break_error = "Inconsistent breaks for vehicle " +
                            std::to_string(input.vehicles[v].id) + ".";

  const auto& breaks = input.vehicles[v].breaks;

  Duration previous_earliest = v_start;

  for (Index i = 0; i < breaks.size(); ++i) {
    const auto& b = breaks[i];
    const auto b_tw =
      std::find_if(b.tws.begin(), b.tws.end(), [&](const auto& tw) {
        return previous_earliest <= tw.end;
      });
    if (b_tw == b.tws.end()) {
      throw Exception(ERROR::INPUT, break_error);
    }

    break_earliest[i] = std::max(previous_earliest, b_tw->start);
    breaks_travel_margin_before[i] = break_earliest[i] - previous_earliest;

    previous_earliest = break_earliest[i] + b.service;
  }

  Duration next_latest = v_end;
  for (Index r_i = 0; r_i < breaks.size(); ++r_i) {
    Index i = breaks.size() - 1 - r_i;
    const auto& b = breaks[i];

    if (next_latest < b.service) {
      throw Exception(ERROR::INPUT, break_error);
    }
    next_latest -= b.service;

    const auto b_tw =
      std::find_if(b.tws.rbegin(), b.tws.rend(), [&](const auto& tw) {
        return tw.start <= next_latest;
      });
    if (b_tw == b.tws.rend()) {
      throw Exception(ERROR::INPUT, break_error);
    }

    break_latest[i] = std::min(next_latest, b_tw->end);
    breaks_travel_margin_after[i] = next_latest - break_latest[i];

    next_latest = break_latest[i];

    if (break_latest[i] < break_earliest[i]) {
      throw Exception(ERROR::INPUT, break_error);
    }
  }
}

Duration TWRoute::new_earliest_candidate(const Input& input,
                                         Index job_rank,
                                         Index rank) const {
  const auto& m = input.get_matrix();
  const auto& v = input.vehicles[vehicle_rank];
  const auto& j = input.jobs[job_rank];

  Duration previous_earliest = v_start;
  Duration previous_service = 0;
  Duration previous_travel = 0;
  if (rank > 0) {
    const auto& previous_job = input.jobs[route[rank - 1]];
    previous_earliest = earliest[rank - 1];
    previous_service = previous_job.service;
    previous_travel = m[previous_job.index()][j.index()];
  } else {
    if (has_start) {
      previous_travel = m[v.start.get().index()][j.index()];
    }
  }

  return previous_earliest + previous_service + previous_travel;
}

Duration TWRoute::new_latest_candidate(const Input& input,
                                       Index job_rank,
                                       Index rank) const {
  const auto& m = input.get_matrix();
  const auto& v = input.vehicles[vehicle_rank];
  const auto& j = input.jobs[job_rank];

  Duration next_latest = v_end;
  Duration next_travel = 0;
  if (rank == route.size()) {
    if (has_end) {
      next_travel = m[j.index()][v.end.get().index()];
    }
  } else {
    next_latest = latest[rank];
    next_travel = m[j.index()][input.jobs[route[rank]].index()];
  }

  assert(j.service + next_travel <= next_latest);
  return next_latest - j.service - next_travel;
}

Duration TWRoute::previous_earliest_end(const Input& input,
                                        Index job_rank,
                                        Index rank,
                                        Duration& previous_travel) const {
  const auto& m = input.get_matrix();
  const auto& v = input.vehicles[vehicle_rank];
  const auto& j = input.jobs[job_rank];

  Duration previous_earliest = v_start;
  Duration previous_service = 0;
  if (rank > 0) {
    const auto& previous_job = input.jobs[route[rank - 1]];
    previous_earliest = earliest[rank - 1];
    previous_service = previous_job.service;
    previous_travel = m[previous_job.index()][j.index()];
  } else {
    if (has_start) {
      previous_travel = m[v.start.get().index()][j.index()];
    }
  }

  return previous_earliest + previous_service;
}

Duration TWRoute::next_latest_start(const Input& input,
                                    Index job_rank,
                                    Index rank,
                                    Duration& next_travel) const {
  const auto& m = input.get_matrix();
  const auto& v = input.vehicles[vehicle_rank];
  const auto& j = input.jobs[job_rank];

  Duration next_latest = v_end;
  if (rank == route.size()) {
    if (has_end) {
      next_travel = m[j.index()][v.end.get().index()];
    }
  } else {
    next_latest = latest[rank];
    next_travel = m[j.index()][input.jobs[route[rank]].index()];
  }

  return next_latest;
}

void TWRoute::fwd_update_earliest_from(const Input& input, Index rank) {
  const auto& m = input.get_matrix();
  const auto& v = input.vehicles[vehicle_rank];

  Duration current_earliest = earliest[rank];
  bool handle_last_breaks = true;

  for (Index i = rank + 1; i < route.size(); ++i) {
    const auto& next_j = input.jobs[route[i]];
    Duration remaining_travel_time =
      m[input.jobs[route[i - 1]].index()][next_j.index()];
    Duration previous_service = input.jobs[route[i - 1]].service;

    // Update earliest dates and margins for breaks.
    assert(breaks_at_rank[i] <= breaks_counts[i]);
    Index break_rank = breaks_counts[i] - breaks_at_rank[i];

    for (Index r = 0; r < breaks_at_rank[i]; ++r, ++break_rank) {
      const auto& b = v.breaks[break_rank];

      current_earliest += previous_service;

      const auto b_tw =
        std::find_if(b.tws.begin(), b.tws.end(), [&](const auto& tw) {
          return current_earliest <= tw.end;
        });
      assert(b_tw != b.tws.end());

      if (current_earliest < b_tw->start) {
        auto margin = b_tw->start - current_earliest;
        breaks_travel_margin_before[break_rank] = margin;
        if (margin < remaining_travel_time) {
          remaining_travel_time -= margin;
        } else {
          remaining_travel_time = 0;
        }

        current_earliest = b_tw->start;
      } else {
        breaks_travel_margin_before[break_rank] = 0;
      }

      break_earliest[break_rank] = current_earliest;
      previous_service = v.breaks[break_rank].service;
    }

    // Back to the job after breaks.
    current_earliest += previous_service + remaining_travel_time;

    const auto& next_TW = next_j.tws[tw_ranks[i]];
    current_earliest = std::max(current_earliest, next_TW.start);

    assert(current_earliest <= latest[i]);
    if (current_earliest == earliest[i]) {
      // There won't be any further update so stop earliest date
      // propagation.
      handle_last_breaks = false;
      break;
    }

    earliest[i] = current_earliest;
  }

  if (handle_last_breaks) {
    // Update earliest dates and margins for potential breaks right
    // before route end.
    Index i = route.size();
    Duration remaining_travel_time =
      (v.has_end()) ? m[input.jobs[route[i - 1]].index()][v.end.get().index()]
                    : 0;

    Duration previous_service = input.jobs[route[i - 1]].service;

    assert(breaks_at_rank[i] <= breaks_counts[i]);
    Index break_rank = breaks_counts[i] - breaks_at_rank[i];

    for (Index r = 0; r < breaks_at_rank[i]; ++r, ++break_rank) {
      const auto& b = v.breaks[break_rank];
      current_earliest += previous_service;

      const auto b_tw =
        std::find_if(b.tws.begin(), b.tws.end(), [&](const auto& tw) {
          return current_earliest <= tw.end;
        });
      assert(b_tw != b.tws.end());

      if (current_earliest < b_tw->start) {
        auto margin = b_tw->start - current_earliest;
        breaks_travel_margin_before[break_rank] = margin;
        if (margin < remaining_travel_time) {
          remaining_travel_time -= margin;
        } else {
          remaining_travel_time = 0;
        }

        current_earliest = b_tw->start;
      } else {
        breaks_travel_margin_before[break_rank] = 0;
      }

      break_earliest[break_rank] = current_earliest;
      previous_service = v.breaks[break_rank].service;
    }

    earliest_end = current_earliest + previous_service + remaining_travel_time;
    assert(earliest_end <= v_end);
  }
}

void TWRoute::bwd_update_latest_from(const Input& input, Index rank) {
  const auto& m = input.get_matrix();
  const auto& v = input.vehicles[vehicle_rank];

  Duration current_latest = latest[rank];
  bool handle_first_breaks = true;

  for (Index next_i = rank; next_i > 0; --next_i) {
    const auto& previous_j = input.jobs[route[next_i - 1]];
    Duration remaining_travel_time =
      m[previous_j.index()][input.jobs[route[next_i]].index()];

    // Update latest dates and margins for breaks.
    assert(breaks_at_rank[next_i] <= breaks_counts[next_i]);
    Index break_rank = breaks_counts[next_i];

    for (Index r = 0; r < breaks_at_rank[next_i]; ++r) {
      --break_rank;

      const auto& b = v.breaks[break_rank];
      assert(b.service <= current_latest);
      current_latest -= b.service;

      const auto b_tw =
        std::find_if(b.tws.rbegin(), b.tws.rend(), [&](const auto& tw) {
          return tw.start <= current_latest;
        });
      assert(b_tw != b.tws.rend());

      if (b_tw->end < current_latest) {
        auto margin = current_latest - b_tw->end;
        breaks_travel_margin_after[break_rank] = margin;
        if (margin < remaining_travel_time) {
          remaining_travel_time -= margin;
        } else {
          remaining_travel_time = 0;
        }

        current_latest = b_tw->end;
      } else {
        breaks_travel_margin_after[break_rank] = 0;
      }

      break_latest[break_rank] = current_latest;
    }

    // Back to the job after breaks.
    auto gap = previous_j.service + remaining_travel_time;
    assert(gap <= current_latest);
    current_latest -= gap;

    const auto& previous_TW = previous_j.tws[tw_ranks[next_i - 1]];
    current_latest = std::min(current_latest, previous_TW.end);

    assert(earliest[next_i - 1] <= current_latest);
    if (current_latest == latest[next_i - 1]) {
      // There won't be any further update so stop latest date
      // propagation.
      handle_first_breaks = false;
      break;
    }

    latest[next_i - 1] = current_latest;
  }

  if (handle_first_breaks) {
    // Update latest dates and margins for breaks right before the
    // first job.
    Index next_i = 0;

    assert(breaks_at_rank[next_i] <= breaks_counts[next_i]);
    Index break_rank = breaks_counts[next_i];

    for (Index r = 0; r < breaks_at_rank[next_i]; ++r) {
      --break_rank;
      const auto& b = v.breaks[break_rank];

      assert(b.service <= current_latest);
      current_latest -= b.service;

      const auto b_tw =
        std::find_if(b.tws.rbegin(), b.tws.rend(), [&](const auto& tw) {
          return tw.start <= current_latest;
        });
      assert(b_tw != b.tws.rend());
      if (b_tw->end < current_latest) {
        breaks_travel_margin_after[break_rank] = current_latest - b_tw->end;

        current_latest = b_tw->end;
      } else {
        breaks_travel_margin_after[break_rank] = 0;
      }

      break_latest[break_rank] = current_latest;
    }
  }
}

bool TWRoute::is_valid_addition_for_tw(const Input& input,
                                       const Index job_rank,
                                       const Index rank) const {
  const auto& v = input.vehicles[vehicle_rank];
  const auto& j = input.jobs[job_rank];

  Duration previous_travel = 0;
  Duration current_earliest =
    previous_earliest_end(input, job_rank, rank, previous_travel);

  Duration next_travel = 0;
  Duration next_start = next_latest_start(input, job_rank, rank, next_travel);

  bool job_added = false;

  assert(breaks_at_rank[rank] <= breaks_counts[rank]);

  for (Index r = 0; r < breaks_at_rank[rank]; ++r) {
    Index break_rank = (breaks_counts[rank] + r) - breaks_at_rank[rank];
    const auto& b = v.breaks[break_rank];

    const auto b_tw =
      std::find_if(b.tws.begin(), b.tws.end(), [&](const auto& tw) {
        return current_earliest <= tw.end;
      });

    if (b_tw == b.tws.end()) {
      // Break does not fit anyway due to its time windows.
      return false;
    }

    if (job_added) {
      // Compute earliest end date for current break.
      if (current_earliest < b_tw->start) {
        auto margin = b_tw->start - current_earliest;
        if (margin < next_travel) {
          next_travel -= margin;
        } else {
          next_travel = 0;
        }

        current_earliest = b_tw->start;
      }

      current_earliest += b.service;
    } else {
      const auto j_tw =
        std::find_if(j.tws.begin(), j.tws.end(), [&](const auto& tw) {
          return current_earliest + previous_travel <= tw.end;
        });
      if (j_tw == j.tws.end()) {
        // Job does not fit anyway due to its time windows.
        return false;
      }

      // Both break and job could fit next based on time windows, so
      // we need to decide whether to include current break or job.
      bool add_job_first = false;
      bool add_break_first = false;

      Duration job_then_break_end = 0; // Dummy init.
      Duration break_then_job_end = 0; // Dummy init.

      // Try putting job first then break.
      Duration earliest_job_end =
        std::max(current_earliest + previous_travel, j_tw->start) + j.service;

      const auto new_b_tw =
        std::find_if(b.tws.begin(), b.tws.end(), [&](const auto& tw) {
          return earliest_job_end <= tw.end;
        });
      if (new_b_tw == b.tws.end()) {
        // Break does not fit after job due to its time windows.
        add_break_first = true;
      } else {
        job_then_break_end =
          std::max(earliest_job_end, new_b_tw->start) + b.service;
      }

      if (!add_break_first) {
        // Try putting break first then job. Only thoroughly check
        // this option if we're not already sure it's the only way.

        Duration travel_after_break = previous_travel;
        Duration earliest_job_start = current_earliest;

        if (current_earliest < b_tw->start) {
          auto margin = b_tw->start - current_earliest;
          if (margin < travel_after_break) {
            travel_after_break -= margin;
          } else {
            travel_after_break = 0;
          }

          earliest_job_start = b_tw->start;
        }

        earliest_job_start += b.service + travel_after_break;

        const auto new_j_tw =
          std::find_if(j.tws.begin(), j.tws.end(), [&](const auto& tw) {
            return earliest_job_start <= tw.end;
          });
        if (new_j_tw == b.tws.end()) {<commit_msg>Fix typo in validity check.<commit_after>/*

This file is part of VROOM.

Copyright (c) 2015-2020, <NAME>.
All rights reserved (see LICENSE).

*/

#include "structures/vroom/tw_route.h"
#include "utils/exception.h"

namespace vroom {

TWRoute::TWRoute(const Input& input, Index v)
  : RawRoute(input, v),
    v_start(input.vehicles[v].tw.start),
    v_end(input.vehicles[v].tw.end),
    breaks_at_rank({static_cast<unsigned>(input.vehicles[v].breaks.size())}),
    breaks_counts({static_cast<unsigned>(input.vehicles[v].breaks.size())}),
    break_earliest(input.vehicles[v].breaks.size()),
    break_latest(input.vehicles[v].breaks.size()),
    breaks_travel_margin_before(input.vehicles[v].breaks.size()),
    breaks_travel_margin_after(input.vehicles[v].breaks.size()) {
  std::string break_error = "Inconsistent breaks for vehicle " +
                            std::to_string(input.vehicles[v].id) + ".";

  const auto& breaks = input.vehicles[v].breaks;

  Duration previous_earliest = v_start;

  for (Index i = 0; i < breaks.size(); ++i) {
    const auto& b = breaks[i];
    const auto b_tw =
      std::find_if(b.tws.begin(), b.tws.end(), [&](const auto& tw) {
        return previous_earliest <= tw.end;
      });
    if (b_tw == b.tws.end()) {
      throw Exception(ERROR::INPUT, break_error);
    }

    break_earliest[i] = std::max(previous_earliest, b_tw->start);
    breaks_travel_margin_before[i] = break_earliest[i] - previous_earliest;

    previous_earliest = break_earliest[i] + b.service;
  }

  Duration next_latest = v_end;
  for (Index r_i = 0; r_i < breaks.size(); ++r_i) {
    Index i = breaks.size() - 1 - r_i;
    const auto& b = breaks[i];

    if (next_latest < b.service) {
      throw Exception(ERROR::INPUT, break_error);
    }
    next_latest -= b.service;

    const auto b_tw =
      std::find_if(b.tws.rbegin(), b.tws.rend(), [&](const auto& tw) {
        return tw.start <= next_latest;
      });
    if (b_tw == b.tws.rend()) {
      throw Exception(ERROR::INPUT, break_error);
    }

    break_latest[i] = std::min(next_latest, b_tw->end);
    breaks_travel_margin_after[i] = next_latest - break_latest[i];

    next_latest = break_latest[i];

    if (break_latest[i] < break_earliest[i]) {
      throw Exception(ERROR::INPUT, break_error);
    }
  }
}

Duration TWRoute::new_earliest_candidate(const Input& input,
                                         Index job_rank,
                                         Index rank) const {
  const auto& m = input.get_matrix();
  const auto& v = input.vehicles[vehicle_rank];
  const auto& j = input.jobs[job_rank];

  Duration previous_earliest = v_start;
  Duration previous_service = 0;
  Duration previous_travel = 0;
  if (rank > 0) {
    const auto& previous_job = input.jobs[route[rank - 1]];
    previous_earliest = earliest[rank - 1];
    previous_service = previous_job.service;
    previous_travel = m[previous_job.index()][j.index()];
  } else {
    if (has_start) {
      previous_travel = m[v.start.get().index()][j.index()];
    }
  }

  return previous_earliest + previous_service + previous_travel;
}

Duration TWRoute::new_latest_candidate(const Input& input,
                                       Index job_rank,
                                       Index rank) const {
  const auto& m = input.get_matrix();
  const auto& v = input.vehicles[vehicle_rank];
  const auto& j = input.jobs[job_rank];

  Duration next_latest = v_end;
  Duration next_travel = 0;
  if (rank == route.size()) {
    if (has_end) {
      next_travel = m[j.index()][v.end.get().index()];
    }
  } else {
    next_latest = latest[rank];
    next_travel = m[j.index()][input.jobs[route[rank]].index()];
  }

  assert(j.service + next_travel <= next_latest);
  return next_latest - j.service - next_travel;
}

Duration TWRoute::previous_earliest_end(const Input& input,
                                        Index job_rank,
                                        Index rank,
                                        Duration& previous_travel) const {
  const auto& m = input.get_matrix();
  const auto& v = input.vehicles[vehicle_rank];
  const auto& j = input.jobs[job_rank];

  Duration previous_earliest = v_start;
  Duration previous_service = 0;
  if (rank > 0) {
    const auto& previous_job = input.jobs[route[rank - 1]];
    previous_earliest = earliest[rank - 1];
    previous_service = previous_job.service;
    previous_travel = m[previous_job.index()][j.index()];
  } else {
    if (has_start) {
      previous_travel = m[v.start.get().index()][j.index()];
    }
  }

  return previous_earliest + previous_service;
}

Duration TWRoute::next_latest_start(const Input& input,
                                    Index job_rank,
                                    Index rank,
                                    Duration& next_travel) const {
  const auto& m = input.get_matrix();
  const auto& v = input.vehicles[vehicle_rank];
  const auto& j = input.jobs[job_rank];

  Duration next_latest = v_end;
  if (rank == route.size()) {
    if (has_end) {
      next_travel = m[j.index()][v.end.get().index()];
    }
  } else {
    next_latest = latest[rank];
    next_travel = m[j.index()][input.jobs[route[rank]].index()];
  }

  return next_latest;
}

void TWRoute::fwd_update_earliest_from(const Input& input, Index rank) {
  const auto& m = input.get_matrix();
  const auto& v = input.vehicles[vehicle_rank];

  Duration current_earliest = earliest[rank];
  bool handle_last_breaks = true;

  for (Index i = rank + 1; i < route.size(); ++i) {
    const auto& next_j = input.jobs[route[i]];
    Duration remaining_travel_time =
      m[input.jobs[route[i - 1]].index()][next_j.index()];
    Duration previous_service = input.jobs[route[i - 1]].service;

    // Update earliest dates and margins for breaks.
    assert(breaks_at_rank[i] <= breaks_counts[i]);
    Index break_rank = breaks_counts[i] - breaks_at_rank[i];

    for (Index r = 0; r < breaks_at_rank[i]; ++r, ++break_rank) {
      const auto& b = v.breaks[break_rank];

      current_earliest += previous_service;

      const auto b_tw =
        std::find_if(b.tws.begin(), b.tws.end(), [&](const auto& tw) {
          return current_earliest <= tw.end;
        });
      assert(b_tw != b.tws.end());

      if (current_earliest < b_tw->start) {
        auto margin = b_tw->start - current_earliest;
        breaks_travel_margin_before[break_rank] = margin;
        if (margin < remaining_travel_time) {
          remaining_travel_time -= margin;
        } else {
          remaining_travel_time = 0;
        }

        current_earliest = b_tw->start;
      } else {
        breaks_travel_margin_before[break_rank] = 0;
      }

      break_earliest[break_rank] = current_earliest;
      previous_service = v.breaks[break_rank].service;
    }

    // Back to the job after breaks.
    current_earliest += previous_service + remaining_travel_time;

    const auto& next_TW = next_j.tws[tw_ranks[i]];
    current_earliest = std::max(current_earliest, next_TW.start);

    assert(current_earliest <= latest[i]);
    if (current_earliest == earliest[i]) {
      // There won't be any further update so stop earliest date
      // propagation.
      handle_last_breaks = false;
      break;
    }

    earliest[i] = current_earliest;
  }

  if (handle_last_breaks) {
    // Update earliest dates and margins for potential breaks right
    // before route end.
    Index i = route.size();
    Duration remaining_travel_time =
      (v.has_end()) ? m[input.jobs[route[i - 1]].index()][v.end.get().index()]
                    : 0;

    Duration previous_service = input.jobs[route[i - 1]].service;

    assert(breaks_at_rank[i] <= breaks_counts[i]);
    Index break_rank = breaks_counts[i] - breaks_at_rank[i];

    for (Index r = 0; r < breaks_at_rank[i]; ++r, ++break_rank) {
      const auto& b = v.breaks[break_rank];
      current_earliest += previous_service;

      const auto b_tw =
        std::find_if(b.tws.begin(), b.tws.end(), [&](const auto& tw) {
          return current_earliest <= tw.end;
        });
      assert(b_tw != b.tws.end());

      if (current_earliest < b_tw->start) {
        auto margin = b_tw->start - current_earliest;
        breaks_travel_margin_before[break_rank] = margin;
        if (margin < remaining_travel_time) {
          remaining_travel_time -= margin;
        } else {
          remaining_travel_time = 0;
        }

        current_earliest = b_tw->start;
      } else {
        breaks_travel_margin_before[break_rank] = 0;
      }

      break_earliest[break_rank] = current_earliest;
      previous_service = v.breaks[break_rank].service;
    }

    earliest_end = current_earliest + previous_service + remaining_travel_time;
    assert(earliest_end <= v_end);
  }
}

void TWRoute::bwd_update_latest_from(const Input& input, Index rank) {
  const auto& m = input.get_matrix();
  const auto& v = input.vehicles[vehicle_rank];

  Duration current_latest = latest[rank];
  bool handle_first_breaks = true;

  for (Index next_i = rank; next_i > 0; --next_i) {
    const auto& previous_j = input.jobs[route[next_i - 1]];
    Duration remaining_travel_time =
      m[previous_j.index()][input.jobs[route[next_i]].index()];

    // Update latest dates and margins for breaks.
    assert(breaks_at_rank[next_i] <= breaks_counts[next_i]);
    Index break_rank = breaks_counts[next_i];

    for (Index r = 0; r < breaks_at_rank[next_i]; ++r) {
      --break_rank;

      const auto& b = v.breaks[break_rank];
      assert(b.service <= current_latest);
      current_latest -= b.service;

      const auto b_tw =
        std::find_if(b.tws.rbegin(), b.tws.rend(), [&](const auto& tw) {
          return tw.start <= current_latest;
        });
      assert(b_tw != b.tws.rend());

      if (b_tw->end < current_latest) {
        auto margin = current_latest - b_tw->end;
        breaks_travel_margin_after[break_rank] = margin;
        if (margin < remaining_travel_time) {
          remaining_travel_time -= margin;
        } else {
          remaining_travel_time = 0;
        }

        current_latest = b_tw->end;
      } else {
        breaks_travel_margin_after[break_rank] = 0;
      }

      break_latest[break_rank] = current_latest;
    }

    // Back to the job after breaks.
    auto gap = previous_j.service + remaining_travel_time;
    assert(gap <= current_latest);
    current_latest -= gap;

    const auto& previous_TW = previous_j.tws[tw_ranks[next_i - 1]];
    current_latest = std::min(current_latest, previous_TW.end);

    assert(earliest[next_i - 1] <= current_latest);
    if (current_latest == latest[next_i - 1]) {
      // There won't be any further update so stop latest date
      // propagation.
      handle_first_breaks = false;
      break;
    }

    latest[next_i - 1] = current_latest;
  }

  if (handle_first_breaks) {
    // Update latest dates and margins for breaks right before the
    // first job.
    Index next_i = 0;

    assert(breaks_at_rank[next_i] <= breaks_counts[next_i]);
    Index break_rank = breaks_counts[next_i];

    for (Index r = 0; r < breaks_at_rank[next_i]; ++r) {
      --break_rank;
      const auto& b = v.breaks[break_rank];

      assert(b.service <= current_latest);
      current_latest -= b.service;

      const auto b_tw =
        std::find_if(b.tws.rbegin(), b.tws.rend(), [&](const auto& tw) {
          return tw.start <= current_latest;
        });
      assert(b_tw != b.tws.rend());
      if (b_tw->end < current_latest) {
        breaks_travel_margin_after[break_rank] = current_latest - b_tw->end;

        current_latest = b_tw->end;
      } else {
        breaks_travel_margin_after[break_rank] = 0;
      }

      break_latest[break_rank] = current_latest;
    }
  }
}

bool TWRoute::is_valid_addition_for_tw(const Input& input,
                                       const Index job_rank,
                                       const Index rank) const {
  const auto& v = input.vehicles[vehicle_rank];
  const auto& j = input.jobs[job_rank];

  Duration previous_travel = 0;
  Duration current_earliest =
    previous_earliest_end(input, job_rank, rank, previous_travel);

  Duration next_travel = 0;
  Duration next_start = next_latest_start(input, job_rank, rank, next_travel);

  bool job_added = false;

  assert(breaks_at_rank[rank] <= breaks_counts[rank]);

  for (Index r = 0; r < breaks_at_rank[rank]; ++r) {
    Index break_rank = (breaks_counts[rank] + r) - breaks_at_rank[rank];
    const auto& b = v.breaks[break_rank];

    const auto b_tw =
      std::find_if(b.tws.begin(), b.tws.end(), [&](const auto& tw) {
        return current_earliest <= tw.end;
      });

    if (b_tw == b.tws.end()) {
      // Break does not fit anyway due to its time windows.
      return false;
    }

    if (job_added) {
      // Compute earliest end date for current break.
      if (current_earliest < b_tw->start) {
        auto margin = b_tw->start - current_earliest;
        if (margin < next_travel) {
          next_travel -= margin;
        } else {
          next_travel = 0;
        }

        current_earliest = b_tw->start;
      }

      current_earliest += b.service;
    } else {
      const auto j_tw =
        std::find_if(j.tws.begin(), j.tws.end(), [&](const auto& tw) {
          return current_earliest + previous_travel <= tw.end;
        });
      if (j_tw == j.tws.end()) {
        // Job does not fit anyway due to its time windows.
        return false;
      }

      // Both break and job could fit next based on time windows, so
      // we need to decide whether to include current break or job.
      bool add_job_first = false;
      bool add_break_first = false;

      Duration job_then_break_end = 0; // Dummy init.
      Duration break_then_job_end = 0; // Dummy init.

      // Try putting job first then break.
      Duration earliest_job_end =
        std::max(current_earliest + previous_travel, j_tw->start) + j.service;

      const auto new_b_tw =
        std::find_if(b.tws.begin(), b.tws.end(), [&](const auto& tw) {
          return earliest_job_end <= tw.end;
        });
      if (new_b_tw == b.tws.end()) {
        // Break does not fit after job due to its time windows.
        add_break_first = true;
      } else {
        job_then_break_end =
          std::max(earliest_job_end, new_b_tw->start) + b.service;
      }

      if (!add_break_first) {
        // Try putting break first then job. Only thoroughly check
        // this option if we're not already sure it's the only way.

        Duration travel_after_break = previous_travel;
        Duration earliest_job_start = current_earliest;

        if (current_earliest < b_tw->start) {
          auto margin = b_tw->start - current_earliest;
          if (margin < travel_after_break) {
            travel_after_break -= margin;
          } else {
            travel_after_break = 0;
          }

          earliest_job_start = b_tw->start;
        }

        earliest_job_start += b.service + travel_after_break;

        const auto new_j_tw =
          std::find_if(j.tws.begin(), j.tws.end(), [&](const auto& tw) {
            return earliest_job_start <= tw.end;
          });
        if (new_j_tw == j.tws.end()) {
{'fraction_non_alphanumeric': 0.12630851273948251, 'fraction_numerical': 0.0034235301863190467, 'mean_word_length': 2.556427066260829, 'pattern_counts': {'":': 0, '<': 95, '<?xml version=': 0, '>': 59, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 28, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1988275', 'n_tokens_mistral': 10371, 'n_tokens_neox': 9887, 'n_words': 2140}