Allen

Validate and reason about relations between intervals, and between points and intervals, in JavaScript and TypeScript.

When working with intervals, we often want to express constraints (invariants) that limit acceptable combinations. Expressing this correctly proves difficult in practice. Falling back to working with isolated start and end points, and reasoning about their relations, in practice proves to be even much more difficult and error-prone. This problem was tackled in 1983 by James Allen:

• Allen, James F. “Maintaining knowledge about temporal intervals”, Communications of the ACM 26(11) pages 832-843; November 1983

Good synopses of this theory are

• Wikipedia
• Thomas A. Alspaugh “Allen's interval algebra”.

This library does not help with inference.

ppwcode dotnet-util-allen offers a C# version of the functionality of this library.

How to use

Example

JavaScript

const { AllenRelation, PointIntervalRelation } = require('@toryt/allen')

function allenRelationExample () {
  const iiCondition1 = AllenRelation.fromString('psSd')
  const iiCondition2 = AllenRelation.fromString('sde')
  const iiCondition = iiCondition1.compose(iiCondition2)

  const i1 = { start: '2022-11-04', end: '2023-04-12' }
  const i2 = { start: '2021-08-22' }

  const iiActual = AllenRelation.relation(i1, i2)
  if (!iiActual.implies(iiCondition)) {
    throw new Error(`i1 and i2 do no uphold ${iiCondition.toString()}`)
  }

  return iiActual
}

function pointIntervalExample () {
  const piCondition1 = PointIntervalRelation.or(PointIntervalRelation.BEFORE, PointIntervalRelation.TERMINATES)
  const iiCondition2 = AllenRelation.fromString('sde')
  const piCondition = piCondition1.compose(iiCondition2)

  const p = '2021-08-15'
  const i = { start: '2021-08-22' }

  const piActual = PointIntervalRelation.relation(p, i)
  if (!piActual.implies(piCondition)) {
    throw new Error(`p and i2 do not uphold ${piCondition.toString()}`)
  }

  return piActual
}

TypeScript

import { AllenRelation, Interval, PointIntervalRelation } from '@toryt/allen'

function allenRelationExample (): AllenRelation {
  const iiCondition1: AllenRelation = AllenRelation.fromString<AllenRelation>('psSd')
  const iiCondition2: AllenRelation = AllenRelation.fromString<AllenRelation>('sde')
  const iiCondition: AllenRelation = iiCondition1.compose(iiCondition2)

  const i1: Interval<string> = { start: '2022-11-04', end: '2023-04-12' }
  const i2: Interval<string> = { start: '2021-08-22' }

  const iiActual: AllenRelation = AllenRelation.relation(i1, i2)
  if (!iiActual.implies(iiCondition)) {
    throw new Error(`i1 and i2 do no uphold ${iiCondition.toString()}`)
  }

  return iiActual
}

function pointIntervalExample (): PointIntervalRelation {
  const piCondition1: PointIntervalRelation = PointIntervalRelation.or(
    PointIntervalRelation.BEFORE,
    PointIntervalRelation.TERMINATES
  )
  const iiCondition2: AllenRelation = AllenRelation.fromString<AllenRelation>('sde')
  const piCondition: PointIntervalRelation = piCondition1.compose(iiCondition2)

  const p: string = '2021-08-15'
  const i: Interval<string> = { start: '2021-08-22' }

  const piActual: PointIntervalRelation = PointIntervalRelation.relation(p, i)
  if (!piActual.implies(piCondition)) {
    throw new Error(`p and i2 do not uphold ${piCondition.toString()}`)
  }

  return piActual
}

Algebra

We find that there are 5 basic relations possible between a definite point and a definite interval:

• t is BEFORE I (b)

  

• t COMMENCES I (c)

  

• t IN I (i)

  

• t TERMINATESI(t`)

  

• t is AFTER I (a)

  

and that there are 13 basic relations possible between definite intervals:

| Basic relation | (.) | Illustration | | -------------------------- | ----- | -------------------------------------------------------------------------------------------------------------------------------------- | | i1 precedes i2 | (p) | | | i1 meets i2 | (m) | | | i1 overlaps i2 | (o) | | | i1 is finished by i2 | (F) | | | i1 contains i2 | (D) | | | i1 starts i2 | (s) | | | i1 equals i2 | (e) | | | i1 is started by i2 | (S) | | | i1 during i2 | (d) | | | i1 finishes i2 | (f) | | | i1 is overlapped by i2 | (O) | | | i1 is met by i2 | (M) | | | i1 is preceded by i2 | (P) | |

These 5, respectively 13, basic relations are an orthogonal basis for all possible general relation-conditions between a point and an interval (PointIntervalRelation), respectively between two intervals (AllenRelation).

(bt) says that a point can be before an interval, or terminate it. (sde) says that an interval i1 may start an interval i2, may be during i2, or be equal to it. Each general relation expresses a certain amount of uncertainty, where a basic relation expresses certainty, and the FULL relation ( (bcita), respectively (pmoFDseSdfOMP)) expresses complete uncertainty.

These 32 (25), respectively 8192 (213), general relations form an algebra, with the operations

• complement
• converse (only for AllenRelation)
• min
• or
• and
• compose

A relation to be used as a condition to the problem at hand is build using these operations.

A relation implies another relation, or not. E.g., if we have determined that a relation between i1 and i2 is (oO), and we need it to be (pmoOMP), this is ok because (oO) implies (pmoOMP). If the relation is (oeO) however, it is not ok, because (pmoOMP) does not allow the intervals to be equal.

Things get even more interesting when we need to reason about indefinite intervals, where the start or end is unknown 🤷.

There are some pitfalls.

Details

• Points and comparison
• Intervals
• Point – Interval Relations
• Allen Relations
• Code documentation

All functions and methods are protected with explicit asserts, that throw when a precondition is violated. Although written in TypeScript, types are verified dynamically too, so that type safety is ensured dynamically when the library is used with plain JavaScript too.

Where to find

Repo, CI, issues, pull requests This project is maintained in Bitbucket (repo, CI, issues, pull requests, …).

npm

@toryt/allen

Style

This code uses the application to TypeScript of the Standard coding style. Tests require complete code coverage.

License

Released under the Apache License, Version 2.0.

Notes

This code was based on a Java implementation last updated in December 2008.