1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
|
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);
[[nodiscard]] auto intersect(period other) const -> std::optional<period>;
[[nodiscard]] auto except(period other) const
-> std::pair<std::optional<period>, std::optional<period>>;
[[nodiscard]] auto start() const -> timestamp;
[[nodiscard]] auto end() const -> timestamp;
};
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);
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);
[[nodiscard]] auto intersect(period_seq const& other) const -> period_seq;
[[nodiscard]] auto except(period_seq const& other) const -> period_seq;
[[nodiscard]] auto periods() const -> std::vector<period> const&;
};
auto operator<<(std::ostream& os, period const& p) -> std::ostream&;
auto operator<<(std::ostream& os, period_seq const& ps) -> std::ostream&;
} // namespace routemon::time
|
