An Interval a is a pair \( (x, y) \text{ such that } x < y\). To create intervals use the parseInterval, beginerval, or enderval functions.

Class representing intervals that can be cast to and from the canonical representation Interval a.

When iv is also an instance of PointedIv, with Ord (Point iv), it should adhere to Allen's construction of the interval algebra for intervals represented by left and right endpoints. See sections 3 and 4 of Allen 1983.

Specifically, the requirements for interval relations imply

ivBegin i < ivEnd i

This module provides default implementations for methods of Iv in that case.

Note iv should not be an instance of Intervallic unless iv ~ Interval a, since Intervallic is a class for getting and setting intervals as Interval a in particular.

A Vector whose elements are provided in strict ascending order is an example of a type that could implement PointedIv without being equivalent to Interval, with ivBegin = head and ivEnd = last.

The SizedIv typeclass is a generic interface for constructing and manipulating intervals. The class imposes strong requirements on its methods, in large part to ensure the constructors ivExpandr and ivExpandl return "valid" intervals, particularly in the typical case where iv also implements the interval algebra.

In all cases, ivExpandr and ivExpandl should preserve the value of the point *not* shifted. That is,

ivBegin (ivExpandr d i) == ivBegin i
ivEnd (ivExpandl d i) == ivEnd i

In addition, using Interval as example, the following must hold:

When iv is Ord, for all i == Interval (b, e),

ivExpandr d i >= i
ivExpandl d i <= i

When Moment iv is Ord,

duration (ivExpandr d i) >= max moment (duration i)
duration (ivExpandl d i) >= max moment (duration i)

In particular, if the duration d by which to expand is less than moment, and duration i >= moment then these constructors should return the input.

ivExpandr d i == i
ivExpandl d i == i

When Moment iv also is Num, the default moment value is 1 and in all cases should be positive.

moment @iv > 0

When in addition Point iv ~ Moment iv, the class provides a default duration as duration i = ivEnd i - ivBegin i.

This module enforces Point (Interval a) = a. However, it need not be that a ~ Moment iv. For example Moment (Interval UTCTime) ~ NominalDiffTime.

SizedIv and the interval algebra

When iv is an instance of Iv, the methods of this class should ensure the validity of the resulting interval with respect to the interval algebra. For example, when Point iv is Ord, they must always produce a valid interval i such that ivBegin i < ivEnd i.

In addition, the requirements of SizedIv implementations in the common case where Moment iv is Num and Ord require the constructors to produce intervals with duration of at least moment.

In order to preserve the properties above, ivExpandr, ivExpandl will not want to assume validity of the input interval. In other words, ivExpandr d i need not be the identity when d < moment since it will need to ensure the result is a valid interval even if i is not.

These two methods can therefore be used as constructors for valid intervals.

The Intervallic typeclass defines how to get and set the Interval content of a data structure. Intervallic types can be compared via IntervalRelation s on their underlying Interval, and functions of this module define versions of the methods from Iv, PointedIv and SizedIv for instances of Intervallic by applying them to the contained interval.

Only the canonical representation Interval should define an instance of all four classes.

PairedInterval is the prototypical example of an Intervallic.

>>> getInterval (Interval (0, 10))
(0, 10)

>>> begin (Interval (0, 10))
0

>>> end (Interval (0, 10))
10

Access the endpoints of an i a .

Access the endpoints of an i a .

A type identifying interval parsing errors.

Parse a pair of as to create an Interval a. Note this checks only that begin < end and has no relation to checking the conditions of SizedIv.

>>> parseInterval 0 1
Right (0, 1)

>>> parseInterval 1 0
Left (ParseErrorInterval "0<=1")

A synonym for parseInterval

Safely creates an 'Interval a' using x as the begin and adding max moment dur to x as the end. For the SizedIv instances this module exports, beginerval is the same as interval. However, it is defined separately since beginerval will always have this behavior whereas interval behavior might differ by implementation.

>>> beginerval (0::Int) (0::Int)
(0, 1)

>>> beginerval (1::Int) (0::Int)
(0, 1)

>>> beginerval (2::Int) (0::Int)
(0, 2)

A synonym for beginerval

Safely creates an 'Interval a' using x as the end and adding negate max moment dur to x as the begin.

