Processing math: 25%

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 kXW(f(k)) O(log|X|)+max
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))