rangeset

defmodule RangeSet do
  @moduledoc """
  This behaves like MapSet except you use it on lists of ranges like `[1..3, 8..9]`.

  Any functions that opperate on individual elements have not been implemented (like `filter`). If this is required, please explicitly call `RangeSet.to_list/1`.

  Behaviour is undefined for ranges with steps other than 1.
  """

  @doc """
    Take a list of ranges and make sure that it is sorted. Any adjacent ranges are merged. Empty ranges are removed.

    `assert RangeSet.clean([2..3, 10..11, 11..12, 1..2, 1..0//1]) == [1..3, 10..12]`

    Input and output of the other functions automatically use this.
  """
  def clean(list) do
    list
    |> Enum.sort()
    |> Enum.reduce([], fn
      e, [] ->
        [e]

      e, [current | tail] ->
        if Range.disjoint?(e, current) and
             not (e.last + 1 == current.first or current.last + 1 == e.first) do
          [e, current] ++ tail
        else
          [Range.new(Enum.min([e.first, current.first]), Enum.max([e.last, current.last])) | tail]
        end
    end)
    |> Enum.filter(fn e -> not Enum.empty?(e) end)
    |> Enum.reverse()
  end

  defp single_difference(a, b) do
    if Range.disjoint?(a, b) do
      [a]
    else
      [Range.new(a.first, b.first - 1, 1), Range.new(b.last + 1, a.last, 1)]
      |> RangeSet.clean()
    end
  end

  def difference(a, b) do
    [a, b] = Enum.map([a, b], &RangeSet.clean/1)

    Enum.reduce(b, a, fn subtrahend, acc ->
      acc |> Enum.flat_map(fn minuend -> single_difference(minuend, subtrahend) end)
    end)
    |> RangeSet.clean()
  end

  def delete(list, el) do
    difference(list, [el..el])
  end

  def subset?(a, b) do
    [a, b] = Enum.map([a, b], &RangeSet.clean/1)
    RangeSet.difference(a, b) |> Enum.empty?()
  end

  def size(list) do
    list |> RangeSet.clean() |> Enum.reduce(0, fn el, acc -> acc + Range.size(el) end)
  end

  def union(a, b) do
    (a ++ b) |> RangeSet.clean()
  end

  def symmetric_difference(a, b) do
    [a, b] = Enum.map([a, b], &RangeSet.clean/1)
    left = RangeSet.difference(a, b)
    right = RangeSet.difference(b, a)
    RangeSet.union(left, right)
  end

  def intersection(a, b) do
    union = RangeSet.union(a, b)
    symdiff = RangeSet.symmetric_difference(a, b)
    RangeSet.difference(union, symdiff)
  end

  def member?(list, el) do
    RangeSet.subset?([el..el], list)
  end

  def disjoint?(a, b) do
    RangeSet.intersection(a, b) |> Enum.empty?()
  end

  def put(list, el) do
    [el..el | list] |> RangeSet.clean()
  end

  def to_list(list) do
    list |> Enum.flat_map(&Range.to_list/1)
  end
end