>>> enderval (0::Int) (0::Int)
(-1, 0)

>>> enderval (1::Int) (0::Int)
(-1, 0)

>>> enderval (2::Int) (0::Int)
(-2, 0)

A synonym for enderval

Safely creates an Interval from a pair of endpoints, expanding from the left endpoint if necessary to create a valid interval according to the rules of SizedIv. This function simply wraps ivExpandr.

>>> safeInterval (4, 5 ::Int)
(4, 5)
>>> safeInterval (4, 3 :: Int)
(4, 5)

A synonym for safeInterval

Resize an i a to by expanding to "left" by l and to the "right" by r. In the case that l or r are less than a moment the respective endpoints are unchanged.

>>> iv2to4 = safeInterval (2::Int, 4)
>>> iv2to4' = expand 0 0 iv2to4
>>> iv1to5 = expand 1 1 iv2to4

>>> iv2to4
(2, 4)

>>> iv2to4'
(2, 4)

>>> iv1to5
(1, 5)

>>> pretty $ standardExampleDiagram [(iv2to4, "iv2to4"), (iv1to5, "iv1to5")] []
  --  <- [iv2to4]
 ---- <- [iv1to5]
=====

Expands an i a to the "left".

>>> iv2to4 = (safeInterval (2::Int, 4::Int))
>>> iv0to4 = expandl 2 iv2to4

>>> iv2to4
(2, 4)

>>> iv0to4
(0, 4)

>>> pretty $ standardExampleDiagram [(iv2to4, "iv2to4"), (iv0to4, "iv0to4")] []
  -- <- [iv2to4]
---- <- [iv0to4]
====

Expands an i a to the "right".

>>> iv2to4 = (safeInterval (2::Int, 4::Int))
>>> iv2to6 = expandr 2 iv2to4

>>> iv2to4
(2, 4)

>>> iv2to6
(2, 6)

>>> pretty $ standardExampleDiagram [(iv2to4, "iv2to4"), (iv2to6, "iv2to6")] []
  --   <- [iv2to4]
  ---- <- [iv2to6]
======

Creates a new Interval spanning the extent x and y.

>>> extenterval (Interval (0, 1)) (Interval (9, 10))
(0, 10)

Generic interface for defining relations between abstract representations of intervals, for the purpose of Allen's interval algebra.

In general, these "intervals" need not be representable as temporal intervals with a fixed beginning and ending. Specifically, the relations can be defined to provide temporal reasoning in a qualitative setting, examples of which are in Allen 1983.

For intervals that can be cast in canonical form as Interval s with begin and end points, see PointedIv and SizedIv.

Instances of Iv must ensure any pair of intervals satisfies exactly one of the thirteen possible IntervalRelation s.

When iv is also an instance of PointedIv, with Ord (Point iv), the requirement implies

ivBegin i < ivEnd i

Allen 1983 defines the IntervalRelation s for such cases, which is provided in this module for the canonical representation Interval a.

Examples

We found the letter during dinner, after we made the decision.

>>> :{
data GoingsOn = Dinner | FoundLetter | MadeDecision
 deriving (Show, Eq)
instance Iv GoingsOn where
 ivRelate MadeDecision Dinner = Before
 ivRelate MadeDecision FoundLetter = Before
 ivRelate FoundLetter Dinner = During
 ivRelate x y
   | x == y = Equals
   | otherwise = converseRelation (ivRelate y x)
:}

The IntervalRelation type and the associated predicate functions enumerate the thirteen possible ways that two SizedIv objects may relate according to Allen's interval algebra. Constructors are shown with their corresponding predicate function.

Does x meets y? Is x metBy y?

Example data with corresponding diagram:

>>> x = bi 5 0
>>> y = bi 5 5
>>> pretty $ standardExampleDiagram [(x, "x"), (y, "y")] []
-----      <- [x]
     ----- <- [y]
==========

Examples:

>>> x `meets` y
True

>>> x `metBy` y
False

>>> y `meets` x
False

>>> y `metBy` x
True

Does x meets y? Is x metBy y?

Example data with corresponding diagram:

>>> x = bi 5 0
>>> y = bi 5 5
>>> pretty $ standardExampleDiagram [(x, "x"), (y, "y")] []
-----      <- [x]
     ----- <- [y]
