hash-set is an implementation of the hash-set data structure. It has constant time lookup, insertion and deletion.

All tests are known to run successfully on SBCL, CCL, ECL, ABCL and CLISP.

Basic usage:

1. Please install Quicklisp first.
2. (ql:quickload 'hash-set)

Note: *!hash-set!* means the hash-set is destructively modified. Functions that are destructive have an 'n' in front of their name like CL's reverse and nreverse. So, the destructive version of hs-insert is hs-ninsert.

Creates a new hash-set.

(let ((hash-set (make-hash-set))) ;; Operations on hash-set )

Creates a hash-set containing all the elements of a list.

HASH-SET> (list-to-hs (alexandria:iota 10)) #<HASH-SET of count: 10{1008832EF3}>

Convenience wrapper around list-to-hs taking &rest arguments.

HASH-SET> (hs 12345) #<HASH-SET of count: 5{1005343743}>

Creates a list containing all the elements of the hash-set.

HASH-SET> (hs-to-list (list-to-hs (alexandria:iota 10))) (0123456789)

Return the number of elements in the hash-set.

HASH-SET> (hs-count (list-to-hs '(4567))) 4

Predicate that tests whether the hash-set is empty or not.

HASH-SET> (hs-emptyp (make-hash-set)) T

Compares two hash-sets for equality.

HASH-SET> (hs-equal (list-to-hs '(789)) (list-to-hs '(789))) T

Returns a copy of the hash-set.

HASH-SET> (let ((hash-set (list-to-hs '(1234)))) (hs-equal hash-set (hs-copy hash-set))) T

Predicate that tests the existence of an element in the hash-set.

HASH-SET-TEST> (let ((hash-set (list-to-hs '(1234)))) (hs-memberp hash-set 4)) T HASH-SET-TEST> (let ((hash-set (list-to-hs '(1234)))) (hs-memberp hash-set 8)) NIL

Do something with each element of the hash-set.

HASH-SET> (dohashset (elt (list-to-hs (alexandria:iota 10))) (princelt)) 0123456789NIL

Maps a function over a hash-set and returns a hash-set containing all the mapped values.

HASH-SET> (hs-to-list (hs-map (lambda (x) (* x x)) (list-to-hs (alexandria:iota 10)))) (0149162536496481)

Filters out elements from a hash-set that test true with function.

HASH-SET> (hs-to-list (hs-filter #'oddp (list-to-hs (alexandria:iota 10)))) (13579)

Returns a new hash-set which contains the element elt in addition to all the elements of the hash-set given as the argument.

HASH-SET> (hs-to-list (hs-insert (list-to-hs '(456)) 123)) (456123)

Inserts elt into the hash-set and returns the modified hash-set.

HASH-SET> (let ((hash-set (list-to-hs '(1234)))) (hs-ninsert hash-set 1984) (hs-to-list hash-set)) (12341984)

Returns a copy of the hash-set, but with the elt removed from it.

HASH-SET> (hs-to-list (hs-remove (list-to-hs '(4567)) 5)) (467)

Removes the element elt from the hash-set.

HASH-SET> (hs-to-list (hs-remove-if #'evenp (list-to-hs (alexandria:iota 10)))) (13579)

The elements testing true with the predicate are removed from a copy of the hash-set.

The elements testing true with the predicate are removed from the hash-set.

The elements testing false with the predicate are removed from a copy of the hash-set.

The elements testing false with the predicate are removed from the hash-set.

Returns an arbitrary element of hash-set. This would be the element returned by hs-pop or hs-npop

Removes an arbitrary element of hash-set and returns both it and a copy of hash-set with the element removed. Returns nil on an empty set.

HASH-SET> (hs-pop (hs 12345)) 1 #<HASH-SET of count: 4{104DE04E43}> HASH-SET> (hs-pop (hs)) NIL #<HASH-SET of count: 0{104DE05CD3}>

Modifying version of hs-pop. Removes an arbitrary element of hash-set and returns both it and hash-set with the element removed. Returns nil on an empty set.

HASH-SET> (let ((hs (hs 12345))) (hs-npop hs) (hs-npop hs) (hs-npop hs)) 3 #<HASH-SET of count: 2{104DF7DDD3}> HASH-SET> (hs-npop (hs)) NIL #<HASH-SET of count: 0{104DE05CD3}>

hs-pop and hs-npop are useful for iterating over sets when the size can change during the loop.

HASH-SET> (loop:with hs = (list-to-hs (alexandria:iota 10)) :while (not (zerop (hs-count hs))) :for removed = (hs-npop hs) :when (evenp removed) :do (dotimes (i 3) (hs-ninsert hs (random20))) :do (formatt"hs is now: ~a~%" (hs-to-list hs)))

A function that returns true if any elements of the hash-set test true with the predicate.

HASH-SET> (hs-any #'oddp (list-to-hs '(24689))) T

A function that returns true if all elements of the hash-set test true with the predicate.

HASH-SET> (hs-all #'evenp (list-to-hs '(24689))) NIL

Returns a hash-set that is the union of two hash-sets.

HASH-SET> (hs-to-list (hs-union (list-to-hs '(123)) (list-to-hs '(456)))) (123456)

Returns a modified hash-set-a with all of hash-set-bs elements added to it.

Returns a hash-set that is the intersection of two hash-sets.

Returns a modified hash-set-a which contains the elements of the intersection of hash-set-a and hash-set-b.

Returns a hash-set that is the set-difference of hash-set-a and hash-set-b.

HASH-SET> (hs-to-list (hs-intersection (list-to-hs '(1234)) (list-to-hs '(3456)))) (34)

Returns a modified hash-set-a that contains the elements of the set-difference of hash-set-a and hash-set-b.

Returns a hash-set with the common elements removed.

HASH-SET> (hs-to-list (hs-symmetric-difference (list-to-hs '(1234)) (list-to-hs '(3456)))) (1256)

Returns t if hash-set-a is a subset of hash-set-b.

HASH-SET> (hs-subsetp (list-to-hs '(12)) (list-to-hs '(123))) T

Returns t if hash-set-a is a proper-subset of hash-set-b.

Returns t if hash-set-a is a superset of hash-set-b.

Returns t if hash-set-a is a proper-superset of hash-set-b.

Returns the powerset of the hash-set.

HASH-SET> (hs-to-list (hs-powerset (list-to-hs '(123)))) (NIL (1) (2) (12) (3) (13) (23) (123))

Returns the hash-set containing the elements of the cartesian product of hash-set-a and hash-set-b.

HASH-SET> (hs-to-list (hs-cartesian-product (list-to-hs (alexandria:iota 3:start1)) (list-to-hs (alexandria:iota 3:start10)))) ((110) (111) (112) (210) (211) (212) (310) (311) (312))

For even more usage examples please see test.lisp.

CL-USER> (ql:quickload 'hash-set-tests) To load"hash-set-tests": Load1 ASDF system: hash-set-tests ; Loading "hash-set-tests" [package hash-set]................................ [package hash-set-test]. (HASH-SET-TESTS) CL-USER> (in-package:hash-set-test) #<PACKAGE "HASH-SET-TEST"> HASH-SET-TEST> (run!) Running test suite ALL-TESTS ...

Engineering guidance taken from Robert Smith's map-set and Takaya Ochiai's cl-intset libraries.

Javier Olaechea

The people at #lisp for their help and guidance.