The hash-set Reference Manual

Table of Contents

Next: , Previous: , Up: (dir)   [Contents][Index]

The hash-set Reference Manual

This is the hash-set Reference Manual, generated automatically by Declt version 2.4 "Will Decker" on Wed Jun 20 11:55:02 2018 GMT+0.


Next: , Previous: , Up: Top   [Contents][Index]

1 Introduction

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

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.


Next: , Previous: , Up: Top   [Contents][Index]

2 Systems

The main system appears first, followed by any subsystem dependency.


Previous: , Up: Systems   [Contents][Index]

2.1 hash-set

Author

Samuel Chase <samebchase@gmail.com>

License

Unlicense

Description

An implementation of the hash-set data structure.

Dependencies
Source

hash-set.asd (file)

Components

Next: , Previous: , Up: Top   [Contents][Index]

3 Files

Files are sorted by type and then listed depth-first from the systems components trees.


Previous: , Up: Files   [Contents][Index]

3.1 Lisp


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.1 hash-set.asd

Location

hash-set.asd

Systems

hash-set (system)


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.2 hash-set/package.lisp

Parent

hash-set (system)

Location

package.lisp

Packages

hash-set


Previous: , Up: Lisp files   [Contents][Index]

3.1.3 hash-set/hash-set.lisp

Dependency

package.lisp (file)

Parent

hash-set (system)

Location

hash-set.lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

4 Packages

Packages are listed by definition order.


Previous: , Up: Packages   [Contents][Index]

4.1 hash-set

Source

package.lisp (file)

Use List

common-lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.


Next: , Previous: , Up: Definitions   [Contents][Index]

5.1 Exported definitions


Next: , Previous: , Up: Exported definitions   [Contents][Index]

5.1.1 Macros

Macro: dohashset (VAR HASH-SET &optional RESULT) &body BODY
Package

hash-set

Source

hash-set.lisp (file)


Next: , Previous: , Up: Exported definitions   [Contents][Index]

5.1.2 Functions

Function: hash-keys-to-set HASH-TABLE
Package

hash-set

Source

hash-set.lisp (file)

Function: hash-table-to-set HASH-TABLE
Package

hash-set

Source

hash-set.lisp (file)

Function: hash-values-to-set HASH-TABLE
Package

hash-set

Source

hash-set.lisp (file)

Function: hs-all PREDICATE HASH-SET
Package

hash-set

Source

hash-set.lisp (file)

Function: hs-any PREDICATE HASH-SET
Package

hash-set

Source

hash-set.lisp (file)

Function: hs-cartesian-product HS-A HS-B
Package

hash-set

Source

hash-set.lisp (file)

Function: hs-copy HASH-SET
Package

hash-set

Source

hash-set.lisp (file)

Function: hs-count HASH-SET
Package

hash-set

Source

hash-set.lisp (file)

Function: hs-difference HS-A HS-B
Package

hash-set

Source

hash-set.lisp (file)

Function: hs-emptyp HASH-SET
Package

hash-set

Source

hash-set.lisp (file)

Function: hs-equal HS-A HS-B
Package

hash-set

Source

hash-set.lisp (file)

Function: hs-filter FN HASH-SET
Package

hash-set

Source

hash-set.lisp (file)

Function: hs-insert HASH-SET ITEM
Package

hash-set

Source

hash-set.lisp (file)

Function: hs-intersection HS-A HS-B
Package

hash-set

Source

hash-set.lisp (file)

Function: hs-map FN HASH-SET
Package

hash-set

Source

hash-set.lisp (file)

Function: hs-memberp HASH-SET ITEM
Package

hash-set

Source

hash-set.lisp (file)

Function: hs-ndifference HS-A HS-B
Package

hash-set

Source

hash-set.lisp (file)

Function: hs-ninsert HASH-SET ITEM
Package

hash-set

Source

hash-set.lisp (file)

Function: hs-nintersection HS-A HS-B
Package

hash-set

Source

hash-set.lisp (file)

Function: hs-nremove HASH-SET ITEM
Package

