Skip to main content

libdis: Disjoint Interval Sets as a Complete Boolean Algebra

3 min read Updated:
C++ data-structures intervals boolean-algebra header-only STL

libdis is a C++17/20/23 header-only library that treats interval sets as first-class mathematical objects forming a complete Boolean algebra. Unlike libraries that merely provide interval containers, libdis gives you the full power of set-theoretic operations with mathematical rigor.

Why Disjoint Interval Sets?

Working with intervals is fundamental in many domains—scheduling, computational geometry, range queries. But most implementations treat intervals as data containers rather than mathematical objects.

libdis takes a different approach:

#include <dis/disjoint_interval_set.hpp>

using dis = dis::disjoint_interval_set<int>;

dis a = dis::closed(1, 5) | dis::closed(10, 15);  // [1,5] ∪ [10,15]
dis b = dis::closed(3, 12);                        // [3,12]

auto intersection = a & b;   // [3,5] ∪ [10,12]
auto union_set = a | b;      // [1,15]
auto difference = a - b;     // [1,3) ∪ (12,15]
auto complement = ~a;        // (-∞,1) ∪ (5,10) ∪ (15,+∞)

Boolean Algebra Axioms

libdis rigorously implements Boolean algebra. These aren’t just convenient operators—they satisfy mathematical laws:

Associativity: (a | b) | c == a | (b | c)

Commutativity: a & b == b & a

Distributivity: a & (b | c) == (a & b) | (a & c)

Identity: a | ∅ == a, a & U == a

Complement: a | ~a == U, a & ~a == ∅

De Morgan’s Laws: ~(a & b) == ~a | ~b

All 94 test cases verify these algebraic properties.

Key Features

  • 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
  • STL Compatibility: Full alignment with C++ Standard Library conventions
  • Production Ready: 97.46% test coverage on core implementation

Interval Types

Create intervals with different boundary conditions:

auto closed = dis::closed(1, 5);      // [1, 5]
auto open = dis::open(1, 5);          // (1, 5)
auto left_open = dis::left_open(1, 5);   // (1, 5]
auto right_open = dis::right_open(1, 5); // [1, 5)

// Unbounded intervals
auto from = dis::from(5);             // [5, +∞)
auto until = dis::until(5);           // (-∞, 5]
auto everything = dis::all();         // (-∞, +∞)
auto nothing = dis::empty();          // ∅

Set Operations

dis a = dis::closed(0, 10);
dis b = dis::closed(5, 15);

// Union
auto u = a | b;  // [0, 15]

// Intersection
auto i = a & b;  // [5, 10]

// Difference
auto d = a - b;  // [0, 5)

// Symmetric difference
auto s = a ^ b;  // [0, 5) ∪ (10, 15]

// Complement
auto c = ~a;     // (-∞, 0) ∪ (10, +∞)

Querying

dis intervals = dis::closed(1, 5) | dis::closed(10, 15);

// Point containment
intervals.contains(3);   // true
intervals.contains(7);   // false

// Interval containment
intervals.contains(dis::closed(2, 4));   // true
intervals.contains(dis::closed(2, 12));  // false

// Overlap detection
intervals.overlaps(dis::closed(4, 11));  // true

// Iteration
for (const auto& interval : intervals) {
    std::cout << interval << std::endl;
}

STL Conformance

libdis v1.1.0 brings full STL container conformance:

dis intervals = dis::closed(1, 5) | dis::closed(10, 15);

// STL-style access
intervals.size();     // Number of disjoint intervals
intervals.empty();    // Check if empty
intervals.begin();    // Iterator to first interval
intervals.end();      // Past-the-end iterator

// Range-based for
for (const auto& iv : intervals) {
    process(iv);
}

// Algorithms
std::find_if(intervals.begin(), intervals.end(),
    [](const auto& iv) { return iv.length() > 3; });

Use Cases

  • Scheduling: Find available time slots, detect conflicts
  • Memory Management: Track allocated/free regions
  • Database Queries: Range predicates, temporal queries
  • Network ACLs: IP range matching, port ranges
  • Computational Geometry: 1D intersection problems

Installation

Header-only—just include:

#include <dis/disjoint_interval_set.hpp>

Or with CMake:

add_subdirectory(libdis)
target_link_libraries(your_target PRIVATE dis::dis)

Resources

libdis: When intervals become first-class mathematical citizens, set operations become trivial.

Related Posts

Discussion