---
title: "algorithm-interval-tree — Mova code model"
description: "Mova code model of algorithms/src/interval_tree/mod.rs: components with their labels, obernants and the model text."
url: "https://groupants.elamur.ai/free/en/mova/algorithms/src/interval_tree/mod.rs.groupant/"
---
Elamur: [Mova](https://md.mova.elamur.ai/free/en/) · [Dictionary](https://md.dictionary.elamur.ai/free/en/) · [Research](https://md.research.elamur.ai/free/en/) · **Groupants**

This page as HTML: <https://groupants.elamur.ai/free/en/mova/algorithms/src/interval_tree/mod.rs.groupant/>

# algorithm-interval-tree

The groupant beside algorithms/src/interval_tree/mod.rs in the Mova repository: what the code computes, what it never does, how to go back from its outputs, its invariants, cost and checks.

## Facts

- **kind:** groupant
- **status:** partial source derived instance
- **source:** [`algorithms/src/interval_tree/mod.rs`](https://github.com/ElamurAI/mova-free/blob/main/algorithms/src/interval_tree/mod.rs)
- **source SHA-256:** `5e70fe6d2bec67a9…`
- **repository folder:** [`algorithms/src/interval_tree/mod.rs.groupant`](https://github.com/ElamurAI/mova-free/tree/main/algorithms/src/interval_tree/mod.rs.groupant)
- **repository commit:** `855da7bd4a7b`

> **Implementation material.** A Mova code model describes this code at one source revision: partial models, finite checks and their stated scope. It is not a reviewed general exposition, and its labels are shown as written, never raised.

## Components

| component | label | where |
|---|---|---|
| **approximant** | partial | [Forward](#forward) |
| **ast** | partial | `syntax.json` |
| **cost** | conditional | [Cost](#cost) |
| **descriptant** | present | [descriptant](#descriptant) |
| **invariant** | partial | [Invariant](#invariant) |
| **tests** | bounded executed | [evidence](#evidence) |

## Obernants

The typed relations around the forward model: the behaviour complement (what the code never does), the reverse reconstruction (every input compatible with an output) and specialised views.

| id | type | label | where |
|---|---|---|---|
| `behavior_complement` | behavior_complement | partial relational specification | [behavior_complement](#behavior-complement) |
| `reverse_reconstruction` | reverse_reconstruction | partial relational specification | [reverse_reconstruction](#reverse-reconstruction) |
| `closed_boundary` | closed_boundary | partial relational specification | [closed_boundary](#closed-boundary) |
| `augmentation` | augmentation | partial relational specification | [augmentation](#augmentation) |
| `stable_identity` | stable_identity | partial relational specification | [stable_identity](#stable-identity) |
| `validation_order` | validation_order | partial relational specification | [validation_order](#validation-order) |

## Model text


### descriptant

#### Closed interval overlap tree

Original std-only Rust implementation and fixtures. Reference: Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, interval-tree augmentation.

##### Prospective epoch, 2026-10-30

Domain, recurrence, invariants, costs and validation plan were saved before implementation in $MOVA_DATA/runs/octopus-wave26-indexes-2026-10-30/prospective.md. No runtime gain was predicted or measured.

##### Executed epoch, 2026-10-30

Three tests: exhaustive_closed_overlap_oracle, duplicate_touching_full_width, validation_and_capacity.

All64 subsets of the six closed intervals on {-1,0,1}, all15 ordered queries on {-2,-1,0,1,2}; direct disjointness predicate is independent of augmented pruning. Duplicate points, full-width endpoints and cap boundaries are explicit.

##### Limits

Exact bounded APIs only. No generic 1/2/5/10% accuracy surrogate is supported. Finite tests do not prove universal correctness or runtime gains. Standard Vec/Box/BTreeMap allocation failure may abort or panic; allocator refusal is not injected. No callbacks, I/O or concurrency effects.
Partial Rust syntax is source-bound; macro expansion, semantic AST proof and whole-Mova quality remain gaps.

### model

## Mathematical model

### Forward

Sort (start,end,index), recursively choose medians, cache maximum endpoint over each subtree. Visit left subtree unless cached maximum is below query start; stop current/right processing when current start exceeds query end. Emit intervals whose end reaches query start, then sort original indexes.

### Invariant

Inorder triples are sorted; cached max_end equals the maximum endpoint among all subtree entries. Every emitted interval has start<=query.end and query.start<=end. A pruned subtree cannot overlap the query.

### Cost

O(n log n) build, O(n) storage. O(n+k log k) worst query time and O(log n+k) scratch; k output indexes need sorting. Balanced immutable topology gives logarithmic stack depth.

### behavior_complement

For valid closed intervals and query, any candidate result containing a non-overlap or missing an overlap is excluded; indexes must be unique and ascending. Touching endpoints are not excluded: closed intervals intersect there. Invalid/reversed query paired with Ok is excluded.

### reverse_reconstruction

A result index set S admits every interval sequence whose members overlap iff their index lies in S. Intersection positions, interval widths and exact endpoints are generally unrecoverable. Empty result admits both empty input and arbitrary disjoint intervals; no unique inverse.

### closed_boundary

Overlap is !(end<query.start || query.end<start). Zero-width intervals and endpoint-touching pairs match. Changing < pruning or <= membership to strict variants loses valid outputs.

### augmentation

max_end is max(own end,left max,right max); i64::MIN is a safe absent-child identity. No addition/subtraction means full-width endpoints cannot overflow.

### stable_identity

Sorted build triples include index for duplicates; duplicate intervals appear separately in answers. Query results sort by original index independently of internal median traversal order.

### validation_order

Reject length>4096 before reversed endpoint check. Otherwise all starts<=ends are admitted, including full i64 width and empty sequence. A reversed query errors even on an empty index; allocations use standard failure behavior.

### Gaps

Exact bounded APIs only. No generic 1/2/5/10% accuracy surrogate is supported. Finite tests do not prove universal correctness or runtime gains. Standard Vec/Box/BTreeMap allocation failure may abort or panic; allocator refusal is not injected. No callbacks, I/O or concurrency effects.

### evidence

#### Evidence, 2026-10-30

Four identical normalized runs: 706 tests; 14 new tests.
kd_tree: compiled production mutant exit Some(101), named assertion exhaustive_grid_oracle; exact restoration and positive rerun exit Some(0).
bk_tree: compiled production mutant exit Some(101), named assertion exhaustive_metric_oracle; exact restoration and positive rerun exit Some(0).
interval_tree: compiled production mutant exit Some(101), named assertion exhaustive_closed_overlap_oracle; exact restoration and positive rerun exit Some(0).
treap: compiled production mutant exit Some(101), named assertion exhaustive_operation_oracle; exact restoration and positive rerun exit Some(0).
splay_tree: compiled production mutant exit Some(101), named assertion exhaustive_stateful_oracle; exact restoration and positive rerun exit Some(0).

Strict mova-algorithms all-target Clippy passed; focused rustfmt passed. Receipts: $MOVA_DATA/runs/octopus-wave26-indexes-2026-10-30. Two freshly generated syntax projections must compare identical before syntax.json installation. No benchmark or training/quality measurement is claimed.

For this module: Three tests: exhaustive_closed_overlap_oracle, duplicate_touching_full_width, validation_and_capacity.