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. Most interval libraries give you containers. This one gives you the algebra.

The Problem

Intervals show up everywhere: scheduling, computational geometry, range queries, memory management. But most C++ libraries treat them as fancy containers. You get insert, remove, maybe a merge. You don’t get complement. You don’t get De Morgan’s laws.

I wanted a library where interval sets are actual mathematical objects. You write a & b and get an intersection. You write ~a and get a complement over the full real line. The operators aren’t sugar; they satisfy the axioms.

#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

These aren’t just convenient operators. They satisfy the actual 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 properties. If you break an axiom, you’ll hear about it.

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

v1.1.0 brings full STL container conformance. Iterators, range-based for, standard algorithms, all of it:

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 it:

#include <dis/disjoint_interval_set.hpp>

Or with CMake:

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

Resources

Related Posts

Discussion