MkTreapTable
functor
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.
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 Tsingleton x
|
O(1) | O(1) |
toSeq Tdomain Trange T
|
O(|T|) | O(log|T|) |
find T kinsertWith f (T,(k,v))insert (T,(k,v))delete (T,k)
|
O(log|T|) | O(log|T|) |
tabulate f X |
∑k∈XW(f(k)) | O(log|X|)+max |
collect SfromSeq S
|
O(|S|\log|S|) | O(\log^2|S|) |
map f\ Tfilter 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\ TfilterKey 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 Tlast Tprev Tnext Trank (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)) |