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

Counting Quotient Filter (CQF) for multiset membership with approximate counting.

A CQF extends the Quotient filter with variable-length counter encoding,
enabling not just "is this item present?" but "how many times has this item
been inserted?" It uses the same quotient/remainder hash split as a standard
Quotient filter, but stores counts inline using a monotonicity-violation
encoding scheme within runs.

## Counter Encoding

Remainders within a run are stored in strictly increasing order. A count
of N for one remainder is represented as N-1 consecutive duplicate
copies of that remainder immediately following the original (count is
recovered at read time by counting how many consecutive slots repeat
the same value) -- there is no compact run-length/bracketing scheme;
every unit of count beyond the first costs one physical slot. See
"Sizing `:q`" below for what this means for capacity planning.

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

## Sizing `:q`: budget for total occurrences, not distinct keys

Every occurrence of every item costs one physical slot -- not just
distinct keys (see "Counter Encoding" above). Size `2^q` against the
*sum* of all expected insert counts (`total_count`, what `count/1`
returns), not the number of distinct items you expect to track.

`put/2` and `put_many/2` return `{:ok, cqf}` / `{:ok, cqf}` |
`{:error, :full, partial_cqf}` when the table has no room left for an
insert, mirroring `ExDataSketch.Cuckoo` -- `put!/2` and `update/2`/
`update_many/2` raise `ExDataSketch.Errors.FilterFullError` instead of
returning the error tuple. Before this signal existed, an undersized
`:q` failed silently and expensively rather than raising: as the table
filled, each insert searched further for a free slot (the shift-right
cascade is bounded to `slot_count` steps specifically so it terminates
rather than looping forever), and once genuinely full, further inserts
were dropped without any error. A table sized at roughly a third of
its needed capacity (e.g. `q: 18`, 262,144 slots, for 1,000,000 total
occurrences) could take from minutes to hours to build instead of a
fraction of a second at a properly-sized `q` (confirmed: `q: 21`,
2,097,152 slots, ~2x headroom, builds the same 1,000,000-event dataset
in well under a second) -- size generously rather than relying on the
error signal alone. See `livebooks/sketches/cqf.livemd`'s "Sizing: q
must budget for total occurrences, not distinct keys" section for a
worked example.

## Merge Semantics

CQF merge is a **multiset union**: counts for identical fingerprints are
**summed**, not OR'd. This enables distributed counting use cases where
partial counts from multiple workers are combined.

## member?/estimate_count/2 Performance

`member?/2`, `estimate_count/2`, and `delete/2` decode only the 40-byte
header plus whichever slots the lookup actually touches -- typically a
handful, the length of one run -- rather than the whole slot table.
This is independent of which `:backend` is configured: there's no
per-item Rust NIF for these (only `put_many/2`/`put_many_raw/2` do),
so they always run through this path. Earlier versions of this module
decoded the entire table into a tuple on every single call regardless
of backend, making these calls cost O(slot_count) per call -- confirmed
at roughly 190ms per single call against a `q: 18` (262,144-slot)
filter, purely from that decode.

## Binary State Layout (CQF1)

40-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. The header includes a 64-bit
total_count field tracking the sum of all item multiplicities.

# `t`

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

# `capabilities`

Returns the set of capabilities supported by CQF.

# `compatible_with?`

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

Returns `true` if two CQFs have compatible parameters.

## Examples

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

# `count`

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

Returns the total count of all items (sum of all multiplicities).

## Examples

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

# `delete`

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

Deletes a single occurrence of an item (decrements its count).

If the item's count reaches 0, it is removed entirely. Deleting a
non-member is a no-op.

## Examples

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

# `deserialize`

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

Deserializes an EXSK binary into a CQF.

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

## Examples

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

# `estimate_count`

```elixir
@spec estimate_count(t(), term()) :: non_neg_integer()
```

Returns the estimated count (multiplicity) of an item.

Returns 0 if the item is not present. Due to hash collisions, the count
may be an overestimate but never an underestimate.

## Examples

    iex> cqf = ExDataSketch.CQF.new(q: 10, r: 8)
    iex> cqf = cqf |> ExDataSketch.CQF.put!("x") |> ExDataSketch.CQF.put!("x") |> ExDataSketch.CQF.put!("x")
    iex> ExDataSketch.CQF.estimate_count(cqf, "x")
    3

# `from_enumerable`

```elixir
@spec from_enumerable(
  Enumerable.t(),
  keyword()
) :: {:ok, t()} | {:error, :full, t()}
```

Creates a CQF from an enumerable of items.

Equivalent to `new(opts) |> put_many(enumerable)`. Returns `{:ok, cqf}`
or `{:error, :full, partial_cqf}` -- see `put_many/2`.

