Disjoint Interval Set (DIS)

A modern C++ header-only library implementing Disjoint Interval Sets as a complete Boolean algebra, featuring an elegant API, compile-time interval arithmetic, multi-dimensional support, and mathematical notation parsing.

Why DIS?

Working with intervals is fundamental in many domains—from computational geometry to scheduling algorithms. While libraries like Boost.ICL provide interval containers, DIS takes a different approach by treating interval sets as first-class mathematical objects that form a complete Boolean algebra. This leads to:

Mathematical Elegance: Operations follow Boolean algebra axioms rigorously
Intuitive API: Express complex set operations naturally with operators
Zero-Cost Abstractions: Compile-time interval validation with no runtime overhead
Composability: Features combine seamlessly without surprises
Production Ready: 97.46% test coverage on core implementation

Quick Start

#include <dis/dis.hpp>
using namespace dis;

// Create intervals with expressive factory methods
auto morning = real_interval::closed(9, 12);    // [9, 12]
auto afternoon = real_interval::closed(14, 18); // [14, 18]

// Build sets using fluent interface
auto work_hours = real_set{}
    .add(morning)
    .add(afternoon);

// Parse from mathematical notation
auto meetings = real_set::from_string("[10,11] ∪ [15,16]");

// Boolean operations with natural syntax
auto free_time = work_hours - meetings;         // Set difference
auto conflicts = work_hours & meetings;         // Intersection
bool has_conflicts = !conflicts.is_empty();

// Rich query interface
std::cout << "Free time: " << free_time << '\n';
std::cout << "Total free hours: " << free_time.measure() << '\n';

Features

🎯 Elegant, Fluent API

Express complex interval operations naturally with an API that reads like mathematical notation.

📐 Complete Boolean Algebra

Full support for union, intersection, complement, difference, and symmetric difference with proper algebraic properties.

🔤 Mathematical Notation Parser

Parse interval sets from strings using standard mathematical notation: "[0,5) ∪ (10,20] ∪ {25}".

⚡ Compile-Time Interval Arithmetic

Zero-overhead interval bounds checking at compile-time using template metaprogramming.

📦 Multi-Dimensional Support

Seamlessly extend to N-dimensional hyperrectangles for spatial and spatio-temporal problems.

🔍 Rich Query Interface

Comprehensive set of predicates and queries: gaps, span, density, measure, overlaps, and more.

🚀 Production Ready

Extensively tested with 90.32% overall coverage and 97.46% coverage on core implementation.

Installation

DIS is a header-only library. Simply clone and include:

git clone https://github.com/yourusername/disjoint_interval_set.git

// Option 1: Include everything
#include <dis/dis.hpp>

// Option 2: Include only what you need
#include <dis/core/interval.hpp>
#include <dis/core/disjoint_interval_set.hpp>

Requirements

C++17 or later (uses std::optional, structured bindings)
No external dependencies
Tested on GCC 9+, Clang 10+, MSVC 2019+

Usage Examples

Basic Intervals

#include <dis/dis.hpp>
using namespace dis;

// Multiple factory methods for clarity
auto closed = real_interval::closed(0, 10);         // [0, 10]
auto open = real_interval::open(0, 10);            // (0, 10)
auto left_open = real_interval::left_open(0, 10);  // (0, 10]
auto right_open = real_interval::right_open(0, 10); // [0, 10)
auto point = real_interval::point(5);              // {5}
auto empty = real_interval::empty();               // ∅

// Unbounded intervals
auto positive = real_interval::greater_than(0);    // (0, ∞)
auto non_negative = real_interval::at_least(0);    // [0, ∞)

// Interval operations
auto i1 = real_interval::closed(0, 10);
auto i2 = real_interval::closed(5, 15);

auto intersection = i1 & i2;  // [5, 10]
auto hull = i1.hull(i2);      // [0, 15]

// Queries
assert(i1.contains(5));
assert(i1.overlaps(i2));
assert(i1.length() == 10);
assert(i1.midpoint() == 5);

Disjoint Interval Sets

// Build sets with fluent interface
auto set = real_set{}
    .add(0, 10)      // Add [0, 10]
    .add(20, 30)     // Add [20, 30]
    .add(25, 35);    // Automatically merged to [20, 35]

