IntervalTree.Net 0.1.0-alpha.1

IntervalTree.Net

Overview

IntervalTree.Net is a small, focused library for .NET 8 that implements an interval tree data structure. It is designed for back‑end services that need to efficiently answer questions such as “which items overlap this range?” or “what is active right now?” The library exposes a minimal, predictable API, has no framework dependencies and is geared toward efficient range queries and clarity. Typical use cases include scheduling conflict detection, evaluating active feature flags or promotions, and applying rules over numeric or temporal ranges.

Why Interval Trees Matter in Back‑End Systems

Naïve range queries require scanning every interval, which is (O(n)) time per query. An interval tree organizes intervals so that overlap and point‑in‑interval queries can be answered in logarithmic time with output‑sensitive cost. This implementation uses a balanced augmented tree so queries run in (O(\log n + m)) time, where m is the number of matching intervals. Insertions and deletions each take (O(\log n)) time.

Installation

IntervalTree.Net is public on GitHub but is not currently published to NuGet. The current package version is a local prerelease candidate, 0.1.0-alpha.1; no NuGet publication has occurred and no stable release is implied.

For local development, restore and build the solution:

dotnet restore IntervalTree.Net.sln
dotnet build IntervalTree.Net.sln --configuration Release --no-restore
dotnet test IntervalTree.Net.sln --configuration Release --no-build
dotnet pack src/IntervalTree.Net/IntervalTree.Net.csproj --configuration Release --no-build
bash scripts/smoke-test-local-package.sh

The library targets net8.0 and uses modern C# features. The library package includes README and XML documentation metadata, SourceLink metadata for GitHub, and local .snupkg symbol package generation. NuGet publishing is not approved or completed in the current repository state.

To inspect or consume the package locally, pack it to a local folder and add that folder as a package source in a separate test project:

dotnet pack src/IntervalTree.Net/IntervalTree.Net.csproj --configuration Release --no-build --output artifacts/package-local
dotnet add <consumer-project>.csproj package IntervalTree.Net --version 0.1.0-alpha.1 --source <repo-root>/artifacts/package-local

After any future approved publication, consumers would be able to install from NuGet.org with dotnet add package IntervalTree.Net --version 0.1.0-alpha.1 or a later published version. That command is not a current live NuGet.org install path.

Quick Start

Here’s a small example that demonstrates constructing a tree, adding intervals and performing both point and overlap queries:

using IntervalTree;

// Create a tree with DateTime as the point type and string as the value type
var tree = new IntervalTree<DateTime, string>();

// Add some half‑open intervals [start, end) associated with values
tree.Add(new Interval<DateTime>(
    new DateTime(2026, 1, 1, 9, 0, 0),
    new DateTime(2026, 1, 1, 10, 0, 0)),
    "Morning meeting");

tree.Add(new Interval<DateTime>(
    new DateTime(2026, 1, 1, 9, 30, 0),
    new DateTime(2026, 1, 1, 11, 0, 0)),
    "Stand‑up call");

tree.Add(new Interval<DateTime>(
    new DateTime(2026, 1, 1, 11, 0, 0),
    new DateTime(2026, 1, 1, 12, 0, 0)),
    "Code review");

// Query what is active at 9:45
var activeAt945 = tree.QueryPoint(new DateTime(2026, 1, 1, 9, 45, 0));
// activeAt945 contains "Morning meeting" and "Stand‑up call"

// Check which meetings overlap a proposed slot [10:00, 11:00)
var overlaps = tree.QueryOverlap(new Interval<DateTime>(
    new DateTime(2026, 1, 1, 10, 0, 0),
    new DateTime(2026, 1, 1, 11, 0, 0)));
// overlaps contains "Stand‑up call"

For more examples, see docs/Examples.md.

Interval Semantics

Intervals in this library are half‑open, written as ([\text{Start},;\text{End})). A half‑open interval includes the start but excludes the end. Empty intervals where Start == End are permitted and represent no coverage; invalid intervals where End < Start throw. This convention represents empty ranges naturally, avoids off‑by‑one errors and composes cleanly because adjacent intervals share a boundary without overlapping.

When querying a point p, a value is returned when Start <= p and p < End. When querying an overlap, two intervals a and b overlap when a.Start < b.End and b.Start < a.End.

Complexity Overview

IntervalTree.Net uses an augmented self‑balancing binary search tree internally. Nodes are ordered by their interval’s start and store the maximum end value of all intervals in their subtree. This extra annotation allows the tree to prune branches when searching for overlaps. Query operations run in (O(\log n + m)) time, where m is the number of reported intervals. Insertions and deletions both take (O(\log n)) time because the tree remains balanced. Memory usage is linear in the number of stored interval–value pairs.

Thread Safety

This library is not thread‑safe. Concurrent modifications or queries from multiple threads can corrupt the internal tree. If you need to access an interval tree from multiple threads, wrap access in appropriate synchronization primitives such as locks.

Further Documentation

• docs/Design.md – Detailed design rationale, data structure choices, node layout and complexity analysis.
• docs/API.md – Full reference documentation for all public types and methods.
• docs/Examples.md – End‑to‑end examples illustrating typical use cases.
• docs/Status.md – Status tracking for planning, implementation and readiness.
• docs/NuGetReadiness.md – Current NuGet-readiness status and remaining release gates.
• docs/ReleaseCandidateReview.md – Final local release-candidate validation and package inspection evidence.
• docs/PublicationRunbook.md – Guarded manual publication runbook for a later separately approved publish action.
• CONTRIBUTING.md – Contribution guidelines and local development instructions.

Current Repository Status

This repository is public on GitHub and remains in local package-candidate development. It is not currently published on NuGet, and NuGet publication is not approved or completed.

The repository default branch is master. Use pull requests for reviewable changes and keep documentation, examples and tests aligned with the implementation.