The MkTreapTable functor

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))$