Interval v0.3.4

View Source Interval (Interval v0.3.4)

An interval represents the points between two endpoints.

The interval can be empty. The empty interval is never contained in any other interval, and itself contains no points.

It can be left and/or right unbounded, in which case it contains all points in the unbounded direction. A fully unbounded interval contains all other intervals, except the empty interval.

features

 Features

The key features of this library are

interval-notation

 Interval Notation

Throughout the documentation and comments, you'll see a notation for writing about intervals. As this library is inspired by the functionality in PostgreSQL's range types, we align ourselves with it's notation choice and borrow it (https://www.postgresql.org/docs/current/rangetypes.html)

This notation is also described in ISO 31-11.

[left-inclusive, right-inclusive]
(left-exclusive, right-exclusive)
[left-inclusive, right-exclusive)
(left-exclusive, right-inclusive]
:empty

An unbounded interval is written by omitting the bound type and point:

,right-exclusive)
[left-inclusive,

When specifying bound types we sometimes leave the point out and just write the left and right bounds:

[]
()
(]
[)
(
)
[
]

types-of-interval

 Types of Interval

This library ships with a few different types of intervals. The built-in intervals are:

However, you can quite easily implement an interval by implementing the Interval.Behaviour.

The easiest way to do so, is by using the Interval.__using__ macro:

defmodule MyInterval do
  use Interval, type: MyType, discrete: false
end

You must implement a few functions defined in Interval.Behaviour. Once that's done, all operations available in the Interval module (like interesection, union, overlap etc) will work on your interval struct.

An obvious usecase for this would be to implement an interval that works with the https://hexdocs.pm/decimal library.

discrete-vs-continuous-intervals

 Discrete vs Continuous intervals

Depending on the behaviour you want from your interval, it is either said to be discrete or continuous.

A discrete interval represents a set of finite points (like integers). A continuous interval can be said to represent the infinite number of points between two endpoints (like an interval between two floats).

With discrete points, it is possible to define what the next and previous point is, and we normalise these intervals to the bound type [).

The distinction between a discrete and continuous interval is important because the two behave slightly different in some of the library functions.

A discrete interval is adjacent to another discrete interval, if there is no points between the two interval. Contrast this to continuous intervals of real numbers where there is always an infinite number of real numbers between two distinct real numbers, and so continuous intervals are only said to be adjacent to each other if they include the same point, and one point is inclusive where the other is exclusive.

Where relevant, the function documentation will mention the differences between discrete and continuous intervals.

create-an-interval

 Create an Interval

See new/1.

normalization

 Normalization

When creating an interval through new/1, it will get normalized so that intervals that represents the same points, are also represented in the same way in the struct. This allows you to compare two intervals for equality by using == (and using pattern matching).

It is therefore not recommended to modify an interval struct directly, but instead do so by using one of the functions that modify the interval.

An interval is said to be empty if it spans zero points. The normalized form of an empty interval is the special interval struct where left and right is set to :empty, however a non-normalized empty struct will still correctly report empty via the empty?/1 function.

Link to this section Summary

Types

bound()

The bound type of an endpoint.

point()

A point in an interval.

t()

Shorthand for t(any())

t(point)

An interval struct, representing all points between two endpoints.

Functions

__using__(opts)

Define an interval struct of a specific point type.

adjacent_left_of?(a, b)

Is the interval a adjacent to b, to the left of b.

adjacent_right_of?(a, b)

Is the interval a adjacent to b, to the right of b.

contains_point?(a, x)

Does a contain the point x?

contains?(a, b)

Does a contain b?

empty?(a)

Is the interval empty?

inclusive_left?(map)

Is the interval left-inclusive?

inclusive_right?(map)

Is the interval right-inclusive?

intersection(a, b)

Compute the intersection between a and b.

left(map)

Return the left point.

new(opts)

Create a new interval.

overlaps?(a, b)

Does a overlap with b?

partition(a, x)

Partition an interval a into 3 intervals using x

right(map)

Return the right point.

size(a)
strictly_left_of?(a, b)

Is a strictly left of b.

strictly_right_of?(a, b)

Is a strictly right of b.

to_map(a)

Convert an Interval.t/0 to a map.

unbounded_left?(map)

Check if the interval is left-unbounded.

unbounded_right?(map)

Check if the interval is right-unbounded.

union(a, b)

Computes the union of a and b.

Link to this section Types

Link to this type

bound()

View Source 
@type bound() :: :inclusive | :exclusive

The bound type of an endpoint.

Link to this type

point()

View Source 
@type point() :: any()

A point in an interval.

Link to this type

t()

View Source 
@type t() :: t(any())

Shorthand for t(any())

Link to this type

t(point)

View Source 
@type t(point) :: %{
  __struct__: atom(),
  left: :empty | :unbounded | {bound(), point},
  right: :empty | :unbounded | {bound(), point}
}

An interval struct, representing all points between two endpoints.

The struct has two fields: left and right, representing the left (lower) and right (upper) points in the interval.

If either left or right is set to :empty, the both must be set to :empty.

The specific struct type depends on the interval implementation, but the left and right field is always present, all will be manipulated by the Interval module regardless of the interval implementation.

Link to this section Functions

Link to this macro

__using__(opts)

View Source (macro)

Define an interval struct of a specific point type.

Support for Ecto.Type and the Postgrex.Range can be automatically generated by specifying ecto_type: <type> when useing.

options

 Options

  • type - The internal point type in this interval. required
  • discrete - Is this interval discrete? default: false
  • jason_encoder - Should it include Jason.Encoder implementation? default: true

examples

 Examples 

defmodule MyInterval do
  use Interval, type: MyType, discrete: false
end
Link to this function

adjacent_left_of?(a, b)

View Source 
@spec adjacent_left_of?(t(), t()) :: boolean()

Is the interval a adjacent to b, to the left of b.

a is adjacent to b left of b, if a and b do not overlap, and there are no points between a.right and b.left.

# a: [---)
# b:     [---)
# r: true

# a: [---]
# b:     [---]
# r: false (overlaps)

# a: (---)
# b:        (---)
# r: false (points exist between a.right and b.left)

examples

 Examples 

iex> adjacent_left_of?(new(module: Interval.Integer, left: 1, right: 2), new(module: Interval.Integer, left: 2, right: 3))
true

iex> adjacent_left_of?(new(module: Interval.Integer, left: 1, right: 3), new(module: Interval.Integer, left: 2, right: 4))
false

iex> adjacent_left_of?(new(module: Interval.Integer, left: 3, right: 4), new(module: Interval.Integer, left: 1, right: 2))
false

iex> adjacent_left_of?(new(module: Interval.Integer, right: 2, bounds: "[]"), new(module: Interval.Integer, left: 3))
true
Link to this function

adjacent_right_of?(a, b)

View Source 
@spec adjacent_right_of?(t(), t()) :: boolean()

Is the interval a adjacent to b, to the right of b.

a is adjacent to b right of b, if a and b do not overlap, and there are no points between a.left and b.right.

# a:     [---)
# b: [---)
# r: true

# a:     [---)
# b: [---]
# r: false (overlaps)

# a:        (---)
# b: (---)
# r: false (points exist between a.left and b.right)

examples

 Examples 

iex> adjacent_right_of?(new(module: Interval.Integer, left: 2, right: 3), new(module: Interval.Integer, left: 1, right: 2))
true

iex> adjacent_right_of?(new(module: Interval.Integer, left: 1, right: 3), new(module: Interval.Integer, left: 2, right: 4))
false

iex> adjacent_right_of?(new(module: Interval.Integer, left: 1, right: 2), new(module: Interval.Integer, left: 3, right: 4))
false

iex> adjacent_right_of?(new(module: Interval.Integer, left: 3), new(module: Interval.Integer, right: 2, bounds: "]"))
true
Link to this function

contains_point?(a, x)

View Source (since 0.1.4) 
@spec contains_point?(t(), point()) :: boolean()

Does a contain the point x?

examples

 Examples 

iex> contains_point?(new(module: Interval.Integer, left: 1, right: 2), 0)
false

iex> contains_point?(new(module: Interval.Integer, left: 1, right: 2), 1)
true
Link to this function

contains?(a, b)

View Source 
@spec contains?(t(), t()) :: boolean()

Does a contain b?

a contains b of all points in b is also in a.

For an interval a to contain an interval b, all points in b must be contained in a:

# a: [-------]
# b:   [---]
# r: true

# a: [---]
# b: [---]
# r: true

# a: [---]
# b: (---)
# r: true

# a: (---)
# b: [---]
# r: false

# a:   [---]
# b: [-------]
# r: false

This means that a.left is less than b.left (or unbounded), and a.right is greater than b.right (or unbounded)

If a and b's point match, then b is "in" a if a and b share bound types.

E.g. if a.left and b.left matches, then a contains b if both a and b's left is inclusive or exclusive.

If either of b endpoints are unbounded, then a only contains b if the corresponding endpoint in a is also unbounded.

examples

 Examples 

iex> contains?(new(module: Interval.Integer, left: 1, right: 2), new(module: Interval.Integer, left: 1, right: 2))
true

iex> contains?(new(module: Interval.Integer, left: 1, right: 3), new(module: Interval.Integer, left: 2, right: 3))
true

iex> contains?(new(module: Interval.Integer, left: 2, right: 3), new(module: Interval.Integer, left: 1, right: 4))
false

iex> contains?(new(module: Interval.Integer, left: 1, right: 3), new(module: Interval.Integer, left: 1, right: 2))
true

iex> contains?(new(module: Interval.Integer, left: 1, right: 2, bounds: "()"), new(module: Interval.Integer, left: 1, right: 3))
false

iex> contains?(new(module: Interval.Integer, right: 1), new(module: Interval.Integer, left: 0, right: 1))
true
Link to this function

empty?(a)

View Source 
@spec empty?(t()) :: boolean()

Is the interval empty?

An empty interval is an interval that represents no points. Any interval containing no points is considered empty.

An unbounded interval is never empty.

For continuous points, the interval is empty when the left and right points are identical, and the point is not included in the interval.

For discrete points, the interval is empty when the left and right point isn't inclusive, and there are no points between the left and right point.

examples

 Examples 

iex> empty?(new(module: Interval.Integer, left: 0, right: 0))
true

iex> empty?(new(module: Interval.Float, left: 1.0))
false

iex> empty?(new(module: Interval.Integer, left: 1, right: 2))
false
Link to this function

inclusive_left?(map)

View Source 
@spec inclusive_left?(t()) :: boolean()

Is the interval left-inclusive?

The interval is left-inclusive if the left endpoint value is included in the interval.

Note

Discrete intervals (like Interval.Integer and Interval.Date) are always normalized to be left-inclusive right-exclusive ([)).

iex> inclusive_left?(new(module: Interval.Float, left: 1.0, right: 2.0, bounds: "[]"))
true

iex> inclusive_left?(new(module: Interval.Float, left: 1.0, right: 2.0, bounds: "[)"))
true

iex> inclusive_left?(new(module: Interval.Float, left: 1.0, right: 2.0, bounds: "()"))
false
Link to this function

inclusive_right?(map)

View Source 
@spec inclusive_right?(t()) :: boolean()

Is the interval right-inclusive?

The interval is right-inclusive if the right endpoint value is included in the interval.

Note

Discrete intervals (like Interval.Integer and Interval.Date) are always normalized to be left-inclusive right-exclusive ([)).

iex> inclusive_right?(new(module: Interval.Float, left: 1.0, right: 2.0, bounds: "[]"))
true

iex> inclusive_right?(new(module: Interval.Float, left: 1.0, right: 2.0, bounds: "[)"))
false

iex> inclusive_right?(new(module: Interval.Float, left: 1.0, right: 2.0, bounds: "()"))
false
Link to this function

intersection(a, b)

View Source 
@spec intersection(t(), t()) :: t()

Compute the intersection between a and b.

The intersection contains all of the points that are both in a and b.

If either a or b are empty, the returned interval will be empty.

# a: [----]
# b:    [----]
# r:    [-]

# a: (----)
# b:    (----)
# r:    (-)

# a: [----)
# b:    [----)
# r:    [-)

examples

 Examples:

Discrete:

# a: [----)
# b:    [----)
# c:    [-)
iex> intersection(new(module: Interval.Integer, left: 1, right: 3), new(module: Interval.Integer, left: 2, right: 4))
new(module: Interval.Integer, left: 2, right: 3)

Continuous:

# a: [----)
# b:    [----)
# c:    [-)
iex> intersection(new(module: Interval.Float, left: 1.0, right: 3.0), new(module: Interval.Float, left: 2.0, right: 4.0))
new(module: Interval.Float, left: 2.0, right: 3.0)

# a: (----)
# b:    (----)
# c:    (-)
iex> intersection(
...>   new(module: Interval.Float, left: 1.0, right: 3.0, bounds: "()"),
...>   new(module: Interval.Float, left: 2.0, right: 4.0, bounds: "()")
...> )
new(module: Interval.Float, left: 2.0, right: 3.0, bounds: "()")

# a: [-----)
# b:   [-------
# c:   [---)
iex> intersection(new(module: Interval.Float, left: 1.0, right: 3.0), new(module: Interval.Float, left: 2.0))
new(module: Interval.Float, left: 2.0, right: 3.0)
Link to this function

left(map)

View Source 
@spec left(t()) :: point()

Return the left point.

This function always returns nil when no point exist. Use the functions empty?/1, inclusive_left?/1 and unbounded_left?/1 to check for the meaning of the point.

example

 Example 

iex> left(new(module: Interval.Integer, left: 1, right: 2))
1
Link to this function

new(opts)

View Source 
@spec new(Keyword.t()) :: t()

Create a new interval.

options

 Options

  • module The interval implementation to use. When calling new/1 from a Interval.Behaviour this is inferred.
  • left The left (or lower) endpoint of the interval
  • right The right (or upper) endpoint of the interval
  • bounds The bound mode to use. Defaults to "[)"

A nil (left or right) endpoint is considered unbounded. The endpoint will also be considered unbounded if the bounds is explicitly set as unbounded.

A special value :empty can be given to left and right to construct an empty interval.

bounds

 Bounds

The bounds options contains the left and right bound mode to use. The bound can be inclusive, exclusive or unbounded.

The following valid bound values are supported:

  • "[)" left-inclusive, right-exclusive (default)
  • "(]" left-exclusive, right-inclusive
  • "[]" left-inclusive, right-inclusive
  • "()" left-exclusive, right-exclusive
  • ")" left-unbounded, right-exclusive
  • "]" left-unbounded, right-inclusive
  • "(" left-exclusive, right-unbounded
  • "[" left-inclusive, right-unbounded

examples

 Examples 

iex> new(module: Interval.Integer)

iex> new(module: Interval.Integer, left: :empty, right: :empty)

iex> new(module: Interval.Integer, left: 1)

iex> new(module: Interval.Integer, left: 1, right: 1, bounds: "[]")

iex> new(module: Interval.Integer, left: 10, right: 20, bounds: "()")
Link to this function

overlaps?(a, b)

View Source 
@spec overlaps?(t(), t()) :: boolean()

Does a overlap with b?

a overlaps with b if any point in a is also in b.

# a: [---)
# b:   [---)
# r: true

# a: [---)
# b:     [---)
# r: false

# a: [---]
# b:     [---]
# r: true

# a: (---)
# b:     (---)
# r: false

# a: [---)
# b:        [---)
# r: false

examples

 Examples 

# [--a--)
#     [--b--)

iex> overlaps?(new(module: Interval.Integer, left: 1, right: 3), new(module: Interval.Integer, left: 2, right: 4))
true


# [--a--)
#       [--b--)

iex> overlaps?(new(module: Interval.Integer, left: 1, right: 3), new(module: Interval.Integer, left: 3, right: 5))
false


# [--a--]
#       [--b--]

iex> overlaps?(new(module: Interval.Integer, left: 1, right: 3), new(module: Interval.Integer, left: 2, right: 4))
true


# (--a--)
#       (--b--)

iex> overlaps?(new(module: Interval.Integer, left: 1, right: 3), new(module: Interval.Integer, left: 3, right: 5))
false


# [--a--)
#          [--b--)

iex> overlaps?(new(module: Interval.Integer, left: 1, right: 2), new(module: Interval.Integer, left: 3, right: 4))
false
Link to this function

partition(a, x)

View Source (since 0.1.4) 
@spec partition(t(), point()) :: [t()] | []

Partition an interval a into 3 intervals using x:

  • The interval with all points from a < x
  • The interval with just x
  • The interval with all points from a > x

If x is not in a this function returns an empty list.

examples

 Examples 

iex> partition(new(module: Interval.Integer, left: 1, right: 5, bounds: "[]"), 3)
[
  new(module: Interval.Integer, left: 1, right: 3, bounds: "[)"),
  new(module: Interval.Integer, left: 3, right: 3, bounds: "[]"),
  new(module: Interval.Integer, left: 3, right: 5, bounds: "(]")
]

iex> partition(new(module: Interval.Integer, left: 1, right: 5), -10)
[]
Link to this function

right(map)

View Source 
@spec right(t()) :: point()

Return the right point.

This function always returns nil when no point exist. Use the functions empty?/1, inclusive_right?/1 and unbounded_right?/1 to check for the meaning of the point.

example

 Example 

iex> right(new(module: Interval.Integer, left: 1, right: 2))
2
Link to this function

size(a)

View Source (since 0.1.3) 
@spec size(t()) :: any()
Link to this function

strictly_left_of?(a, b)

View Source 
@spec strictly_left_of?(t(), t()) :: boolean()

Is a strictly left of b.

a is strictly left of b if no point in a is in b, and all points in a is left (<) of all points in b.

examples

 Examples 

# a: [---)
# b:     [---)
# r: true

# a: [---)
# b:        [---)
# r: true

# a: [---)
# b:    [---)
# r: false (overlaps)

iex> strictly_left_of?(new(module: Interval.Integer, left: 1, right: 2), new(module: Interval.Integer, left: 3, right: 4))
true

iex> strictly_left_of?(new(module: Interval.Integer, left: 1, right: 3), new(module: Interval.Integer, left: 2, right: 4))
false

iex> strictly_left_of?(new(module: Interval.Integer, left: 3, right: 4), new(module: Interval.Integer, left: 1, right: 2))
false
Link to this function

strictly_right_of?(a, b)

View Source 
@spec strictly_right_of?(t(), t()) :: boolean()

Is a strictly right of b.

a is strictly right of b if no point in a is in b, and all points in a is right (>) of all points in b.

examples

 Examples 

# a:     [---)
# b: [---)
# r: true

# a:        [---)
# b: [---)
# r: true

# a:    [---)
# b: [---)
# r: false (overlaps)

iex> strictly_right_of?(new(module: Interval.Integer, left: 1, right: 2), new(module: Interval.Integer, left: 3, right: 4))
false

iex> strictly_right_of?(new(module: Interval.Integer, left: 1, right: 3), new(module: Interval.Integer, left: 2, right: 4))
false

iex> strictly_right_of?(new(module: Interval.Integer, left: 3, right: 4), new(module: Interval.Integer, left: 1, right: 2))
true
Link to this function

to_map(a)

View Source (since 0.3.0) 
@spec to_map(t()) :: %{
  type: String.t(),
  empty: boolean(),
  left: nil | %{inclusive: boolean(), value: any()},
  right: nil | %{inclusive: boolean(), value: any()}
}

Convert an Interval.t/0 to a map.

The returned map contains the struct module used for the interval in the type key, so that it is possible to reconstruct the interval from the map.

Link to this function

unbounded_left?(map)

View Source 
@spec unbounded_left?(t()) :: boolean()

Check if the interval is left-unbounded.

The interval is left-unbounded if all points left of the right bound is included in this interval.

examples

 Examples 

iex> unbounded_left?(new(module: Interval.Integer))
true

iex> unbounded_left?(new(module: Interval.Integer, right: 2))
true

iex> unbounded_left?(new(module: Interval.Integer, left: 1, right: 2))
false
Link to this function

unbounded_right?(map)

View Source 
@spec unbounded_right?(t()) :: boolean()

Check if the interval is right-unbounded.

The interval is right-unbounded if all points right of the left bound is included in this interval.

examples

 Examples 

iex> unbounded_right?(new(module: Interval.Integer, right: 1))
false

iex> unbounded_right?(new(module: Interval.Integer))
true

iex> unbounded_right?(new(module: Interval.Integer, left: 1))
true
Link to this function

union(a, b)

View Source 
@spec union(t(), t()) :: t()

Computes the union of a and b.

The union contains all of the points that are either in a or b.

If either a or b are empty, the returned interval will be empty.

# a: [---)
# b:   [---)
# r: [-----)

examples

 Examples 

# [--A--)
#     [--B--)
# [----C----)

iex> union(new(module: Interval.Integer, left: 1, right: 3), new(module: Interval.Integer, left: 2, right: 4))
new(module: Interval.Integer, left: 1, right: 4)


# [-A-)
#     [-B-)
# [---C---)

iex> union(new(module: Interval.Integer, left: 1, right: 2), new(module: Interval.Integer, left: 2, right: 3))
new(module: Interval.Integer, left: 1, right: 3)

iex> union(new(module: Interval.Integer, left: 1, right: 2), new(module: Interval.Integer, left: 3, right: 4))
new(module: Interval.Integer, left: 0, right: 0)