## Examples

    iex> {:ok, cqf} = ExDataSketch.CQF.from_enumerable(["a", "b", "c"])
    iex> ExDataSketch.CQF.member?(cqf, "a")
    true

# `member?`

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

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

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> cqf = ExDataSketch.CQF.new(q: 10, r: 8) |> ExDataSketch.CQF.put!("hello")
    iex> ExDataSketch.CQF.member?(cqf, "hello")
    true

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

# `merge`

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

Merges two CQFs via multiset union (counts are summed).

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

## Examples

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

# `merge_many`

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

Merges a non-empty enumerable of CQFs into one.

## Examples

    iex> filters = Enum.map(1..3, fn i ->
    ...>   ExDataSketch.CQF.new(q: 10, r: 8) |> ExDataSketch.CQF.put!("item_#{i}")
    ...> end)
    iex> merged = ExDataSketch.CQF.merge_many(filters)
    iex> ExDataSketch.CQF.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.CQF.merger(), 2)
    true

# `new`

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

Creates a new empty Counting 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> cqf = ExDataSketch.CQF.new()
    iex> cqf.opts[:q]
    16

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

# `put`

```elixir
@spec put(t(), term()) :: {:ok, t()} | {:error, :full}
```

Inserts a single item into the filter, incrementing its count.

Returns `{:ok, cqf}`, or `{:error, :full}` if the table has no
capacity left for the insertion -- see the "Sizing `:q`" section above.
Unlike `put_many/2`, there is no partial state to return on failure:
the filter is unchanged. See `put!/2` for a raising, chainable variant.

## Examples

    iex> {:ok, cqf} = ExDataSketch.CQF.new(q: 10, r: 8) |> ExDataSketch.CQF.put("hello")
    iex> ExDataSketch.CQF.member?(cqf, "hello")
    true

# `put!`

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

Inserts a single item, raising on failure.

Added for chaining convenience (`new() |> put!(...) |> put!(...)`) --
`put/2` remains the family-idiomatic name for callers that want to
handle a full table explicitly.

## Examples

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

# `put_many`

```elixir
@spec put_many(t(), Enumerable.t()) :: {:ok, t()} | {:error, :full, t()}
```

Inserts multiple items in a single pass.

Returns `{:ok, cqf}` if all items were inserted, or
`{:error, :full, partial_cqf}` if the table filled up partway through
-- `partial_cqf` reflects every item inserted before the one that
didn't fit.

## Examples

    iex> {:ok, cqf} = ExDataSketch.CQF.new(q: 10, r: 8) |> ExDataSketch.CQF.put_many(["a", "b"])
    iex> ExDataSketch.CQF.member?(cqf, "a")
    true

# `reducer`

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

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

The reducer calls `put!/2` and raises if the filter becomes full.

## Examples

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

# `serialize`

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

Serializes the filter to the EXSK binary format.

## Options

- `:format` - serialization format: `:v2` (default, EXSK v2 with CRC32C)
  or `:v1` (legacy EXSK v1, compatible with v0.7.x readers). The v1
  format is only valid for filters using `:phash2` hash strategy.

## Examples

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

    iex> cqf = ExDataSketch.CQF.new(q: 10, r: 8, hash_strategy: :phash2)
    iex> binary = ExDataSketch.CQF.serialize(cqf, format: :v1)
    iex> <<"EXSK", 1, 10, _rest::binary>> = binary

# `size_bytes`

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

Returns the byte size of the state binary.

## Examples

    iex> cqf = ExDataSketch.CQF.new()
    iex> ExDataSketch.CQF.size_bytes(cqf) > 0
    true

# `update`

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

Alias for `put!/2`, added so `ExDataSketch.CQF` satisfies the
`ExDataSketch.Sketch` behaviour's generic `update/2` callback (which
returns a bare sketch, not `{:ok, ...} | {:error, ...}`).

`put/2`/`put!/2` remain the family-idiomatic names and the ones used
throughout this module's own documentation; `update/2` exists purely
for cross-family generic code (see `ExDataSketch.update/2`).

## Examples

    iex> cqf = ExDataSketch.CQF.new() |> ExDataSketch.CQF.update("hello")
    iex> ExDataSketch.CQF.member?(cqf, "hello")
    true

# `update_many`

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

Alias for `put_many/2`, added so `ExDataSketch.CQF` satisfies the
`ExDataSketch.Sketch` behaviour's generic `update_many/2` callback.
Raises `ExDataSketch.Errors.FilterFullError` if the table fills up
partway through -- use `put_many/2` directly to keep the partial
result instead.

## Examples

    iex> cqf = ExDataSketch.CQF.new() |> ExDataSketch.CQF.update_many(["a", "b", "c"])
    iex> ExDataSketch.CQF.member?(cqf, "a")
    true

---

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