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:
- Please install Quicklisp first.
(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 1 2 3 4 5)
#<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)))
(0 1 2 3 4 5 6 7 8 9)Return the number of elements in the hash-set.
HASH-SET> (hs-count (list-to-hs '(4 5 6 7)))
4Predicate that tests whether the hash-set is empty or not.
HASH-SET> (hs-emptyp (make-hash-set))
TCompares two hash-sets for equality.
HASH-SET> (hs-equal (list-to-hs '(7 8 9))
(list-to-hs '(7 8 9)))
TReturns a copy of the hash-set.
HASH-SET> (let ((hash-set (list-to-hs '(1 2 3 4))))
(hs-equal hash-set
(hs-copy hash-set)))
TPredicate that tests the existence of an element in the hash-set.
HASH-SET-TEST> (let ((hash-set (list-to-hs '(1 2 3 4))))
(hs-memberp hash-set 4))
T
HASH-SET-TEST> (let ((hash-set (list-to-hs '(1 2 3 4))))
(hs-memberp hash-set 8))
NILDo something with each element of the hash-set.
HASH-SET> (dohashset (elt (list-to-hs (alexandria:iota 10)))
(princ elt))
0123456789
NILMaps 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))))
(0 1 4 9 16 25 36 49 64 81)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))))
(1 3 5 7 9)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 '(4 5 6)) 123))
(4 5 6 123)Inserts elt into the hash-set and returns the modified hash-set.
HASH-SET> (let ((hash-set (list-to-hs '(1 2 3 4))))
(hs-ninsert hash-set 1984)
(hs-to-list hash-set))
(1 2 3 4 1984)Returns a copy of the hash-set, but with the elt removed from
it.
HASH-SET> (hs-to-list (hs-remove (list-to-hs '(4 5 6 7)) 5))
(4 6 7)Removes the element elt from the hash-set.
HASH-SET> (hs-to-list (hs-remove-if #'evenp
(list-to-hs (alexandria:iota 10))))
(1 3 5 7 9)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 1 2 3 4 5))
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 1 2 3 4 5)))
(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 (random 20)))
:do
(format t "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 '(2 4 6 8 9)))
TA function that returns true if all elements of the hash-set test true with the predicate.
HASH-SET> (hs-all #'evenp (list-to-hs '(2 4 6 8 9)))
NILReturns a hash-set that is the union of two hash-sets.
HASH-SET> (hs-to-list (hs-union (list-to-hs '(1 2 3))
(list-to-hs '(4 5 6))))
(1 2 3 4 5 6)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 '(1 2 3 4))
(list-to-hs '(3 4 5 6))))
(3 4)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 '(1 2 3 4))
(list-to-hs '(3 4 5 6))))
(1 2 5 6)Returns t if hash-set-a is a subset of hash-set-b.
HASH-SET> (hs-subsetp (list-to-hs '(1 2)) (list-to-hs '(1 2 3)))
TReturns 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 '(1 2 3))))
(NIL (1) (2) (1 2) (3) (1 3) (2 3) (1 2 3))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 :start 1))
(list-to-hs (alexandria:iota 3 :start 10))))
((1 10) (1 11) (1 12) (2 10) (2 11) (2 12) (3 10) (3 11) (3 12))For even more usage examples please see test.lisp.
CL-USER> (ql:quickload 'hash-set-tests)
To load "hash-set-tests":
Load 1 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.
The people at #lisp for their help and guidance.