Nui
Loading...
Searching...
No Matches
range_event_context.hpp
Go to the documentation of this file.
1#pragma once
2
4
5#include <interval-tree/interval_tree.hpp>
6#include <interval-tree/tree_hooks.hpp>
7
8#include <cstddef>
9#include <algorithm>
10#include <vector>
11#include <optional>
12
13namespace Nui
14{
16 {
17 Keep = 0b0001,
18 Modify = 0b0010,
19 Insert = 0b0100,
20 Erase = 0b1000
21 };
22
23 namespace Detail
24 {
25 template <typename ValueType, typename IntervalKind = lib_interval_tree::closed>
26 class RangeStateInterval;
27
28 template <typename ValueType, typename IntervalKind>
30 {
31 public:
34
35 public:
36 // NOLINTNEXTLINE(bugprone-easily-swappable-parameters)
38 : low_{low}
39 , high_{high}
40 {}
41 // NOLINTNEXTLINE(bugprone-easily-swappable-parameters)
43 {
44 low_ = low;
45 high_ = high;
46 }
48 {
49 return lhs.low_ == rhs.low_ && lhs.high_ == rhs.high_;
50 }
52 {
53 return !(lhs == rhs);
54 }
56 {
57 return low_;
58 }
60 {
61 return high_;
62 }
63 void low(value_type value)
64 {
65 low_ = value;
66 }
67 void high(value_type value)
68 {
69 high_ = value;
70 }
72 {
73 // return low_ <= h && l <= high_;
74 return overlapsOrIsAdjacent(l, h);
75 }
76 // looks inclusive, but inclusive now means adjacent:
78 {
79 return low_ <= h && l <= high_;
80 }
82 {
83 // return overlaps(other.low_, other.high_);
85 }
87 {
88 return low_ <= h + 1 && l - 1 <= high_;
89 }
91 {
92 return low_ <= other.high_ + 1 && other.low_ - 1 <= high_;
93 }
95 {
96 return overlaps_exclusive(other.low_, other.high_);
97 }
98 bool within(value_type value) const
99 {
100 return interval_kind::within(low_, high_, value);
101 }
102 bool within(RangeStateInterval const& other) const
103 {
104 return low_ <= other.low_ && high_ >= other.high_;
105 }
107 {
108 low_ += offset;
109 high_ += offset;
110 }
112 {
113 low_ -= offset;
114 high_ -= offset;
115 }
117 {
118 return high_ < other.low_;
119 }
121 {
122 if (overlaps(other))
123 return 0;
124 if (high_ < other.low_)
125 return other.low_ - high_;
126 return low_ - other.high_;
127 }
129 {
130 return high_ - low_;
131 }
132 // undefined if they do not overlap
134 {
135 const auto low = std::min(low_, other.low_);
136 // +1, because if they overlap they share a side, so its not double counted
137 // [0, 1] and [1, 2] -> [0, 2]
138 // [8, 8] and [8, 8] -> [8, 9]
139 const auto high = low + size() + other.size() + 1;
140 return {low, high};
141 }
143 {
144 return RangeStateInterval{std::min(low_, other.low_), std::max(high_, other.high_)};
145 }
146
147 private:
148 value_type low_;
149 value_type high_;
150 };
151
153 : public lib_interval_tree::node<long, RangeStateInterval<long>, CustomIntervalTreeNode>
154 {
155 using lib_interval_tree::node<long, RangeStateInterval<long>, CustomIntervalTreeNode>::node;
156
158 {
159 this->interval_.low(this->interval_.low() + offset);
160 this->interval_.high(this->interval_.high() + offset);
161 this->max_ = this->max_ + offset;
162 }
163
164 void shiftLeft(long offset)
165 {
166 this->interval_.low(this->interval_.low() - offset);
167 this->interval_.high(this->interval_.high() - offset);
168 this->max_ = this->max_ - offset;
169 }
170 };
171
172 struct IntervalTreeHook : public lib_interval_tree::hooks::regular
173 {
175 };
176
177 // stream iterator for intervals
178 template <typename T, typename Kind>
179 std::ostream& operator<<(std::ostream& os, RangeStateInterval<T, Kind> const& interval)
180 {
181 os << "[" << interval.low() << ", " << interval.high() << "]";
182 return os;
183 }
184 }
185
187 {
188 public:
190 : RangeEventContext(false)
191 {}
192 explicit RangeEventContext(bool disableOptimizations)
193 : trackedRanges_{}
194 , operationType_{RangeOperationType::Keep}
195 , nextEraseOverride_{std::nullopt}
196 , fullRangeUpdate_{false}
197 , disableOptimizations_{disableOptimizations}
198 {}
199 enum class InsertResult
200 {
201 Perform,
203 Accepted,
205 };
207 {
208 fullRangeUpdate_ = true;
209 }
212 bool eraseNotify(long low, long high)
213 {
214 if (operationType_ == RangeOperationType::Keep || operationType_ == RangeOperationType::Erase ||
215 fullRangeUpdate_ || disableOptimizations_ || trackedRanges_.empty())
216 return false;
217 if (operationType_ == RangeOperationType::Modify)
218 return eraseModificationFixup(low, high);
219 return eraseInsertionFixup(low, high);
220 }
221 bool eraseNotify(std::size_t low, std::size_t high)
222 {
223 return eraseNotify(static_cast<long>(low), static_cast<long>(high));
224 }
226 {
227 if (disableOptimizations_)
228 {
229 fullRangeUpdate_ = true;
231 }
232
233 if (operationType_ == RangeOperationType::Keep)
234 {
235 operationType_ = type;
236 }
237 else if (operationType_ != type)
239
240 switch (type)
241 {
242 default:
245 {
246 // Insert and merge interval only:
247 trackedRanges_.insert_overlap({low, high});
248 break;
249 }
251 {
252 insertInsertRange(low, high);
253 break;
254 }
256 {
257 if (nextEraseOverride_)
258 {
259 insertEraseRange(nextEraseOverride_->low(), nextEraseOverride_->high());
260 nextEraseOverride_ = std::nullopt;
261 }
262 else
263 insertEraseRange(low, high);
264 break;
265 }
266 }
267
269 }
270 InsertResult insertModificationRange(std::size_t low, std::size_t high, RangeOperationType type)
271 {
272 return insertModificationRange(static_cast<long>(low), static_cast<long>(high), type);
273 }
274 void reset(bool requireFullRangeUpdate = false)
275 {
276 trackedRanges_.clear();
277 fullRangeUpdate_ = requireFullRangeUpdate;
278 operationType_ = RangeOperationType::Keep;
279 }
280 bool isInDefaultState() const
281 {
282 return trackedRanges_.empty() && operationType_ == RangeOperationType::Keep;
283 }
284 bool isFullRangeUpdate() const noexcept
285 {
286 return fullRangeUpdate_;
287 }
288 auto begin() const
289 {
290 return trackedRanges_.begin();
291 }
292 auto end() const
293 {
294 return trackedRanges_.end();
295 }
296 auto rbegin() const
297 {
298 return trackedRanges_.rbegin();
299 }
300 auto rend() const
301 {
302 return trackedRanges_.rend();
303 }
305 {
306 return operationType_;
307 }
308
309 private:
310 void insertInsertRange(long low, long high)
311 {
312 // TODO: perform optimization using interval tree specialization for shifting subtrees.
313 auto newRange = Detail::RangeStateInterval<long>{low, high};
314
315 // find insert at same position first to move previous insert at that position over:
316 auto it = trackedRanges_.find(newRange, [](auto const& a, auto const& b) {
317 return a.low() == b.low();
318 });
319
320 if (it != trackedRanges_.end())
321 {
322 newRange = it->expand(newRange);
323 trackedRanges_.erase(it);
324 it = trackedRanges_.insert(newRange);
325 }
326 else
327 {
328 it = trackedRanges_.insert(newRange);
329 }
330 if (it != std::end(trackedRanges_))
331 ++it;
332
333 // move all subsequent intervals to the right:
334 // TODO: This is the expensive part and should be optimized.
335 for (; it != trackedRanges_.end(); ++it)
336 {
337 it.node()->shiftRight(high - low + 1);
338 }
339 }
340 void insertEraseRange(long low, long high)
341 {
342 auto newRange = Detail::RangeStateInterval<long>{low, high};
343 const bool processed = [&newRange, this]() {
344 for (auto it = trackedRanges_.begin(); it != trackedRanges_.end(); ++it)
345 {
346 // Shift erasure over when previous erasures shrank the range,
347 // since erasures are replayed from the end.
348 if (it->low() < newRange.low())
349 {
350 // +1 because the range includes its end
351 newRange.shiftRight(it->size() + 1);
352 }
353 else if (it->overlapsOrIsAdjacent(newRange))
354 {
355 do
356 {
357 newRange = it->expand(newRange);
358
359 // Remove the old range and insert the new one
360 it = trackedRanges_.erase(it);
361 } while (it != trackedRanges_.end() && it->overlapsOrIsAdjacent(newRange));
362 trackedRanges_.insert(newRange);
363 return true;
364 }
365 else
366 {
367 return false;
368 }
369 }
370 return false;
371 }();
372 if (!processed)
373 {
374 trackedRanges_.insert_overlap(newRange);
375 }
376 }
377
384 bool eraseInsertionFixup(long low, long high)
385 {
386 const auto lastInterval = *trackedRanges_.rbegin();
387
388 // If the erase interval is left of the last insert interval, we must apply the changes and
389 // retry. The following optimization would make the insert positions invalid.
390 // TODO: Moving them might be possible, but expensive.
391 if (high < lastInterval.high())
392 return true;
393
394 auto eraseRange = Detail::RangeStateInterval<long>{low, high};
395 auto eraseRangeOrig = eraseRange;
396
397 auto iter = trackedRanges_.overlap_find(eraseRange, true);
398 // if erase is completely at the end of a previous insert, we can cut the inserted elements out.
399 for (; iter != trackedRanges_.end(); iter = trackedRanges_.overlap_find(eraseRangeOrig, true))
400 {
401 if (iter == trackedRanges_.end())
402 return true;
403 const auto insertInterval = *iter;
404
405 // erase overlaps insert to the end or over:
406 if (eraseRangeOrig.high() >= insertInterval.high())
407 {
408 trackedRanges_.erase(iter);
409 // if beginning of insert is left of erase, we have to insert the left part of the insert
410 if (insertInterval.low() < eraseRangeOrig.low())
411 {
412 trackedRanges_.insert({insertInterval.low(), eraseRangeOrig.low() - 1});
413 eraseRangeOrig.high(-insertInterval.high() + eraseRangeOrig.low() + eraseRangeOrig.high() - 1);
414 }
415
416 eraseRange.high(eraseRange.high() - insertInterval.size() - 1);
417 }
418 else
419 {
420 break; // bail out
421 }
422 }
423
424 if (eraseRange.high() != high)
425 nextEraseOverride_ = eraseRange;
426
427 // Other tracking cases are too complicated.
428 // The reason is that cutting the intervals is not enough, we also have to modify where these insertions are
429 // taken from.
430 return true;
431 }
432
439 bool eraseModificationFixup(long low, long high)
440 {
441 auto range = Detail::RangeStateInterval<long>{low, high};
442
443 auto iter = trackedRanges_.overlap_find(range, false);
444
445 if (iter == trackedRanges_.end())
446 {
447 // If we dont have an overlap, there might still be a case where modifications exists
448 // after the erase. In that case we have to apply these changes immediately and retry the erase.
449 // (Shifting the previous modifications would work too, but is more expensive)
450 const auto lastInterval = *trackedRanges_.rbegin();
451
452 // If the erase interval is left of the last modification interval, we must apply the changes and
453 // retry. An overlap would have been found otherwise.
454 return high < lastInterval.low();
455 }
456
457 // find all overlapping modifications and cut them
458 for (; iter != trackedRanges_.end(); iter = trackedRanges_.overlap_find(range, false))
459 {
460 const auto modInterval = *iter;
461 trackedRanges_.erase(iter);
462
463 // cut erasure from found modification interval:
464 // 1. erase is within modification interval:
465 if (modInterval.within(range))
466 {
467 if (modInterval.low() < range.low())
468 trackedRanges_.insert({modInterval.low(), range.low() - 1});
469 if (range.high() < modInterval.high())
470 trackedRanges_.insert({range.high() + 1, modInterval.high()});
471 return true; // cannot overlap any further
472 }
473
474 if (modInterval.low() < range.low())
475 {
476 // 2. erase starts within modification interval:
477 trackedRanges_.insert({modInterval.low(), range.low() - 1});
478
479 // reduce range to right part:
480 range.low(range.low() + 1);
481 if (range.low() > range.high())
482 return true;
483 }
484 else if (range.high() < modInterval.high())
485 {
486 // 3. erase ends within modification interval:
487 trackedRanges_.insert({range.high() + 1, modInterval.high()});
488
489 // reduce range to left part:
490 range.high(range.high() - 1);
491 if (range.low() > range.high())
492 return true;
493 }
494 else if (range.within(modInterval))
495 {
496 // 4. erase encompasses modification interval, only deletion is necessary:
497 continue;
498 }
499 else
500 {
501 NUI_ASSERT(false, "Overlap without overlapping?");
502 }
503 }
504 return true;
505 }
506
507 private:
508 lib_interval_tree::interval_tree<Detail::RangeStateInterval<long>, Detail::IntervalTreeHook> trackedRanges_;
509 RangeOperationType operationType_;
510 std::optional<Detail::RangeStateInterval<long>> nextEraseOverride_;
511 bool fullRangeUpdate_;
512 bool disableOptimizations_;
513 };
514}
#define NUI_ASSERT(condition, message)
Definition assert.hpp:31
Definition range_event_context.hpp:30
bool overlaps(RangeStateInterval const &other) const
Definition range_event_context.hpp:81
friend bool operator==(RangeStateInterval const &lhs, RangeStateInterval const &rhs)
Definition range_event_context.hpp:47
bool overlaps_exclusive(RangeStateInterval const &other) const
Definition range_event_context.hpp:94
bool within(RangeStateInterval const &other) const
Definition range_event_context.hpp:102
RangeStateInterval join(RangeStateInterval const &other) const
Definition range_event_context.hpp:142
bool isLeftOf(RangeStateInterval const &other) const
Definition range_event_context.hpp:116
IntervalKind interval_kind
Definition range_event_context.hpp:33
void high(value_type value)
Definition range_event_context.hpp:67
value_type high() const
Definition range_event_context.hpp:59
void low(value_type value)
Definition range_event_context.hpp:63
bool overlaps(value_type l, value_type h) const
Definition range_event_context.hpp:71
value_type operator-(RangeStateInterval const &other) const
Definition range_event_context.hpp:120
ValueType value_type
Definition range_event_context.hpp:32
friend bool operator!=(RangeStateInterval const &lhs, RangeStateInterval const &rhs)
Definition range_event_context.hpp:51
bool overlapsOrIsAdjacent(value_type l, value_type h) const
Definition range_event_context.hpp:86
bool within(value_type value) const
Definition range_event_context.hpp:98
void reset(value_type low, value_type high)
Definition range_event_context.hpp:42
void shiftLeft(value_type offset)
Definition range_event_context.hpp:111
bool overlaps_exclusive(value_type l, value_type h) const
Definition range_event_context.hpp:77
RangeStateInterval expand(RangeStateInterval const &other) const
Definition range_event_context.hpp:133
bool overlapsOrIsAdjacent(RangeStateInterval const &other) const
Definition range_event_context.hpp:90
value_type size() const
Definition range_event_context.hpp:128
void shiftRight(value_type offset)
Definition range_event_context.hpp:106
RangeStateInterval(value_type low, value_type high)
Definition range_event_context.hpp:37
value_type low() const
Definition range_event_context.hpp:55
Definition range_event_context.hpp:187
auto begin() const
Definition range_event_context.hpp:288
InsertResult insertModificationRange(long low, long high, RangeOperationType type)
Definition range_event_context.hpp:225
bool eraseNotify(std::size_t low, std::size_t high)
Definition range_event_context.hpp:221
RangeOperationType operationType() const noexcept
Definition range_event_context.hpp:304
bool isFullRangeUpdate() const noexcept
Definition range_event_context.hpp:284
auto rend() const
Definition range_event_context.hpp:300
auto rbegin() const
Definition range_event_context.hpp:296
bool isInDefaultState() const
Definition range_event_context.hpp:280
void reset(bool requireFullRangeUpdate=false)
Definition range_event_context.hpp:274
InsertResult insertModificationRange(std::size_t low, std::size_t high, RangeOperationType type)
Definition range_event_context.hpp:270
RangeEventContext()
Definition range_event_context.hpp:189
RangeEventContext(bool disableOptimizations)
Definition range_event_context.hpp:192
auto end() const
Definition range_event_context.hpp:292
void performFullRangeUpdate()
Definition range_event_context.hpp:206
InsertResult
Definition range_event_context.hpp:200
bool eraseNotify(long low, long high)
Done before the erasure is performed:
Definition range_event_context.hpp:212
std::ostream & operator<<(std::ostream &os, RangeStateInterval< T, Kind > const &interval)
Definition range_event_context.hpp:179
static constexpr auto extractJsonMember(nlohmann::json const &json) -> decltype(auto)
Definition rpc_hub.hpp:29
Definition file_dialog.hpp:6
RangeOperationType
Definition range_event_context.hpp:16
@ Modify
Definition range_event_context.hpp:18
@ Insert
Definition range_event_context.hpp:19
@ Erase
Definition range_event_context.hpp:20
@ Keep
Definition range_event_context.hpp:17
ObservedRange< ObservedValue > range(ObservedValue &observedValues)
Definition range.hpp:83
Definition range_event_context.hpp:154
void shiftRight(long offset)
Definition range_event_context.hpp:157
void shiftLeft(long offset)
Definition range_event_context.hpp:164
Definition range_event_context.hpp:173