Related Work¶

This section positions the DIS library within the broader context of interval arithmetic, set theory, and C++ library design.

Interval Arithmetic Libraries¶

Boost.ICL (Interval Container Library)¶

Overview: Part of the Boost C++ Libraries, ICL provides interval containers with various aggregation policies.

Key Features:

• Interval sets and maps
• Multiple interval types (discrete, continuous)
• Aggregation on overlap (combine, intersect, etc.)
• Generic interval container implementation

Comparison with DIS:

When to Use ICL:

• Already using Boost ecosystem
• Need interval maps (key-value with interval keys)
• Require specific aggregation policies
• Working with date/time intervals (via Boost.DateTime)

When to Use DIS:

• Want zero dependencies
• Prefer mathematical notation
• Need compile-time intervals
• Want simpler API
• Need multi-dimensional support

Code Comparison:

// Boost.ICL
#include <boost/icl/interval_set.hpp>
boost::icl::interval_set<int> s;
s.add(boost::icl::interval<int>::closed(0, 10));
s.add(boost::icl::interval<int>::closed(20, 30));
auto result = s + other_set;  // Union via operator+

// DIS
#include <dis/dis.hpp>
auto s = integer_set{}
    .add(0, 10)
    .add(20, 30);
auto result = s | other_set;  // Union via operator|

MPFI (Multiple Precision Floating-Point Interval)¶

Overview: High-precision interval arithmetic library built on MPFR.

Key Features:

• Arbitrary precision floating-point
• Rigorous rounding guarantees
• Mathematical functions (sin, cos, exp, etc.)
• Formal error bounds

Comparison with DIS:

DIS focuses on set operations rather than numerical computation. MPFI is designed for rigorous numerical analysis where precision is paramount. DIS is designed for interval set manipulation where the Boolean algebra structure is central.

Use MPFI when: Numerical computation requires arbitrary precision with rigorous bounds.

Use DIS when: Manipulating sets of intervals is the primary operation.

Potential Integration: DIS could be instantiated with MPFI intervals:

#include <mpfi.h>
#include <dis/dis.hpp>

template<>
struct interval_traits<mpfi_t> {
    // Adapt MPFI to DIS interface
};

using precise_interval_set = disjoint_interval_set<interval<mpfi_wrapper>>;

Related C++ Libraries¶

std::set and Interval Representations¶

Common Pattern: Represent intervals as pairs in std::set:

std::set<std::pair<double, double>> intervals;
intervals.insert({0, 10});
intervals.insert({20, 30});

Limitations:

1. No automatic merging: Overlapping intervals remain separate
2. Manual operations: Must implement union, intersection manually
3. No boundary types: Can't distinguish \([a,b)\) from \((a,b]\)
4. Higher overhead: Red-black tree vs. sorted vector
5. No mathematical guarantees: Easy to create invalid states

DIS Advantages:

• Automatic normalization
• Rich set operations built-in
• Explicit boundary types
• Mathematical correctness guarantees
• Better performance (2-4× faster)

Ranges (C++20)¶

Overview: C++20 ranges provide composable lazy views over sequences.

Relationship to DIS: Ranges and DIS are complementary:

// Use ranges to process intervals in a set
auto large_intervals = my_set
    | std::views::filter([](const auto& i) { return i.length() > 10; })
    | std::views::transform([](const auto& i) { return i.midpoint(); });

DIS intervals are range-compatible:

for (const auto& interval : my_set) {
    // Process each interval
}

Theoretical Foundations¶

Boolean Algebra Theory¶

Classic References:

• Huntington (1904): Axiomatization of Boolean algebra
• Stone (1936): Stone representation theorem
• Halmos (1963): Lectures on Boolean Algebras

DIS Contribution: Practical implementation of Boolean algebra for intervals with:

• Constructive algorithms for all operations
• Efficient canonical form (disjoint, sorted)
• C++ type system encoding algebraic properties

Interval Arithmetic¶

Classic References:

• Moore (1966): Interval Analysis - Foundational work
• Hickey et al. (2001): "Interval arithmetic: From principles to implementation"
• Jaulin et al. (2001): Applied Interval Analysis

DIS Contribution: Extends from single intervals to sets of intervals with:

• Full Boolean algebra operations
• Set-theoretic semantics
• Practical applications beyond numerical analysis

Domain Theory and Denotational Semantics¶

References:

• Scott (1970): Continuous lattices and domain theory
• Abramsky & Jung (1994): Domain theory

Connection: Intervals form a domain with:

