hash-set

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)

Function reference

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.

make-hash-set : () -> hash-set

Creates a new hash-set.

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

list-to-hs : list -> 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}>

hs : &rest elements -> hash-set

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

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

hs-to-list : hash-set -> list

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

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

hs-count : hash-set -> integer

Return the number of elements in the hash-set.

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

hs-emptyp : hash-set -> bool

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

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

hs-equal : hash-set hash-set -> bool

Compares two hash-sets for equality.

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

hs-copy : hash-set -> hash-set

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

hs-memberp : hash-set elt -> bool

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

dohashset

Do something with each element of the hash-set.

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

hs-map : function hash-set -> hash-set

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)

hs-filter : function hash-set -> hash-set

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)

Insertion/Deletion

hs-insert : hash-set elt -> hash-set

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)

hs-ninsert : hash-set elt -> *!hash-set!*

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)

hs-remove : hash-set elt -> hash-set

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)

hs-nremove : hash-set elt -> *!hash-set!*

Removes the element elt from the hash-set.

hs-remove-if : predicate hash-set -> 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.

hs-nremove-if : predicate hash-set -> *!hash-set!*

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

hs-remove-if-not : predicate hash-set -> hash-set

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

hs-nremove-if-not : predicate hash-set -> *!hash-set!*

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

hs-first : hash-set -> elt

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

hs-pop : hash-set -> elt hash-set

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}>

hs-npop : hash-set -> elt *!hash-set!*

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)))

Set operations

hs-any : predicate hash-set -> bool

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

hs-all : predicate hash-set -> bool

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

hs-union : hash-set hash-set -> hash-set

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)

hs-nunion : hash-set-a hash-set-b -> *!hash-set-a!*

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

hs-intersection : hash-set hash-set -> hash-set

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

hs-nintersection : hash-set-a hash-set-b -> *!hash-set-a!*

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

hs-difference : hash-set-a hash-set-b -> hash-set

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)

hs-ndifference : hash-set-a hash-set-b -> *!hash-set-a!*

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

hs-symmetric-difference : hash-set-a hash-set-b -> hash-set

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)

hs-subsetp : hash-set-a hash-set-b -> bool

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

hs-proper-subsetp : hash-set-a hash-set-b -> bool

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

hs-supersetp : hash-set-a hash-set-b -> bool

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

hs-proper-supersetp : hash-set-a hash-set-b -> bool

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

hs-powerset : hash-set -> hash-set

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))

hs-cartesian-product : hash-set-a hash-set-b -> hash-set

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.

Running the tests

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
...

Credits

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

Contributors

Javier Olaechea

Thanks to

The people at #lisp for their help and guidance.