Struct aho_corasick::util::remapper::IndexMapper

struct IndexMapper {
    stride2: usize,
}

A simple type for mapping between state indices and state IDs.

The reason why this exists is because state IDs are “premultiplied” in a DFA. That is, in order to get to the transitions for a particular state, one need only use the state ID as-is, instead of having to multiply it by transition table’s stride.

The downside of this is that it’s inconvenient to map between state IDs using a dense map, e.g., Vec. That’s because state IDs look like 0, stride, 2*stride, 3*stride, etc., instead of 0, 1, 2, 3, etc.

Since our state IDs are premultiplied, we can convert back-and-forth between IDs and indices by simply unmultiplying the IDs and multiplying the indices.

Note that for a sparse NFA, state IDs and indices are equivalent. In this case, we set the stride of the index mapped to be 0, which acts as an identity.

Fields

stride2: usize

The power of 2 corresponding to the stride of the corresponding transition table. ‘id >> stride2’ de-multiplies an ID while ‘index << stride2’ pre-multiplies an index to an ID.

Implementations

impl IndexMapper

fn to_index(&self, id: StateID) -> usize

Convert a state ID to a state index.

fn to_state_id(&self, index: usize) -> StateID

Convert a state index to a state ID.

Trait Implementations

impl Debug for IndexMapper

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.