Module sparse_set

This module defines a sparse set data structure. Its most interesting properties are:

• They preserve insertion order.
• Set membership testing is done in constant time.
• Set insertion is done in constant time.
• Clearing the set is done in constant time.

The cost for doing this is that the capacity of the set needs to be known up front, and the elements in the set are limited to state identifiers.

These sets are principally used when traversing an NFA state graph. This happens at search time, for example, in the PikeVM. It also happens during DFA determinization.

Copied above documentation from https://github.com/rust-lang/regex/blob/master/regex-automata/src/util/sparse_set.rs and based my implementation off the same file.

Structs

SparseSetFunctions

This struct contains the sparse set functions

SparseSetLayout

This struct describes the layout of a “sparse set”, which is used to track NFA state ID membership.