# `ExDataSketch.Quotient`
[🔗](https://github.com/thanos/ex_data_sketch/blob/main/lib/ex_data_sketch/quotient.ex#L1)

Quotient filter for probabilistic membership testing with safe deletion and merge.

A Quotient filter is a compact approximate membership data structure that
splits a fingerprint into a quotient (slot index) and remainder (stored value).
It supports insertion, safe deletion, membership queries, and merge without
re-hashing.

## Parameters

- `:q` -- quotient bits (default: 16). Determines the number of slots: 2^q.
- `:r` -- remainder bits (default: 8). Determines false positive rate: ~1/2^r.
  Constraint: q + r <= 64.
- `:seed` -- hash seed (default: 0).

## False Positive Rates

| r bits | FPR       |
|--------|-----------|
| 4      | ~6.25%    |
| 8      | ~0.39%    |
| 12     | ~0.024%   |
| 16     | ~0.0015%  |

## Hash Strategy

Items are hashed via `ExDataSketch.Hash.hash64/1` at the API boundary.
The upper q bits of the 64-bit hash are the quotient (slot index).
The next r bits are the remainder (stored value).

## Merge Properties

Quotient filter merge is **commutative** and **associative**. The sortable
property of the slot array enables merge via sorted fingerprint extraction
and merge-sort without re-hashing the original items. Two filters can merge
only if they have identical q, r, and seed.

## Deletion Safety

Unlike Cuckoo filters, Quotient filter deletion is safe: deleting a
non-inserted item is a no-op and does not create false negatives for
other items.

## Binary State Layout (QOT1)

32-byte header followed by a packed slot array. Each slot contains
3 metadata bits (is_occupied, is_continuation, is_shifted) and r
remainder bits, packed LSB-first.

# `t`

```elixir
@type t() :: %ExDataSketch.Quotient{
  backend: module(),
  opts: keyword(),
  state: binary()
}
```

# `capabilities`

Returns the set of capabilities supported by Quotient filter.

# `compatible_with?`

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

Returns `true` if two Quotient filters have compatible parameters.

## Examples

    iex> a = ExDataSketch.Quotient.new(q: 10, r: 8)
    iex> b = ExDataSketch.Quotient.new(q: 10, r: 8)
    iex> ExDataSketch.Quotient.compatible_with?(a, b)
    true

# `count`

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

Returns the number of items stored in the filter.

## Examples

    iex> ExDataSketch.Quotient.new(q: 10, r: 8) |> ExDataSketch.Quotient.count()
    0

# `delete`

```elixir
@spec delete(t(), term()) :: t()
```

Deletes a single item from the filter.

Unlike Cuckoo filters, this operation is safe: deleting a non-member
is a no-op and does not create false negatives.

## Examples

    iex> qf = ExDataSketch.Quotient.new(q: 10, r: 8) |> ExDataSketch.Quotient.put("hello")
    iex> qf = ExDataSketch.Quotient.delete(qf, "hello")
    iex> ExDataSketch.Quotient.member?(qf, "hello")
    false

# `deserialize`

```elixir
@spec deserialize(binary()) :: {:ok, t()} | {:error, Exception.t()}
```

Deserializes an EXSK binary into a Quotient filter.

Returns `{:ok, quotient}` on success or `{:error, reason}` on failure.

## Examples

    iex> qf = ExDataSketch.Quotient.new(q: 10, r: 8) |> ExDataSketch.Quotient.put("test")
    iex> {:ok, recovered} = ExDataSketch.Quotient.deserialize(ExDataSketch.Quotient.serialize(qf))
    iex> ExDataSketch.Quotient.member?(recovered, "test")
    true

# `from_enumerable`

```elixir
@spec from_enumerable(
  Enumerable.t(),
  keyword()
) :: t()
```

Creates a Quotient filter from an enumerable of items.

Equivalent to `new(opts) |> put_many(enumerable)`.

## Examples

    iex> qf = ExDataSketch.Quotient.from_enumerable(["a", "b", "c"])
    iex> ExDataSketch.Quotient.member?(qf, "a")
    true

# `member?`

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

Tests whether an item may be a member of the set.

Returns `true` if the item is possibly in the set (may be a false positive),
`false` if the item is definitely not in the set.

## Examples

    iex> qf = ExDataSketch.Quotient.new(q: 10, r: 8) |> ExDataSketch.Quotient.put("hello")
    iex> ExDataSketch.Quotient.member?(qf, "hello")
    true

    iex> qf = ExDataSketch.Quotient.new(q: 10, r: 8)
    iex> ExDataSketch.Quotient.member?(qf, "hello")
    false

# `merge`

```elixir
@spec merge(t(), t()) :: t()
```

Merges two Quotient filters via sorted fingerprint merge.

Both filters must have identical q, r, and seed.
Raises `ExDataSketch.Errors.IncompatibleSketchesError` if parameters differ.

## Examples

    iex> a = ExDataSketch.Quotient.new(q: 10, r: 8) |> ExDataSketch.Quotient.put("x")
    iex> b = ExDataSketch.Quotient.new(q: 10, r: 8) |> ExDataSketch.Quotient.put("y")
    iex> merged = ExDataSketch.Quotient.merge(a, b)
    iex> ExDataSketch.Quotient.member?(merged, "x") and ExDataSketch.Quotient.member?(merged, "y")
    true

# `merge_many`

```elixir
@spec merge_many(Enumerable.t()) :: t()
```

Merges a non-empty enumerable of Quotient filters into one.

## Examples

    iex> filters = Enum.map(1..3, fn i ->
    ...>   ExDataSketch.Quotient.new(q: 10, r: 8) |> ExDataSketch.Quotient.put("item_#{i}")
    ...> end)
    iex> merged = ExDataSketch.Quotient.merge_many(filters)
    iex> ExDataSketch.Quotient.member?(merged, "item_1")
    true

# `merger`

```elixir
@spec merger(keyword()) :: (t(), t() -&gt; t())
```

Returns a 2-arity merge function for combining filters.

## Examples

    iex> is_function(ExDataSketch.Quotient.merger(), 2)
    true

# `new`

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

Creates a new empty Quotient filter.

## Options

- `:q` -- quotient bits (default: 16). Range: 1..28.
- `:r` -- remainder bits (default: 8). Range: 1..32.
  Constraint: q + r <= 64.
- `:seed` -- hash seed (default: 0).
- `:backend` -- backend module (default: `ExDataSketch.Backend.Pure`).
- `:hash_fn` -- custom hash function `(term -> non_neg_integer)`.

## Examples

    iex> qf = ExDataSketch.Quotient.new()
    iex> qf.opts[:q]
    16

    iex> qf = ExDataSketch.Quotient.new(q: 12, r: 10)
    iex> qf.opts[:r]
    10

# `put`

```elixir
@spec put(t(), term()) :: t()
```

Inserts a single item into the filter.

## Examples

    iex> qf = ExDataSketch.Quotient.new(q: 10, r: 8) |> ExDataSketch.Quotient.put("hello")
    iex> ExDataSketch.Quotient.member?(qf, "hello")
    true

# `put_many`

```elixir
@spec put_many(t(), Enumerable.t()) :: t()
```

Inserts multiple items in a single pass.

## Examples

    iex> qf = ExDataSketch.Quotient.new(q: 10, r: 8) |> ExDataSketch.Quotient.put_many(["a", "b"])
    iex> ExDataSketch.Quotient.member?(qf, "a")
    true

# `reducer`

```elixir
@spec reducer() :: (term(), t() -&gt; t())
```

Returns a 2-arity reducer function for use with `Enum.reduce/3`.

## Examples

    iex> is_function(ExDataSketch.Quotient.reducer(), 2)
    true

# `serialize`

```elixir
@spec serialize(t()) :: binary()
```

Serializes the filter to the EXSK binary format.

## Examples

    iex> qf = ExDataSketch.Quotient.new(q: 10, r: 8)
    iex> binary = ExDataSketch.Quotient.serialize(qf)
    iex> <<"EXSK", _rest::binary>> = binary
    iex> byte_size(binary) > 0
    true

# `size_bytes`

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

Returns the byte size of the state binary.

## Examples

    iex> qf = ExDataSketch.Quotient.new()
    iex> ExDataSketch.Quotient.size_bytes(qf) > 0
    true

---

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