MkTreapTable functorfunctor MkTreapTable(structure HashKey :
HASHKEY) : TABLE
Implements SET and
TABLE simultaneously
with a Treap
BSTREE, where
type 'a table = 'a bst
type set = unit bst
Seq
substructure is defined to be
ArraySequence.
SET and TABLE Cost SpecificationsThe following costs assume that the work and span of the application
of Key.compare is constant.
For insert the given costs assume that
the work and span of the application of $f$ is constant.
| Work | Span | |
size $T$ |
\[O(1)\] | \[O(1)\] |
toSeq $T$domain $T$range $T$ |
\[O(|T|)\] | \[O(\log|T|)\] |
find $T\:k$insert $f\:(k,v)\:T$delete $k\:T$ |
\[O(\log|T|)\] | \[O(\log|T|)\] |
tabulate $f\:X$ | \[\sum_{k\in X} \mathcal{W}(f(k))\] | \[\max_{k\in X} \mathcal{S}(f(k))\] |
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))\] |
mapk $f\:T$filterk $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))\] |
For iter and iterh,
$i$ is the index in the implementation-defined
order of the key-value pairs.
For reduce, $\mathcal{O}_r(f,b,S)$
represents the set of applications of $f$ as defined in the
SEQUENCE
specification, where $S =$ toSeq $T$.
| Work | Span | |
iter $f\:b_0\:T$iterh $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)))\] |
reduce $f\:b\:T$ |
\[O(|S|)+\sum_{f(x,y)\in\mathcal{O}_r(f,b,S)} \mathcal{W}(f(x,y))\] | \[O\left(\log|S|\max_{f(x,y)\in\mathcal{O}_r(f,b,S)} \mathcal{S}(f(x,y))\right)\] |
For the following functions which take an argument pair $(A,B)$, assume that $n=\mathsf{max}(|A|,|B|)$ and $m=\mathsf{min}(|A|,|B|)$. For merge, the given costs assume that the work and span of the application of $f$ is constant.
| Work | Span | |
union $(X,Y)$intersection $(X,Y)$difference $(X,Y)$ |
\[O\left(m\log\left(1+\frac{n}{m}\right)\right)\] | \[O(\log(n+m))\] |
merge $f\:(T_1,T_2)$extract $(T,X)$erase $(T,X)$ |
\[O\left(m\log\left(1+\frac{n}{m}\right)\right)\] | \[O(\log(n+m))\] |