# `Feel.Type.StringSet`
[🔗](https://github.com/FeeJai/BDM/blob/feel-v0.1.0/apps/feel/lib/feel/type/string_set.ex#L1)

A set of strings that has intervals in it: `["a".."m"]`, `("m"..)`, `(.."c")`, and strings that are
left out of them: `(..) except "a"`, which is every string but `"a"` (D-39).

A set of strings is one of three things:

  * `:all`, every string;
  * a list of strings, which is exactly those strings. These are the sets of the types so far
    (D-39), and a set with no interval in it is always a list;
  * a `Feel.Type.StringSet`, which has intervals in it, and perhaps single strings next to them, or
    left out of them.

The functions here take and give any of the three, and they give the simplest one: a set with no
interval is a list, a set of every string is `:all`, and a single string is in the one place that
says it.

## The order

The intervals are in the order of the run (`Feel.Runtime.Compare`): by code point, a prefix
first, with the trailing U+0000 left out. That order is not a total one: `"a"` and `"a\0"` are
neither less nor more than one another, and they are not equal. So a *key* is a string without its
trailing U+0000, and the strings with the same key are a *class*: `"a"`, `"a\0"`, `"a\0\0"`, and so
on, as many as there are. An interval is of whole classes: one that ends at `"a"` and is closed has
all of them in it. A single string is of one string, and so is a string that is left out.

A set is therefore three parts, and it is exact: its strings are those in an interval and not left
out of it, and the single ones. The intervals say *which classes*, and the other two part *which
of the strings of a class*, which is what the run needs, because `"a" <= "a\0"` is false, and
so is `"a" > "a\0"`: the strings that `? <= "a"` accepts are those below the class of `"a"`, and
`"a"`. The complement of a set is then a set too, its parts swapped: the classes it does not have,
with its single strings left out, and the strings it left out, as single ones.

The lowest string is `""`, so a set that starts there starts at `(..`, and there is no highest
one, so an interval can end at `)`. Strings are dense: between two there are always others, so
`[.."a")` and `("a"..]` do not make the strings together, and `[.."a"]` and `("a"..]` do.

    iex> alias Feel.Type.StringSet
    iex> set = StringSet.union(StringSet.below("c", :open), ["x"])
    iex> StringSet.format(set)
    ~s'(.."c"), "x"'
    iex> {StringSet.contains?(set, "b"), StringSet.contains?(set, "c"), StringSet.contains?(set, "x")}
    {true, false, true}
    iex> not_a = StringSet.complement(["a"])
    iex> {StringSet.format(not_a), StringSet.contains?(not_a, "a"), StringSet.contains?(not_a, "a\0")}
    {~s'(..) except "a"', false, true}

# `bound`

```elixir
@type bound() :: {String.t(), :open | :closed}
```

A lower bound, and whether the class is in the interval; an upper bound, or none.

# `range`

```elixir
@type range() :: {bound(), bound() | :infinity}
```

An interval of classes: from a lower bound to an upper bound, or to no end.

# `set`

```elixir
@type set() :: :all | [String.t()] | t()
```

Any set of strings.

# `t`

```elixir
@type t() :: %Feel.Type.StringSet{
  except: [String.t()],
  points: [String.t()],
  ranges: [range(), ...]
}
```

# `above`

```elixir
@spec above(String.t(), :open | :closed) :: set()
```

The strings above a class: its key is larger, or the same if `state` is `:closed`.

    iex> Feel.Type.StringSet.above("m", :open) |> Feel.Type.StringSet.format()
    ~s'("m"..)'
    iex> Feel.Type.StringSet.above("", :closed)
    :all

# `below`

```elixir
@spec below(String.t(), :open | :closed) :: set()
```

The strings below a class: its key is smaller, or the same if `state` is `:closed`.

    iex> Feel.Type.StringSet.below("m", :open) |> Feel.Type.StringSet.format()
    ~s'(.."m")'
    iex> Feel.Type.StringSet.below("", :open)
    []

# `between`

```elixir
@spec between(bound(), bound() | :infinity) :: set()
```

The strings from a bound to another, which can be `:infinity`.

# `bounds`

```elixir
@spec bounds(set()) :: {:ok, {bound(), bound() | :infinity}} | :error
```

The lowest and the highest bound of a set, or `:error` for an empty one. The highest is `:infinity`
where an interval has no end; a single string is a closed bound. A string that is left out does not
move a bound: a class has more strings than can be left out.

    iex> Feel.Type.StringSet.bounds(["b", "a"])
    {:ok, {{"a", :closed}, {"b", :closed}}}
    iex> Feel.Type.StringSet.bounds(Feel.Type.StringSet.above("m", :open))
    {:ok, {{"m", :open}, :infinity}}

# `class`

```elixir
@spec class(String.t()) :: set()
```

The class of a string: it, and the ones that tie with it.

    iex> Feel.Type.StringSet.class("a") |> Feel.Type.StringSet.contains?("a\0")
    true

# `complement`

```elixir
@spec complement(set()) :: set()
```

The strings that are not in the set. The classes it has not, the strings it left out as single ones,
and the single strings it had as the ones that are left out.

    iex> alias Feel.Type.StringSet
    iex> StringSet.complement(StringSet.below("m", :open)) |> StringSet.format()
    ~s'["m"..)'
    iex> StringSet.complement(["a", "b"]) |> StringSet.format()
    ~s'(..) except "a", "b"'
    iex> {StringSet.complement(:all), StringSet.complement([])}
    {[], :all}
    iex> StringSet.complement(StringSet.complement(["a", "b"]))
    ["a", "b"]

# `contains?`

```elixir
@spec contains?(set(), String.t()) :: boolean()
```

Whether a string is in a set.

    iex> set = Feel.Type.StringSet.between({"a", :closed}, {"c", :open})
    iex> {Feel.Type.StringSet.contains?(set, "b"), Feel.Type.StringSet.contains?(set, "c")}
    {true, false}
    iex> Feel.Type.StringSet.contains?(["a"], "a\0")
    false

# `decide`

```elixir
@spec decide(:lt | :lte | :gt | :gte, set(), set()) :: :always | :never | :unknown
```

Whether `x operator y` holds for every `x` of the first set and `y` of the second (`:always`),
for none (`:never`), or it is not known (`:unknown`). `operator` is `:lt`, `:lte`, `:gt` or `:gte`,
and the order is the run's. It is read from the lowest and the highest bound of each set, so it is
not said where a tie could matter: `"a" <= "a\0"` is false, so `<=` is `:always` only when every
key of the first is below every key of the second.

    iex> alias Feel.Type.StringSet
    iex> StringSet.decide(:lt, ["a", "b"], StringSet.above("c", :closed))
    :always
    iex> StringSet.decide(:lt, StringSet.above("c", :closed), ["a", "b"])
    :never
    iex> StringSet.decide(:lt, ["a", "z"], StringSet.between({"m", :closed}, {"n", :closed}))
    :unknown

# `empty?`

```elixir
@spec empty?(set()) :: boolean()
```

Whether a set has no string. A set that has an interval has some, since a class is as large as it is.

# `format`

```elixir
@spec format(set()) :: String.t()
```

Writes a set: single strings and intervals, in the order of their lower bound, separated by commas,
and `except` and the strings that are left out.

    iex> alias Feel.Type.StringSet
    iex> StringSet.format(StringSet.union(["q"], StringSet.between({"a", :closed}, {"m", :open})))
    ~s'["a".."m"), "q"'
    iex> StringSet.format(StringSet.above("m", :closed))
    ~s'["m"..)'
    iex> StringSet.format(:all)
    "(..)"

# `intersect`

```elixir
@spec intersect(set(), set()) :: set()
```

The strings that are in both sets.

    iex> alias Feel.Type.StringSet
    iex> StringSet.intersect(["a", "m", "z"], StringSet.between({"b", :closed}, {"n", :closed}))
    ["m"]
    iex> StringSet.intersect(StringSet.below("n", :open), StringSet.above("c", :closed)) |> StringSet.format()
    ~s'["c".."n")'
    iex> StringSet.intersect(StringSet.complement(["a"]), ["a", "b"])
    ["b"]

# `intersect_all`

```elixir
@spec intersect_all([set()]) :: set()
```

The strings that are in all of the sets: what `intersect/2` gives folded over them from `:all`
(`Enum.reduce(sets, :all, &intersect/2)`), in the same form, made in one pass over the bounds and not by pairing every
interval so far with every interval of the next set at each step.

The fold is `n * n` for `n` sets of two intervals each, which is what the false sets of the tests of `not(…)` are
(left open by D-39). The intervals of the intersection are those where every set has an interval, from the largest
of their lower bounds to the smallest of their upper bounds. Where bounds tie (`"a"` and `"a\0"` have the same key)
the fold keeps the string of the first operand of `intersect/2`, which is the later set's, so the bound is the one of
the last set, in the order given, of those that have the bound that decides. That does not depend on the order in
which the pairs are met, so the bounds are sorted once and read from a sweep that counts the intervals the place is
in. The single strings are counted in the same sweep: one is in the intersection if as many sets have it as there
are, as a single string of theirs or inside an interval of theirs and not left out of it. The work is that of the
sort, `n log n`.

    iex> alias Feel.Type.StringSet
    iex> StringSet.intersect_all([StringSet.below("n", :open), StringSet.above("c", :closed)]) |> StringSet.format()
    ~s'["c".."n")'
    iex> StringSet.intersect_all([StringSet.complement(["a"]), ["a", "b"], :all])
    ["b"]
    iex> StringSet.intersect_all([StringSet.complement(["a"]), StringSet.complement(["b"])]) |> StringSet.format()
    ~s'(..) except "a", "b"'
    iex> StringSet.intersect_all([])
    :all

# `new`

```elixir
@spec new([String.t()], [range()], [String.t()]) :: set()
```

The set of some strings, some intervals, and the strings that are left out of the intervals, in
the simplest form that has them.

    iex> Feel.Type.StringSet.new(["b", "a", "b"], [])
    ["a", "b"]
    iex> Feel.Type.StringSet.new(["m"], [{{"a", :closed}, {"z", :closed}}]) |> Feel.Type.StringSet.format()
    ~s'["a".."z"]'
    iex> Feel.Type.StringSet.new([], [{{"", :closed}, :infinity}])
    :all
    iex> Feel.Type.StringSet.new([], [{{"a", :closed}, {"z", :closed}}], ["m", "?"]) |> Feel.Type.StringSet.format()
    ~s'["a".."z"] except "m"'

# `point_count`

```elixir
@spec point_count(set()) :: non_neg_integer()
```

How many single strings a set names, in it or left out of it. An interval is not counted.

# `points`

```elixir
@spec points(set()) :: {:ok, [String.t()]} | :error
```

The strings of a set that has no interval, or `:error` if it has.

    iex> Feel.Type.StringSet.points(["a", "b"])
    {:ok, ["a", "b"]}
    iex> Feel.Type.StringSet.points(Feel.Type.StringSet.above("m", :open))
    :error

# `single`

```elixir
@spec single(set()) :: {:ok, String.t()} | :error
```

The string of a set that has one, and no interval.

# `subset?`

```elixir
@spec subset?(set(), set()) :: boolean()
```

Whether every string of the first set is in the second: none is in the first and not in the second.

    iex> alias Feel.Type.StringSet
    iex> StringSet.subset?(["b"], StringSet.below("c", :open))
    true
    iex> StringSet.subset?(StringSet.below("c", :closed), StringSet.below("c", :open))
    false
    iex> StringSet.subset?(StringSet.complement(["a"]), StringSet.complement(["a", "b"]))
    false

# `union`

```elixir
@spec union(set(), set()) :: set()
```

The strings that are in either set.

    iex> alias Feel.Type.StringSet
    iex> StringSet.union(StringSet.below("b", :closed), StringSet.above("b", :open))
    :all
    iex> StringSet.union(StringSet.below("b", :open), StringSet.above("b", :open)) |> StringSet.contains?("b")
    false
    iex> StringSet.union(StringSet.complement(["a"]), ["a"])
    :all

# `union_all`

```elixir
@spec union_all([set()], :left | :right) :: set()
```

The strings that are in any of the sets: what `union/2` gives folded over them from `[]`, in the same form, made
with the work of the strings once and not at each step.

A fold of `union/2` sorts and de-duplicates the strings it has so far, and sorts and merges the intervals it has so far,
at every step, so the join of the types of `n` string constants was `n * n / 2` strings of work before it was cut to
`string` (D-39), and the join of `n` intervals `n * n * n` (D-39). The strings and the strings left out do not depend on
the order of the sets, so they are put together at once: a string that a set leaves out stays out if no set has it as a
single string and as many sets leave it out as have an interval over it, which is a count over the sorted bounds of
all the intervals, found by halving (`left_out/2`), and the strings of the lists go into the same `new/3`. The intervals
do depend on the order, for the bounds that tie (`"a"` and `"a\0"` have the same key): a merged interval keeps the bound
that it met first. They are put in one at a time, in an ordered map, and merged with the ones they touch as the scan of
the fold merges them, so the bounds are the ones the fold keeps, and the work for each is that of its neighbours.
`side` is where the set joined so far is in the fold: `:left` for `union(all, set)`, where of two bounds that tie the
one so far is kept, and `:right` for `union(set, all)`, where the new one is.

    iex> alias Feel.Type.StringSet
    iex> StringSet.union_all([["b", "a"], ["c", "a"], []])
    ["a", "b", "c"]
    iex> StringSet.union_all([["a"], StringSet.above("m", :open), ["z", "p"]]) |> StringSet.format()
    ~s'"a", ("m"..)'
    iex> StringSet.union_all([["a"], :all])
    :all
    iex> StringSet.union_all([])
    []
    iex> a = StringSet.new([], [{{"a", :closed}, {"m", :open}}], ["c"])
    iex> b = StringSet.new([], [{{"b", :closed}, {"n", :open}}], ["c"])
    iex> StringSet.union_all([a, b]) |> StringSet.format()
    ~s'["a".."n") except "c"'
    iex> StringSet.union_all([a, StringSet.below("d", :open)]) |> StringSet.format()
    ~s'(.."m")'

---

*Consult [api-reference.md](api-reference.md) for complete listing*