Simple, Deterministic Sets

This package defines immutable and mutable deterministic sets (or dsets, for short). A dset is a set (i.e. it implements the generic interface gen:set) that guarantees LIFO ordering when iterating over the elements.

Caveats concerning concurrent modification: A mutable dset can be manipulated with functions such as set-add!, and set-remove! concurrently by multiple threads; updates to internal state are performed with a check-and-set operation which protects from invalid internal states. However, elements which are removed concurrently during the following operations may or may not be visited during the traversal: set-map, set-for-each, in-set and in-dset.

Caveat concerning mutable elements: If an element in an equal?-based dset is mutated, then the dset’s behavior for insertion and lookup operations becomes unpredictable.

1 Constructors

The vals are added in the order they appear in the argument list, so later mappings can hide earlier ones if they are equal.

2 Basic Predicates

dset-eqv? returns #t if the given dset’s elements are compared with eqv?, #f otherwise.

dset-eq? returns #t if the given dset’s elements are compared with eq?, #f otherwise.

3 Traversal and Iteration

4 Performance and Memory Usage

Performance. Immutable and mutable dsets internally use Racket’s immutable hash data structure along with a list of the elements in order to provide set-like performance and a deterministic iteration order. Performing set operations on dsets will have a small overhead in comparison to Racket’s unordered sets, but the asymptotic complexity is unaffected.

Memory Usage. In order to keep dset operations such as dset-remove efficient (i.e. non-linear), we do not immediately remove elements from the internal element list. Instead, a certain amount of “fragmentation” in the element list is tolerated, but once it passes a predetermined threshold (when the number of removed element slots exceeds the number of active elements), the list is then “defragmented”. To prevent this fragmentation from causing unexpected memory leaks, each element in the list is stored in a weak-box so its presence in the element list after removal does not prevent garbage collection that would otherwise occur.

The hope is that these implementation details are mostly unobservable to dset users since their costs will be amortized.

If a user is concerned and wants more fine grained control over the presence of internal fragmentation (e.g. if removals are performed early on in computation then never again) the following functions report on the presence of fragmentation and allow a user to remove any: