Parallel Augmented Maps
Questions?
Contact: syhlalala at gmail dot com
The main functions and their definitions. For a complete list of functions and their arguments, please check the library. Many of the definitions are also informal, formal definitions can be found in the PAM paper [PPoPP2018].

For Sequences:

M is the set type. E = K. Z is the integer set.
rank(m, k) M × E → K The rank of key k in m
first(m) M → E The first element in m
last(m) M → E The last element in m
filter(m, φ) M × (E → bool) → M All elements in m that satisfy φ
map_reduce(m, map, reduce, zero) M × (E → B) × (B × B → B) × B → B Mapping all elements in m using the function "map" and then reduce all result using the function "reduce", with an identity of "zero"
pam_seq() ∅ → M Constructor. Create an empty sequence (tree)
pam_seq(e) E → M Constructor Create a sequence (tree) from a single entry
pam_seq(a) array → M Constructor. Construct a sequence (tree) from an array.
for_each_index(m, φ) M × (E × Z → B) → ∅ Apply φ to all entries and their ranks in the map
to_seq(m) M → array Output all elements in m to an array
keys(m) M → array Output all keys in m to an array
insert(m, e) M × E → M Insert an entry e in m
join2(m1, m2) M × M → M Concatenate two sequences
size(m) M → Z The size of m
clear(m) M → M Clear m to an empty sequence (tree)
reserve(n) Z → ∅ Reserve n tree nodes
finish Static function. Collect related tree nodes at the end

For Ordered Sets:

M is the sequence type. E = K. Z is the integer set.
All functions on sequences can also be applied on sets with the same definition.

select(m,i) M × Z → E The i-th element in m
first(m) M → E The first element in m
last(m) M → E The last element in m
previous(m, k) M × K → E The largest element in m with key smaller than k
next(m, k) M × K → E The smallest element in m with key larger than k
find(m, k) M × K → bool Determine if k is in m
insert(m, e) M × E → M Insert an entry e in m
delete(m, k) M × K → M Delete they key k in m
map_union(m1, m2) M × M → M Take the union of two sets
map_intersection(m1, m2) M × M → M Take the intersection of two sets
map_difference(m1, m2) M × M → M Take the difference of two sets
multi_insert(m, a) M × array → M Insert an array of entries into m
range(m, k1, k2) M × K × K → M All entries in m in the key range [k1, k2]
upTo(m, k) M × K × K → M All entries in m in with keys no greater than k
DownTo(m, k) M × K × K → M All entries in m with keys no less than k

For Ordered Maps:

M is the sequence type. E = K × V. Z is the integer set.
All functions on sequences and ordered sets can also be applied on maps with the same definition.

find(m, k) M × K → V The value of k in m
insert(m, e, φ) M × E × (V × V) → M Insert an entry e in m. If the key of e already exists in m, combine the the original value in the map with the value of e
map_union(m1, m2, φ) M × M × (V × V) → M Take the union of two sets. If there are duplicate keys in both m1 and m2, combine their values using φ
map_intersection(m1, m2, φ) M × M × (V × V) → M Take the intersection of two sets. If there are duplicate keys in both m1 and m2, combine their values using φ
map_difference(m1, m2) M × M → M Take the difference of two sets
multi_insert(m, a, φ) M × array → M Insert an array of entries into m. If there are duplicate keys in a, or any key in a has already appeared in m, combine their values using φ
pam_map(a, φ) M × array → M Constructor. Build an ordered map (tree) from an array of entries. If there are duplicate keys in a, combine their values using φ

For Augmented Maps:

M is the augmented map type. E = K × V. Z is the integer set.
All functions on sequences, ordered sets and ordered maps can also be applied on augmented maps with the same definition.

aug_val(m) M → A The augemented value of m
aug_left(m, k) M × K → A The augmented value of all entries with keys no more than k
aug_right(m, k) M × K → A The augmented value of all entries with keys no less than k
aug_range(m, k1, k2) M × K × → A The augmented value of all entries within key range [k1, k2]
aug_select(m, φ) M × (A → bool) → E The first entry e that makes φ(aug_left(m, key(e))) true. Only applicable when φ(a1) ⇒ φ(f(a1, a2)). E.g., when the combine function is addition and φ(x) determines if x is greater than some constant.
aug_filter(m, h) M × (A → bool) → M Equivalent to filter(m,h') for h': K × V → bool, where h(g(k,v)) ⇒ h'(k,v). Only applicable when h(a) or h(b) → h(f(a,b)).
aug_sum_range(m, k1, k2, h1, h2, zero) M × K × K × (V × B → B) × (A × B → B) × B → M For all entries in m within key range [k1, k2], add their values to "zero" by h1. Only applicable when adding values using h1 is equivalent to adding augmented values by h2.