# `Minga.Core.IntervalTree`
[🔗](https://github.com/jsmestad/minga/blob/main/lib/minga/core/interval_tree.ex#L1)

Augmented interval tree for efficient range queries over buffer decorations.

Backed by an AVL-balanced binary search tree where each node stores an
interval `{start, end}` keyed by the start position, and is augmented
with the maximum end position in its subtree. This augmentation enables
O(log n + k) stabbing and overlap queries, where n is the total number
of intervals and k is the number of results.

## Interval representation

Intervals use `{line, col}` tuple positions, compared lexicographically.
Start is inclusive, end is exclusive: `[start, end)`. This matches the
convention used by tree-sitter, LSP, and Zed's decoration system.

## Performance characteristics

- **Insert**: O(log n) amortized (AVL rebalancing)
- **Delete**: O(log n) amortized
- **Overlap query** ("all intervals intersecting [qstart, qend)"): O(log n + k)
- **Stabbing query** ("all intervals containing point p"): O(log n + k)
- **Bulk rebuild**: O(n log n) from a list of intervals

The tree is optimized for the read path (queries every frame at 60fps)
over the write path (decorations change on edits and sync, not every frame).

## Design decisions

- Pure Elixir, no NIFs. The BEAM's per-process GC handles tree nodes
  without global pauses.
- AVL balancing (not red-black) for simpler implementation with the same
  O(log n) guarantees. The constant factor difference is irrelevant for
  our workload (thousands of nodes, not millions).
- Immutable: every mutation returns a new tree. This is the Elixir way
  and enables safe concurrent reads from the render pipeline while the
  buffer process updates decorations.

# `interval`

```elixir
@type interval() :: %{
  id: reference(),
  start: position(),
  end_: position(),
  value: term()
}
```

An interval stored in the tree. `start` is inclusive, `end_` is exclusive.
`id` is a unique reference for deletion. `value` is the associated data
(e.g., a highlight range struct).

# `node_t`

```elixir
@type node_t() :: %{
  interval: interval(),
  max_end: position(),
  left: t(),
  right: t(),
  height: non_neg_integer()
}
```

A node in the AVL tree.

- `interval`: the interval stored at this node
- `max_end`: the maximum `end_` position in this node's entire subtree
- `left`, `right`: child subtrees
- `height`: AVL height for balance factor computation

# `position`

```elixir
@type position() :: {non_neg_integer(), non_neg_integer()}
```

A position in the buffer: `{line, col}`, both 0-indexed.
Compared lexicographically (line first, then col).

# `t`

```elixir
@type t() :: node_t() | nil
```

The tree: either nil (empty) or a node.

# `delete`

```elixir
@spec delete(t(), reference()) :: t()
```

Deletes the interval with the given ID from the tree.

Returns the new tree. No-op if the ID is not found.

# `empty?`

```elixir
@spec empty?(t()) :: boolean()
```

Returns true if the tree is empty.

# `from_list`

```elixir
@spec from_list([interval()]) :: t()
```

Builds an interval tree from a list of intervals.

More efficient than repeated `insert/2` calls: sorts once, then builds
a balanced tree via median splitting. O(n log n).

# `insert`

```elixir
@spec insert(t(), interval()) :: t()
```

Inserts an interval into the tree. Returns the new tree.

The interval must have `:id`, `:start`, `:end_`, and `:value` keys.
Duplicate IDs are not checked; callers should ensure uniqueness.

# `map_filter`

```elixir
@spec map_filter(t(), (interval() -> {:keep, interval()} | :remove)) :: t()
```

Applies a transformation function to every interval in the tree and
rebuilds it. Used for bulk anchor adjustment after buffer edits.

The function receives an interval and returns either `{:keep, updated_interval}`
or `:remove` (if the edit invalidated the interval, e.g., its entire
range was deleted).

Rebuilds from scratch via `from_list/1` after transformation, which is
O(n log n). This is appropriate for edit-time updates (not per-frame).

# `new`

```elixir
@spec new() :: t()
```

Returns an empty interval tree.

# `query`

```elixir
@spec query(t(), position(), position()) :: [interval()]
```

Returns all intervals that overlap with the query range `[query_start, query_end)`.

An interval `[s, e)` overlaps `[qs, qe)` when `s < qe AND e > qs`.

Runs in O(log n + k) where k is the number of results, thanks to the
`max_end` augmentation that prunes entire subtrees.

# `query_lines`

```elixir
@spec query_lines(t(), non_neg_integer(), non_neg_integer()) :: [interval()]
```

Returns all intervals that intersect any line in the range `[start_line, end_line]`
(both inclusive).

This is the primary query for the render pipeline: "give me all decorations
that touch lines 50-80." It's a range query where the query range spans
from `{start_line, 0}` to `{end_line + 1, 0}`.

# `size`

```elixir
@spec size(t()) :: non_neg_integer()
```

Returns the number of intervals in the tree.

# `stabbing`

```elixir
@spec stabbing(t(), position()) :: [interval()]
```

Returns all intervals that contain the given point (stabbing query).

A point `p` is contained by interval `[s, e)` when `s <= p AND e > p`.
This is equivalent to `query(tree, p, {line, col + 1})` but expressed
more clearly for point queries.

# `to_list`

```elixir
@spec to_list(t()) :: [interval()]
```

Converts the tree to a sorted list of intervals (in-order traversal).

---

*Consult [api-reference.md](api-reference.md) for complete listing*