The MkTreapTable functor

« 210 Library Documentation

Overview

functor MkTreapTable(structure HashKey : HASHKEY) : TABLE

Implements SET and TABLE simultaneously with a Treap BSTREE, where

type 'a table = 'a bst
type set = unit bst
The Seq substructure is defined to be ArraySequence.

SET and TABLE Cost Specifications

The 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))\]