• Partial order: subset relation
• Least upper bound: union
• Greatest lower bound: intersection
• Bottom element: empty set

DIS implements this domain constructively in C++.

Design Pattern Literature¶

API Design¶

Influences on DIS API:

1. Stepanov & McJones (2009): Elements of Programming
2. Generic programming principles

3. Regular types and algebraic structures

4. Alexandrescu (2001): Modern C++ Design

5. Policy-based design

6. Template metaprogramming

7. Sutter & Alexandrescu (2004): C++ Coding Standards

8. Make interfaces easy to use correctly and hard to use incorrectly

9. Stroustrup (2013): The C++ Programming Language

10. Resource acquisition is initialization (RAII)
11. Zero-overhead abstractions

DIS Applications:

• Named constructors (factory pattern)
• Fluent interface (builder pattern)
• Operator overloading (domain-specific notation)
• Value semantics (functional programming)

Unix Philosophy¶

Principles Applied:

1. Do one thing well: Intervals and interval sets, nothing more
2. Expect the output to become the input: Composable operations
3. Make it easy to modify: Clean abstractions, clear invariants
4. Write programs to work together: Header-only, zero dependencies

// Composability example
auto result = real_set::from_string("[0,10]")
    .unite(real_set::from_string("[20,30]"))
    .intersect(real_set::from_string("[5,25]"))
    .complement();

Related Academic Work¶

Constraint Programming¶

References:

• Van Hentenryck (1989): Constraint satisfaction problems
• Benhamou & Older (1997): Interval constraints

Connection: Intervals represent constraint domains. DIS operations implement:

• Domain reduction: Intersection with constraints
• Constraint propagation: Set operations across variables

Temporal Logic and Model Checking¶

References:

• Alur & Dill (1994): Timed automata
• Henzinger et al. (1994): Symbolic model checking

Connection: Intervals represent time periods. DIS provides:

• Temporal operations: Before, after, during
• State space representation: Sets of time intervals
• Reachability: Computed via set operations

Spatial Databases¶

References:

• Guttman (1984): R-trees for spatial indexing
• Beckmann et al. (1990): R*-tree variant

Connection: Multi-dimensional intervals (hyperrectangles) represent:

• Bounding boxes: Spatial extent of objects
• Range queries: Find objects in region
• Spatial joins: Intersecting regions

DIS provides the algebraic operations while R-trees provide the indexing structure.

Programming Language Features¶

DSL Embedding in C++¶

Techniques Used in DIS:

1. Operator Overloading: |, &, ~ for set operations
2. Named Constructors: closed(), open() factory methods
3. Fluent Interface: Chainable methods returning *this or new object
4. String Parsing: External DSL via from_string()
5. Template Metaprogramming: Compile-time intervals

Comparison with Other Approaches:

C++20/23 Features¶

Current Usage (C++17):

• std::optional for nullable bounds
• constexpr for compile-time evaluation
• Structured bindings

Future Opportunities (C++20/23):

• Concepts: Better error messages

  template<Boundary T>
  concept IntervalBoundary = std::totally_ordered<T> && std::regular<T>;
  

• Ranges: Lazy views over intervals

  auto large = my_set | std::views::filter(has_length_greater_than(10));
  

• Modules: Faster compilation

  import dis;
  

Open Source Ecosystem¶

Similar Projects¶

Interval Libraries:

• libieeep1788 (C++): IEEE 1788 standard implementation
• JInterval (Java): Similar goals, limited by language
• intervaltree (Python): Interval tree data structure
• portion (Python): Interval set operations

C++ Mathematical Libraries:

• Eigen: Linear algebra
• Armadillo: Matrix operations
• CGAL: Computational geometry
• GMP/MPFR: Arbitrary precision arithmetic

DIS Position: Focused on interval set operations with emphasis on API elegance and mathematical correctness.

Summary¶

DIS builds on rich theoretical foundations while differentiating itself through:

1. Mathematical First: Boolean algebra as central abstraction
2. Zero Dependencies: No external requirements
3. Elegant API: Multiple expression styles
4. Modern C++: Leveraging language features for safety and performance
5. Practical Focus: Real-world applications over pure theory

The library synthesizes ideas from:

• Interval arithmetic (Moore, Hickey)
• Boolean algebra (Huntington, Stone)
• Generic programming (Stepanov)
• API design (Stroustrup, Alexandrescu)
• Unix philosophy (Thompson, Kernighan)

The result: a library that is mathematically rigorous, ergonomically pleasant, and practically useful.