@toryt/allen NPM

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

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

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.