5#include <interval-tree/interval_tree.hpp>
6#include <interval-tree/tree_hooks.hpp>
25 template <
typename ValueType,
typename IntervalKind = lib_
interval_tree::closed>
26 class RangeStateInterval;
28 template <
typename ValueType,
typename IntervalKind>
79 return low_ <=
h &&
l <= high_;
88 return low_ <=
h + 1 &&
l - 1 <= high_;
92 return low_ <=
other.high_ + 1 &&
other.low_ - 1 <= high_;
100 return interval_kind::within(low_, high_, value);
104 return low_ <=
other.low_ && high_ >=
other.high_;
118 return high_ <
other.low_;
124 if (high_ <
other.low_)
125 return other.low_ - high_;
126 return low_ -
other.high_;
135 const auto low = std::min(low_,
other.low_);
153 :
public lib_interval_tree::node<long, RangeStateInterval<long>, CustomIntervalTreeNode>
159 this->interval_.low(this->interval_.low() +
offset);
160 this->interval_.high(this->interval_.high() +
offset);
166 this->interval_.low(this->interval_.low() -
offset);
167 this->interval_.high(this->interval_.high() -
offset);
178 template <
typename T,
typename Kind>
195 , nextEraseOverride_{std::nullopt}
196 , fullRangeUpdate_{false}
197 , disableOptimizations_{disableOptimizations}
208 fullRangeUpdate_ =
true;
215 fullRangeUpdate_ || disableOptimizations_ || trackedRanges_.empty())
218 return eraseModificationFixup(low, high);
219 return eraseInsertionFixup(low, high);
223 return eraseNotify(
static_cast<long>(low),
static_cast<long>(high));
227 if (disableOptimizations_)
229 fullRangeUpdate_ =
true;
235 operationType_ = type;
237 else if (operationType_ != type)
247 trackedRanges_.insert_overlap({low, high});
252 insertInsertRange(low, high);
257 if (nextEraseOverride_)
259 insertEraseRange(nextEraseOverride_->low(), nextEraseOverride_->high());
260 nextEraseOverride_ = std::nullopt;
263 insertEraseRange(low, high);
274 void reset(
bool requireFullRangeUpdate =
false)
276 trackedRanges_.clear();
277 fullRangeUpdate_ = requireFullRangeUpdate;
286 return fullRangeUpdate_;
290 return trackedRanges_.begin();
294 return trackedRanges_.end();
298 return trackedRanges_.rbegin();
302 return trackedRanges_.rend();
306 return operationType_;
310 void insertInsertRange(
long low,
long high)
316 auto it = trackedRanges_.find(newRange, [](
auto const& a,
auto const& b) {
317 return a.low() == b.low();
320 if (it != trackedRanges_.end())
322 newRange = it->expand(newRange);
323 trackedRanges_.erase(it);
324 it = trackedRanges_.insert(newRange);
328 it = trackedRanges_.insert(newRange);
330 if (it != std::end(trackedRanges_))
335 for (; it != trackedRanges_.end(); ++it)
337 it.node()->shiftRight(high - low + 1);
340 void insertEraseRange(
long low,
long high)
343 const bool processed = [&newRange,
this]() {
344 for (
auto it = trackedRanges_.begin(); it != trackedRanges_.end(); ++it)
348 if (it->low() < newRange.low())
351 newRange.shiftRight(it->size() + 1);
353 else if (it->overlapsOrIsAdjacent(newRange))
357 newRange = it->expand(newRange);
360 it = trackedRanges_.erase(it);
361 }
while (it != trackedRanges_.end() && it->overlapsOrIsAdjacent(newRange));
362 trackedRanges_.insert(newRange);
374 trackedRanges_.insert_overlap(newRange);
384 bool eraseInsertionFixup(
long low,
long high)
386 const auto lastInterval = *trackedRanges_.rbegin();
391 if (high < lastInterval.high())
395 auto eraseRangeOrig = eraseRange;
397 auto iter = trackedRanges_.overlap_find(eraseRange,
true);
399 for (; iter != trackedRanges_.end(); iter = trackedRanges_.overlap_find(eraseRangeOrig,
true))
401 if (iter == trackedRanges_.end())
403 const auto insertInterval = *iter;
406 if (eraseRangeOrig.high() >= insertInterval.high())
408 trackedRanges_.erase(iter);
410 if (insertInterval.low() < eraseRangeOrig.low())
412 trackedRanges_.insert({insertInterval.low(), eraseRangeOrig.low() - 1});
413 eraseRangeOrig.high(-insertInterval.high() + eraseRangeOrig.low() + eraseRangeOrig.high() - 1);
416 eraseRange.high(eraseRange.high() - insertInterval.size() - 1);
424 if (eraseRange.high() != high)
425 nextEraseOverride_ = eraseRange;
439 bool eraseModificationFixup(
long low,
long high)
443 auto iter = trackedRanges_.overlap_find(
range,
false);
445 if (iter == trackedRanges_.end())
450 const auto lastInterval = *trackedRanges_.rbegin();
454 return high < lastInterval.low();
458 for (; iter != trackedRanges_.end(); iter = trackedRanges_.overlap_find(
range,
false))
460 const auto modInterval = *iter;
461 trackedRanges_.erase(iter);
465 if (modInterval.within(
range))
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()});
474 if (modInterval.low() <
range.low())
477 trackedRanges_.insert({modInterval.low(),
range.low() - 1});
484 else if (
range.high() < modInterval.high())
487 trackedRanges_.insert({
range.high() + 1, modInterval.high()});
494 else if (
range.within(modInterval))
501 NUI_ASSERT(
false,
"Overlap without overlapping?");
508 lib_interval_tree::interval_tree<Detail::RangeStateInterval<long>, Detail::IntervalTreeHook> trackedRanges_;
510 std::optional<Detail::RangeStateInterval<long>> nextEraseOverride_;
511 bool fullRangeUpdate_;
512 bool disableOptimizations_;
#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