Processing math: 28%

The MkTreapAugTable functor

« 210 Library Documentation

Overview

functor MkTreapAugTable
(structure Key : HASHKEY
 structure Val : MONOID)
:> ORDTABLE where Key = Key and Val = Val and Seq = ArraySequence

Implements augmented, ordered tables (and ordered sets) as treaps.

Implementation-Defined Behavior

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

ORDSET and AUG_ORDTABLE Cost Specifications

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

The following costs also apply to the substructure Set, which implements sets as tables without associated values.

Work Span
reduceVal T O(1) O(1)
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 ∑k∈XW(f(k)) O(log|X|)+max
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, (k_i \mapsto v_i) is the i^\text{th} smallest key-value mapping, and b_i is the result of the iteration after the first i elements, where b_0 = b.

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

In the following, asume that the work and span of f is constant, and tht 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))