MkTreapAugTable functorfunctor MkTreapAugTable
(structure Key : HASHKEY
structure Val : MONOID)
:> ORDTABLE where Key = Key and Val = Val and Seq = ArraySequenceImplements augmented, ordered tables (and ordered sets) as treaps.
The functions range, toString, and
toSeq each produce elements in increasing key-sorted order.
ORDSET and AUG_ORDTABLE Cost Specifications
The following costs assume that the work and span of
Key.compare, Key.hash, and Val.f (and in the case of
insertWith, of $f$) are constant.
The following costs also apply to the substructure Set,
which implements sets as tables without associated values.
| Work | Span | |
reduceVal $T$
|
\[O(1)\] | \[O(1)\] |
size $T$singleton $x$
|
\[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$ |
\[\sum_{k \in X} \mathcal{W}(f(k))\] | \[O(\log |X|) + \max_{k \in X} \mathcal{S}(f(k))\] |
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,
$(k_i \mapsto v_i)$ is the $i^\text{th}$ smallest key-value mapping, and $b_i$ is
the result of the iteration after the first $i$ elements, where $b_0 = b$.
| 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)))\] |
In the following, asume that the work and span of $f$ is constant, and tht $n$ and $m$ are the sizes of the arguments with $m \leq n$.
| 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))\] |