1 files changed, 173 insertions, 0 deletions

diff --git a/server/src/time.cpp b/server/src/time.cpp
new file mode 100644
index 0000000..8f99dd2
--- /dev/null
+++ b/server/src/time.cpp
@@ -0,0 +1,173 @@
+module routemon:time$impl;
+
+import :time;
+
+export namespace routemon::time {
+
+using timestamp = std::chrono::time_point<std::chrono::utc_clock>;
+
+period::period(timestamp start, timestamp end) : start_{start}, end_{end}
+{
+  if (start >= end)
+  {
+    throw std::invalid_argument("period: start should be before end");
+  }
+}
+
+auto period::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;
+}
+
+auto period::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);
+}
+
+auto period::start() const -> timestamp { return start_; }
+auto period::end() const -> timestamp { return end_; }
+
+period_seq::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"};
+      }
+    }
+  }
+}
+
+period_seq::period_seq(period singleton) : periods_{singleton} {}
+
+auto period_seq::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};
+}
+
+auto period_seq::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};
+}
+
+auto period_seq::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