PAM library


PAM is a parallel C++ library implementing the interface for sequence, ordered sets, ordered maps, and augmented maps. It uses the underlying balanced binary tree structure using join-based algorithms. PAM supports four balancing schemes, including AVL trees, red-black trees, treaps and weight-balanced trees.
PAM is a parallel library and is also safe for concurrency. The parallelism is supported by cilk. Theoretically, all algorithms in PAM are work-efficient and have polylogarithmic depth. PAM uses underlying persistent tree structure such that multi-versioning is allowed. PAM also supports efficient GC.

Interface

Sequences

To define a sequence, users need to specify the key type of the sequence.
PAM supports functions on sequences including construction, find an entry with a certain rank, first, last, next, previous, size, empty, filter, map-reduce, concatenating, etc.

Ordered sets

To define an ordered set, users need to specify the key type and the comparison function defining a total ordering on the key type.
On top of the sequence interface, PAM also supports functions for ordered sets including insertion, deletion, union, intersection, difference, etc.

Ordered maps

To define an ordered map, users need to specify the key type, the comparison function on the key type, and the value type.
On top of the ordered set interface, PAM also supports functions for ordered maps, such as insertion with combining values.

Augmented maps

To define an augmented map, users need to specify the key type, the comparison function on the key type, the value type, the augmented value type, the base function, the combine function and the identity of the combine function.
On top of the ordered map interface, PAM also supports functions for augmented maps, such as aug_range.
In addition to the tree structures, PAM also implements the prefix structure for augmented maps.

Implementation for Example Applications

The library also provides example implementations for a number of applications, including 1D stabbing query, 2D segment query, 2D rectangle query, inverted index searching, etc.