Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

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.

K-Path Iteration

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 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.