Set structures

Sets are collections of unique elements. Therefore the only operation which can be performed on the set is checking if objects is member of the set, removing object from the set, and adding object to the set.

API

To modify content of the mutable set use the following functions.

  • PUT!
  • ERASE!

To query content of the set use AT function. Pass object as a key. Function will return T if element is in the set and NIL otherwise.

QP-Trie set

QP-Trie set is dedicated storage for the (simple-array (unsigned-byte 8) (*)) objects. Primary use case are utf-8. This data structure is uniquely suited toward storing large sets of such strings because it utilizes prefix structure that will compress set to reuse memory for storing identical prefixes of the content.

Symbols in the package CL-DATA-STRUCTURES.SETS.QP-TRIE:
MUTABLE-QP-TRIE-SET
Inheritance
Description: Mutable variant of the mutable-qp-trie-set.
MAKE-MUTABLE-QP-TRIE-SET
Lambda List: ()
Description: Constructs and returns a new instance of the mutable-qp-trie-set

Skip-list set

Skip lists are a general purpose ordered containers, like a self-balancing trees.

Symbols in the package CL-DATA-STRUCTURES.SETS.SKIP-LIST:
MUTABLE-SKIP-LIST-SET
Inheritance
Description: Mutable skip list set.
MAKE-MUTABLE-SKIP-LIST-SET
Lambda List: (ORDERING TEST &KEY (MAXIMUM-LEVEL 32))
Description: Constructs and returns a new instance of mutable-skip-list.