wam

# WAM

Pure Elixir implementation of Walker's Alias Method (WAM). It's method for performing weighted random sampling.

## Installation

If [available in Hex](https://hex.pm/docs/publish), the package can be installed
by adding `wam` to your list of dependencies in `mix.exs`:

```elixir
def deps do
  [
    {:wam, "~> 0.2.0"}
  ]
end
```

## Upgrading from 0.1.x

**The meaning of the public `probs` field has flipped.** It used to hold the
probability of taking the *alias*; it now holds the probability of **keeping**
the bucket, so a draw reads `if rng < probs[i], do: i, else: aliases[i]`. Sampling
through `fetch/3`, `get/4` and `index/3` behaves exactly as before — only code
that reads `wam.probs` directly, or that passes a hand-picked `rng` to steer the
comparison, is affected.

The reason for the change is a guarantee: a zero-weight atom is always paired
away, so its `probs` entry is exactly `0.0`, and `rng < 0.0` is false for **any**
`rng >= 0`. A weight of `0` is therefore unreachable by construction, no longer
depending on the generator staying strictly below `1.0`. Code that mutes content
by weighting it `0` can rely on that.

If you were calling `get(wam, index, sentinel_rng)` to read a slot without
drawing, use `at/3` instead — see below.

## Usage

It supports both weights and probabilities.

```elixir
wam = WAM.new(%{a: 10, b: 4, c: 5})
wam = WAM.new(%{a: 10 / 19, b: 4 / 19, c: 5 / 19})
```

Also it supports list of tuples and two lists:

```elixir
wam = WAM.new([{:a, 10}, {:b, 4}, {:c, 5}])
wam = WAM.new([:a, :b, :c], [10, 4, 5])
```

And provides three functions to work with random sampling:

- `fetch(wam, index, random)` - to get weighted value in form of `{:ok, value}` or return `{:error, reason}` tuple in case of error. 

  ```elixir
  {:ok, value} = WAM.fetch(wam, :rand.uniform(wam.size) - 1, :rand.uniform())
  {:error, reason} = WAM.fetch(wam, :rand.uniform(wam.size) + 1, :rand.uniform())
  ```

- `fetch(wam, index, random, default \\ nil)` - to get weighted value or default value in case of error. The default value is `nil` unless otherwise specified. 

  ```elixir
  value = WAM.get(wam, :rand.uniform(wam.size) - 1, :rand.uniform())
  nil = WAM.get(wam, :rand.uniform(wam.size) + 1, :rand.uniform())
  value = WAM.get(wam, :rand.uniform(wam.size) - 1, :rand.uniform(), :default)
  :default = WAM.get(wam, :rand.uniform(wam.size) + 1, :rand.uniform(), :default)
  ```

- `index(wam, index, random)` - to get weighted index in form of `{:ok, value}` or return `{:error, reason}` tuple in case of error

  ```elixir
  {:ok, index} = WAM.fetch(wam, :rand.uniform(wam.size) - 1, :rand.uniform())
  {:error, reason} = WAM.fetch(wam, :rand.uniform(wam.size) + 1, :rand.uniform())
  ```

And two functions to read a slot without drawing at all:

- `at(wam, index, default \\ nil)` and `fetch_at(wam, index)`

  ```elixir
  :a = WAM.at(wam, 0)
  {:ok, :a} = WAM.fetch_at(wam, 0)
  {:error, :invalid_index} = WAM.fetch_at(wam, wam.size)
  ```

  Reach for these rather than passing an `rng` picked to defeat the alias — that
  trick depends on how `probs` is oriented and breaks silently when it changes.

Documentation can be generated with [ExDoc](https://github.com/elixir-lang/ex_doc)
and published on [HexDocs](https://hexdocs.pm). Once published, the docs can
be found at <https://hexdocs.pm/wam>.