segment_trie

Overview ¶

Package segment_trie provides a trie data structure for storing URL paths. It has the main purpose of checking for path collisions.

The SegmentTrie is a trie data structure that segments paths into tokens. Stored paths can contain the `{*}` and `{**}` operators:

• operator `{*}` is used to match a single segment in a path, and may include a prefix and/or suffix.
• operator `{**}` is used any number of segments in a path, and may include a prefix and/or suffix. It must be the last operator in the stored path (this is not validated but is assumed to be true).

During insertion, the trie is first traversed to detect collisions: literal and `{*}` nodes are matched segment by segment, and any `{**}` node checks its stored suffixes against the remaining path, to catch overlapping multi-segment matches. If any path already in the trie can match the new token sequence under these rules, insertion fails with a collision error.