==========

Examples:

>>> x `meets` y
True

>>> x `metBy` y
False

>>> y `meets` x
False

>>> y `metBy` x
True

Is x before y? Does x precedes y? Is x after y? Is x precededBy y?

Example data with corresponding diagram:

>>> x = bi 3 0
>>> y = bi 4 6
>>> pretty $ standardExampleDiagram [(x, "x"), (y, "y")] []
---        <- [x]
      ---- <- [y]
==========

Examples:

>>> x `before` y
True
>>> x `precedes` y
True

>>> x `after`y
False
>>> x `precededBy` y
False

>>> y `before` x
False
>>> y `precedes` x
False

>>> y `after` x
True
>>> y `precededBy` x
True

Is x before y? Does x precedes y? Is x after y? Is x precededBy y?

Example data with corresponding diagram:

>>> x = bi 3 0
>>> y = bi 4 6
>>> pretty $ standardExampleDiagram [(x, "x"), (y, "y")] []
---        <- [x]
      ---- <- [y]
==========

Examples:

>>> x `before` y
True
>>> x `precedes` y
True

>>> x `after`y
False
>>> x `precededBy` y
False

>>> y `before` x
False
>>> y `precedes` x
False

>>> y `after` x
True
>>> y `precededBy` x
True

Does x overlaps y? Is x overlappedBy y?

Example data with corresponding diagram:

>>> x = bi 6 0
>>> y = bi 6 4
>>> pretty $ standardExampleDiagram [(x, "x"), (y, "y")] []
------     <- [x]
    ------ <- [y]
==========

Examples:

>>> x `overlaps` y
True

>>> x `overlappedBy` y
False

>>> y `overlaps` x
False

>>> y `overlappedBy` x
True

Does x overlaps y? Is x overlappedBy y?

Example data with corresponding diagram:

>>> x = bi 6 0
>>> y = bi 6 4
>>> pretty $ standardExampleDiagram [(x, "x"), (y, "y")] []
------     <- [x]
    ------ <- [y]
==========

Examples:

>>> x `overlaps` y
True

>>> x `overlappedBy` y
False

>>> y `overlaps` x
False

>>> y `overlappedBy` x
True

Does x finishes y? Is x finishedBy y?

Example data with corresponding diagram:

>>> x = bi 3 7
>>> y = bi 6 4
>>> pretty $ standardExampleDiagram [(x, "x"), (y, "y")] []
       --- <- [x]
    ------ <- [y]
==========

Examples:

>>> x `finishes` y
True

>>> x `finishedBy` y
False

>>> y `finishes` x
False

>>> y `finishedBy` x
True

Does x finishes y? Is x finishedBy y?

Example data with corresponding diagram:

>>> x = bi 3 7
>>> y = bi 6 4
>>> pretty $ standardExampleDiagram [(x, "x"), (y, "y")] []
       --- <- [x]
    ------ <- [y]
==========

Examples:

>>> x `finishes` y
True

>>> x `finishedBy` y
False

>>> y `finishes` x
False

>>> y `finishedBy` x
True

Is x during y? Does x contains y?

Example data with corresponding diagram:

>>> x = bi 3 5
>>> y = bi 6 4
>>> pretty $ standardExampleDiagram [(x, "x"), (y, "y")] []
     ---   <- [x]
    ------ <- [y]
==========

Examples:

>>> x `during` y
True

>>> x `contains` y
False

>>> y `during` x
False

>>> y `contains` x
True

Is x during y? Does x contains y?

Example data with corresponding diagram:

>>> x = bi 3 5
>>> y = bi 6 4
>>> pretty $ standardExampleDiagram [(x, "x"), (y, "y")] []
     ---   <- [x]
    ------ <- [y]
==========

Examples:

>>> x `during` y
True

>>> x `contains` y
False

>>> y `during` x
False

>>> y `contains` x
True

Does x starts y? Is x startedBy y?

Example data with corresponding diagram:

>>> x = bi 3 4
>>> y = bi 6 4
>>> pretty $ standardExampleDiagram [(x, "x"), (y, "y")] []
    ---    <- [x]
    ------ <- [y]
==========

Examples:

>>> x `starts` y
True

>>> x `startedBy` y
False

