From 973aec43ea54bbf95b64fbcb636403401d1ca60e Mon Sep 17 00:00:00 2001 From: Rutger Broekhoff Date: Fri, 28 Aug 2026 18:03:05 +0200 Subject: Import from e4b104792206ee7ea64bf39c6b7d2c0c230f9d14 --- server/src/time.cppm | 205 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 205 insertions(+) create mode 100644 server/src/time.cppm (limited to 'server/src/time.cppm') 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; + + 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 { + 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> { + auto const before_start = start_; + auto const before_end = other.start(); + auto const after_start = end_; + auto const after_end = other.end(); + std::optional 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 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 S> + requires std::same_as, period> + static auto consolidate(I begin, S end) -> std::vector { + auto periods = std::vector{}; + auto preds = std::vector>{}; + + 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 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 S> + requires std::same_as, 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{}; + 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{}; + 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 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 -- cgit v1.3