InPlace.SparseSet (inplace v0.7.1)

Copy Markdown

Sparse set implementation based on https://youtu.be/PUJ_XdmSDZw?si=41ySCBvOdoNCV-zR

The main purpose is to support delete/undo operations on the set, so we can use it for backtracking.

NOTE: The code is intentionally kept close to the material in above video, even if it may not adhere to a conventional Elixir style.

The set is a permutation on 1..domain_size. Note: it's different from Knuth's implementation, where the set values are 0-based.

Options: :mapper - function of arity 2. Allows to associate elements of the set with values.

Summary

Functions

delete(set, el)

each(set, action)

empty?(set)

get(set, el)

iterate(set, acc, reducer)

member?(set, el)

new(domain_size, opts \\ [])

reduce(set, acc, reducer)

size(set)

to_list(set)

undelete(set)

undelete(set, num)