hash-set

Source

hash-set.lisp (file)

Function: hs-nremove-if PREDICATE HASH-SET
Package

hash-set

Source

hash-set.lisp (file)

Function: hs-nremove-if-not PREDICATE HASH-SET
Package

hash-set

Source

hash-set.lisp (file)

Function: hs-nunion HS-A HS-B
Package

hash-set

Source

hash-set.lisp (file)

Function: hs-powerset HASH-SET
Package

hash-set

Source

hash-set.lisp (file)

Function: hs-proper-subsetp HS-SUBSET HS-SUPERSET
Package

hash-set

Source

hash-set.lisp (file)

Function: hs-proper-supersetp HS-SUPERSET HS-SUBSET
Package

hash-set

Source

hash-set.lisp (file)

Function: hs-remove HASH-SET ITEM
Package

hash-set

Source

hash-set.lisp (file)

Function: hs-remove-if PREDICATE HASH-SET
Package

hash-set

Source

hash-set.lisp (file)

Function: hs-remove-if-not PREDICATE HASH-SET
Package

hash-set

Source

hash-set.lisp (file)

Function: hs-subsetp HS-SUBSET HS-SUPERSET
Package

hash-set

Source

hash-set.lisp (file)

Function: hs-supersetp HS-SUPERSET HS-SUBSET
Package

hash-set

Source

hash-set.lisp (file)

Function: hs-symmetric-difference HS-A HS-B
Package

hash-set

Source

hash-set.lisp (file)

Function: hs-to-list HASH-SET
Package

hash-set

Source

hash-set.lisp (file)

Function: hs-union HS-A HS-B
Package

hash-set

Source

hash-set.lisp (file)

Function: list-to-hs LIST
Package

hash-set

Source

hash-set.lisp (file)

Function: make-hash-set ()
Package

hash-set

Source

hash-set.lisp (file)


Previous: , Up: Exported definitions   [Contents][Index]

5.1.3 Classes

Class: hash-set ()

A hashset.

Package

hash-set

Source

hash-set.lisp (file)

Direct superclasses

standard-object (class)

Direct methods
  • print-object (method)
  • table (method)
  • table (method)
Direct slots
Slot: table
Initform

(make-hash-table :test (function equal) :synchronized t)

Readers

table (generic function)

Writers

(setf table) (generic function)


Previous: , Up: Definitions   [Contents][Index]

5.2 Internal definitions


Next: , Previous: , Up: Internal definitions   [Contents][Index]

5.2.1 Functions

Function: %one-bit-positions N
Package

hash-set

Source

hash-set.lisp (file)


Previous: , Up: Internal definitions   [Contents][Index]

5.2.2 Generic functions

Generic Function: table OBJECT
Generic Function: (setf table) NEW-VALUE OBJECT
Package

hash-set

Methods
Method: table (HASH-SET hash-set)

automatically generated reader method

Source

hash-set.lisp (file)

Method: (setf table) NEW-VALUE (HASH-SET hash-set)

automatically generated writer method

Source

hash-set.lisp (file)


Previous: , Up: Top   [Contents][Index]

Appendix A Indexes


Next: , Previous: , Up: Indexes   [Contents][Index]

A.1 Concepts

Jump to:   F   H   L  
Index Entry  Section

F
File, Lisp, hash-set.asd: The hash-set<dot>asd file
File, Lisp, hash-set/hash-set.lisp: The hash-set/hash-set<dot>lisp file
File, Lisp, hash-set/package.lisp: The hash-set/package<dot>lisp file

H
hash-set.asd: The hash-set<dot>asd file
hash-set/hash-set.lisp: The hash-set/hash-set<dot>lisp file
hash-set/package.lisp: The hash-set/package<dot>lisp file

L
Lisp File, hash-set.asd: The hash-set<dot>asd file
Lisp File, hash-set/hash-set.lisp: The hash-set/hash-set<dot>lisp file
Lisp File, hash-set/package.lisp: The hash-set/package<dot>lisp file

Jump to:   F   H   L  