>>> y `starts` x
False

>>> y `startedBy` x
True

Does x starts y? Is x startedBy y?

Example data with corresponding diagram:

>>> x = bi 3 4
>>> y = bi 6 4
>>> pretty $ standardExampleDiagram [(x, "x"), (y, "y")] []
    ---    <- [x]
    ------ <- [y]
==========

Examples:

>>> x `starts` y
True

>>> x `startedBy` y
False

>>> y `starts` x
False

>>> y `startedBy` x
True

Does x equals y?

Example data with corresponding diagram:

>>> x = bi 6 4
>>> y = bi 6 4
>>> pretty $ standardExampleDiagram [(x, "x"), (y, "y")] []
    ------ <- [x]
    ------ <- [y]
==========

Examples:

>>> x `equals` y
True

>>> y `equals` x
True

Is x before y? Does x precedes y? Is x after y? Is x precededBy y?

Example data with corresponding diagram:

>>> x = bi 3 0
>>> y = bi 4 6
>>> pretty $ standardExampleDiagram [(x, "x"), (y, "y")] []
---        <- [x]
      ---- <- [y]
==========

Examples:

>>> x `before` y
True
>>> x `precedes` y
True

>>> x `after`y
False
>>> x `precededBy` y
False

>>> y `before` x
False
>>> y `precedes` x
False

>>> y `after` x
True
>>> y `precededBy` x
True

Is x before y? Does x precedes y? Is x after y? Is x precededBy y?

Example data with corresponding diagram:

>>> x = bi 3 0
>>> y = bi 4 6
>>> pretty $ standardExampleDiagram [(x, "x"), (y, "y")] []
---        <- [x]
      ---- <- [y]
==========

Examples:

>>> x `before` y
True
>>> x `precedes` y
True

>>> x `after`y
False
>>> x `precededBy` y
False

>>> y `before` x
False
>>> y `precedes` x
False

>>> y `after` x
True
>>> y `precededBy` x
True

Are x and y disjoint (before, after, meets, or metBy)?

Example data with corresponding diagram:

>>> x = bi 3 0
>>> y = bi 3 5
>>> pretty $ standardExampleDiagram [(x, "x"), (y, "y")] []
---      <- [x]
     --- <- [y]
========

Examples:

>>> x `disjoint` y
True

>>> y `disjoint` x
True

Example data with corresponding diagram:

>>> x = bi 3 0
>>> y = bi 3 3
>>> pretty $ standardExampleDiagram [(x, "x"), (y, "y")] []
---    <- [x]
   --- <- [y]
======

Examples:

>>> x `disjoint` y
True

>>> y `disjoint` x
True

Example data with corresponding diagram:

>>> x = bi 6 0
>>> y = bi 3 3
>>> pretty $ standardExampleDiagram [(x, "x"), (y, "y")] []
------ <- [x]
   --- <- [y]
======

Examples:

>>> x `disjoint` y
False

>>> y `disjoint` x
False

Does x concur y, meaning x and y share some support? Is x notDisjoint y? This is the complement of disjoint.

Example data with corresponding diagram:

>>> x = bi 3 0
>>> y = bi 3 4
>>> pretty $ standardExampleDiagram [(x, "x"), (y, "y")] []
---     <- [x]
    --- <- [y]
=======

Examples:

>>> x `notDisjoint` y
False
>>> y `concur` x
False

Example data with corresponding diagram:

>>> x = bi 3 0
>>> y = bi 3 3
>>> pretty $ standardExampleDiagram [(x, "x"), (y, "y")] []
---    <- [x]
   --- <- [y]
======

Examples:

>>> x `notDisjoint` y
False
>>> y `concur` x
False

Example data with corresponding diagram:

>>> x = bi 6 0
>>> y = bi 3 3
>>> pretty $ standardExampleDiagram [(x, "x"), (y, "y")] []
------ <- [x]
   --- <- [y]
======

Examples:

>>> x `notDisjoint` y
True
>>> y `concur` x
True

Does x concur y, meaning x and y share some support? Is x notDisjoint y? This is the complement of disjoint.

Example data with corresponding diagram:

>>> x = bi 3 0
>>> y = bi 3 4
>>> pretty $ standardExampleDiagram [(x, "x"), (y, "y")] []
---     <- [x]
    --- <- [y]
