Dense map covering $[0, n)$ that manages non-overlapping intervals $(l, r)$ within it. Each interval has an associated value $x$. Use onAdd and onDel hooks to track interval state changes during buildM, insertM and deleteM operations.

Since: 1.1.0.0

$O(n)$ Creates an empty IntervalMap.

Since: 1.1.0.0

$O(n + m \log n)$ Creates an IntervalMap by combining consecutive equal values into one interval.

Example

>>> itm <- build @_ @Int (VU.fromList [10,10,11,11,12,12])
>>> freeze itm
[(0,(2,10)),(2,(4,11)),(4,(6,12))]

Since: 1.1.0.0

$O(n + m \log n)$ Creates an IntervalMap by combining consecutive equal values into one interval, while performing onAdd hook for each interval.

Since: 1.1.0.0

$O(1)$ Returns the capacity $n$, where the interval $[0, n)$ is managed by the map.

Since: 1.1.0.0

$O(\log n)$ Returns whether a point $x$ is contained within any of the intervals.

Since: 1.1.0.0

$O(\log n)$ Returns whether an interval $[l, r)$ is fully contained within any of the intervals.

Since: 1.1.0.0

$O(\log n)$ Looks up an interval that fully contains $[l, r)$.

Since: 1.1.0.0

$O(\log n)$ Looks up an interval that fully contains $[l, r)$ and reads out the value. Throws an error if no such interval exists.

Since: 1.1.0.0

$O(\log n)$ Looks up an interval that fully contains $[l, r)$ and reads out the value. Returns Nothing if no such interval exists.

Since: 1.1.0.0

Amortized $O(\log n)$ Inserts an interval $[l, r)$ with associated value $v$ into the map. Overwrites any overlapping intervals.

Since: 1.1.0.0

Amortized $O(\log n)$ Inserts an interval $[l, r)$ with associated value $v$ into the map. Overwrites any overlapping intervals. Tracks interval state changes via onAdd and onDel hooks.

Since: 1.1.0.0

Amortized $O(\log n)$ Deletes an interval $[l, r)$ from the map.

Since: 1.1.0.0

Amortized $O(\log n)$ Deletes an interval $[l, r)$ from the map. Tracks interval state changes via onAdd and onDel hooks.

Since: 1.1.0.0

$O(\log n)$ Shorthand for overwriting the value of an interval that contains $[l, r)$.

Since: 1.1.0.0

$O(\log n)$. Shorthand for overwriting the value of an interval that contains $[l, r)$. Tracks interval state changes via onAdd and onDel hooks.

Since: 1.1.0.0

$O(n \log n)$ Enumerates the intervals and the associated values as $(l, (r, x))$ tuples, where $[l, r)$ is the interval and $x$ is the associated value.

Since: 1.1.0.0