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 1 2 3 4 5)
#<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)))
(0 1 2 3 4 5 6 7 8 9)

hs-count : hash-set -> integer

Return the number of elements in the hash-set.

HASH-SET> (hs-count (list-to-hs '(4 5 6 7)))
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 '(7 8 9))
                    (list-to-hs '(7 8 9)))
T

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

Returns 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)))
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 '(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))
NIL

dohashset

Do something with each element of the hash-set.

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

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))))
(0 1 4 9 16 25 36 49 64 81)

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))))
(1 3 5 7 9)

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 '(4 5 6)) 123))
(4 5 6 123)

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 '(1 2 3 4))))
            (hs-ninsert hash-set 1984)
            (hs-to-list hash-set))
(1 2 3 4 1984)

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 '(4 5 6 7)) 5))
(4 6 7)

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))))
(1 3 5 7 9)

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 1 2 3 4 5))
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 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)))

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 '(2 4 6 8 9)))
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 '(2 4 6 8 9)))
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 '(1 2 3))
                                (list-to-hs '(4 5 6))))
(1 2 3 4 5 6)

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 '(1 2 3 4))
                                       (list-to-hs '(3 4 5 6))))
(3 4)

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 '(1 2 3 4))
                                               (list-to-hs '(3 4 5 6))))
(1 2 5 6)

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 '(1 2)) (list-to-hs '(1 2 3)))
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 '(1 2 3))))
(NIL (1) (2) (1 2) (3) (1 3) (2 3) (1 2 3))

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

Running the tests

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

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.