Disjoint Interval Set (DIS)¶

A Boolean Algebra for C++
Modern, elegant, and mathematically rigorous interval set library

Overview¶

Disjoint Interval Set (DIS) is a modern C++ header-only library implementing interval sets as a complete Boolean algebra. Unlike traditional interval libraries that focus on container semantics, DIS treats interval sets as first-class mathematical objects with intuitive operations and strong correctness guarantees.

#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

Why DIS?¶

Working with intervals is fundamental in many domains—from computational geometry to scheduling algorithms. DIS provides:

Mathematical Elegance¶

Operations follow Boolean algebra axioms rigorously, providing strong correctness guarantees and intuitive semantics.

Intuitive API¶

Express complex set operations naturally with multiple equivalent notations:

• Operators: (a | b) & ~c for concise symbolic notation
• Methods: a.unite(b).intersect(c.complement()) for clarity
• Fluent: real_set{}.add(0,10).add(20,30) for chaining

Zero-Cost Abstractions¶

Compile-time interval validation with no runtime overhead. Everything is constexpr where possible.

Composability¶

Features combine seamlessly without surprises. All operations maintain the disjoint invariant automatically.

Production Ready¶

97.46% test coverage on core implementation, extensively tested with 94 test cases across edge cases and real-world scenarios.

Key Features¶

🎯 Complete Boolean Algebra¶

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

📐 Elegant, Fluent API¶

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

🔤 Mathematical Notation Parser¶

Parse interval sets from strings using standard 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 predicates and queries: gaps(), span(), density(), measure(), and more.

🚀 Performance¶

• O(log n) membership queries via binary search
• O(n + m) set operations via linear merge
• Automatic normalization maintains canonical form

Quick Example¶

#include <dis/dis.hpp>
#include <iostream>

using namespace dis;

int main() {
    // Define available time slots
    auto availability = real_set{}
        .add(9, 12)   // Morning: 9 AM - 12 PM
        .add(14, 17); // Afternoon: 2 PM - 5 PM

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

    // Calculate free time using set difference
    auto free_time = availability - meetings;

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

    // Calculate utilization
    double utilization = meetings.measure() / availability.measure();
    std::cout << "Utilization: " << (utilization * 100) << "%\n";

    return 0;
}

Output:

Free time: [9,10) ∪ (11,12] ∪ [14,15) ∪ (16,17]
Total free hours: 4
Utilization: 33.33%

Design Principles¶

DIS follows Unix philosophy and modern C++ best practices:

1. Simplicity: Every component does one thing exceptionally well
2. Composability: Operations naturally compose together
3. Mathematical Rigor: Models true mathematical concepts accurately
4. Zero-Cost Abstractions: Template-based design with compile-time optimization
5. Multiple Expression Styles: Support both mathematical and programming idioms

Installation¶

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

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

#include <dis/dis.hpp>

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

Applications¶

DIS excels in domains requiring interval manipulation:

• 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

Next Steps¶

License¶

MIT License - See LICENSE for details.

Citation¶

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

@software{dis2025,
  title = {Disjoint Interval Set: A Boolean Algebra for C++},
  author = {Anonymous},
  year = {2025},
  url = {https://github.com/yourusername/disjoint_interval_set}
}