Processing math: 25%

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