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(),
[](https://metafunctor.com/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)
