An implementation of Allen's Interval Algebra, for .Net
This document uses the common interval notation. The examples here all use the Integer
type, but this library is designed to support anything that implements IEquatable
and IComparable
.
Set | Notation |
---|---|
Setting up open/closed boundaries and their respective intervals:
open Interval.Core
open Interval.Functions
// (1,5)
let x1 = { Value = 1; Kind = Excluded }
let y1 = { Value = 5; Kind = Excluded }
let b1 = { Start = x1; End = y1 }
// [3,7]
let x2 = { Value = 3; Kind = Included }
let y2 = { Value = 7; Kind = Included }
let b2 = { Start = x2; End = y2 }
// [6,8)
let x3 = { Value = 6; Kind = Excluded }
let y3 = { Value = 8; Kind = Included }
let b3 = { Start = x3; End = y3 }
// (6,10]
let x4 = { Value = 6; Kind = Excluded }
let y4 = { Value = 10; Kind = Included }
let b4 = { Start = x4; End = y4 }
// [11,12]
let x5 = { Value = 11; Kind = Included }
let y5 = { Value = 12; Kind = Included }
let b5 = { Start = x5; End = y5 }
A Singleton
is a set with only one interval:
// { (1,5) }
let i1 = Singleton b1
// { [3,7] }
let i2 = Singleton b2
// { [6,8) }
let i3 = Singleton b3
// { (6,10] }
let i4 = Singleton b4
// { [11,12] }
let i5 = Singleton b5
// { (1,5) } ∩ { [3,7] }
intersection i1 i2
// Generates...
Singleton {
Start = { Value = 3; Kind = Included }
End = { Value = 5; Kind = Excluded }
}
// { [3,7] } ∩ { (6,8] }
intersection i2 i3
// Generates...
Singleton {
Start = { Value = 6; Kind = Excluded }
End = { Value = 7; Kind = Included }
}
an intersection between two intervals may also return an Empty
result.
// { [1,5] } ∩ { (6,8] }
intersection i1 i3
// Generates...
Empty
One can also take two singletons and compute their union:
// { (1,5) } ∪ { [3,7] }
union i1 i2
// Generates
Singleton {
Start = { Value = 1; Kind = Excluded }
End = { Value = 7; Kind = Included } }
}
or:
// { [3,7] } ∪ { (6,8] }
union i2 i3
// Generates
Singleton {
Start = { Value = 3; Kind = Included }
End = { Value = 8; Kind = Included }
}
The result of a disjoint union
is not a singleton:
// { (1,5) } ∪ { (6,8] }
union i1 i3
// Generates
Union (
set [ { Start = { Value = 1; Kind = Excluded }
End = { Value = 5; Kind = Excluded } }
{ Start = { Value = 6; Kind = Excluded }
End = { Value = 8; Kind = Included } } ]
)
// { (1,5) } Overlaps { [3,7] }
relate i1 i2
// { [3,7] } Overlaps { (6,8] }
relate i2 i3
// { [1,5] } Before { (6,8] }
relate i1 i3
// { (6,8] } Starts { (6,10] }
relate i3 i4
// { [11,12] } After { (6,10] }
relate i5 i4
// Merging (1,5) [3,7] [6,8) (6,10] [11,12]
let boundaries = [ b1; b2; b3; b4; b5 ]
merge(boundaries)
// Outputs
Union (
set [{ Start = { Value = 1; Kind = Excluded }
End = { Value = 10; Kind = Included } }
{ Start = { Value = 11; Kind = Included }
End = { Value = 12; Kind = Included } }]
)
The whole reason for the existence of this package was to solve a particular issue at work, it's alpha quality at best, but usable.
- Setup a Nix devenv
- Build the .Net package with Nix
- Remove every silly
TODO
from the codebase, they smell - Add property based-testing