MkTreapTable functor
functor MkTreapTable (structure Key :
HASHKEY) :>
ORDTABLE
where Key = Key and Seq =
ArraySequence
Implements tables and sets as treaps. Also implicitly ascribes to
TABLE.
MkTreapTable-Specific Behavior
The functions range, toString, and
toSeq each produce elements in increasing key-sorted order.
ORDSET and ORDTABLE Cost Specifications
The following costs assume that the work and span of
Key.compare (and in the case of insertWith, of
$f$) are constant.
| Work | Span | |
size $T$ |
O(1) | O(1) |
toSeq $T$domain $T$range $T$
|
O(|T|) | O(log|T|) |
find $T\ k$insertWith $f\ (T, (k, v))$insert $(T, (k, v))$delete $(T, k)$
|
O(log|T|) | O(log|T|) |
tabulate $f\ X$ |
∑k∈XW(f(k)) | O(log|X|)+max |
collect $S$fromSeq $S$
|
O(|S|\log|S|) | O(\log^2|S|) |
map $f\ T$filter $f\ T$
|
\sum_{(k \mapsto v) \in T} \mathcal{W}(f(v)) | O(\log|T|) + \max_{(k \mapsto v) \in T} \mathcal{S}(f(v)) |
mapKey $f\ T$filterKey $f\ T$
|
\sum_{(k \mapsto v) \in T} \mathcal{W}(f(k,v)) | O(\log|T|) + \max_{(k \mapsto v) \in T} \mathcal{S}(f(k,v)) |
first $T$last $T$prev $T$next $T$rank $(T, k)$select $(T, i)$split $(T, k)$splitRank $(T, i)$getRange $T\ (k_1, k_2)$
|
O(\log|T|) | O(\log|T|) |
join $(T_1, T_2)$
|
O(\log(|T_1| + |T_2|)) | O(\log(|T_1| + |T_2|)) |
For iterate and iteratePrefixes,
$(k_i \mapsto v_i)$ is the $i^\text{th}$ smallest key-value mapping.
| Work | Span | |
reduce $f\ b\ T$ |
$\mathcal{W}\big($Seq.reduce $f\ b\ ($range $T)\big)$ |
$\mathcal{S}\big($Seq.reduce $f\ b\ ($range $T)\big)$ |
iterate $f\ b_0\ T$ |
\sum_{i=0}^{|T|-1} \mathcal{W}(f(b_i,(k_i,v_i))) | \sum_{i=0}^{|T|-1} \mathcal{S}(f(b_i,(k_i,v_i))) |
iteratePrefixes $f\ b_0\ T$ |
\sum_{i=0}^{|T|-1} \mathcal{W}(f(b_i,(k_i,v_i))) | \sum_{i=0}^{|T|-1} \mathcal{S}(f(b_i,(k_i,v_i))) |
For the following functions which take an argument pair $(A, B)$, assume that $n = \max(|A|, |B|)$ and $m = \min(|A|, |B|)$. We also assume the work and span of $f$ are constant.
| Work | Span | |
union $f\ (X, Y)$intersection $f\ (X, Y)$difference $(X, Y)$restrict $(T, X)$subtract $(T, X)$
|
O\left(m\log\left(1+\frac{n}{m}\right)\right) | O(\log(n+m)) |