Module range_trie

Structs

NextDupe 🔒

The next state to process during duplication.

NextInsert 🔒

The next state to process during insertion and any remaining ranges that we want to add for a particular sequence of ranges. The first such instance is always the root state along with all ranges given.

NextIter 🔒

The next state (and its corresponding transition) that we want to visit during iteration in lexicographic order.

RangeTrie

A range trie represents an ordered set of sequences of bytes.

Split 🔒

Split represents a partitioning of two ranges into one or more ranges. This is the secret sauce that makes a range trie work, as it’s what tells us how to deal with two overlapping but unequal ranges during insertion.

State 🔒

A single state in this trie.

Transition 🔒

A transition is a single range of bytes. If a particular byte is in this range, then the corresponding machine may transition to the state pointed to by next_id.

Enums

SplitRange 🔒

A tagged range indicating how it was derived from a pair of ranges.

Constants

FINAL 🔒

There is only one final state in this trie. Every sequence of byte ranges added shares the same final state.

ROOT 🔒

The root state of the trie.

Functions

intersects 🔒

Returns true if and only if the given ranges intersect.