The MkTreapTable functor

« 210 Library Documentation

Overview

functor MkTreapTable (structure Key : HASHKEY) :> ORDTABLE where Key = Key and Seq = ArraySequence

Implements tables and sets as treaps. Also implicitly ascribes to TABLE.

Implementation-SpecDefinedific Behavior

The functions range, toString, and toSeq produce elements in increasing key-sorted order.

ORDSET and ORDTABLE Cost Specifications

The following costs assume that the work and span of Key.compare and Key.hash (and in the case of insertWith, of $f$) are constant.

The following costs also apply to the substructure Set, which implements the set type with unit table.

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))\]
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))\]
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 and iteratePrefixes, $(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)))\]
iteratePrefixes $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, assume that the work and span of $f$ is constant, and that $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))\]