=======

Examples:

>>> x `notDisjoint` y
False
>>> y `concur` x
False

Example data with corresponding diagram:

>>> x = bi 3 0
>>> y = bi 3 3
>>> pretty $ standardExampleDiagram [(x, "x"), (y, "y")] []
---    <- [x]
   --- <- [y]
======

Examples:

>>> x `notDisjoint` y
False
>>> y `concur` x
False

Example data with corresponding diagram:

>>> x = bi 6 0
>>> y = bi 3 3
>>> pretty $ standardExampleDiagram [(x, "x"), (y, "y")] []
------ <- [x]
   --- <- [y]
======

Examples:

>>> x `notDisjoint` y
True
>>> y `concur` x
True

Is x within (enclosedBy) y? That is, during, starts, finishes, or equals?

Example data with corresponding diagram:

>>> x = bi 6 4
>>> y = bi 6 4
>>> pretty $ standardExampleDiagram [(x, "x"), (y, "y")] []
    ------ <- [x]
    ------ <- [y]
==========

Examples:

>>> x `within` y
True

>>> y `enclosedBy` x
True

Example data with corresponding diagram:

>>> x = bi 6 4
>>> y = bi 5 4
>>> pretty $ standardExampleDiagram [(x, "x"), (y, "y")] []
    ------ <- [x]
    -----  <- [y]
==========

Examples:

>>> x `within` y
False

>>> y `enclosedBy` x
True

Example data with corresponding diagram:

>>> x = bi 6 4
>>> y = bi 4 5
>>> pretty $ standardExampleDiagram [(x, "x"), (y, "y")] []
    ------ <- [x]
     ----  <- [y]
==========

Examples:

>>> x `within` y
False
>>> y `enclosedBy` x
True

Example data with corresponding diagram:

>>> x = bi 2 7
>>> y = bi 1 5
>>> pretty $ standardExampleDiagram [(x, "x"), (y, "y")] []
       -- <- [x]
     -    <- [y]
=========

Examples:

>>> x `within` y
False

>>> y `enclosedBy` x
False

Does x encloses y? That is, is y within x?

Example data with corresponding diagram:

>>> x = bi 6 4
>>> y = bi 6 4
>>> pretty $ standardExampleDiagram [(x, "x"), (y, "y")] []
    ------ <- [x]
    ------ <- [y]
==========

Examples:

>>> x `encloses` y
True

>>> y `encloses` x
True

Example data with corresponding diagram:

>>> x = bi 6 4
>>> y = bi 5 4
>>> pretty $ standardExampleDiagram [(x, "x"), (y, "y")] []
    ------ <- [x]
    -----  <- [y]
==========

Examples:

>>> x `encloses` y
True

>>> y `encloses` x
False

Example data with corresponding diagram:

>>> x = bi 6 4
>>> y = bi 4 5
>>> pretty $ standardExampleDiagram [(x, "x"), (y, "y")] []
    ------ <- [x]
     ----  <- [y]
==========

Examples:

>>> x `encloses` y
True

>>> y `encloses` x
False

Example data with corresponding diagram:

>>> x = bi 2 7
>>> y = bi 1 5
>>> pretty $ standardExampleDiagram [(x, "x"), (y, "y")] []
       -- <- [x]
     -    <- [y]
=========

Examples:

>>> x `encloses` y
False

>>> y `encloses` x
False

Is x within (enclosedBy) y? That is, during, starts, finishes, or equals?

Example data with corresponding diagram:

>>> x = bi 6 4
>>> y = bi 6 4
>>> pretty $ standardExampleDiagram [(x, "x"), (y, "y")] []
    ------ <- [x]
    ------ <- [y]
==========

Examples:

>>> x `within` y
True

>>> y `enclosedBy` x
True

Example data with corresponding diagram:

>>> x = bi 6 4
>>> y = bi 5 4
>>> pretty $ standardExampleDiagram [(x, "x"), (y, "y")] []
    ------ <- [x]
    -----  <- [y]
==========

Examples:

>>> x `within` y
False

>>> y `enclosedBy` x
True

Example data with corresponding diagram:

