This is an alternative site for discovering Elm packages. You may be looking for the official Elm package site instead.

# Interval

A representation of numeric intervals (also known as ranges.)

# Types

type Interval = Bounded Bound Bound | Degenerate Float | Empty

An interval over the reals. May be over either the Ordinary Reals `(-∞, +∞)` or the Extended Reals `[-∞, +∞]`. `Bounded x y` will always satisfy `x < y`. (`x == y` is either degenerate or empty)

Opaque type.

type Bound = Inclusive Float | Exclusive Float

Represents an upper or lower, closed or open endpoint of an Interval. This encompasses the "endpoints" of unbounded intervals when the bound value is either of the `Infinity` values in the floating point spec.

Opaque type.

# Constructors

`interval` is the primary constructor; the others are just for convenience.

interval : Bound -> Bound -> Interval

Constructs an `Interval` from two Bounds.

degenerate : Float -> Interval

A degenerate Interval.

empty : Interval

An empty Interval.

leftBounded : Bound -> Interval

Convenience function for a left-bounded Interval (from some n to +∞)

rightBounded : Bound -> Interval

Convenience function for a right-bounded Interval (from -∞ to some n)

unbounded : Interval

An unbounded Interval over the Extended Reals. `[-∞, +∞]`

# Endpoint (Bound) constructors

excludes : Float -> Bound

An exclusive endpoint of an interval.

includes : Float -> Bound

An inclusive endpoint of an interval.

# Operations on Intervals

hull : Interval -> Interval -> Interval

The convex hull of two intervals. This is similar to union in that it includes all the points of the component intervals, and for non-overlapping intervals, the points between them.

intersection : Interval -> Interval -> Interval

The intersection of two intervals. If the intervals overlap, this is the common part. If not, this is the empty interval.

intervalToString : Interval -> String

Return a String representation of an Interval.

interior : Interval -> Interval

Returns the largest open interval contained within a.

``````-- `interior([x, y]) == (x, y)`
interior (interval (includes 0) (includes 2)) == interval (excludes 0) (excludes 2)
``````
closure : Interval -> Interval

Returns the smallest closed interval containing a.

``````-- `closure((x, y)) == [x, y]`
interior (interval (excludes 0) (excludes 2)) == interval (includes 0) (includes 2)
``````
subtract : Interval -> Interval -> List Interval

Subtract interval `b` from interval `a`, returning a list of the parts of `a` that did not intersect with `b`.

E.g.:

• [1, 3) - (1, 2] = [ {1}, (2, 3) ]
upperBoundValue : Interval -> Maybe Float

Extract the value of the upper bound of an Interval.

lowerBoundValue : Interval -> Maybe Float

Extract the value of the lower bound of an Interval.

# Tests on Intervals

adjoins : Interval -> Interval -> Bool

Are these two intervals adjoins? I.e., do they share an upper-lower or lower-upper bound, exactly one of which is closed, and do not intersect each other?

``````let
a = interval (includes 1) (excludes 3)  -- [1, 3)
b = interval (includes 2) (includes 4)  -- [3, 4]
c = interval (includes 3) (includes 4)  -- (3, 4]
d = interval (includes 3) (includes 4)  -- [2, 3]
in
[ adjoins a b = True
, adjoins a c = False
, adjoins a d = False
]
``````
intersects : Interval -> Interval -> Bool

Do these two intervals intersect?

``````let
a = interval (includes 1) (excludes 3)
b = interval (includes 2) (includes 4)
c = interval (includes 3) (includes 4)
in
[ intersects a b = True
, intersects a c = False
]
``````
intersectsPoint : Interval -> Float -> Bool

Does this interval contain the given point?

``````let
a = interval (includes 1) (excludes 3)
in
[ intersectsPoint a 0 = False
, intersectsPoint a 1 = True
, intersectsPoint a 3 = False
]
``````
isBounded : Interval -> Bool

Does this interval have finite bounds?

isDegenerate : Interval -> Bool

Is this a degenerate (point-valued) interval?

