# `Talan.CountingBloomFilter`
[🔗](https://github.com/preciz/talan/blob/v1.0.0/lib/talan/counting_bloom_filter.ex#L1)

Counting Bloom filter implementation with **safe concurrent access**,
powered by the [:atomics](http://erlang.org/doc/man/atomics.html) module.

## Features

  * Fixed-size Counting Bloom filter
  * Concurrent reads and writes
  * Custom and default hash functions
  * Estimate number of unique elements
  * Estimate false positive probability

Counting bloom filters support probabilistic deletion
of elements but have higher memory consumption because
they need to store a counter of N bits for every Bloom filter bit.

Counters are the source of truth for membership. Updates to individual
counters are atomic, but reads concurrent with writes may observe an
operation in progress.

# `counters_bit_size`

```elixir
@type counters_bit_size() :: 2 | 4 | 8 | 16 | 32
```

# `option`

```elixir
@type option() ::
  {:counters_bit_size, counters_bit_size()}
  | {:signed, boolean()}
  | {:false_positive_probability, float()}
  | {:hash_functions, [Talan.hash_function()]}
```

# `options`

```elixir
@type options() :: [option()]
```

# `t`

```elixir
@type t() :: %Talan.CountingBloomFilter{
  counter: Abit.Counter.t(),
  filter_length: pos_integer(),
  hash_functions: [Talan.hash_function(), ...]
}
```

# `update_result`

```elixir
@type update_result() :: :ok | {:error, :value_out_of_bounds}
```

# `cardinality`

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

See `Talan.BloomFilter.cardinality/1` for docs.

## Examples

    iex> cbf = Talan.CountingBloomFilter.new(10_000)
    iex> cbf |> Talan.CountingBloomFilter.put("hat")
    iex> cbf |> Talan.CountingBloomFilter.put("hat")
    iex> cbf |> Talan.CountingBloomFilter.put("hat")
    iex> cbf |> Talan.CountingBloomFilter.put("car keys")
    iex> cbf |> Talan.CountingBloomFilter.cardinality()
    2

# `clear`

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

Clears every counter in `counting_bloom_filter` and returns the same filter.

The filter is reset in place without reallocating its packed counter storage.
Clearing individual atomic words is safe during concurrent access, but the
filter is not cleared as one atomic operation. Concurrent reads may observe a
partially cleared filter, and concurrent updates may be cleared or remain
visible depending on their timing.

## Examples

    iex> cbf = Talan.CountingBloomFilter.new(1000)
    iex> Talan.CountingBloomFilter.put(cbf, "hat")
    iex> Talan.CountingBloomFilter.clear(cbf) == cbf
    true
    iex> Talan.CountingBloomFilter.count(cbf, "hat")
    0

# `count`

```elixir
@spec count(t(), any()) :: integer()
```

Returns the estimated net frequency of `term` after insertions and deletions.
The estimate is the minimum of the counters selected by the term's hashes.
Hash collisions and deletions can distort it.

## Examples

    iex> cbf = Talan.CountingBloomFilter.new(10_000)
    iex> cbf |> Talan.CountingBloomFilter.put("hat")
    iex> cbf |> Talan.CountingBloomFilter.put("hat")
    iex> cbf |> Talan.CountingBloomFilter.put("hat")
    iex> cbf |> Talan.CountingBloomFilter.count("hat")
    3

# `delete`

```elixir
@spec delete(t(), any()) :: update_result()
```

Probabilistically deletes `term` from `bloom_filter` and
decrements counters in `counter`.

Returns `:ok`, or `{:error, :value_out_of_bounds}` if an affected counter is
already at its minimum value. Updates to other affected counters may already
have succeeded because the operation is not atomic across counters.

## Examples

    iex> cbf = Talan.CountingBloomFilter.new(10_000)
    iex> cbf |> Talan.CountingBloomFilter.put("hat")
    iex> cbf |> Talan.CountingBloomFilter.count("hat")
    1
    iex> cbf |> Talan.CountingBloomFilter.delete("hat")
    :ok
    iex> cbf |> Talan.CountingBloomFilter.count("hat")
    0
    iex> cbf |> Talan.CountingBloomFilter.delete("this wasn't there")
    iex> cbf |> Talan.CountingBloomFilter.count("this wasn't there")
    -1

# `false_positive_probability`

```elixir
@spec false_positive_probability(t()) :: float()
```

See `Talan.BloomFilter.false_positive_probability/1` for
docs.

# `member?`

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

See `Talan.BloomFilter.member?/2` for docs.

## Examples

    iex> cbf = Talan.CountingBloomFilter.new(10_000)
    iex> cbf |> Talan.CountingBloomFilter.put("hat")
    iex> cbf |> Talan.CountingBloomFilter.member?("hat")
    true

# `new`

```elixir
@spec new(pos_integer(), options()) :: t()
```

Returns a new `%Talan.CountingBloomFilter{}` struct.

`cardinality` is the expected number of unique items. Duplicate items do not
count toward the expected cardinality.

Raises `ArgumentError` if `cardinality` or any option is invalid.

## Options
  * `:counters_bit_size` - bit size of counters, defaults to `8`
  * `:signed` - whether counters are signed, defaults to `true`
  * `:false_positive_probability` - a float, defaults to `0.01`
  * `:hash_functions` - a list of functions that each accept a term and return a
    non-negative integer, defaults to randomly seeded Murmur

## Examples

    iex> cbf = Talan.CountingBloomFilter.new(10_000)
    iex> cbf |> Talan.CountingBloomFilter.put("hat")
    iex> cbf |> Talan.CountingBloomFilter.put("hat")
    iex> cbf |> Talan.CountingBloomFilter.put("phone")
    :ok
    iex> cbf |> Talan.CountingBloomFilter.count("hat")
    2
    iex> cbf |> Talan.CountingBloomFilter.count("phone")
    1

# `put`

```elixir
@spec put(t(), any()) :: update_result()
```

Puts `term` into the filter by incrementing its counters.

A successful insertion increments every counter selected by the term's
hashes. Membership is true only while all selected counters are positive, so
earlier deletions can keep it false.

Returns `:ok`, or `{:error, :value_out_of_bounds}` if an affected counter is
already at its maximum value. Updates to other affected counters may already
have succeeded because the operation is not atomic across counters.

## Examples

    iex> cbf = Talan.CountingBloomFilter.new(10_000)
    iex> cbf |> Talan.CountingBloomFilter.put("hat")
    :ok

---

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