Iteration using a Zipper

Zippers can facilitate several different iteration strategies to systematically explore a trie.

ZipperIteration

The [ZipperIteration] trait extends [ZipperMoving] to provides methods for traversal of the trie structure.

Path-Byte Based Iteration

[to_next_step] moves the zipper to the next existing position in the trie structure, regardless of whether it contains a value. Calling this method repeatedly will cycle through through all existing positions in the trie, visiting each position once before visiting any position twice. If the focus is not at a leaf, this method descends. If it is at a leaf, it ascends repeatedly until finding a sibling, then moves to that sibling.

Value Based Iteration

[to_next_val] advances the zipper to the next position containing a value, using depth-first traversal. Calling this method repeatedly will visit each position containing a value once, before visiting any position twice.

The k_path methods allow iterating over children at depth k relative to the focus (or starting focus). This enables efficiently visiting all paths at a specific distances from a common root, which is useful for certain algorithmic patterns. For example, if your trie contains a number of 4-byte data types (e.g. record IDs, etc.), you can visit the subtrie below each one using a k_path iteration.

[descend_first_k_path] descends k bytes from the current focus, following the first child at each branch until reaching the target depth.
[to_next_k_path] moves to the next position at the same depth level, useful for systematically exploring all paths of a given length.

Example: Iterating Fixed-Length Records

#![allow(unused)]
fn main() {
extern crate pathmap;
use pathmap::{PathMap, zipper::*};

// Create a map with various 4-byte keys
let mut map = PathMap::new();
map.insert(b"abcd:subtrie1", ());
map.insert(b"abce:subtrie2", ());
map.insert(b"abxy:subtrie3", ());
map.insert(b"wxyz:subtrie4", ());
map.insert(b"ab:", ());  // shorter than 4 bytes

let mut zipper = map.read_zipper();

// Find and iterate all 4-byte paths
if zipper.descend_first_k_path(4) {
    println!("Visited 4-byte path: {:?}",
             std::str::from_utf8(zipper.path()).unwrap());

    // Continue to next 4-byte paths
    while zipper.to_next_k_path(4) {
        println!("Visited 4-byte path: {:?}",
                 std::str::from_utf8(zipper.path()).unwrap());
    }
}

// Output:
// Visited 4-byte path: "abcd"
// Visited 4-byte path: "abce"
// Visited 4-byte path: "abxy"
// Visited 4-byte path: "wxyz"
// Note: "ab:" is skipped (too short), longer paths also skipped
}

ZipperReadOnlyIteration

The [ZipperReadOnlyIteration] trait combines [ZipperReadOnlyValues] with [ZipperIteration] to provide iteration over values, exposing the same pattern as the std Rust Iterator trait.

[to_next_get_val] combines the functionality of [to_next_val] with [get_val], returning Some(&'a V) if positioned at a value, or None if iteration is complete.

ZipperReadOnlyConditionalIteration

The [ZipperReadOnlyConditionalIteration] provides the same functionality as ZipperReadOnlyIteration but for zipper types that require a witness type. See [ZipperReadOnlyConditionalValues] for more discussion on the use of witness types.

[to_next_get_val_with_witness] behaves like [ZipperReadOnlyIteration::to_next_get_val], but requires a witness to guarantee the lifetime of the returned references.

pathmap usage guide