isEmpty : Interval -> Bool

Is this an empty interval?

isLeftBounded : Interval -> Bool

Does this interval have a finite lower bound, and an infinite upper bound?

isRightBounded : Interval -> Bool

Does this interval have a finite upper bound, and an infinite lower bound?

isLeftOpen : Interval -> Bool

Is the lower bound of this interval open?

isRightOpen : Interval -> Bool

Is the upper bound of this interval open?

``````module Interval
exposing
, Bound
, closure
, degenerate
, empty
, excludes
, hull
, includes
, interior
, intersection
, intersects
, intersectsPoint
, Interval
, interval
, intervalToString
, isBounded
, isDegenerate
, isEmpty
, isLeftBounded
, isLeftOpen
, isRightBounded
, isRightOpen
, leftBounded
, lowerBoundValue
, rightBounded
, subtract
, unbounded
, upperBoundValue
)

{-| A representation of numeric intervals (also known as *ranges*.)

# Types

@docs Interval
@docs Bound

# Constructors

`interval` is the primary constructor; the others are just for convenience.

@docs interval
@docs degenerate
@docs empty
@docs leftBounded
@docs rightBounded
@docs unbounded

# Endpoint (Bound) constructors

@docs excludes
@docs includes

# Operations on Intervals

@docs hull
@docs intersection
@docs intervalToString
@docs interior
@docs closure
@docs subtract
@docs upperBoundValue
@docs lowerBoundValue

# Tests on Intervals

@docs intersects
@docs intersectsPoint
@docs isBounded
@docs isDegenerate
@docs isEmpty
@docs isLeftBounded
@docs isRightBounded
@docs isLeftOpen
@docs isRightOpen

- [Interval](<https://en.wikipedia.org/wiki/Interval_(mathematics)>
- [Interval tree](https://en.wikipedia.org/wiki/Interval_tree)
- [Allen's interval algebra](https://en.wikipedia.org/wiki/Allen%27s_interval_algebra)

-}

{-| An interval over the reals. May be over either the Ordinary Reals `(-∞, +∞)` or
the Extended Reals `[-∞, +∞]`.
`Bounded x y` will always satisfy `x < y`. (`x == y` is either degenerate or empty)

Opaque type.

-}
type Interval
= Bounded Bound Bound
| Degenerate Float
| Empty

{-| Represents an upper or lower, closed or open endpoint of an Interval.
This encompasses the "endpoints" of unbounded intervals when the bound value
is either of the `Infinity` values in the floating point spec.

Opaque type.

-}
type Bound
= Inclusive Float
| Exclusive Float

{-| An inclusive endpoint of an interval.
-}
includes : Float -> Bound
includes n =
Inclusive n

{-| An exclusive endpoint of an interval.
-}
excludes : Float -> Bound
excludes n =
Exclusive n

boundValue : Bound -> Float
boundValue b =
case b of
Inclusive n ->
n

Exclusive n ->
n

{-| An empty Interval.
-}
empty : Interval
empty =
Empty

{-| A degenerate Interval.
-}
degenerate : Float -> Interval
degenerate n =
Degenerate n

{-| An unbounded Interval over the [Extended Reals.] `[-∞, +∞]`

[Extended Reals.]: https://en.wikipedia.org/wiki/Interval_(mathematics)#Infinite_endpoints

-}
unbounded : Interval
unbounded =
interval (Inclusive <| -1 / 0) (Inclusive <| 1 / 0)

{-| Convenience function for a right-bounded Interval (from -∞ to some n)
-}
rightBounded : Bound -> Interval
rightBounded b =
interval (Inclusive <| -1 / 0) b

{-| Convenience function for a left-bounded Interval (from some n to +∞)
-}
leftBounded : Bound -> Interval
leftBounded b =
interval b (Inclusive <| 1 / 0)

{-| Constructs an `Interval` from two Bounds.
-}
interval : Bound -> Bound -> Interval
interval i j =
let
t =
boundValue i

u =
boundValue j
in
case (t == u) of
True ->
case ( i, j ) of
( Inclusive _, Inclusive _ ) ->
Degenerate t

( _, _ ) ->
Empty

False ->
case (t < u) of
True ->
Bounded i j

False ->
Empty

{-| Return a String representation of an Interval.
-}
intervalToString : Interval -> String
intervalToString interval =
case interval of
Empty ->
"{}"

Degenerate n ->
"{" ++ toString n ++ "}"

Bounded x y ->
let
left =
case x of
Exclusive n ->
"(" ++ toString n

Inclusive n ->
"[" ++ toString n

right =
case y of
Exclusive n ->
toString n ++ ")"

Inclusive n ->
toString n ++ "]"
in
left ++ ", " ++ right

{-| Return the outer minimum of two Bounds.

minOuterBound (includes 1) (excludes 1) == (includes 1)

minOuterBound (includes 1) (excludes 0) == (excludes 0)

-}
minOuterBound : Bound -> Bound -> Bound
minOuterBound a b =
let
x =
boundValue a

y =
boundValue b
in
case (x < y) of
True ->
a

False ->
case (y < x) of
True ->
b

False ->
-- x == y
andInclusives a b

{-| Return the outer maximum of two Bounds.

maxOuterBound (includes 1) (excludes 1) == (includes 1)

maxOuterBound (includes 1) (excludes 2) == (excludes 2)

-}
maxOuterBound : Bound -> Bound -> Bound
maxOuterBound a b =
let
x =
boundValue a

y =
boundValue b
in
case (x < y) of
True ->
b

False ->
case (y < x) of
True ->
a

False ->
-- x == y
andInclusives a b

{-| Return the inner minimum of two Bounds.

minOuterBound (includes 1) (excludes 1) == (excludes 1)

minOuterBound (includes 0) (excludes 1) == (includes 0)

-}
minInnerBound : Bound -> Bound -> Bound
minInnerBound a b =
let
x =
boundValue a

y =
boundValue b
in
case (x < y) of
True ->
a

False ->
case (y < x) of
True ->
b

False ->
-- x == y
andExclusives a b

{-| Return the inner maximum of two Bounds.

maxInnerBound (includes 1) (excludes 1) == (excludes 1)

maxInnerBound (includes 0) (excludes 1) == (includes 0)

-}
maxInnerBound : Bound -> Bound -> Bound
maxInnerBound a b =
let
x =
boundValue a

y =
boundValue b
in
case (x < y) of
True ->
b

False ->
case (y < x) of
True ->
a

False ->
-- x == y
andExclusives a b

{-| If either Bound is Exclusive, return that. Else, both are Inclusive; return the first.
-}
andInclusives : Bound -> Bound -> Bound
andInclusives a b =
case ( a, b ) of
( Inclusive _, Inclusive _ ) ->
a

( Exclusive _, _ ) ->
a

( _, Exclusive _ ) ->
b

{-| If either Bound is Inclusive, return that. Else, both are Exclusive; return the first.
-}
andExclusives : Bound -> Bound -> Bound
andExclusives a b =
case ( a, b ) of
( Exclusive _, Exclusive _ ) ->
a

( Inclusive _, _ ) ->
a

( _, Inclusive _ ) ->
b

{-| The intersection of two intervals. If the intervals overlap, this is the common part. If not, this is the empty interval.
-}
intersection : Interval -> Interval -> Interval
intersection a b =
case ( a, b ) of
( Empty, _ ) ->
Empty

( _, Empty ) ->
Empty

( Degenerate x, Degenerate y ) ->
case (x == y) of
True ->
Degenerate x

False ->
Empty

( Degenerate w, Bounded y z ) ->
interval
(maxOuterBound (includes w) y)
(minOuterBound (includes w) z)

( Bounded w x, Degenerate y ) ->
interval
(maxOuterBound w (includes y))
(minOuterBound x (includes y))

( Bounded w x, Bounded y z ) ->
interval
(maxOuterBound w y)
(minOuterBound x z)

{-| The convex hull of two intervals. This is similar to union in that
it includes all the points of the component intervals, and for
non-overlapping intervals, the points between them.
-}
hull : Interval -> Interval -> Interval
hull a b =
case ( a, b ) of
( Empty, _ ) ->
b

( _, Empty ) ->
a

( Degenerate x, Degenerate y ) ->
interval (includes <| min x y) (includes <| max x y)

( Degenerate w, Bounded y z ) ->
interval
(minInnerBound (includes w) y)
(maxInnerBound (includes w) z)

( Bounded w x, Degenerate y ) ->
interval
(minInnerBound w (includes y))
(maxInnerBound x (includes y))

( Bounded w x, Bounded y z ) ->
interval
(minInnerBound w y)
(maxInnerBound x z)

{-| Extract the value of the lower bound of an Interval.
-}
lowerBoundValue : Interval -> Maybe Float
lowerBoundValue a =
case a of
Empty ->
Nothing

Degenerate n ->
Just n

Bounded l u ->
Just <| boundValue l

{-| Extract the value of the upper bound of an Interval.
-}
upperBoundValue : Interval -> Maybe Float
upperBoundValue a =
case a of
Empty ->
Nothing

Degenerate n ->
Just n

Bounded l u ->
Just <| boundValue l

{-| Do these two intervals intersect?

let
a = interval (includes 1) (excludes 3)
b = interval (includes 2) (includes 4)
c = interval (includes 3) (includes 4)
in
[ intersects a b = True
, intersects a c = False
]

-}
intersects : Interval -> Interval -> Bool
intersects a b =
case ( a, b ) of
( Empty, _ ) ->
False

( _, Empty ) ->
False

( Degenerate x, Degenerate y ) ->
x == y

( Degenerate w, Bounded y z ) ->
(intersection a b) == a

( Bounded w x, Degenerate y ) ->
(intersection a b) == b

( Bounded w x, Bounded y z ) ->
(intersection a b) /= empty

{-| Are these two intervals adjoins? I.e., do they share an upper-lower or
lower-upper bound, exactly one of which is closed, and do not intersect each other?

let
a = interval (includes 1) (excludes 3)  -- [1, 3)
b = interval (includes 2) (includes 4)  -- [3, 4]
c = interval (includes 3) (includes 4)  -- (3, 4]
d = interval (includes 3) (includes 4)  -- [2, 3]
in
[ adjoins a b = True
, adjoins a c = False
, adjoins a d = False
]

-}
adjoins : Interval -> Interval -> Bool
case ( a, b ) of
( Empty, _ ) ->
False

( _, Empty ) ->
False

( Degenerate x, Degenerate y ) ->
False

( Degenerate w, Bounded y z ) ->
(isOpenBound y && w == boundValue y) || (isOpenBound z && w == boundValue z)

( Bounded w x, Degenerate y ) ->
(isOpenBound w && y == boundValue w) || (isOpenBound x && y == boundValue x)

( Bounded w x, Bounded y z ) ->
let
( wOpen, xOpen, yOpen, zOpen ) =
( isOpenBound w, isOpenBound x, isOpenBound y, isOpenBound z )

upperLowerMatch =
(xOpen |> xor yOpen)
&& (boundValue x == boundValue y)

lowerUpperMatch =
(wOpen |> xor zOpen)
&& (boundValue w == boundValue z)
in
not (a |> intersects b) && (upperLowerMatch || lowerUpperMatch)

{-| Does this interval contain the given point?

let
a = interval (includes 1) (excludes 3)
in
[ intersectsPoint a 0 = False
, intersectsPoint a 1 = True
, intersectsPoint a 3 = False
]

-}
intersectsPoint : Interval -> Float -> Bool
intersectsPoint a n =
case a of
Empty ->
False

Degenerate x ->
x == n

Bounded w x ->
intersection a (degenerate n) == (degenerate n)

{-| Does this interval have finite bounds?
-}
isBounded : Interval -> Bool
isBounded a =
case a of
Empty ->
False

Degenerate x ->
not <| isInfinite x

Bounded x y ->
not <| isInfinite (boundValue x) || isInfinite (boundValue y)

{-| Is this a degenerate (point-valued) interval?
-}
isDegenerate : Interval -> Bool
isDegenerate a =
case a of
Degenerate _ ->
True

Empty ->
False

Bounded _ _ ->
False

{-| Is this an empty interval?
-}
isEmpty : Interval -> Bool
isEmpty a =
case a of
Empty ->
True

Degenerate _ ->
False

Bounded _ _ ->
False

{-| Does this interval have a finite lower bound, and an infinite upper bound?
-}
isLeftBounded : Interval -> Bool
isLeftBounded a =
case a of
Empty ->
False

Degenerate x ->
False

Bounded x y ->
(not <| isInfinite (boundValue x)) && isInfinite (boundValue y)

{-| Does this interval have a finite upper bound, and an infinite lower bound?
-}
isRightBounded : Interval -> Bool
isRightBounded a =
case a of
Empty ->
False

Degenerate x ->
False

Bounded x y ->
(not <| isInfinite (boundValue y)) && isInfinite (boundValue x)

{-| Is this interval unbounded?
-}
isUnbounded : Interval -> Bool
isUnbounded a =
case a of
Empty ->
False

Degenerate _ ->
False

Bounded lower upper ->
(isInfinite <| boundValue lower) && (isInfinite <| boundValue upper)

isOpenBound : Bound -> Bool
isOpenBound b =
case b of
Inclusive _ ->
False

Exclusive _ ->
True

{-| Is the lower bound of this interval open?
-}
isLeftOpen : Interval -> Bool
isLeftOpen a =
case a of
Empty ->
False

Degenerate _ ->
False

Bounded lower upper ->
isOpenBound lower

{-| Is the upper bound of this interval open?
-}
isRightOpen : Interval -> Bool
isRightOpen a =
case a of
Empty ->
False

Degenerate _ ->
False

Bounded lower upper ->
isOpenBound upper

{-| Returns the largest open interval contained within a.

-- `interior([x, y]) == (x, y)`
interior (interval (includes 0) (includes 2)) == interval (excludes 0) (excludes 2)

-}
interior : Interval -> Interval
interior a =
case a of
Empty ->
empty

Degenerate _ ->
empty

Bounded x y ->
let
t =
boundValue x

u =
boundValue y
in
interval (excludes t) (excludes u)

{-| Returns the smallest closed interval containing a.

-- `closure((x, y)) == [x, y]`
interior (interval (excludes 0) (excludes 2)) == interval (includes 0) (includes 2)

-}
closure : Interval -> Interval
closure a =
case a of
Empty ->
empty

Degenerate _ ->
a

Bounded x y ->
let
t =
boundValue x

u =
boundValue y
in
interval (includes t) (includes u)

{-| Subtract interval `b` from interval `a`, returning a list of the parts of
`a` that did not intersect with `b`.

E.g.:

- [1, 3) - (1, 2] = [ {1}, (2, 3) ]

-}
subtract : Interval -> Interval -> List Interval
subtract a b =
if (a |> intersects b) then
case ( a, b ) of
( _, Empty ) ->
[ a ]

( Empty, _ ) ->
[]

( Degenerate w, _ ) ->
[]

( Bounded w x, Degenerate y ) ->
-- ?w, x? - {y} = [ ?w, y), (y, x? ]
[ interval w (excludes y)
, interval (excludes y) x
]

( Bounded w x, Bounded y z ) ->
let
left =
if (minInnerBound w y == w && w /= y) then
[ interval w (invertBound y) ]
else
[]

right =
if (maxInnerBound x z == x && x /= z) then
[ interval (invertBound z) x ]
else
[]
in
List.append left right
else
[ a ]

{-| Hold the bound value steady, but invert the open/closed property.
-}
invertBound : Bound -> Bound
invertBound b =
case b of
Inclusive n ->
Exclusive n

Exclusive n ->
Inclusive n
```
```