>>> x = bi 6 4
>>> y = bi 4 5
>>> pretty $ standardExampleDiagram [(x, "x"), (y, "y")] []
    ------ <- [x]
     ----  <- [y]
==========

Examples:

>>> x `within` y
False
>>> y `enclosedBy` x
True

Example data with corresponding diagram:

>>> x = bi 2 7
>>> y = bi 1 5
>>> pretty $ standardExampleDiagram [(x, "x"), (y, "y")] []
       -- <- [x]
     -    <- [y]
=========

Examples:

>>> x `within` y
False

>>> y `enclosedBy` x
False

Operator for composing the union of two predicates on Intervallic s.

Forms a predicate function from the union of a set of IntervalRelations.

Compose a list of interval relations with _or_ to create a new ComparativePredicateOf1 i a. For example, unionPredicates [before, meets] creates a predicate function determining if one interval is either before or meets another interval.

The set of IntervalRelation meaning two intervals are disjoint.

The set of IntervalRelation meaning one interval is within the other.

The set of IntervalRelation meaning one interval is *strictly* within the other.

Defines a predicate of two objects of type a.

Defines a predicate of two object of different types.

Creates a new Interval from the end of another.

Creates a new Interval from the begin of another.

Safely creates a new Interval with moment length with begin at x

>>> beginervalMoment (10 :: Int)
(10, 11)

Safely creates a new Interval with moment length with end at x

>>> endervalMoment (10 :: Int)
(9, 10)

Modifies the endpoints of second argument's interval by taking the difference from the first's input's begin.

Example data with corresponding diagram:

>>> a = bi 3 2 :: Interval Int
>>> a
(2, 5)
>>> x = bi 3 7 :: Interval Int
>>> x
(7, 10)
>>> y = bi 4 9 :: Interval Int
>>> y
(9, 13)
>>> pretty $ standardExampleDiagram [(a, "a"), (x, "x"), (y, "y")] []
  ---         <- [a]
       ---    <- [x]
         ---- <- [y]
=============

Examples:

>>> x' = shiftFromBegin a x
>>> x'
(5, 8)
>>> y' = shiftFromBegin a y
>>> y'
(7, 11)
>>> pretty $ standardExampleDiagram [(x', "x'"), (y', "y'")] []
     ---    <- [x']
       ---- <- [y']
===========

Modifies the endpoints of second argument's interval by taking the difference from the first's input's end.

Example data with corresponding diagram:

>>> a = bi 3 2 :: Interval Int
>>> a
(2, 5)
>>> x = bi 3 7 :: Interval Int
>>> x
(7, 10)
>>> y = bi 4 9 :: Interval Int
>>> y
(9, 13)
>>> pretty $ standardExampleDiagram [(a, "a"), (x, "x"), (y, "y")] []
  ---         <- [a]
       ---    <- [x]
         ---- <- [y]
=============

Examples:

>>> x' = shiftFromEnd a x
>>> x'
(2, 5)
>>> y' = shiftFromEnd a y
>>> y'
(4, 8)
>>> pretty $ standardExampleDiagram [(x', "x'"), (y', "y'")] []
  ---    <- [x']
    ---- <- [y']
========

Changes the duration of an Intervallic value to a moment starting at the begin of the interval. Uses beginervalMoment.

>>> momentize (Interval (6, 10))
(6, 7)

Converts an i Int to an i a via toEnum. This assumes the provided toEnum method is strictly monotone increasing: For a types that are Ord, then for Int values x, y it holds that x < y implies toEnum x < toEnum y.

Converts an i a to an i Int via fromEnum. This assumes the provided fromEnum method is strictly monotone increasing: For a types that are Ord with values x, y, then x < y implies fromEnum x < fromEnum y, so long as the latter is well-defined.

The Set of all IntervalRelations.

Compare two i a to determine their IntervalRelation.

>>> relate (Interval (0::Int, 1)) (Interval (1, 2))
Meets

>>> relate (Interval (1::Int, 2)) (Interval (0, 1))
MetBy

Compose two interval relations according to the rules of the algebra. The rules are enumerated according to this table.

Finds the complement of a Set IntervalRelation.

Find the union of two Sets of IntervalRelations.

Find the intersection of two Sets of IntervalRelations.

Find the converse of a Set IntervalRelation.

Find the converse of a single IntervalRelation