The `MkTreapTable` functor

Overview


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

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

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

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