Processing math: 25%

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 tables and sets as treaps.

MkTreapAugTable-Specific 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 and Val.f (and in the case of insertWith, of f) are constant.

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 ∑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|))
reduceVal T O(1) O(1)

For iterate, (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)))

For the following functions which take an argument pair (A, B), assume that n = \max(|A|, |B|) and m = \min(|A|, |B|). We also assume the work and span of f are constant.

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