// From initializer list
real_set ranges = {
    real_interval::closed(0, 5),
    real_interval::closed(10, 15),
    real_interval::closed(12, 20)  // Overlaps merged automatically
};

// Set operations with multiple notations
auto a = real_set::from_string("[0,10] ∪ [20,30]");
auto b = real_set::from_string("[5,15] ∪ [25,35]");

auto union_set = a | b;          // [0, 15] ∪ [20, 35]
auto intersection = a & b;       // [5, 10] ∪ [25, 30]
auto difference = a - b;         // [0, 5) ∪ (10, 20) ∪ (30, 35]
auto symmetric = a ^ b;          // [0, 5) ∪ (10, 15] ∪ [20, 25) ∪ (30, 35]

// Advanced queries
auto gaps = set.gaps();          // Intervals between components
auto span = set.span();          // Smallest interval containing all
auto density = set.density();    // measure / span.length
auto measure = set.measure();    // Total length covered

// Functional operations
set.for_each([](const auto& interval) {
    std::cout << interval << '\n';
});

auto filtered = set.filter([](const auto& i) {
    return i.length() > 5;
});

String DSL

// Parse from mathematical notation
auto set = real_set::from_string("[0,5) ∪ (10,20] ∪ {25} ∪ [30,∞)");

// Alternative notation support
auto set2 = real_set::from_string("[0,5) U (10,20] U {25}");  // 'U' for union
auto set3 = real_set::from_string("[0,5), (10,20], {25}");    // Comma separated

// Round-trip formatting
std::string notation = set.to_string();
assert(real_set::from_string(notation) == set);

// Custom formatting
std::cout << set.to_string(format_options::unicode) << '\n';    // Uses ∪, ∩, ∅
std::cout << set.to_string(format_options::ascii) << '\n';      // Uses U, ^, {}

Compile-Time Intervals

#include <dis/static_interval.hpp>

// Define compile-time intervals
template<int Min, int Max>
using valid_range = dis::static_interval<int, Min, Max, false, false>;

// Compile-time validation
using age_range = valid_range<0, 150>;
using percentage_range = valid_range<0, 100>;

static_assert(age_range::contains(25), "25 is a valid age");
static_assert(!age_range::contains(200), "200 is not a valid age");

// Build bounded types with zero runtime overhead
template<int Min, int Max>
class bounded {
    using bounds = valid_range<Min, Max>;
    int value_;
public:
    constexpr bounded(int v) : value_(v) {
        if (!bounds::contains(v))
            throw std::out_of_range("Value out of bounds");
    }
    constexpr operator int() const { return value_; }
};

using age = bounded<0, 150>;
using percentage = bounded<0, 100>;
using score = bounded<0, 1000>;

// Compile-time interval operations
using work_hours = valid_range<9, 17>;
using lunch_hours = valid_range<12, 13>;
using morning_work = dis::static_intersection<work_hours, valid_range<0, 12>>;

static_assert(morning_work::min == 9);
static_assert(morning_work::max == 12);

Multi-Dimensional Intervals

#include <dis/interval_nd.hpp>

// 2D rectangles
auto screen = dis::rectangle<int>::closed(0, 1920, 0, 1080);
auto window = dis::rectangle<int>::closed(100, 500, 100, 400);

assert(screen.contains(window));
assert(window.area() == 120000);

// 3D boxes
auto room = dis::box<double>::closed(0, 10, 0, 10, 0, 3);  // 10x10x3 meter room
auto furniture = dis::box<double>::closed(2, 4, 3, 5, 0, 1);

bool fits = room.contains(furniture);
double volume = furniture.volume();  // 4 cubic meters

// N-dimensional hyperrectangles
using vec4 = std::array<double, 4>;
dis::interval_nd<double, 4> hypercube(vec4{0, 0, 0, 0}, vec4{1, 1, 1, 1});

