interval.ex

defmodule Interval do
  @moduledoc """
  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

  The key features of this library are

  - Common interval operations built in are
    - `intersection/2`
    - `union/2`
    - `overlaps?/2`
    - `contains?/2`
    - `partition/2`
    - adjacent?
    - empty?
    - unbounded?
  - Built in support for intervals containing
      - `Integer`
      - `Float`
      - `Date`
      - `DateTime`
      - `NaiveDateTime`
      - `Decimal`
  - Also implements
    - `Ecto.Type`
    - `Jason.Encoder`

  ## 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

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

  - `Interval.Date` containing points of type `Date`
  - `Interval.DateTime` containing points of type `DateTime`
  - `Interval.NaiveDateTime` containing points of type `NaiveDateTime`
  - `Interval.Float` containing points of type `Float`
  - `Interval.Integer` containing points of type `Integer`
  - `Interval.Decimal` containing points of type `Decimal` (See https://hexdocs.pm/decimal/2.0.0)

  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

  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

  See `new/1`.

  ## 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.
  """

  @typedoc """
  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.
  """
  @type t(point) :: %{
          __struct__: atom(),
          # Left endpoint
          left: :empty | :unbounded | {bound(), point},
          # Right  endpoint
          right: :empty | :unbounded | {bound(), point}
        }

  @typedoc """
  Shorthand for `t(any())`
  """
  @type t() :: t(any())

  @typedoc """
  A point in an interval.
  """
  @type point() :: any()

  @typedoc """
  The bound type of an endpoint.
  """
  @type bound() :: :inclusive | :exclusive

  @doc """
  Create a new interval.

  ## 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

  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

      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: "()")
  """
  @spec new(Keyword.t()) :: t()
  def new(opts) when is_list(opts) do
    module = Keyword.get(opts, :module, nil)
    left = Keyword.get(opts, :left, nil)
    right = Keyword.get(opts, :right, nil)
    bounds = Keyword.get(opts, :bounds, nil)
    {left_bound, right_bound} = unpack_bounds(bounds)

    module = module || infer_implementation([left, right])

    if is_nil(module) do
      raise ArgumentError,
        message: "No implementation for interval available. Options given: #{inspect(opts)}"
    end

    left_endpoint = normalize_bound(left, left_bound)
    right_endpoint = normalize_bound(right, right_bound)

    module
    |> struct!(left: left_endpoint, right: right_endpoint)
    |> normalize()
  end

  defp normalize_bound(point, bound) do
    case {point, bound} do
      {:empty, _} -> :empty
      {nil, _} -> :unbounded
      {:unbound, _} -> :unbounded
      {_, :unbounded} -> :unbounded
      {_, :inclusive} -> {:inclusive, point}
      {_, :exclusive} -> {:exclusive, point}
    end
  end

  @doc """
  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

      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

  """
  @spec empty?(t()) :: boolean()
  def empty?(a)
  def empty?(%{left: :unbounded}), do: false
  def empty?(%{right: :unbounded}), do: false
  def empty?(%{left: :empty, right: :empty}), do: true

  # If the interval is not properly normalized, we don't want to give an
  # incorrect answer, so we do the math to check if the interval is indeed empty:
  def empty?(%{
        left: {:exclusive, p},
        right: {:exclusive, p}
      }) do
    true
  end

  def empty?(%module{
        left: {left_bound, left_point},
        right: {right_bound, right_point}
      }) do
    compare = module.point_compare(left_point, right_point)

    cond do
      # left and right is equal, then the interval is empty
      # if the point is not included in the interval.
      # We don't want to rely on normalized intervals in empty?/1
      # in this function body, because if the interval was already normalized,
      # we'd only have to check for the `(zero,zero)` interval.
      # Therefore we must assume that the bounds could be incorrectly set to e.g. [p,p)
      compare == :eq ->
        left_bound == :exclusive or right_bound == :exclusive

      # if the point type is discrete and both bounds are exclusive,
      # then the interval could _also_ be empty if next(left) == right,
      # because the interval would represent 0 points.
      module.discrete?() and
        left_bound == :exclusive and right_bound == :exclusive ->
        :eq ==
          left_point
          |> module.point_step(+1)
          |> module.point_compare(right_point)

      # If none of the above, then the interval is not empty
      true ->
        false
    end
  end

  @doc """
  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

      iex> left(new(module: Interval.Integer, left: 1, right: 2))
      1
  """
  @compile {:inline, left: 1}
  @spec left(t()) :: point()
  def left(%{left: {_, value}}), do: value
  def left(%{left: _}), do: nil

  @doc """
  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

      iex> right(new(module: Interval.Integer, left: 1, right: 2))
      2
  """
  @compile {:inline, right: 1}
  @spec right(t()) :: point()
  def right(%{right: {_, value}}), do: value
  def right(%{right: _}), do: nil

  @doc """
  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

      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

  """
  @spec unbounded_left?(t()) :: boolean()
  def unbounded_left?(%{left: :unbounded}), do: true
  def unbounded_left?(%{}), do: false

  @doc """
  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

      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

  """
  @spec unbounded_right?(t()) :: boolean()
  def unbounded_right?(%{right: :unbounded}), do: true
  def unbounded_right?(%{}), do: false

  @doc """
  Is the interval left-inclusive?

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

  > #### Note {: .info}
  > 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

  """
  @spec inclusive_left?(t()) :: boolean()
  def inclusive_left?(%{left: {:inclusive, _}}), do: true
  def inclusive_left?(%{}), do: false

  @doc """
  Is the interval right-inclusive?

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

  > #### Note {: .info}
  > 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

  """
  @spec inclusive_right?(t()) :: boolean()
  def inclusive_right?(%{right: {:inclusive, _}}), do: true
  def inclusive_right?(%{}), do: false

  @doc since: "0.1.3"
  @spec size(t()) :: any()
  def size(%module{} = a), do: module.size(a)

  @doc """
  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

      # 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
  """
  @spec strictly_left_of?(t(), t()) :: boolean()
  def strictly_left_of?(%module{} = a, %module{} = b) do
    not unbounded_right?(a) and
      not unbounded_left?(b) and
      not empty?(a) and
      not empty?(b) and
      case module.point_compare(right(a), left(b)) do
        :lt -> true
        :eq -> not inclusive_right?(a) or not inclusive_left?(b)
        :gt -> false
      end
  end

  @doc """
  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

      # 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
  """
  @spec strictly_right_of?(t(), t()) :: boolean()
  def strictly_right_of?(%module{} = a, %module{} = b) do
    not unbounded_left?(a) and
      not unbounded_right?(b) and
      not empty?(a) and
      not empty?(b) and
      case module.point_compare(left(a), right(b)) do
        :lt -> false
        :eq -> not inclusive_left?(a) or not inclusive_right?(b)
        :gt -> true
      end
  end

  @doc """
  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


      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
  """
  @spec adjacent_left_of?(t(), t()) :: boolean()
  def adjacent_left_of?(%module{} = a, %module{} = b) do
    prerequisite =
      not unbounded_right?(a) and
        not unbounded_left?(b) and
        not empty?(a) and
        not empty?(b)

    with true <- prerequisite do
      # Assuming we've normalized both a and b,
      # if the point types are discrete, and and normalized to `[)`
      # then continuous and discrete intervals are checked in the same way.
      # To ensure we don't give the wrong answer though,
      # we have an assertion that that a discrete point type must be
      # bounded as `[)`:
      assert_normalized_bounds(a)
      assert_normalized_bounds(b)

      inclusive_right?(a) != inclusive_left?(b) and
        module.point_compare(right(a), left(b)) == :eq
    end
  end

  @doc """
  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

      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
  """
  @spec adjacent_right_of?(t(), t()) :: boolean()
  def adjacent_right_of?(%module{} = a, %module{} = b) do
    prerequisite =
      not unbounded_left?(a) and
        not unbounded_right?(b) and
        not empty?(a) and
        not empty?(b)

    with true <- prerequisite do
      # Assuming we've normalized both a and b,
      # if the point types are discrete, and and normalized to `[)`
      # then continuous and discrete intervals are checked in the same way.
      # To ensure we don't give the wrong answer though,
      # we have an assertion that that a discrete point type must be
      # bounded as `[)`:
      assert_normalized_bounds(a)
      assert_normalized_bounds(b)

      module.point_compare(left(a), right(b)) == :eq and
        inclusive_left?(a) != inclusive_right?(b)
    end
  end

  @doc """
  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

      # [--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
  """
  @spec overlaps?(t(), t()) :: boolean()
  def overlaps?(%module{} = a, %module{} = b) do
    not empty?(a) and
      not empty?(b) and
      not strictly_left_of?(a, b) and
      not strictly_right_of?(a, b)
  end

  @doc """
  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

      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
  """
  @spec contains?(t(), t()) :: boolean()
  def contains?(%module{} = a, %module{} = b) do
    # Neither A or B must be empty, so that's a prerequisite for
    # even checking anything.
    prerequisite = not (empty?(a) or empty?(b))

    with true <- prerequisite do
      # check that left(a) is less than or equal to (if inclusive) left(b):
      contains_left =
        unbounded_left?(a) or
          (not unbounded_left?(b) and
             case module.point_compare(left(a), left(b)) do
               :gt -> false
               :eq -> inclusive_left?(a) == inclusive_left?(b)
               :lt -> true
             end)

      # check that right(a) is greater than or equal to (if inclusive) right(b):
      contains_right =
        unbounded_right?(a) or
          (not unbounded_right?(b) and
             case module.point_compare(right(a), right(b)) do
               :gt -> true
               :eq -> inclusive_right?(a) == inclusive_right?(b)
               :lt -> false
             end)

      # a contains b if both the left check and right check passes:
      contains_left and contains_right
    end
  end

  @doc """
  Does `a` contain the point `x`?

  ## 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
  """
  @doc since: "0.1.4"
  @spec contains_point?(t(), point()) :: boolean()
  def contains_point?(%module{} = a, x) do
    with true <- not empty?(a) do
      contains_left =
        unbounded_left?(a) or
          case module.point_compare(left(a), x) do
            :gt -> false
            :eq -> inclusive_left?(a)
            :lt -> true
          end

      contains_right =
        unbounded_right?(a) or
          case module.point_compare(right(a), x) do
            :gt -> true
            :eq -> inclusive_right?(a)
            :lt -> false
          end

      contains_left and contains_right
    end
  end

  @doc """
  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

      # [--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)
  """
  @spec union(t(), t()) :: t()
  def union(%module{} = a, %module{} = b) do
    cond do
      # if either is empty, return the other
      empty?(a) ->
        b

      empty?(b) ->
        a

      # if a and b overlap or are adjacent, we can union the intervals
      overlaps?(a, b) or adjacent_left_of?(a, b) or adjacent_right_of?(a, b) ->
        left = pick_union_left(module, a.left, b.left)
        right = pick_union_right(module, a.right, b.right)

        from_endpoints(module, left, right)

      # fall-through, if neither A or B is empty,
      # but there is also no overlap or adjacency,
      # then the two intervals are either strictly left or strictly right,
      # we return empty (A and B share an empty amount of points)
      true ->
        # This assertion _must_ be true, since overlap?/2 returned false
        # so there is no point in running it.
        # true == strictly_left_of?(a, b) or strictly_right_of?(a, b)
        new_empty(module)
    end
  end

  @doc """
  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:

  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)

  """
  @spec intersection(t(), t()) :: t()
  def intersection(%module{} = a, %module{} = b) do
    cond do
      # if A is empty, we return A
      empty?(a) ->
        a

      # if B is empty, we return B
      empty?(b) ->
        b

      # if A and B doesn't overlap,
      # then there can be no intersection
      not overlaps?(a, b) ->
        new_empty(module)

      # otherwise, we can compute the intersection
      true ->
        # The intersection between `a` and `b` is the points that exist in
        # both `a` and `b`.
        left = pick_intersection_left(module, a.left, b.left)
        right = pick_intersection_right(module, a.right, b.right)
        from_endpoints(module, left, right)
    end
  end

  @doc """
  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

      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)
      []
  """
  @doc since: "0.1.4"
  @spec partition(t(), point()) :: [t()] | []
  def partition(%module{} = a, x) do
    case contains_point?(a, x) do
      false ->
        []

      true ->
        [
          from_endpoints(module, a.left, {:exclusive, x}),
          from_endpoints(module, {:inclusive, x}, {:inclusive, x}),
          from_endpoints(module, {:exclusive, x}, a.right)
        ]
    end
  end

  @doc """
  Convert an `t: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.
  """
  @doc 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()}
        }
  def to_map(%module{} = a) do
    empty? = Interval.empty?(a)

    %{
      type: Module.split(module) |> Enum.join("."),
      empty: empty?,
      left:
        if(not Interval.unbounded_left?(a) and not empty?,
          do: %{
            inclusive: Interval.inclusive_left?(a),
            value: Interval.left(a)
          }
        ),
      right:
        if(not Interval.unbounded_right?(a) and not empty?,
          do: %{
            inclusive: Interval.inclusive_right?(a),
            value: Interval.right(a)
          }
        )
    }
  end

  @doc false
  @doc since: "0.3.4"
  @spec to_inspect_doc(t(), Inspect.Opts.t()) :: Inspect.Algebra.t()
  def to_inspect_doc(%module{left: _, right: _} = a, opts) do
    content =
      case empty?(a) do
        true ->
          "empty"

        false ->
          open =
            cond do
              unbounded_left?(a) -> ""
              inclusive_left?(a) -> "["
              not inclusive_left?(a) -> "("
            end
            |> Inspect.Algebra.color(:list, opts)

          close =
            cond do
              unbounded_right?(a) -> ""
              inclusive_right?(a) -> "]"
              not inclusive_right?(a) -> ")"
            end
            |> Inspect.Algebra.color(:list, opts)

          sep = Inspect.Algebra.color(",", :list, opts)

          Inspect.Algebra.container_doc(
            open,
            [left(a), right(a)],
            close,
            opts,
            &to_interval_value_doc/2,
            separator: sep
          )
      end

    prefix =
      ["#", Inspect.Algebra.to_doc(module, opts), "<"]
      |> Inspect.Algebra.concat()
      |> Inspect.Algebra.group()

    postfix = ">"

    Inspect.Algebra.concat([
      prefix,
      Inspect.Algebra.nest(content, :cursor, :break),
      postfix
    ])
    |> Inspect.Algebra.group()
  end

  defp to_interval_value_doc(value, opts)
  defp to_interval_value_doc(nil, _), do: ""
  defp to_interval_value_doc(value, opts), do: Inspect.Algebra.to_doc(value, opts)

  ##
  ## Helpers
  ##

  defp from_endpoints(module, left, right) do
    left_bound =
      case left do
        :unbounded -> :unbounded
        {:exclusive, _} -> :exclusive
        {:inclusive, _} -> :inclusive
      end

    right_bound =
      case right do
        :unbounded -> :unbounded
        {:exclusive, _} -> :exclusive
        {:inclusive, _} -> :inclusive
      end

    left_point =
      case left do
        :unbounded -> nil
        {_, point} -> point
      end

    right_point =
      case right do
        :unbounded -> nil
        {_, point} -> point
      end

    new(
      module: module,
      left: left_point,
      right: right_point,
      bounds: pack_bounds({left_bound, right_bound})
    )
  end

  # non-empty non-unbounded Interval:
  defp normalize(
         %module{
           left: {left_bound, left_point} = left,
           right: {right_bound, right_point} = right
         } = original
       ) do
    if not module.point_valid?(left_point) do
      raise ArgumentError,
        message: "#{left_point} not a valid left point in #{module}"
    end

    if not module.point_valid?(right_point) do
      raise ArgumentError,
        message: "#{right_point} not a valid right point in #{module}"
    end

    type = if module.discrete?(), do: :discrete, else: :continuous
    comp = module.point_compare(left_point, right_point)

    case {type, comp, left_bound, right_bound} do
      # left > right is an error:
      {_, :gt, _, _} ->
        raise ArgumentError,
          message: "#{left_point} > #{right_point} which is not valid in an interval #{module}"

      # intervals given as either (p,p), [p,p) or (p,p]
      # (If you want a single point in an interval, give it as [p,p])
      # The (p,p) interval is already normalize form
      {_, :eq, :exclusive, :exclusive} ->
        new_empty(module)

      # [p,p) and (p,p] is normalized by taking the exlusive endpoint and
      # setting it as both left and right
      {_, :eq, :inclusive, :exclusive} ->
        new_empty(module)

      {_, :eq, :exclusive, :inclusive} ->
        new_empty(module)

      # otherwise, if the point type is continuous, the the orignal
      # interval was already normalized form:
      {:continuous, _, _, _} ->
        original

      ## Discrete types:
      # if discrete type, we want to always normalize to bounds == [)
      # because it makes life a bit easier elsewhere.

      # if both bounds are exclusive, we also need to check for empty, because
      # we could still have an empty interval like (1,2)
      # which is the same as (1,1) so we normalize by setting
      # both endpoints to the same value.
      {:discrete, _, :exclusive, :exclusive} ->
        case module.point_compare(module.point_step(left_point, 1), right_point) do
          :eq ->
            new_empty(module)

          :lt ->
            %{original | left: normalize_left_endpoint(module, left)}
        end

      # Remaining bound combinations are:
      # [], (], [)
      # we don't need to touch [), so we only need to deal with
      # the ones that are upper-inclusive. We want to perform the following
      # transformations:
      # [a,b] -> [a, b+1)
      # (a,b] -> [a+1, b+1)
      {:discrete, _, :inclusive, :inclusive} ->
        %{
          original
          | right: normalize_right_endpoint(module, right)
        }

      {:discrete, _, :exclusive, :inclusive} ->
        %{
          original
          | left: normalize_left_endpoint(module, left),
            right: normalize_right_endpoint(module, right)
        }

      # Finally, if we have an [) interval, then the original was
      # valid:
      {:discrete, :lt, :inclusive, :exclusive} ->
        original
    end
  end

  # the interval is already empty normalized form
  defp normalize(%_module{left: :empty, right: :empty} = original) do
    original
  end

  # Either left or right or both must be unbounded
  defp normalize(%module{left: left, right: right} = original) do
    %{
      original
      | left: normalize_left_endpoint(module, left),
        right: normalize_right_endpoint(module, right)
    }
  end

  defp normalize_right_endpoint(_module, :unbounded), do: :unbounded

  defp normalize_right_endpoint(module, {right_bound, right_point} = right) do
    case {module.discrete?(), right_bound} do
      {true, :inclusive} -> {:exclusive, module.point_step(right_point, 1)}
      {_, _} -> right
    end
  end

  defp normalize_left_endpoint(_module, :unbounded), do: :unbounded

  defp normalize_left_endpoint(module, {left_bound, left_point} = left) do
    case {module.discrete?(), left_bound} do
      {true, :exclusive} -> {:inclusive, module.point_step(left_point, 1)}
      {_, _} -> left
    end
  end

  # Pick the exclusive endpoint if it exists
  defp pick_exclusive({:exclusive, _} = a, _), do: a
  defp pick_exclusive(_, {:exclusive, _} = b), do: b
  defp pick_exclusive(a, b) when a < b, do: b
  defp pick_exclusive(a, _b), do: a

  # Pick the inclusive endpoint if it exists
  defp pick_inclusive({:inclusive, _} = a, _), do: a
  defp pick_inclusive(_, {:inclusive, _} = b), do: b
  defp pick_inclusive(a, b) when a < b, do: b
  defp pick_inclusive(a, _b), do: a

  # Pick the left point of a union from two left points
  defp pick_union_left(_, :unbounded, _), do: :unbounded
  defp pick_union_left(_, _, :unbounded), do: :unbounded

  defp pick_union_left(module, a, b) do
    case module.point_compare(point(a), point(b)) do
      :gt -> b
      :lt -> a
      :eq -> pick_inclusive(a, b)
    end
  end

  # Pick the right point of a union from two right points
  defp pick_union_right(_, :unbounded, _), do: :unbounded
  defp pick_union_right(_, _, :unbounded), do: :unbounded

  defp pick_union_right(module, a, b) do
    case module.point_compare(point(a), point(b)) do
      :gt -> a
      :lt -> b
      :eq -> pick_inclusive(a, b)
    end
  end

  # Pick the left point of a intersection from two left points
  defp pick_intersection_left(_, :unbounded, :unbounded), do: :unbounded
  defp pick_intersection_left(_, a, :unbounded), do: a
  defp pick_intersection_left(_, :unbounded, b), do: b

  defp pick_intersection_left(module, a, b) do
    case module.point_compare(point(a), point(b)) do
      :gt -> a
      :lt -> b
      :eq -> pick_exclusive(a, b)
    end
  end

  # Pick the right point of a intersection from two right points
  defp pick_intersection_right(_, :unbounded, :unbounded), do: :unbounded
  defp pick_intersection_right(_, a, :unbounded), do: a
  defp pick_intersection_right(_, :unbounded, b), do: b

  defp pick_intersection_right(module, a, b) do
    case module.point_compare(point(a), point(b)) do
      :gt -> b
      :lt -> a
      :eq -> pick_exclusive(a, b)
    end
  end

  # completely unbounded:
  @compile {:inline, unpack_bounds: 1}
  defp unpack_bounds(nil), do: unpack_bounds("[)")
  defp unpack_bounds(""), do: {:unbounded, :unbounded}
  # unbounded either left or right
  defp unpack_bounds(")"), do: {:unbounded, :exclusive}
  defp unpack_bounds("("), do: {:exclusive, :unbounded}
  defp unpack_bounds("]"), do: {:unbounded, :inclusive}
  defp unpack_bounds("["), do: {:inclusive, :unbounded}
  # bounded both sides
  defp unpack_bounds("()"), do: {:exclusive, :exclusive}
  defp unpack_bounds("[]"), do: {:inclusive, :inclusive}
  defp unpack_bounds("[)"), do: {:inclusive, :exclusive}
  defp unpack_bounds("(]"), do: {:exclusive, :inclusive}

  @compile {:inline, pack_bounds: 1}
  defp pack_bounds({:unbounded, :unbounded}), do: ""
  # unbounded either left or right
  defp pack_bounds({:unbounded, :exclusive}), do: ")"
  defp pack_bounds({:exclusive, :unbounded}), do: "("
  defp pack_bounds({:unbounded, :inclusive}), do: "]"
  defp pack_bounds({:inclusive, :unbounded}), do: "["
  # bounded both sides
  defp pack_bounds({:exclusive, :exclusive}), do: "()"
  defp pack_bounds({:inclusive, :inclusive}), do: "[]"
  defp pack_bounds({:inclusive, :exclusive}), do: "[)"
  defp pack_bounds({:exclusive, :inclusive}), do: "(]"

  defp new_empty(module) do
    module.new(left: :empty, right: :empty)
  end

  # Endpoint value extraction:
  @compile {:inline, point: 1}
  defp point({_, point}), do: point

  # Left is bounded and has a point
  defp assert_normalized_bounds(%module{left: {_, _}} = a) do
    assert_normalized_bounds(a, module.discrete?())
  end

  # right is bounded and has a point
  defp assert_normalized_bounds(%module{right: {_, _}} = a) do
    assert_normalized_bounds(a, module.discrete?())
  end

  defp assert_normalized_bounds(%module{} = a, true) do
    left_ok = unbounded_left?(a) or inclusive_left?(a)
    right_ok = unbounded_right?(a) or not inclusive_right?(a)

    if not (left_ok and right_ok) do
      raise ArgumentError,
        message:
          "non-normalized discrete interval #{module}: #{inspect(a)} " <>
            "(expected normalized bounds `[)`)"
    end
  end

  defp assert_normalized_bounds(_a, _discrete) do
    nil
  end

  defp infer_implementation(values) do
    implementations =
      values
      # reject nil-values (they mean "unbounded")
      |> Enum.reject(&is_nil/1)
      # check that an implementation exists for the value
      |> Enum.map(&(Interval.Intervalable.impl_for(&1) && &1))
      # reject if nil implementation
      |> Enum.reject(&is_nil/1)
      # call infer_implementation/1 on the remaining values we know has an implementation
      |> Enum.map(&Interval.Intervalable.infer_implementation/1)
      # get the unique list of implementations available
      |> Enum.uniq()

    case implementations do
      [] ->
        nil

      [impl] ->
        impl

      [_first_impl | _] = multiple ->
        raise ArgumentError,
          message: "Got multiple potential implementations for intervals: #{inspect(multiple)}"
    end
  end

  ##
  ## using-macro
  ##

  @doc """
  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 `use`ing.

  ## 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

      defmodule MyInterval do
        use Interval, type: MyType, discrete: false
      end
  """
  defmacro __using__(opts) do
    quote location: :keep,
          bind_quoted: [
            type: Keyword.fetch!(opts, :type),
            discrete: Keyword.get(opts, :discrete, false),
            jason_encoder: Keyword.get(opts, :jason_encoder, true)
          ] do
      @moduledoc """
      Represents a #{if discrete, do: "discrete", else: "continuous"}
      interval containing `#{type}`
      """

      @behaviour Interval.Behaviour
      @discrete discrete

      @typedoc "An interval of point type `#{type}`"
      @type t() :: %__MODULE__{}

      defstruct left: nil, right: nil

      @spec new(Keyword.t()) :: Interval.t()
      def new(opts \\ []) do
        Interval.new(Keyword.put(opts, :module, __MODULE__))
      end

      @spec discrete?() :: unquote(@discrete)
      def discrete?(), do: @discrete

      ##
      ## Implement the inspect protocol automatically:
      ##
      defimpl Inspect do
        @moduledoc false
        def inspect(interval, opts), do: Interval.to_inspect_doc(interval, opts)
      end

      ##
      ## Jason support
      ## If Jason is loaded, we define an implementation for Jason.Encoder.
      ##
      if jason_encoder and Code.ensure_loaded?(Jason) do
        defimpl Jason.Encoder do
          @moduledoc false
          def encode(%{left: _, right: _} = interval, opts) do
            Jason.Encode.map(Interval.to_map(interval), opts)
          end
        end
      end
    end
  end
end