1 files changed, 205 insertions, 0 deletions

diff --git a/server/src/time.cppm b/server/src/time.cppm
new file mode 100644
index 0000000..767883c
--- /dev/null
+++ b/server/src/time.cppm
@@ -0,0 +1,205 @@
+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