Parameter Join.Iterator
This module is really an interface for the trie iterators from "Leapfrog Triejoin: A Simple, Worst-Case Optimal Join Algorithm" by Todd L. Veldhuizen (1)), but because we want typed iterators, we cannot implement the open and up methods from the paper directly.
Instead, we build one iterator per level of the trie, and use hidden references (aka type wormholes) to communicate between the different levels of the iterator.
The up function is no longer needed: the iterators at previous depths can directly be reused.
The open function is split into two parts, accept and init, which interact as follows.
acceptis called on the iterator at depthd. This prepares the iterator at depthd + 1for iteration on the trie currently pointed to by the iterator at depthd.
initis called on the iterator at depthdto start a new iteration at depthd. Each call toiniton the iterator at depthdwill iterate on the same set of keys untilacceptis called again on the iterator at depthd - 1.
There are two special cases:
- When
accepton the iterator at depthdanddis the last depth, there is no iterator at depthd + 1. Instead, the value associated with the current tuple is stored in another hidden reference -- the way to access this hidden reference depends on the concrete implementation of theIteratorsignature.
- There is no iterator at depth
-1, and so there is no way from this signature to set a value to iterate on at depth0. This is again done through explicit setting of yet another hidden reference whose location depends on the concrete implementation of theIteratorsignature.
val current : 'a Iterator.t -> 'a optioncurrent it is the key at the current position of the iterator it, or None if the iterator is exhausted.
val advance : 'a Iterator.t -> unitadvance it advances the iterator to the next key.
advance is a no-op on an exhausted iterator.
val seek : 'a Iterator.t -> 'a -> unitseek it x moves the iterator to the least upper bound for x, i.e. the least key y such that y >= x, exhausting the iterator if no such key exists.
Note: Only keys greater than the current position are considered: seek does nothing if x is smaller than the current key.
val init : 'a Iterator.t -> unitinit it resets it to the first key of a new iteration.
val accept : 'a Iterator.t -> unitaccept it accepts the value associated with the current key, preparing the iterator at the next depth for iteration.
val equal_key : 'a Iterator.t -> 'a -> 'a -> boolequal_key it is an equality function iterator keys.
val compare_key : 'a Iterator.t -> 'a -> 'a -> intequal_key it is a comparison function on iterator keys.