path: root/server/src/time.cppm

export module routemon:time;

import std;

export namespace routemon::time {

using timestamp = std::chrono::time_point<std::chrono::utc_clock>;

class period
{
  // Assuming [start, end). Unfortunately the DATEX II model is not
  // clear about this.
  timestamp start_;
  timestamp end_;

public:
  explicit period(timestamp start, timestamp end) : start_{start}, end_{end}
  {
    if (start >= end)
    {
      throw std::invalid_argument("period: start should be before end");
    }
  }

  [[nodiscard]] auto intersect(period other) const -> std::optional<period>
  {
    auto const new_start = start_ < other.start() ? other.start() : start_;
    auto const new_end = other.end() < end_ ? other.end() : end_;
    return new_start < new_end ? std::make_optional(period{new_start, new_end})
                               : std::nullopt;
  }

  [[nodiscard]] auto except(period other) const
      -> std::pair<std::optional<period>, std::optional<period>>
  {
    auto const before_start = start_;
    auto const before_end = other.start();
    auto const after_start = end_;
    auto const after_end = other.end();
    std::optional<period> before, after;
    if (before_start < before_end)
      before = period{before_start, before_end};
    if (after_start < after_end)
      after = period{after_end, after_start};
    return std::make_pair(before, after);
  }

  [[nodiscard]] auto start() const -> timestamp { return start_; }
  [[nodiscard]] auto end() const -> timestamp { return end_; }
};

class period_seq
{
  std::vector<period> periods_;

  // The way lt and ge are ordered makes a difference for how the sorting
  // (insertion based on lower_bound) works. Do not carelessly reorder this.
  enum lt_ge : std::uint8_t
  {
    ge, // >=
    lt, // <
  };

  // O(n log n)
  template <std::input_iterator I, std::sentinel_for<I> S>
    requires std::same_as<std::iter_value_t<I>, period>
  static auto consolidate(I begin, S end) -> std::vector<period>
  {
    auto periods = std::vector<period>{};
    auto preds = std::vector<std::pair<timestamp, lt_ge>>{};

    for (auto it = begin; it != end; it++)
    {
      auto const& period = *it;

      auto const a = std::make_pair(period.start(), ge);
      auto const b = std::make_pair(period.end(), lt);
      preds.insert(std::lower_bound(preds.begin(), preds.end(), a), a);
      preds.insert(std::lower_bound(preds.begin(), preds.end(), b), b);
    }

    if (preds.empty())
      return periods;

    if (preds.size() < 2)
      throw std::logic_error{
          "period_seq::consolidate: amount of predicates should be >= 2"
      };
    if (preds.front().second != ge)
      throw std::logic_error{"period_seq::consolidate: first element of preds "
                             "should be a ge-element"};
    if (preds.back().second != lt)
      throw std::logic_error{"period_seq::consolidate: last element of preds "
                             "should be an lt-element"};

    auto period_start = preds[0].first;
    for (std::size_t i = 1; i < preds.size(); i++)
    {
      if (preds[i].second == lt
          && (i + 1 == preds.size() || preds[i + 1].second == ge))
      {
        auto const period_end = preds[i].first;
        if (!periods.empty() && periods.back().start() == period_start)
          periods.back() = period{periods.back().end(), period_end};
        else
          periods.emplace_back(period_start, period_end);
        if (i + 1 != preds.size())
        {
          period_start = preds[i + 1].first;
          i++;
        }
      }
    }

    return periods;
  }

  explicit period_seq(std::vector<period> periods)
    : periods_{std::move(periods)}
  {
    for (auto i = 0uz; i < periods_.size(); i++)
    {
      if (i + 1 < periods_.size())
      {
        if (periods_[i].end() >= periods_[i + 1].start())
        {
          throw std::logic_error{"period_seq: vector provided to private "
                                 "constructor not ordered properly"};
        }
      }
    }
  }

public:
  template <std::input_iterator I, std::sentinel_for<I> S>
    requires std::same_as<std::iter_value_t<I>, period>
  explicit period_seq(I begin, S end) : periods_{consolidate(begin, end)}
  {
  }

  explicit period_seq(period singleton) : periods_{singleton} {}

  [[nodiscard]] auto intersect(period_seq const& other) const -> period_seq
  {
    auto it1 = periods_.begin();
    auto end1 = periods_.end();
    auto it2 = other.periods_.begin();
    auto end2 = other.periods_.end();

    auto res = std::vector<period>{};
    while (it1 != end1 && it2 != end2)
    {
      auto overlap = it1->intersect(*it2);
      if (overlap)
      {
        res.push_back(*overlap);
        if (it1->end() < it2->end())
        {
          it1++;
        }
        else
        {
          it2++;
        }
      }
      else
      {
        if (it1->end() < it2->start())
        {
          it1++;
        }
        else
        {
          it2++;
        }
      }
    }

    return period_seq{res};
  }

  [[nodiscard]] auto except(period_seq const& other) const -> period_seq
  {
    // This code was pretty tricky to write, I wouldn't be surprised if it
    // has some bugs in it.

    auto it1 = periods_.begin();
    auto end1 = periods_.end();
    auto it2 = other.periods_.begin();
    auto end2 = other.periods_.end();

    auto res = std::vector<period>{};
    if (it1 == end1)
      return period_seq{res};
    if (it2 == end2)
      return period_seq{periods_};
    auto period1 = period{*it1++};

    while (it1 != end1 && it2 != end2)
    {
      if (period1.end() <= it2->start())
      {
        res.push_back(period1);
        period1 = *it1++;
      }
      else if (it2->end() <= period1.start())
      {
        it2++;
      }
      else /* period1.begin() < it2->end() && it2->begin() <
              period1.end() */
      {
        auto const [mbefore, mafter] = period1.except(*it2);
        if (mbefore)
          res.push_back(*mbefore);
        if (mafter)
        {
          period1 = *mafter;
        }
        else
        {
          period1 = *it1++;
        }
      }
    }

    return period_seq{res};
  }

  [[nodiscard]] auto periods() const -> std::vector<period> const&
  {
    return periods_;
  }
};

auto operator<<(std::ostream& os, period const& p) -> std::ostream&
{
  return os << "[" << p.start() << ", " << p.end() << ")";
}

auto operator<<(std::ostream& os, period_seq const& ps) -> std::ostream&
{
  os << "{";
  auto it = ps.periods().begin();
  while (it != ps.periods().end())
  {
    os << " " << *it;
    if (++it != ps.periods().end())
    {
      os << ",";
    }
  }
  return os << " }";
}

} // namespace routemon::time