Documentation
¶
Overview ¶
Package interval provides an augmented interval tree for efficient range-overlap queries. It supports Insert, Delete, QueryOverlap, and QueryPoint operations with O(log N) insert/delete and O(log N + k) query time, where k is the number of overlapping intervals.
The tree is backed by a red-black tree where each node stores the maximum right endpoint (maxHigh) in its subtree, enabling subtree pruning during overlap queries.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Integer ¶
type Integer interface {
~int | ~int8 | ~int16 | ~int32 | ~int64 |
~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr
}
Integer constrains interval endpoints to integer types.
type Interval ¶
type Interval[K Integer, V comparable] struct { Low K High K Value V }
Interval represents a closed range [Low, High] with an associated Value.
type Tree ¶
type Tree[K Integer, V comparable] struct { // contains filtered or unexported fields }
Tree is an augmented interval tree supporting overlap queries.
func (*Tree[K, V]) Delete ¶
Delete removes one interval matching [low, high, value] from the tree. Returns true if the interval was found and removed, false otherwise.
func (*Tree[K, V]) Insert ¶
func (t *Tree[K, V]) Insert(low, high K, value V)
Insert adds an interval [low, high] with the given value to the tree.
func (*Tree[K, V]) QueryOverlap ¶
QueryOverlap returns all intervals that overlap with the query range [low, high]. An interval [a, b] overlaps [low, high] when a <= high AND b >= low.
func (*Tree[K, V]) QueryPoint ¶
QueryPoint returns all intervals containing the given point. Equivalent to QueryOverlap(point, point).
Source Files