# `Xb5.Set`
[🔗](https://github.com/g-andrade/xb5_elixir/blob/1.0.0/lib/xb5/set.ex#L1)

An ordered set backed by a [B-tree](https://en.wikipedia.org/wiki/B-tree) of order 5.

Elements are kept in ascending Erlang term order, and each value appears at most once.
Comparisons use `==` rather than `===` — so `1` and `1.0` are treated as the same
element, unlike `MapSet`.

Conversion to a list via `to_list/1` always yields elements in ascending
order.

## Erlang interop

`Xb5.Set` is compatible with the Erlang `:xb5_sets` module. Build one from an
`:xb5_sets` term via `new/1`. To go the other way, call `unwrap!/1` to extract the
size and root node, then pass the result to `:xb5_sets.wrap/1`.

## See also

  * `Xb5.Bag` — ordered multiset with order-statistic operations (percentile, rank)
  * `Xb5.Tree` — ordered key-value store.

## Examples

    iex> set = Xb5.Set.new([3, 1, 2, 1])
    Xb5.Set.new([1, 2, 3])
    iex> Xb5.Set.member?(set, 2)
    true
    iex> Xb5.Set.last!(set)
    3

# `order`

```elixir
@type order() :: :asc | :desc
```

# `t`

```elixir
@type t() :: t(value())
```

# `t`

```elixir
@type t(value) :: %Xb5.Set{root: :xb5_sets_node.t(value), size: non_neg_integer()}
```

# `value`

```elixir
@type value() :: term()
```

# `delete`

```elixir
@spec delete(t(val1), val2) :: t(val1) when val1: value(), val2: value()
```

Deletes `value` from `set`.

Returns a new set which is a copy of `set` but without `value`.

## Examples

    iex> set = Xb5.Set.new([1, 2, 3])
    iex> Xb5.Set.delete(set, 4)
    Xb5.Set.new([1, 2, 3])
    iex> Xb5.Set.delete(set, 2)
    Xb5.Set.new([1, 3])

# `difference`

```elixir
@spec difference(t(val1), t(val2)) :: t(val1) when val1: value(), val2: value()
```

Returns a set that is `set1` without the members of `set2`.

## Examples

    iex> Xb5.Set.difference(Xb5.Set.new([1, 2]), Xb5.Set.new([2, 3, 4]))
    Xb5.Set.new([1])

# `disjoint?`

```elixir
@spec disjoint?(t(), t()) :: boolean()
```

Checks if `set1` and `set2` have no members in common.

## Examples

    iex> Xb5.Set.disjoint?(Xb5.Set.new([1, 2]), Xb5.Set.new([3, 4]))
    true
    iex> Xb5.Set.disjoint?(Xb5.Set.new([1, 2]), Xb5.Set.new([2, 3]))
    false

# `equal?`

```elixir
@spec equal?(t(), t()) :: boolean()
```

Checks if two sets are equal.

The comparison between elements is done using `==`, so for example
`Xb5.Set.new([1])` is equal to `Xb5.Set.new([1.0])`.

## Examples

    iex> Xb5.Set.equal?(Xb5.Set.new([1, 2]), Xb5.Set.new([2, 1, 1]))
    true
    iex> Xb5.Set.equal?(Xb5.Set.new([1, 2]), Xb5.Set.new([3, 4]))
    false
    iex> Xb5.Set.equal?(Xb5.Set.new([1]), Xb5.Set.new([1.0]))
    true

# `filter`

```elixir
@spec filter(t(a), (a -> as_boolean(term()))) :: t(a) when a: value()
```

Filters `set` by returning only elements for which `fun` returns a truthy value.

Also see `reject/2` which discards all elements where the function returns
a truthy value.

## Examples

    iex> Xb5.Set.filter(Xb5.Set.new(1..5), fn x -> x > 3 end)
    Xb5.Set.new([4, 5])

    iex> Xb5.Set.filter(Xb5.Set.new(["a", :b, "c"]), &is_atom/1)
    Xb5.Set.new([:b])

# `first`

```elixir
@spec first(t(value()), default) :: value() | default when default: term()
```

Returns the first (smallest) element in `set`, or `default` if `set` is empty.

## Examples

    iex> Xb5.Set.first(Xb5.Set.new([1, 2, 3]))
    1
    iex> Xb5.Set.first(Xb5.Set.new())
    nil
    iex> Xb5.Set.first(Xb5.Set.new(), :empty)
    :empty

# `first!`

```elixir
@spec first!(t(value())) :: value()
```

Returns the first (smallest) element in `set`.

Raises `Xb5.EmptyError` if `set` is empty.

## Examples

    iex> Xb5.Set.first!(Xb5.Set.new([1, 2, 3]))
    1
    iex> Xb5.Set.first!(Xb5.Set.new())
    ** (Xb5.EmptyError) empty error

# `higher`

```elixir
@spec higher(t(value()), value()) :: {:ok, value()} | :error
```

Returns the smallest element in `set` strictly greater (larger) than `value`,
or `:error` if none exists.

`value` does not need to be a member of `set`.

## Examples

    iex> Xb5.Set.higher(Xb5.Set.new([1, 2, 3]), 2)
    {:ok, 3}
    iex> Xb5.Set.higher(Xb5.Set.new([1, 2, 3]), 1.5)
    {:ok, 2}
    iex> Xb5.Set.higher(Xb5.Set.new([1, 2, 3]), 3)
    :error

# `intersection`

```elixir
@spec intersection(t(value()), t(value())) :: t(value())
```

Returns a set containing only members that `set1` and `set2` have in common.

## Examples

    iex> Xb5.Set.intersection(Xb5.Set.new([1, 2]), Xb5.Set.new([2, 3, 4]))
    Xb5.Set.new([2])

    iex> Xb5.Set.intersection(Xb5.Set.new([1, 2]), Xb5.Set.new([3, 4]))
    Xb5.Set.new([])

# `last`

```elixir
@spec last(t(value()), default) :: value() | default when default: term()
```

Returns the last (largest) element in `set`, or `default` if `set` is empty.

## Examples

    iex> Xb5.Set.last(Xb5.Set.new([1, 2, 3]))
    3
    iex> Xb5.Set.last(Xb5.Set.new())
    nil
    iex> Xb5.Set.last(Xb5.Set.new(), :empty)
    :empty

# `last!`

```elixir
@spec last!(t(value())) :: value()
```

Returns the last (largest) element in `set`.

Raises `Xb5.EmptyError` if `set` is empty.

## Examples

    iex> Xb5.Set.last!(Xb5.Set.new([1, 2, 3]))
    3
    iex> Xb5.Set.last!(Xb5.Set.new())
    ** (Xb5.EmptyError) empty error

# `lower`

```elixir
@spec lower(t(value()), value()) :: {:ok, value()} | :error
```

Returns the largest element in `set` strictly less (smaller) than `value`, or
`:error` if none exists.

`value` does not need to be a member of `set`.

## Examples

    iex> Xb5.Set.lower(Xb5.Set.new([1, 2, 3]), 2)
    {:ok, 1}
    iex> Xb5.Set.lower(Xb5.Set.new([1, 2, 3]), 1.5)
    {:ok, 1}
    iex> Xb5.Set.lower(Xb5.Set.new([1, 2, 3]), 1)
    :error

# `map`

```elixir
@spec map(t(a), (a -> b)) :: t(b) when a: value(), b: value()
```

Applies `fun` to each element and returns a new set built from the results.

Because the mapped elements may not be unique, they are deduplicated.

## Examples

    iex> Xb5.Set.map(Xb5.Set.new([1, 2, 3]), fn x -> x * 2 end)
    Xb5.Set.new([2, 4, 6])
    iex> Xb5.Set.map(Xb5.Set.new([1, 2, 3]), fn _ -> :same end)
    Xb5.Set.new([:same])

# `member?`

```elixir
@spec member?(t(), value()) :: boolean()
```

Checks if `set` contains `value`.

Membership is tested using `==`, not `===`, so for example `member?(set, 1.0)` will
match an element `1`.

## Examples

    iex> Xb5.Set.member?(Xb5.Set.new([1, 2, 3]), 2)
    true
    iex> Xb5.Set.member?(Xb5.Set.new([1, 2, 3]), 4)
    false

# `new`

```elixir
@spec new() :: t()
```

Returns a new empty set.

## Examples

    iex> Xb5.Set.new()
    Xb5.Set.new([])

# `new`

```elixir
@spec new(:xb5_sets.set(value()) | Enumerable.t()) :: t(value())
```

Creates a set from an Erlang `:xb5_sets` term or an enumerable.

When given an enumerable, elements are deduplicated and stored in ascending order.
When given an Erlang `:xb5_sets` term, the underlying structure is reused directly.

## Examples

    iex> Xb5.Set.new([:b, :a, 3])
    Xb5.Set.new([3, :a, :b])
    iex> Xb5.Set.new([3, 3, 3, 2, 2, 1])
    Xb5.Set.new([1, 2, 3])

# `new`

```elixir
@spec new(:xb5_sets.set() | Enumerable.t(), (term() -> value())) :: t(value())
```

Creates a set from an Erlang `:xb5_sets` term or an enumerable via the transformation function.

The results of `transform` are deduplicated and stored in ascending order.

## Examples

    iex> Xb5.Set.new([1, 2, 1], fn x -> 2 * x end)
    Xb5.Set.new([2, 4])

# `pop_first!`

```elixir
@spec pop_first!(t(value())) :: {value(), t(value())}
```

Removes and returns `{value, updated_set}` for the first (smallest) element in `set`.

Raises `Xb5.EmptyError` if `set` is empty.

## Examples

    iex> Xb5.Set.pop_first!(Xb5.Set.new([1, 2, 3]))
    {1, Xb5.Set.new([2, 3])}
    iex> Xb5.Set.pop_first!(Xb5.Set.new())
    ** (Xb5.EmptyError) empty error

# `pop_last!`

```elixir
@spec pop_last!(t(value())) :: {value(), t(value())}
```

Removes and returns `{value, updated_set}` for the last (largest) element in `set`.

Raises `Xb5.EmptyError` if `set` is empty.

## Examples

    iex> Xb5.Set.pop_last!(Xb5.Set.new([1, 2, 3]))
    {3, Xb5.Set.new([1, 2])}
    iex> Xb5.Set.pop_last!(Xb5.Set.new())
    ** (Xb5.EmptyError) empty error

# `put`

```elixir
@spec put(t(value()), new_value) :: t(value() | new_value) when new_value: value()
```

Inserts `value` into `set` if `set` doesn't already contain it.

## Examples

    iex> Xb5.Set.put(Xb5.Set.new([1, 2, 3]), 3)
    Xb5.Set.new([1, 2, 3])
    iex> Xb5.Set.put(Xb5.Set.new([1, 2, 3]), 4)
    Xb5.Set.new([1, 2, 3, 4])

# `reject`

```elixir
@spec reject(t(a), (a -> as_boolean(term()))) :: t(a) when a: value()
```

Returns a set by excluding the elements from `set` for which `fun` returns a truthy value.

See also `filter/2`.

## Examples

    iex> Xb5.Set.reject(Xb5.Set.new(1..5), fn x -> rem(x, 2) != 0 end)
    Xb5.Set.new([2, 4])

    iex> Xb5.Set.reject(Xb5.Set.new(["a", :b, "c"]), &is_atom/1)
    Xb5.Set.new(["a", "c"])

# `size`

```elixir
@spec size(t()) :: non_neg_integer()
```

Returns the number of elements in `set`.

## Examples

    iex> Xb5.Set.size(Xb5.Set.new([1, 2, 3]))
    3

# `split_with`

```elixir
@spec split_with(t(), (term() -> as_boolean(term()))) :: {t(), t()}
```

Splits `set` into two sets according to the given function `fun`.

Returns a tuple with the first set containing all elements for which `fun` returned
a truthy value, and a second set with all elements for which `fun` returned a falsy
value (`false` or `nil`).

## Examples

    iex> {while_true, while_false} = Xb5.Set.split_with(Xb5.Set.new([1, 2, 3, 4]), fn v -> rem(v, 2) == 0 end)
    iex> while_true
    Xb5.Set.new([2, 4])
    iex> while_false
    Xb5.Set.new([1, 3])

    iex> {while_true, while_false} = Xb5.Set.split_with(Xb5.Set.new(), fn v -> v > 50 end)
    iex> while_true
    Xb5.Set.new([])
    iex> while_false
    Xb5.Set.new([])

# `stream`

```elixir
@spec stream(t(value()), order()) :: Enumerable.t()
```

Returns a lazy stream over all elements of `set`.

`order` controls traversal direction: `:asc` (ascending, the default) or
`:desc` (descending).

## Examples

    iex> set = Xb5.Set.new([1, 2, 3])
    iex> Xb5.Set.stream(set) |> Enum.to_list()
    [1, 2, 3]
    iex> Xb5.Set.stream(set, :desc) |> Enum.to_list()
    [3, 2, 1]
    iex> Xb5.Set.stream(Xb5.Set.new()) |> Enum.to_list()
    []

# `stream_from`

```elixir
@spec stream_from(t(value()), value(), order()) :: Enumerable.t()
```

Returns a lazy stream over elements of `set` starting from `value`.

For `:asc` (the default), starts at the first element greater than or
equal to `value`. For `:desc`, starts at the first element less than or
equal to `value`. Returns an empty stream if no such element exists.

## Examples

    iex> set = Xb5.Set.new([1, 2, 3, 4, 5])
    iex> Xb5.Set.stream_from(set, 3) |> Enum.to_list()
    [3, 4, 5]
    iex> Xb5.Set.stream_from(set, 3, :desc) |> Enum.to_list()
    [3, 2, 1]
    iex> Xb5.Set.stream_from(set, 6) |> Enum.to_list()
    []

# `structural_stats`

```elixir
@spec structural_stats(t()) :: :xb5_structural_stats.t()
```

Returns structural statistics about the underlying B-tree.

Useful for inspecting tree balance and node utilization.

## Examples

    iex> Xb5.Set.structural_stats(Xb5.Set.new(1..100))
    [
      height: 4,
      node_counts: [
        internal4: 2,
        internal3: 3,
        internal2: 3,
        internal1: 1,
        leaf4: 6,
        leaf3: 14,
        leaf2: 5,
        leaf1: 0
      ],
      node_percentages: [
        internal4: 5.9,
        internal3: 8.8,
        internal2: 8.8,
        internal1: 2.9,
        leaf4: 17.6,
        leaf3: 41.2,
        leaf2: 14.7,
        leaf1: 0.0
      ],
      total_keys: 100,
      key_percentages: [
        internal4: 8.0,
        internal3: 9.0,
        internal2: 6.0,
        internal1: 1.0,
        leaf4: 24.0,
        leaf3: 42.0,
        leaf2: 10.0,
        leaf1: 0.0
      ],
      avg_keys_per_node: 2.9411764705882355,
      avg_keys_per_internal_node: 2.6666666666666665,
      avg_keys_per_leaf_node: 3.04
    ]

# `subset?`

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

Checks if `set1`'s members are all contained in `set2`.

This function checks if `set1` is a subset of `set2`.

## Examples

    iex> Xb5.Set.subset?(Xb5.Set.new([1, 2]), Xb5.Set.new([1, 2, 3]))
    true
    iex> Xb5.Set.subset?(Xb5.Set.new([1, 2, 3]), Xb5.Set.new([1, 2]))
    false

# `symmetric_difference`

```elixir
@spec symmetric_difference(t(val1), t(val2)) :: t(val1 | val2)
when val1: value(), val2: value()
```

Returns a set with elements that are present in only one but not both sets.

Implemented as `union(difference(set1, set2), difference(set2, set1))`.

## Examples

    iex> Xb5.Set.symmetric_difference(Xb5.Set.new([1, 2, 3]), Xb5.Set.new([2, 3, 4]))
    Xb5.Set.new([1, 4])

# `to_list`

```elixir
@spec to_list(t(value())) :: [value()]
```

Converts `set` to a sorted list.

## Examples

    iex> Xb5.Set.to_list(Xb5.Set.new([1, 2, 3]))
    [1, 2, 3]

# `union`

```elixir
@spec union(t(val1), t(val2)) :: t(val1 | val2) when val1: value(), val2: value()
```

Returns a set containing all members of `set1` and `set2`.

## Examples

    iex> Xb5.Set.union(Xb5.Set.new([1, 2]), Xb5.Set.new([2, 3, 4]))
    Xb5.Set.new([1, 2, 3, 4])

# `unwrap!`

```elixir
@spec unwrap!(t(value())) :: :xb5_sets.unwrapped_set(value())
```

Returns the size and root node of `set` as `%{size: n, root: node}`.

Pass the result to `:xb5_sets.wrap/1` to obtain a proper `:xb5_sets` term.

## Examples

    iex> %{size: size} = Xb5.Set.unwrap!(Xb5.Set.new([1, 2, 3]))
    iex> size
    3

---

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