Zippers are persistent pointers that refer to a location within a trie, called the zipper's focus. When an operation is applied through a zipper, it accesses and /or acts on the focus. The advantage of zippers is that they don't require re-traversal of the in-memory data structure for each operation.
A zipper is most often used to point to a location within a [PathMap], however a zipper may also operate within other kinds of tries. One example is the [ACT] on-disk file format, which allows a trie to be explored without requiring the entire data structure to be loaded into memory. Another example is a virtualized trie, such as an infinite trie that is defined parametrically.
Zipper capabilities are defined across a number of traits. There are many different zipper objects depending on the function of the zipper and the underlying data structure it accesses. Therefore it makes sense to treat zippers as generic types with the feature-specific trait bounds you require.
| Trait | Purpose / Description |
|---|---|
Zipper |
Inspect the trie structure |
ZipperConcrete |
Inspect structural sharing |
ZipperSubtries |
Make a map from a subtrie, or provide an operand to algebraic ops |
ZipperReadOnlySubtries |
Create [TrieRef] objects |
ZipperForking |
Create temporary zippers |
ZipperValues |
Access values |
ZipperReadOnlyValues |
Access values with extended lifetime |
ZipperReadOnlyConditionalValues |
Access values with witness pattern |
ZipperPath |
Get basic path information |
ZipperAbsolutePath |
Get more complete path information |
ZipperPathBuffer |
Control zipper's internal buffer allocation |
ZipperMoving |
Moves the zipper's focus within the trie |
ZipperIteration |
Traverse / exploration the trie |
ZipperReadOnlyIteration |
Iterate and borrow values in the trie |
ZipperReadOnlyConditionalIteration |
Iterate trie values with witness pattern |
ZipperWriting |
Modify the trie structure and values, and perform algebraic ops |
The pathmap crate provides a number of zipper and zipper-like objects with different capabilities and performance characteristics. It is also permissible to implement most (but not all) of the zipper traits on outside objects. Therefore this is not a complete set of zippers, but includes the core types that work directly on [PathMap] tries.
| Object | Lifetime | Writing | Moving | Cost to Create | Primary Use Case |
|---|---|---|---|---|---|
[PathMap] |
'static | ✓ | ✗ | Med | Root data structure, stand-alone trie |
[TrieRefBorrowed] |
Borrowed | ✗ | ✗ | Ultra Low | Quick focus access, no navigation |
[TrieRefOwned] |
'static | ✗ | ✗ | Low | Focus access without lifetime, no navigation |
[ReadZipper] |
Borrowed | ✗ | ✓ | Med | Reading, navigation and iteration |
[ReadZipperOwned] |
'static | ✗ | ✓ | High | Reading, navigation and iteration, send across threads |
[WriteZipper] |
Borrowed | ✓ | ✓ | Med | Trie modifications |
[WriteZipperOwned] |
'static | ✓ | ✓ | High | Trie modifications, send across threads |