A complementary representation of a VersionRange, using an increasing sequence of separated (i.e., non-overlapping, non-touching) non-empty intervals. The represented range is the union of these intervals, meaning that the empty sequence denotes the empty range.

As ranges form a Boolean algebra, we can compute union, intersection, and complement. These operations are all linear in the size of the input, thanks to the ordered representation.

The interval-sequence representation gives a canonical representation for the semantics of VersionRanges. This makes it easier to check things like whether a version range is empty, covers all versions, or requires a certain minimum or maximum version. It also makes it easy to check equality (just ==) or containment. It also makes it easier to identify 'simple' version predicates for translation into foreign packaging systems that do not support complex version range expressions.

Convert a VersionRange to a sequence of version intervals.

Convert a VersionIntervals value back into a VersionRange expression representing the version intervals.

Test if a version falls within the version intervals.

It exists mostly for completeness and testing. It satisfies the following properties:

withinIntervals v (toVersionIntervals vr) = withinRange v vr
withinIntervals v ivs = withinRange v (fromVersionIntervals ivs)

Inspect the list of version intervals.

Directly construct a VersionIntervals from a list of intervals.

Union two interval sequences, fusing intervals where necessary. Computed \( O(n+m) \) time, resulting in sequence of length \( ≤ n+m \).

The intersection \( is \cap is' \) of two interval sequences \( is \) and \( is' \) of lengths \( n \) and \( m \), resp., satisfies the specification \( is ∩ is' = \{ i ∩ i' \mid i ∈ is, i' ∈ is' \} \). Thanks to the ordered representation of intervals it can be computed in \( O(n+m) \) (rather than the naive \( O(nm) \).

The length of \( is \cap is' \) is \( ≤ \min(n,m) \).

Compute the complement. \( O(n) \).

Remove the last upper bound, enlarging the range. But empty ranges stay empty. \( O(n) \).

Remove the first lower bound (i.e, make it \( [0 \). Empty ranges stay empty. \( O(1) \).

View a VersionRange as a sequence of separated intervals.

This provides a canonical view of the semantics of a VersionRange as opposed to the syntax of the expression used to define it. For the syntactic view use foldVersionRange.

Canonical means that two semantically equal ranges translate to the same [VersionInterval], thus its Eq instance can decide semantical equality of ranges.

In the returned sequence, each interval is non-empty. The sequence is in increasing order and the intervals are separated, i.e., they neither overlap nor touch. Therefore only the first and last interval can be unbounded. The sequence can be empty if the range is empty (e.g. a range expression like > 2 && < 1).

Other checks are trivial to implement using this view. For example:

isNoVersion vr | [] <- asVersionIntervals vr = True
               | otherwise                   = False

isSpecificVersion vr
   | [(LowerBound v  InclusiveBound
      ,UpperBound v' InclusiveBound)] <- asVersionIntervals vr
   , v == v'   = Just v
   | otherwise = Nothing

Version intervals with exclusive or inclusive bounds, in all combinations:

1. \( (lb,ub) \) meaning \( lb < \_ < ub \).
2. \( (lb,ub] \) meaning \( lb < \_ ≤ ub \).
3. \( [lb,ub) \) meaning \( lb ≤ \_ < ub \).
4. \( [lb,ub] \) meaning \( lb ≤ \_ < ub \).

The upper bound can also be missing, meaning "\( ..,∞) \)".