Next: , Previous: , Up: Indexes   [Contents][Index]

A.2 Functions

Jump to:   %   (  
D   F   G   H   L   M   T  
Index Entry  Section

%
%one-bit-positions: Internal functions

(
(setf table): Internal generic functions
(setf table): Internal generic functions

D
dohashset: Exported macros

F
Function, %one-bit-positions: Internal functions
Function, hash-keys-to-set: Exported functions
Function, hash-table-to-set: Exported functions
Function, hash-values-to-set: Exported functions
Function, hs-all: Exported functions
Function, hs-any: Exported functions
Function, hs-cartesian-product: Exported functions
Function, hs-copy: Exported functions
Function, hs-count: Exported functions
Function, hs-difference: Exported functions
Function, hs-emptyp: Exported functions
Function, hs-equal: Exported functions
Function, hs-filter: Exported functions
Function, hs-insert: Exported functions
Function, hs-intersection: Exported functions
Function, hs-map: Exported functions
Function, hs-memberp: Exported functions
Function, hs-ndifference: Exported functions
Function, hs-ninsert: Exported functions
Function, hs-nintersection: Exported functions
Function, hs-nremove: Exported functions
Function, hs-nremove-if: Exported functions
Function, hs-nremove-if-not: Exported functions
Function, hs-nunion: Exported functions
Function, hs-powerset: Exported functions
Function, hs-proper-subsetp: Exported functions
Function, hs-proper-supersetp: Exported functions
Function, hs-remove: Exported functions
Function, hs-remove-if: Exported functions
Function, hs-remove-if-not: Exported functions
Function, hs-subsetp: Exported functions
Function, hs-supersetp: Exported functions
Function, hs-symmetric-difference: Exported functions
Function, hs-to-list: Exported functions
Function, hs-union: Exported functions
Function, list-to-hs: Exported functions
Function, make-hash-set: Exported functions

G
Generic Function, (setf table): Internal generic functions
Generic Function, table: Internal generic functions

H
hash-keys-to-set: Exported functions
hash-table-to-set: Exported functions
hash-values-to-set: Exported functions
hs-all: Exported functions
hs-any: Exported functions
hs-cartesian-product: Exported functions
hs-copy: Exported functions
hs-count: Exported functions
hs-difference: Exported functions
hs-emptyp: Exported functions
hs-equal: Exported functions
hs-filter: Exported functions
hs-insert: Exported functions
hs-intersection: Exported functions
hs-map: Exported functions
hs-memberp: Exported functions
hs-ndifference: Exported functions
hs-ninsert: Exported functions
hs-nintersection: Exported functions
hs-nremove: Exported functions
hs-nremove-if: Exported functions
hs-nremove-if-not: Exported functions
hs-nunion: Exported functions
hs-powerset: Exported functions
hs-proper-subsetp: Exported functions
hs-proper-supersetp: Exported functions
hs-remove: Exported functions
hs-remove-if: Exported functions
hs-remove-if-not: Exported functions
hs-subsetp: Exported functions
hs-supersetp: Exported functions
hs-symmetric-difference: Exported functions
hs-to-list: Exported functions
hs-union: Exported functions

L
list-to-hs: Exported functions

M
Macro, dohashset: Exported macros
make-hash-set: Exported functions
Method, (setf table): Internal generic functions
Method, table: Internal generic functions

T
table: Internal generic functions
table: Internal generic functions

Jump to:   %   (  
D   F   G   H   L   M   T  

Next: , Previous: , Up: Indexes   [Contents][Index]

A.3 Variables

Jump to:   S   T  
Index Entry  Section

S
Slot, table: Exported classes

T
table: Exported classes

Jump to:   S   T  

Previous: , Up: Indexes   [Contents][Index]

A.4 Data types

Jump to:   C   H   P   S  
Index Entry  Section

C
Class, hash-set: Exported classes

H
hash-set: The hash-set system
hash-set: The hash-set package
hash-set: Exported classes

P
Package, hash-set: The hash-set package

S
System, hash-set: The hash-set system

Jump to:   C   H   P   S