IntervalTree.Net is a small prerelease .NET 8 interval tree library for storing half-open intervals and querying by point or overlap. It exposes a focused API, has no runtime package dependencies, includes xUnit coverage with edge-case and deterministic randomized checks, and is published on NuGet as 0.1.0-alpha.1 with SourceLink, symbols, package inspection, CI validation, and Trusted Publishing via GitHub Actions OIDC.
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.
Install the current prerelease from NuGet.org:
dotnet add package IntervalTree.Net --version 0.1.0-alpha.1This is a prerelease package. It does not imply a stable 1.0.0 API, production readiness, broad adoption, benchmarked high-performance behavior, or thread safety.
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.shThe library targets net8.0 and uses modern C# features. The package includes README and XML documentation metadata, SourceLink metadata for GitHub, and a .snupkg symbol package.
To inspect or consume a locally packed artifact, 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-localHere’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.
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.
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.
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.
- 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 prerelease publication status and remaining release boundaries.
- docs/ReleaseCandidateReview.md – Historical local release-candidate validation and package inspection evidence.
- docs/PublicationRunbook.md – Trusted Publishing workflow record and future publication boundaries.
- CONTRIBUTING.md – Contribution guidelines and local development instructions.
This repository is public on GitHub. IntervalTree.Net 0.1.0-alpha.1 is published on NuGet as a prerelease package through GitHub Actions Trusted Publishing with OIDC, and post-publication verification confirmed NuGet flat-container/package availability plus external net8.0 consumer install validation.
No GitHub release or git tag exists for this package, no additional NuGet version is approved, and no stable or production-ready claim is implied. Future package versions, releases, tags, API-key paths, or broader release automation require separate approval.
The repository default branch is master. Use pull requests for reviewable changes and keep documentation, examples and tests aligned with the implementation.