// Disjoint sets in multiple dimensions
dis::disjoint_interval_set<dis::rectangle<double>> floor_plan;
floor_plan.insert(dis::rectangle<double>::closed(0, 5, 0, 5));    // Room 1
floor_plan.insert(dis::rectangle<double>::closed(5, 10, 0, 5));   // Room 2
floor_plan.insert(dis::rectangle<double>::closed(0, 10, 5, 10));  // Room 3

// Spatial queries
bool occupied = floor_plan.contains(dis::point2d{3, 3});
auto free_space = ~floor_plan;  // Complement in 2D space

API Reference

Core Classes

`interval<T>`

Represents a single interval with configurable boundaries.

Key Methods:

contains(T value) - Test membership
overlaps(interval other) - Test overlap
length() - Get interval length
is_empty() - Test if interval is empty
hull(interval other) - Compute convex hull

`disjoint_interval_set<IntervalType>`

Maintains a set of non-overlapping intervals with Boolean algebra operations.

Key Methods:

insert(interval) - Add interval (merges if needed)
erase(interval) - Remove interval
contains(value) - Test value membership
operator|, operator&, operator~, operator-, operator^ - Set operations
measure() - Total length covered
gaps() - Get intervals between components
span() - Smallest containing interval

Factory Functions

// Interval creation helpers
auto i = real_interval::closed(a, b);      // [a, b]
auto i = real_interval::open(a, b);        // (a, b)
auto i = real_interval::left_open(a, b);   // (a, b]
auto i = real_interval::right_open(a, b);  // [a, b)
auto i = real_interval::point(x);          // {x}
auto i = real_interval::empty();           // ∅
auto i = real_interval::unbounded();       // (-∞, ∞)
auto i = real_interval::greater_than(x);   // (x, ∞)
auto i = real_interval::at_least(x);       // [x, ∞)
auto i = real_interval::less_than(x);      // (-∞, x)
auto i = real_interval::at_most(x);        // (-∞, x]

Type Aliases

namespace dis {
    // Common interval types
    using real_interval = interval<double>;
    using integer_interval = interval<int>;

    // Common set types
    using real_set = disjoint_interval_set<real_interval>;
    using integer_set = disjoint_interval_set<integer_interval>;

    // Multi-dimensional types
    template<typename T>
    using rectangle = interval_nd<T, 2>;

    template<typename T>
    using box = interval_nd<T, 3>;
}

Mathematical Foundation

Boolean Algebra

The Disjoint Interval Set forms a complete Boolean algebra where:

Elements: Sets of disjoint intervals
Join (∨): Union operation (operator|)
Meet (∧): Intersection operation (operator&)
Complement (¬): Complement operation (operator~)
Bottom (⊥): Empty set
Top (⊤): Universal set

Axioms Satisfied

Associativity: (A ∪ B) ∪ C = A ∪ (B ∪ C) and (A ∩ B) ∩ C = A ∩ (B ∩ C)
Commutativity: A ∪ B = B ∪ A and A ∩ B = B ∩ A
Distributivity: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
Identity: A ∪ ∅ = A and A ∩ U = A
Complement: A ∪ ~A = U and A ∩ ~A = ∅
Idempotence: A ∪ A = A and A ∩ A = A
Absorption: A ∪ (A ∩ B) = A and A ∩ (A ∪ B) = A
De Morgan's Laws: ~(A ∪ B) = ~A ∩ ~B and ~(A ∩ B) = ~A ∪ ~B

Why Disjoint?

Maintaining disjoint (non-overlapping) intervals provides:

Canonical Form: Unique representation for each set
Efficient Operations: O(n + m) for most set operations
Space Efficiency: No redundant interval storage
Clear Semantics: Each point belongs to at most one interval

Performance

Complexity Analysis

Operation	Complexity	Notes
`insert(interval)`	O(n)	n = number of intervals
`contains(value)`	O(log n)	Binary search
`union (A ∪ B)`	O(n + m)	Linear merge
`intersection (A ∩ B)`	O(n + m)	Linear scan
`complement (~A)`	O(n)	Invert boundaries
`measure()`	O(n)	Sum all lengths
`parse(string)`	O(s)	s = string length

Memory Usage

Each interval: 2 × sizeof(T) + 2 bits for boundaries
Set overhead: std::vector overhead + bookkeeping
No memory allocation for compile-time intervals

