The MkTreapAugTable functor

Overview

functor MkTreapAugTable
(structure Key : HASHKEY
structure Val : MONOID)
:> ORDTABLE where Key = Key and Val = Val and Seq = ArraySequence

Implements tables and sets as treaps.

MkTreapAugTable-Specific Behavior

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 and Val.f (and in the case of insertWith, of $f$) are constant.

 Work Span 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|))$ reduceVal $T$ $O(1)$ $O(1)$

For iterate, $(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)))$

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