---
title: "algorithm-li-chao-tree — Mova code model"
description: "Mova code model of algorithms/src/li_chao_tree/mod.rs: components with their labels, obernants and the model text."
url: "https://groupants.elamur.ai/free/en/mova/algorithms/src/li_chao_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/li_chao_tree/mod.rs.groupant/>

# algorithm-li-chao-tree

The groupant beside algorithms/src/li_chao_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/li_chao_tree/mod.rs`](https://github.com/ElamurAI/mova-free/blob/main/algorithms/src/li_chao_tree/mod.rs)
- **source SHA-256:** `131fc4e32f41d0cb…`
- **repository folder:** [`algorithms/src/li_chao_tree/mod.rs.groupant`](https://github.com/ElamurAI/mova-free/tree/main/algorithms/src/li_chao_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) |
| `tie_fiber` | tie_fiber | partial relational specification | [tie_fiber](#tie-fiber) |
| `coordinate_projection` | coordinate_projection | partial relational specification | [coordinate_projection](#coordinate-projection) |
| `numeric_domain` | numeric_domain | partial relational specification | [numeric_domain](#numeric-domain) |

## Model text


### descriptant

#### li_chao_tree epoch memory

2026-10-30: choose exact bounded integer computation before implementation. Raw n<=2^18, distinct m<=n. Sort O(n log(n+1)), storage 4m nodes plus m coordinates; insertion/query O(log(m+1)), recursion depth O(log(m+1)); insertion count<=2^20. Allocator failure follows std and is not a typed recoverable result.

Retain the distinction between observation and internal representation: query ties preserve insertion identity; connectivity results preserve only partitions. The compiled faulty reduction/rollback controls establish sensitivity at named assertions. Original code follows the classic descriptions cited in module documentation; no copied solution.

No performance gain or approximate substitute claimed. These small files use file-level models, with no nested fragments. Source-bound partial syntax is generated twice identically; macro expansion and semantic AST remain absent. Allocation-failure behavior is not fault-injected.

### model

## li_chao_tree mod.rs

### Forward

Given fixed sorted distinct coordinates X and insertion sequence L, query x in X returns lexicographic min (a*x+b,insertion_id) over L, evaluated exactly in i128. Unknown x returns UnknownCoordinate before NoLines. Constructor caps raw input before sorting/deduplication; cap-rejected insertion preserves tree and IDs.

### Invariant

Each occupied interval node stores its best surviving line at midpoint; a displaced line can beat it on at most one side, since the difference of affine functions has at most one crossing. Query's root-to-leaf candidates include the global minimum. Equal value uses insertion ID. i64*i64+i64 stays strictly within i128 limits; no wrapping.

### Cost

Raw n<=2^18, distinct m<=n. Sort O(n log(n+1)), storage 4m nodes plus m coordinates; insertion/query O(log(m+1)), recursion depth O(log(m+1)); insertion count<=2^20. Allocator failure follows std and is not a typed recoverable result.

### behavior_complement

Universe: admitted coordinate sets and insertion/query histories paired with candidate results. Exclude any successful unknown-coordinate query, any value below all inserted lines or above their minimum, or a later ID tied with an earlier minimum. Empty coordinate construction cannot succeed; empty-line registered query cannot succeed; cap-rejected insertion cannot consume an ID.

### reverse_reconstruction

Given fixed X, an observed (x,v,id) retains all line histories where line id evaluates to v at x, every other line has value>=v, and every earlier ID has value>v. Intercepts/slopes and nonwinning lines remain ambiguous: at x=0, lines (0,2) and (7,2) both give v=2. Across several queries intersect these constraints; dominated lines remain unrecoverable.

### tie_fiber

Lexicographic (value,id) ordering makes identical lines choose ID0, and crossing lines choose earlier insertion exactly at equality. Reversing the query reduction can return a dominated path candidate; exhaustive_envelopes rejects this compiled mutation.

### coordinate_projection

Sorting/deduplication maps [3,1,3] and [1,3] to the same domain. Raw cap checks occur before this projection, so repeated coordinates exceeding the cap still fail. Queries at unregistered points are rejected even when between registered extremes.

### numeric_domain

For all i64 a,x,b, |a*x|<=2^126 and adding b remains inside signed i128. Explicit MIN/MAX coefficient/coordinate fixtures compare literal wide arithmetic; no floating interpolation or saturation occurs.

### evidence

#### Evidence, 2026-10-30

Source SHA-256: 131fc4e32f41d0cbcf21be978aee039a96e98849ee9bcb410a6fa4740a9fc9eb. Three tests for this algorithm pass twice debug and twice release with identical normalized names/results. Strict all-target Clippy and narrow rustfmt pass. One production mutant per algorithm compiles and fails a named assertion, then exact source bytes are restored.

15625 triples, 234375 exact query comparisons, plus 2^20 identical insertions and accepted/rejected coordinate cap fixtures. Finite bounded test cost; no timing benchmark.

Li Chao mutant changes query min reduction to max and fails exhaustive_envelopes. Connectivity mutant suppresses rollback and fails rollback_and_lifecycle. Six tests and two production controls total across the two algorithms. Finite evidence is not general correctness proof. No live parser/teacher/GPU, full-course or performance evidence.

External raw log hashes:

- li_chao_tree-debug-1.log: 687640980e1bf24e31543834663e3c5cbe1e5a7bf2f6cc1222b97853776fe233
- li_chao_tree-debug-2.log: 72852b921325550691d13252bc4c347c280f77b7e63f8b16dec50db5d1363de2
- li_chao_tree-release-1.log: 6d888dbb1cf62c740a1a7a550c6af192310831d058877a028d485b243514a7b9
- li_chao_tree-release-2.log: f2a4cd2701f54bb3d33a54356ef487d748e7398b73ba2188c6a3c6a6ac412fb3
- mutant-li_chao_tree.log: 9a3bd984ae011320809e9937a4af599b90a46409e39c402374477d59448858a4
- clippy.log: 999837d8357e2d33f39923fa376807b31cc10864ed60f5c06e089e5eae83c248
- check.log: 3b85fdb7533db33eb312c32b2094a66227d8ed4399e049ad5930461499eaf4de

Structural receipts: four file sidecars, eighteen typed views (five per production file, four per tests file), zero fragments, four source-bound partial syntax projections. Each syntax artifact and groupant report generated twice identically. Temporary scaffold includes the base registry unchanged; no shared registry edits committed. Initial own-only scaffold was rejected for excluding existing ownership declarations, then corrected by including base nodes.

- groupants-1.json: 07c0b20d6224715f6344d25485b47d19a0bca2cf20e787b5cd4848c073d4d3cf
- groupants-2.json: 07c0b20d6224715f6344d25485b47d19a0bca2cf20e787b5cd4848c073d4d3cf
- changed.json: 2684631f0c0110701eb8bfc5d8a70f9973f8634f19c5aa6c24c59a7e6f377c15