Optimization Techniques

Move Semantics: Full support for efficient transfers
Small Vector Optimization: For sets with few intervals
Lazy Evaluation: Operations can be composed without materialization
Compile-Time Computation: Zero runtime cost for static intervals

Comparison with Alternatives

vs Boost.ICL (Interval Container Library)

Feature	DIS	Boost.ICL
Philosophy	Mathematical Boolean algebra	Container-centric
API Style	Natural operators (`\|`, `&`, `~`)	Method calls
String Parsing	Built-in DSL	Not available
Compile-Time	Full support	Limited
Multi-Dimensional	Native support	Requires extension
Dependencies	None	Boost
Header-Only	Yes	Yes
Learning Curve	Intuitive	Steeper

vs std::set<std::pair<T,T>>

Feature	DIS	std::set
Interval Merging	Automatic	Manual
Set Operations	O(n + m)	O(n × m) worst case
Mathematical Operations	Native	Must implement
Memory Usage	Optimized	Higher overhead
Type Safety	Interval types	Raw pairs

vs Manual Implementation

DIS provides:

Correctness: Extensively tested edge cases
Completeness: Full Boolean algebra implementation
Performance: Optimized algorithms
Maintainability: Clean, documented API
Reusability: Generic, composable design

Building and Testing

Running Tests

# Clone the repository
git clone https://github.com/yourusername/disjoint_interval_set.git
cd disjoint_interval_set

# Build and run tests
mkdir build && cd build
cmake ..
make
ctest --verbose

Test Coverage

Current test coverage:

Overall: 90.32% (94 test cases)
Core implementation: 97.46%
Parser/Formatter: 88.91%
Multi-dimensional: 85.23%

Running Examples

# Compile and run examples
g++ -std=c++17 -I./include examples/elegant_api_demo.cpp -o demo
./demo

Contributing

We welcome contributions! Please see our Contributing Guidelines for details.

Development Setup

Fork the repository
Create your feature branch (git checkout -b feature/amazing-feature)
Write tests for your changes
Ensure all tests pass
Update documentation as needed
Commit your changes (git commit -m 'Add amazing feature')
Push to the branch (git push origin feature/amazing-feature)
Open a Pull Request

Code Style

Follow modern C++ best practices
Use descriptive names
Document public APIs
Write comprehensive tests
Keep commits atomic and well-described

Testing Guidelines

Write tests for all new features
Ensure edge cases are covered
Maintain or improve coverage metrics
Test compile-time features with static_assert

Applications

Real-World Use Cases

Computational Geometry: Polygon clipping, CSG operations
Scheduling Systems: Resource allocation, conflict detection
Numerical Analysis: Interval arithmetic, error bounds
Access Control: Time-based permissions, IP range filtering
Data Visualization: Histogram binning, range queries
Signal Processing: Frequency band allocation
Game Development: Collision detection, spatial indexing

Roadmap

C++20 concepts for better error messages
Parallel algorithms for large sets
Persistent data structures
Interval tree indexing for very large sets
Python bindings
Formal verification of algebraic properties
Integration with computational geometry libraries

License

This project is licensed under the MIT License - see the LICENSE file for details.

Acknowledgments

Inspired by mathematical interval theory and Boolean algebra
Thanks to the C++ community for feedback and suggestions
Special thanks to contributors and early adopters

Citation

If you use this library in academic work, please cite:

@software{dis2024,
  title = {Disjoint Interval Set: A Boolean Algebra for C++},
  author = {Your Name},
  year = {2024},
  url = {https://github.com/yourusername/disjoint_interval_set}
}

Elegant interval arithmetic for modern C++

Name		Name	Last commit message	Last commit date
Latest commit History 3 Commits
.vscode		.vscode
examples		examples
include		include
tests		tests
CLAUDE.md		CLAUDE.md
CMakeLists.txt		CMakeLists.txt
ELEGANT_API.md		ELEGANT_API.md
README.md		README.md
TEST_COVERAGE_REPORT.md		TEST_COVERAGE_REPORT.md

queelius/disjoint_interval_set

Folders and files

Latest commit

History

Repository files navigation