Source Repository: https://github.com/alex-gutev/generic-cl
GENERIC-CL provides a generic function wrapper over various functions in the Common Lisp standard, such as equality predicates and sequence operations. The goal of this wrapper is to provide a standard interface to common operations, such as testing for the equality of two objects, which is extensible to user-defined classes and structures.
Usage
This library is divided into multiple systems each encapsulating a
specific generic interface. The simplest way to use this library is to
load the system GENERIC-CL
, which loads all the interface
subsystems, and use the GENERIC-CL
package which exports all symbols
in the COMMON-LISP
package along with all the generic interface
functions. This package should be used instead of COMMON-LISP
.
The GENERIC-CL-USER exports all symbols in the CL-USER and
GENERIC-CL packages. This package is intended to be used only at the
REPL.
|
Using Specific Interface
If you don’t want to load all the generic interfaces, but only require a specific interface, such as the generic comparability interface, then load only the system which contains that interface and import its package.
The packages generally contain symbols which shadow those in the
COMMON-LISP
package, thus they cannot simply be used alongside
COMMON-LISP
. You’ll either have to manually import the shadowing
symbols, with :SHADOWING-IMPORT-FROM
or use the :MIX
option to
UIOP:DEFINE-PACKAGE.
The STATIC-DISPATCH-CL package should be used instead of CL
in order to be able to optimize generic function calls. See
https://github.com/alex-gutev/static-dispatch for more information.
|
;; Using comparison interface GENERIC-CL.COMPARISON
(defpackage my-pkg
(:use :static-dispatch-cl)
(:shadowing-import-from
:generic-cl.comparison
:equalp
:=
:/=))
(uiop:define-package my-pkg
(:use) ;; Necessary otherwise CL package is used
;; Packages listed earlier on shadow the packages listed after them
(:mix :generic-cl.comparison
:static-dispatch-cl)
...)
Comparison
System and package name: GENERIC-CL.COMPARISON
.
The comparison interface provides functions for comparing objects in terms of equality, greater than, less than, greater than or equal to and less than or equal to relations.
EQUALP is the generic binary equality predicate function to
implement for user-defined types. = and
/= are the n-ary equality predicates similar to the
functions with the same names in the COMMON-LISP
package.
LESSP, LESS-EQUAL-P, GREATERP, GREATER-EQUAL-P are the
generic binary comparison functions to implement for user-defined
types. It is sufficient to just implement LESSP
as the remaining
functions have default methods that are implemented in terms of
LESSP
.
<, <=, >,
>= are the n-ary comparison functions similar to
the functions with the same names in the COMMON-LISP
package.
EQUALP
Generic Function: EQUALP A B
Returns true if object A
is equal to object B
.
-
NUMBER NUMBER
Returns true if
A
andB
represent the same numeric value, byCL:=
. -
CHARACTER CHARACTER
Returns true if
A
andB
represent the same character, byCL:CHAR=
. -
CONS CONS
Returns true if the
CAR
ofA
is equal (byEQUALP
) to theCAR
ofB
and if theCDR
ofA
is equal (byEQUALP
) to theCDR
ofB
. -
VECTOR VECTOR
Returns true if
A
andB
are vectors of the same length and each element ofA
is equal (byEQUALP
) to the corresponding element ofB
. -
ARRAY ARRAY
Multi-dimensional arrays.
Returns true if
A
andB
have the same dimensions and each element ofA
is equal (byEQUALP
) to the corresponding element ofB
. -
STRING STRING
Returns true if both strings are equal, by
CL:STRING=
. -
PATHNAME PATHNAME
Returns true if both
PATHNAME
objects are functionally equivalent, byUIOP:PATHNAME-EQUAL
. -
T T
Default method.
Returns true if
A
andB
are the same object, byCL:EQ
.
LIKEP
Generic Function: LIKEP A B
Returns true if A
is similar to B
, where similarity is defined as
the same as equality however ignoring differences in certain aspects
such as case in strings.
-
CHARACTER CHARACTER
Returns true if
A
andB
represent the same character ignoring differences in case. Compared usingCL:CHAR-EQUAL
. -
CONS CONS
Returns true if the
CAR
ofA
is similar (byLIKEP
) to theCAR
ofB
and if theCDR
ofA
is similar (byLIKEP
) to theCDR
ofB
. -
VECTOR VECTOR
Returns true if
A
andB
are vectors of the same length and each element ofA
is similar (byLIKEP
) to the corresponding element ofB
. -
ARRAY ARRAY
Multi-dimensional arrays.
Returns true if
A
andB
have the same dimensions and each element ofA
is similar (byLIKEP
) to the corresponding element ofB
. -
STRING STRING
Returns true if both strings are equal, ignoring differences in case. Compared using
CL:STRING-EQUAL
. -
T T
Default method.
Returns true if
(EQUALP A B)
returns true.
=
Function: = X &REST XS
Returns true if all objects in XS
are equal (by EQUALP
) to X
.
/=
Function: = X &REST XS
Returns true if at least one object in XS
is not equal (by EQUALP
)
to X
.
LESSP
Generic Function: LESSP A B
Returns true if object A
is less than object B
.
It is sufficient to just implement this function, for
user-defined types, as the rest of the comparison functions have
default (T T ) methods which are implemented in terms of LESSP .
|
-
REAL REAL
Returns true if the numeric value of
A
is less than the numeric value ofB
, byCL:<
. -
CHARACTER CHARACTER
Returns true if the character code of
A
is less than the character code ofB
, byCL:CHAR<
. -
STRING STRING
Returns true if the string
A
is lexicographically less thanB
, byCL:STRING<
.
LESS-EQUAL-P
Generic Function: LESS-EQUAL-P A B
Returns true if object A
is less than or equal to object B
.
-
REAL REAL
Returns true if the numeric value of
A
is less than or equal to the numeric value ofB
, byCL:<=
. -
CHARACTER CHARACTER
Returns true if the character code of
A
is less than or equal to the character code ofB
, byCL:CHAR<=
. -
STRING STRING
Returns true if the string
A
is lexicographically less than or equal toB
, byCL:STRING<=
. -
T T
(or (lessp a b) (equalp a b))
GREATERP
Generic Function: GREATERP A B
Returns true if object A
is greater than object B
.
-
REAL REAL
Returns true if the numeric value of
A
is greater than the numeric value ofB
, byCL:>
. -
CHARACTER CHARACTER
Returns true if the character code of
A
is greater than the character code ofB
, byCL:CHAR>
. -
STRING STRING
Returns true if the string
A
is lexicographically greater thanB
, byCL:STRING>
. -
T T
Returns true if
A
is not less than or equal toB
, by LESS-EQUAL-P.(not (less-equal-p a b))
GREATER-EQUAL-P
Generic Function: GREATER-EQUAL-P A B
Returns true if object A
is greater than or equal to object B
.
-
REAL REAL
Returns true if the numeric value of
A
is greater than or equal to the numeric value ofB
, byCL:>=
. -
CHARACTER CHARACTER
Returns true if the character code of
A
is greater than or equal to the character code ofB
, byCL:CHAR>=
. -
STRING STRING
Returns true if the string
A
is lexicographically greater than or equal toB
, byCL:STRING>=
. -
T T
Returns true if
A
is not less thanB
, by LESSP.(not (lessp a b))
COMPARE
Generic Function: COMPARE A B
Returns:
:LESS
-
if
A
is less thanB
. :EQUAL
-
if
A
is equal toB
. :GREATER
-
if
A
is greater thanB
.
The default T T
method returns:
:LESS
-
if
(LESSP A B)
is true. :EQUAL
-
if
(EQUALP A B)
is true. :GREATER
-
otherwise.
<
Function: < X &REST XS
Returns true if each argument is less than the following argument, by LESSP.
<=
Function: <= X &REST XS
Returns true if each argument is less than or equal to the following argument, by LESS-EQUAL-P.
>
Function: > X &REST XS
Returns true if each argument is greater than the following argument, by GREATERP.
>=
Function: >= X &REST XS
Returns true if each argument is greater than or equal to the following argument, by GREATER-EQUAL-P.
MIN
Function: MIN X &REST XS
Returns the minimum argument.
The comparisons are performed by LESSP. Any one of the arguments which is less than or equal to the other arguments may be returned.
MAX
Function: MAX X &REST XS
Returns the maximum argument.
The comparisons are performed by GREATERP. Any one of the arguments which is greater than or equal to the other arguments may be returned.
Arithmetic
System and package name: GENERIC-CL.ARITHMETIC
.
The arithmetic interface provides generic functions for arithmetic operations.
ADD, SUBTRACT, MULTIPLY, DIVIDE are the generic binary arithmetic functions, and NEGATE is the generic unary negation function, to implement for user-defined types.
+, -, *, /
are the n-ary arithmetic functions similar to the functions with the
same names in the COMMON-LISP
package.
ADD
Generic Function: ADD A B
Returns the sum of A
and B
.
-
NUMBER NUMBER
Returns
(CL:+ A B)
.
SUBTRACT
Generic Function: SUBTRACT A B
Returns the difference of A
and B
.
-
NUMBER NUMBER
Returns
(CL:- A B)
.
MULTIPLY
Generic Function: MULTIPLY A B
Returns the product of A
and B
.
-
NUMBER NUMBER
Returns
(CL:* A B)
.
DIVIDE
Generic Function: DIVIDE A B
Returns the quotient of A
and B
. If A
is the constant 1
, the
result should be the reciprocal of B
.
-
NUMBER NUMBER
Returns
(CL:/ A B)
.
NEGATE
Generic Function: NEGATE A
Returns the negation of A
.
-
NUMBER
Returns
(CL:- A)
.
+
Function: + X &REST XS
Returns the sum of all the arguments, computed by reducing over the argument list with the ADD function.
If no arguments are provided, 0
is returned. If a single argument is
provided it is returned.
-
Function: - X &REST XS
Returns the difference of all the arguments, computed by reducing over the argument list with the SUBTRACT function.
If only a single argument is provided the negation of that argument is returned, by the NEGATE function.
*
Function: * X &REST XS
Returns the product of all the arguments, computed by reducing over the argument list with the MULTIPLY function.
If no arguments are provided, 1
is returned. If a single argument is
provided it is returned.
/
Function: / X &REST XS
Returns the quotient of all the arguments, computed by reducing over the argument list with the DIVIDE function.
If only a single argument is provided, the reciprocal of the argument,
(DIVIDE 1 X)
, is returned.
1+
Generic Function: 1+ A
Returns A + 1
.
-
NUMBER
Returns
(CL:1+ A)
. -
T
Returns
(ADD A 1)
.
1-
Generic Function: 1- A
Returns A - 1
.
-
NUMBER
Returns
(CL:1- A)
. -
T
Returns
(SUBTRACT A 1)
.
INCF
Macro: INCF PLACE &OPTIONAL (DELTA 1)
Increments the value of PLACE
by DELTA
, which defaults to 1
,
using the ADD function.
Effectively:
(setf place (add place delta))
DECF
Macro: DECF PLACE &OPTIONAL (DELTA 1)
Decrements the value of PLACE
by DELTA
, which defaults to 1
,
using the SUBTRACT function.
Effectively:
(setf place (subtract place delta))
MINUSP
Generic Function: MINUSP A
Returns true if A
is less than zero.
-
REAL
Returns
(CL:MINUSP A)
. -
T
Returns true if
A
compares less than0
, by LESSP.(lessp a 0)
PLUSP
Generic Function: PLUSP A
Returns true if A
is greater than zero.
-
REPL
Returns
(CL:PLUSP A)
. -
T
Returns true if
A
compares greater than0
, by GREATERP.(greaterp a 0)
ZEROP
Generic Function: ZEROP A
Returns true if A
is equal to zero.
-
NUMBER
Returns
(CL:ZEROP A)
. -
T
Returns true if
A
is equal to0
, by EQUALP.(equalp a 0)
SIGNUM
Generic Function: SIGNUM A
Returns -1
, 0
or 1
depending on whether A
is negative, is
equal to zero or is positive.
-
SIGNUM
Returns
(CL:SIGNUM A)
. -
T
Returns
-1
if(MINUSP A)
is true,0
if(ZEROP A)
is true,1
otherwise.
ABS
Generic Function: ABS A
Returns the absolute value of A
.
-
NUMBER
Returns
(CL:ABS A)
. -
T
If
(MINUSP A)
is true, returns(NEGATE A)
otherwise returnsA
.(if (minusp a) (negate a) a)
EVENP
Generic Function: EVENP A
Returns true if A
is even.
-
INTEGER
Returns
(CL:EVENP A)
-
T
Returns
(ZEROP (MOD A 2))
ODDP
Generic Function: ODDP A
Returns true if A
is odd.
-
INTEGER
Returns
(CL:ODDP A)
-
T
Returns
(NOT (EVENP A))
FLOOR
Generic Function: FLOOR N D
Performs the division N/D
if D
is provided, otherwise equivalent
to N/1
, and returns the result rounded towards negative infinity as
the first value, and the remainder N - result * D
as the second return
value.
-
REAL
Returns
(CL:FLOOR N D)
ifD
is provided otherwise returns(CL:FLOOR N)
.
CEILING
Generic Function: CEILING N D
Performs the division N/D
if D
is provided, otherwise equivalent
to N/1
, and returns the result rounded towards positive infinity as
the first value, and the N - result * D
as the second return value.
-
REAL
Returns
(CL:CEILING N D)
ifD
is provided otherwise returns(CL:CEILING N)
.
TRUNCATE
Generic Function: TRUNCATE N D
Performs the division N/D
if D
is provided, otherwise equivalent
to N/1
, and returns the result rounded towards zero as the first
value, and the remainder N - result * D
as the second return value.
-
REAL
Returns
(CL:TRUNCATE N D)
ifD
is provided otherwise returns(CL:TRUNCATE N)
.
ROUND
Generic Function: ROUND N D
Performs the division N/D
if D
is provided, otherwise equivalent
to N/1
, and returns the result rounded towards the nearest integer
as the first value, and the remainder N - result * D
as the second
return value.
If the result lies exactly halfway between two integers, it is rounded to the nearest even integer.
-
REAL
Returns
(CL:ROUND N D)
ifD
is provided otherwise returns(CL:ROUND N)
.
MOD
Generic Function: MOD N D
Returns the remainder of the FLOOR operation on N
and D
.
-
REAL
Returns
(CL:MOD N D)
. -
T
Returns the second return value of
(FLOOR N D)
.
REM
Generic Function: REM N D
Returns the remainder of the TRUNCATE operation on N
and D
.
-
REAL
Returns
(CL:REM N D)
. -
T
Returns the second return value of
(TRUNCATE N D)
.
Object
System and package name: GENERIC-CL.OBJECT
.
The object interface provides miscellaneous functions for manipulating objects, such as copying and type conversions.
COPY
Generic Function: COPY OBJECT &KEY &ALLOW-OTHER-KEYS
Return a copy of OBJECT
.
If OBJECT
is mutable, by some other functions, then the returned
object should be distinct (not EQ
) from OBJECT
, otherwise the
return value may be identical (EQ
) to OBJECT
.
This function may accept additional keyword arguments which
specify certain options as to how the object should be copied. Methods
specialized on containers accept a :DEEP keyword parameter, which if
provided and is true a deep copy is returned otherwise a shallow copy
is returned. If a user-defined type acts as a container or sequence
then the COPY method for that type should also accept the :DEEP
keyword argument.
|
-
CONS
Returns a new list which contains all the elements in
OBJECT
. If:DEEP
is provided and is true, the list returned contains a copy of the elements, copied using(COPY ELEM :DEEP T)
. -
VECTOR
Returns a new vector which contains all the elements in
OBJECT
. If:DEEP
is provided and is true, the vector returned contains a copy of the elements, copied using(COPY ELEM :DEEP T)
. -
ARRAY
Multi-Dimensional Arrays.
Returns a new array, of the same dimensions as
OBJECT
, which contains all the elements inOBJECT
. If:DEEP
is provided and is true, the array returned contains a copy of the elements, copied using(COPY ELEM :DEEP T)
. -
STRUCTURE-OBJECT
Returns a shallow copy of the structure object, using
COPY-STRUCTURE
. -
T
Simply returns
OBJECT
.This method is provided to allow sequences containing arbitrary objects to be copied safely, without signaling a condition, and to avoid having to write simple pass-through methods for each user-defined type.
If an object can be mutated, and there is no specialized copy method for it, the constraints of the COPY
function are violated.
COERCE
Generic Function: COERCE OBJECT TYPE
Coerce OBJECT
to the type TYPE
.
The default (T T
) method simply calls CL:COERCE
.
DEFCONSTANT
Macro: DEFCONSTANT SYMBOL VALUE &OPTIONAL DOCUMENTATION
Ensure that SYMBOL
is a constant with a value that is equal, by
GENERIC-CL:EQUALP
to VALUE
.
This means that if SYMBOL
already names a constant, at the time of
evaluating the DEFCONSTANT
form, no condition will be signalled if
its value is equal (by GENERIC-CL:EQUALP
) to VALUE
.
Implemented using ALEXANDRIA:DEFINE-CONSTANT
|
Container
System and package name: GENERIC-CL.CONTAINER
.
The container interface provides generic functions for retrieving elements from containers, such as lists, arrays and hash-tables, and for querying various properties of containers, such as the container’s size.
All the following functions are applicable to both ordered containers, sequences, and unordered containers, such as hash-maps, however some only make sense when applied on sequences.
Creation
The following functions are for creating an empty container suitable for accumulating items using the Collector interface.
CLEARED
Generic Function: CLEARED CONTAINER &KEY &ALLOW-OTHER-KEYS
Return a new empty container of the same type, and with the same
properties, as CONTAINER
, suitable for accumulating items into it
using the collector interface.
Individual methods may accept keyword parameters which specify certain options of the container which is to be created. |
-
LIST
Returns
NIL
. -
VECTOR
Returns an adjustable vector of the same length as
CONTAINER
, with the fill-pointer set to0
.If the
:KEEP-ELEMENT-TYPE
argument is provided and is true, the element type of the new vector is the same as the element type ofCONTAINER
.
MAKE-SEQUENCE-OF-TYPE
Generic Function: MAKE-SEQUENCE-OF-TYPE TYPE ARGS
Return a new empty sequence / container of type TYPE
.
ARGS
are the type arguments, if any.
The default method creates a built-in sequence of the same type as that returned by:
(make-sequence (cons type args) 0)
SEQUENCE-OF-TYPE
Function: SEQUENCE-OF-TYPE TYPE
Create a new sequence / container of type TYPE
, using
MAKE-SEQUENCE-OF-TYPE.
If TYPE
is a list the CAR
of the list is passed as the first
argument, to MAKE-SEQUENCE-OF-TYPE
, and the CDR
is passed as the
second argument. Otherwise, if TYPE
is not a list, it is passed as
the first argument and NIL
is passed as the second argument.
Elements
ELT
Generic Function: ELT SEQUENCE INDEX
Return the element at position INDEX
in the sequence SEQUENCE
.
-
SEQUENCE T
andVECTOR T
Returns
(CL:ELT SEQUENCE INDEX)
. -
ARRAY INTEGER
Multi-Dimensional Arrays.
Returns
(ROW-MAJOR-AREF SEQUENCE INDEX)
. -
ARRAY LIST
Multi-Dimensional Arrays.
If length of
INDEX
matches array’s rank, returns(apply #'aref sequence index)
.If
INDEX
's length is less than the array’s rank, then returns a displaced array whose dimensions areSEQUENCE
's unused dimensions (ie(nthcdr (array-dimensions sequence) (length index))
) and which shares storage with the subarray ofSEQUENCE
specificied byINDEX
.
(SETF ELT)
Generic Function: (SETF ELT) VALUE SEQUENCE INDEX
Set the value of the element at position INDEX
in the sequence
SEQUENCE
.
-
T SEQUENCE T
andT VECTOR T
Returns
(SETF (CL:ELT SEQUENCE INDEX) VALUE)
. -
T ARRAY INTEGER
Multi-Dimensional Arrays.
Returns
(SETF (ROW-MAJOR-AREF SEQUENCE INDEX) VALUE)
-
ARRAY LIST
Multi-Dimensional Arrays.
If length of
INDEX
matches array’s rank, returns(setf (apply #'aref sequence index) value)
.If
INDEX
's length is less than the array’s rank, then copies the contents ofVALUE
to the subarray (see ELT) specified byINDEX
and then returns(elt sequence index)
.VALUE
's dimensions must equal the unused dimensions ofSEQUENCE
(ie(nthcdr (array-dimensions sequence) (length index))
).
FIRST
Generic Function: FIRST SEQUENCE
Return the first element in the sequence SEQUENCE
.
Implemented for lists, vectors and multi-dimensional arrays. For
multi-dimensional arrays, the first element is obtained by
ROW-MAJOR-AREF
.
The default method is implemented using GENERIC-CL:ELT, i.e. is equivalent to:
(elt sequence 0)
LAST
Generic Function: LAST SEQUENCE &OPTIONAL (N 0)
Return the N
'th element from the last element of the sequence
SEQUENCE
.
N
defaults to 0
which indicates the last element. 1
indicates
the second to last element, 2
the third to last and so on.
Implemented for lists, vectors and multi-dimensional arrays. For multi-dimensional arrays, the last element is obtained by:
(row-major-aref sequence (- (array-total-size array) 1 n))
The default method is implemented using GENERIC-CL:ELT, i.e. is equivalent to:
(elt sequence (- (length sequence) 1 n))
The behaviour of this function differs from CL:LAST when
called on lists, it returns the last element rather than the last
CONS cell. The LASTCDR function performs the same function as
CL:LAST .
|
LASTCDR
Function: LASTCDR LIST &OPTIONAL (N 1)
Return the CDR
of the N
'th CONS
cell from the end of the list.
This function is equivalent to the CL:LAST function.
|
ERASE
Generic Function: ERASE SEQUENCE INDEX
Remove the element at index INDEX
from the sequence SEQUENCE
.
Destructively modifies SEQUENCE .
|
-
VECTOR T
Shifts the elements following
INDEX
one element towards the front of the vector and shrinks the vector by one element.Signals a TYPE-ERROR
if the vector is not adjustable and does not have a fill pointer.
This method is not implemented for lists as removing the first element of a list cannot be implemented as a side effect alone. |
Container Size
LENGTH
Generic Function: LENGTH CONTAINER
Return the number of elements in the container CONTAINER
.
If CONTAINER
is an iterator, return the number of remaining elements
following the iterator’s position.
This function is implemented for all Common Lisp sequences, returning
the length of the sequence (by CL:LENGTH
), and multi-dimensional
arrays, returning the total number of elements in the array by
ARRAY-TOTAL-SIZE
.
EMPTYP
Generic Function: EMPTYP CONTAINER
Return true if the container CONTAINER
is empty.
Implemented for lists, vectors and multi-dimensional arrays (always
returns NIL
).
CLEAR
Generic Function: CLEAR CONTAINER
Destructively remove all elements from the container CONTAINER
.
Implemented for vectors.
ADJUST-SIZE
Generic Function: ADJUST-SIZE CONTAINER N &KEY ELEMENT
Return a new container with the same elements as CONTAINER
however
with its size changed to N
.
If N
is less than the number of elements in CONTAINER
, the
returned container contains only the first N
elements of
CONTAINER
.
If N
is greater than the number of elements in CONTAINER
, the
returned sequence contains all the elements of CONTAINER
with an
additional (LENGTH CONTAINER) - N
elements initialized to the value
of ELEMENT
.
NADJUST-SIZE
Generic Function: NADJUST-SIZE CONTAINER N &KEY ELEMENT
Return a new sequence containing the same elements as CONTAINER
however with its size changed to N
.
CONTAINER may be destructively modified.
|
If N
is less than the number of elements in CONTAINER
, the
returned container contains only the first N
elements of
CONTAINER
.
If N
is greater than the number of elements in CONTAINER
, the
returned sequence contains all the elements of CONTAINER
with an
additional (LENGTH CONTAINER) - N
elements initialized to the value
of ELEMENT
.
Subsequences
SUBSEQ
Generic Function: SUBSEQ SEQUENCE START &OPTIONAL END
Return a new sequence that contains the elements of SEQUENCE
at the
positions in the range [START, END)
.
If SEQUENCE
is an iterator, an iterator for the sub-sequence
relative to the current position of the iterator is returned.
START
is the index of the first element of the subsequence, with 0
indicating the start of the sequence. if SEQUENCE
is an iterator,
START
is the number of times the iterator should be ADVANCE'd to
reach the first element of the subsequence.
END
is the index of the element following the last element of the
subsequence. NIL
(the default) indicates the end of the sequence. If
SEQUENCE
is an iterator, END
is the number of times the iterator
should be ADVANCE'd till the end position is reached.
-
SEQUENCE T
Returns the subsequence using
CL:SUBSEQ
.
(SETF SUBSEQ)
Generic Function: (SETF SUBSEQ) NEW-SEQUENCE SEQUENCE START &OPTIONAL END
Replace the elements of SEQUENCE
at the positions in the range
[START, END)
, with the elements of NEW-SEQUENCE
.
The shorter length of NEW-SEQUENCE
and the number of elements
between START
and END
determines how many elements of SEQUENCE
are actually modified.
See SUBSEQ for more details of how the START
and END
arguments are
interpreted.
-
SEQEUNCE SEQUENCE T
Sets the elements of the subsequence using
(SETF CL:SUBSEQ)
.
Iterator
System and package name GENERIC-CL.ITERATOR
.
The iterator interface is a generic interface for iterating over the elements of sequences and containers.
Implemented for lists, vectors and multi-dimensional arrays.
(loop
with it = (iterator sequence) ; Create iterator for SEQUENCE
until (endp it) ; Loop until the iterator's end position is reached
do
(something (at it)) ; Do something with the current element
(advance it)) ; Advance iterator to next element
Base Iterator Type
Structure: ITERATOR
This structure serves as the base iterator type and is used by certain methods of generic functions to specialize on iterators.
All iterators should inherit from (include) ITERATOR
, in order for
methods which specialize on iterators to be invoked.
A COPY method should be implemented for user-defined iterators. |
Iterator Creation
ITERATOR is the high-level function for creating iterators, whereas MAKE-ITERATOR AND MAKE-REVERSE-ITERATOR are the generic iterator creation functions to implement for user-defined sequence types.
MAKE-ITERATOR
Generic Function: MAKE-ITERATOR SEQUENCE START END
Return an iterator for the sub-sequence of SEQUENCE
, identified by
the range [START, END)
.
START
is the index of the first element to iterate over. 0
indicates the first element of the sequence.
END
is the index of the element at which to terminate the iteration,
i.e. 1 + the index of the last element to be iterated over. NIL
indicates iterating till the end of the sequence.
MAKE-REVERSE-ITERATOR
Generic Function: MAKE-REVERSE-ITERATOR SEQUENCE START END
Return an iterator for the sub-sequence of SEQUENCE
, identified by
the range [START, END)
, in which the elements are iterated over in
reverse order.
Even though the elements are iterated over in reverse order,
START and END are still relative to the start of the sequence, as
in MAKE-ITERATOR .
|
START
is the index of the last element to visit.
END
is the index of the element following the first element to be
iterated over.
ITERATOR
Function: ITERATOR SEQUENCE &KEY (START 0) END FROM-END
Return an iterator for the sub-sequence of SEQUENCE
identified by
the range [START, END)
.
START
(defaults to 0
- the start of the sequence) and END
(defaults to NIL
- the end of the sequence) are the start and end
indices of the sub-sequence to iterate over (see MAKE-ITERATOR and
MAKE-REVERSE-ITERATOR for more a detailed description).
If FROM-END
is true a reverse iterator is created (by
MAKE-REVERSE-ITERATOR) otherwise a forward iterator is created (by
MAKE-ITERATOR).
Mandatory Functions
These functions must be implemented for all user-defined iterators.
AT
Generic Function: AT ITERATOR
Return the value of the element at the current position of the
iterator ITERATOR
.
The effects of calling this method, after the iterator has reached the end of the subsequence are unspecified. |
ENDP
Generic Function: ENDP ITERATOR
Return true if the iterator is at the end of the subsequence, false otherwise.
The end of the subsequence is defined as the the position of the iterator after advancing it (by ADVANCE) from the position of the last element.
If the subsequence is empty ENDP
should immediately return true.
The default T method calls CL:ENDP since this function
shadows the CL:ENDP function.
|
Optional Functions
Implementing the following functions for user-defined iterators is optional either because a default method is provided, which is implemented using the mandatory functions, or the function is only used by a select few sequence operations.
START
Generic Function: START ITERATOR
Return the element at the current position of the iterator, if the
iterator is not at the end of the sequence. Otherwise return NIL
.
The default method first checks whether the end of the iterator has
been reached, using ENDP
, and if not returns the current element
using AT
.
The default method is equivalent to the following:
(unless (endp iterator)
(at iterator))
(SETF AT)
Generic Function: (SETF AT) VALUE ITERATOR
Set the value of the sequence element at the iterator’s current position.
The effects of calling this function when, the iterator is past the end of the subsequence are unspecified. |
Implementing this function is only mandatory if destructive sequence operations will be used. |
Macros
Macros for iteratoring over a generic sequence. Analogous to
CL:DOLIST
.
DOSEQ
Macro: DOSEQ (ELEMENT SEQUENCE &REST ARGS) &BODY BODY
Iterate over the elements of a sequence, evaluating a list of forms at each iteration.
The iterator interface must be implemented for the sequence, the elements of which, are being iterated over. |
An optimized expansion, which does not use the iterator interface, may be emitted if the type of sequence can be determined at compile-time and there is a MAKE-DOSEQ method for that type. |
ELEMENT
-
Name of the variable which receives the value of the current sequence element at each iteration. May also be a list in which case it is interpreted as a destructuring pattern, as if to
DESTRUCTURING-BIND
, according to which the element is destructured. ARGS
-
Remaining arguments passed to the ITERATOR function. The following keyword arguments are recognized
:START
,:END
and:FROM-END
. BODY
-
List of forms to evaluate at each iteration.
The forms are evaluated in an implicit
PROGN
, with the variables introduced byELEMENT
visible to these forms. The loop may be terminated early usingRETURN-FROM
to aNIL
block, with the value returned from theDOSEQ
form.The forms may be preceded by one or more declarations.
Returns NIL
unless a RETURN-FROM
to block NIL
is executed in
BODY
.
DO-SEQUENCES
Macro: DO-SEQUENCES (&REST SEQUENCES) &BODY BODY
Same as DOSEQ however for iterating over multiple sequences simultaneously.
SEQUENCES
-
The sequences over which to iterate and the names of the variables which receive the values of their elements.
Each element is of the form
(ELEMENT SEQUENCE &REST ARGS)
, which corresponds to theELEMENT
,SEQUENCE
andARGS
arguments of DOSEQ. BODY
-
List of forms to evaluate at each iteration, same as the body argument to DOSEQ
The forms may be preceded by one or more declarations.
DOSEQ!
Macro: DOSEQ! (NAME SEQUENCE &REST ARGS) &BODY BODY
Same as DOSEQ
however allows for the sequence elements to be
mutated.
The (SETF AT) function must be implemented for the sequence type. |
NAME
-
Name of the symbol-macro which expands to the place of the current sequence elements.
The symbol-macro can be used to either reference the element’s value or set the element’s value, using
SETF
. ARGS
-
Remaining arguments passed to the ITERATOR function. The following keyword arguments are recognized
:START
,:END
and:FROM-END
. BODY
-
List of forms to evaluate at each iteration.
The forms are evaluated in an implicit
PROGN
, with the symbol-macro introduced byNAME
visible to these forms. The loop may be terminated early usingRETURN-FROM
to aNIL
block, with the value returned from theDOSEQ
form.The forms may be preceded by one or more declarations.
Returns NIL
unless a RETURN-FROM
to block NIL
is executed in
BODY
.
DO-SEQUENCES!
Macro: DO-SEQUENCES! (&REST SEQUENCES) &BODY BODY
Same as DOSEQ! however for iterating over multiple sequences simultaneously.
SEQUENCES
-
The sequences over which to iterate and the names of the variables which receive the values of their elements.
Each element is of the form
(NAME SEQUENCE &REST ARGS)
, which corresponds to theNAME
,SEQUENCE
andARGS
arguments of DOSEQ. BODY
-
List of forms to evaluate at each iteration, same as the body argument to DOSEQ
The forms may be preceded by one or more declarations.
Low-Level Macros
These macros provide access to the iterator’s themselves, used to implement the high-level iteration macros, allowing for greater control over the iteration process.
WITH-ITERATORS
Macro: WITH-ITERATORS (&REST SEQUENCES) &BODY FORMS
Setup the iterator state for iterating over one or more sequences.
WITH-ITER-VALUE and WITH-ITER-PLACE, can be used within this macro to retrieve/set the element pointed to by the iterators and advance their positions.
This macro attempts to determine the type of each sequence
and calls MAKE-DOSEQ to generate optimal iterator code for the given
sequence types, rather than creating dynamic iterator objects. Falls
back to the iterator interface, if the types of the sequences cannot
be determined.
|
SEQUENCES
-
List of sequences to create iterators for.
Each element is of the form
(ITER SEQUENCE . ARGS)
, whereITER
is a symbol with which the iterator is identified,SEQUENCE
is the form producing the sequence to iterate over, andARGS
are the remaining iteration arguments, interpreted as the keyword arguments to the ITERATOR arguments.Each
ITER
is a symbol that identifies the iterator, inWITH-ITER-VALUE
andWITH-ITER-PLACE
.Iterator identifiers are in a namespace of their own that is they do not name lexical variables/symbol-macros nor functions/macros. FORMS
-
A list of forms evaluated in an implicit
TAGBODY
, thus symbols are interpreted as tag names.The
WITH-ITER-VALUE
macro can be used, withinFORMS
, to retrieve the current element of the sequence and advance the iterator to the next position.The
WITH-ITER-PLACE
macro can be used, withinFORMS
, both to retrieve and set the value of the current element of the sequence, and advance the iterator to the next position.The value of the last form is not returned, due to it being evaluated in a TAGBODY
, insteadNIL
is returned.RETURN-FROM
, to an outerBLOCK
, should be used to return a value from this form.
Whilst the intended use of WITH-ITERATORS is to implement
iteration macros, such as DOSEQ , the FORMS are only evaluated once. It
is up to the user to implement the actual loop, using the provided
TAGBODY facility.
|
WITH-ITER-VALUE
Macro: WITH-ITER-VALUE (PATTERN ITER) &BODY BODY
Bind the current element of a sequence, pointed to by an iterator, to a variable, and advance the iterator’s position to the next element.
This macro may only be used within the body of a WITH-ITERATORS macro. |
The value of the element at the current position of the iterator,
identified by ITER
, is bound to the variable(s) specified by
PATTERN
, with the bindings visible to the forms in BODY
.
If the iterator is already at the end of the sequence, a non-local
jump to the end of the WITH-ITERATORS
form, in which the iterator
was introduced, is performed.
After binding the values, the position of the iterator is advanced to the next element in the sequence.
PATTERN
-
A binding pattern specifying the variable(s) to which the value of the element, at the current position of the iterator, is bound.
This may either be a symbol, naming a variable, or a list which is interpreted as a
DESTRUCTURING-BIND
pattern. ITER
-
Symbol identifying the iterator, that was given as the
ITER
argument to a parentWITH-ITERATORS
form. BODY
-
The body of the
WITH-ITER-VALUE
form, which consists of a list of forms optionally preceded by a number of declaration expressions.BODY ::= DECLARATION* FORM*
The forms are evaluated in an implicit
PROGN
, with the value of the last form returned from theWITH-ITER-VALUE
form. The binding(s) introduced byPATTERN
are visible to the forms.If there are no more elements in the sequence, the forms are not evaluated.
WITH-ITER-VALUES
Macro WITH-ITER-VALUES (&REST BINDINGS) &BODY BODY
Like WITH-ITER-VALUE except the values of multiple sequence elements are bound simultaneously.
If one of the iterators has reached the end of its sequence, a non-local jump is performed to the end of the WITH-ITERATORS form corresponding to the first iterator which has reached the end of its sequence.
BINDINGS
-
A list of sequence element bindings as if to
WITH-ITER-VALUE
, each of the form(PATTERN ITER)
.((pattern-1 iter-1) (pattern-2 iter-2) ... (pattern-n iter-n))
This is functionally equivalent to a series of nested
WITH-ITER-VALUE
forms.(with-iter-value (pattern-1 iter-1) (with-iter-value (pattern-2 iter-2) (... (with-iter-value (pattern-n iter-n) ,@body))))
However unlike simply nesting
WITH-ITER-VALUE
forms, declarations occurring inBODY
are handled properly and associated with the correctWITH-ITER-VALUE
form, depending on which variable(s) they apply to. BODY
-
The body of the
WITH-ITER-VALUES
form, which consists of a list of forms optionally preceded by a number of declaration expressions.BODY ::= DECLARATION* FORM*
The forms are evaluated in an implicit
PROGN
, with the value of the last form returned from theWITH-ITER-VALUES
form. The binding(s) introduced byPATTERN
are visible to the forms.If there are no more elements in at least one of the sequences, the forms are not evaluated.
WITH-ITER-PLACE
Macro: WITH-ITER-PLACE (NAME ITER &OPTIONAL MOREP) &BODY BODY
Bind a symbol to the place, suitable for use with SETF
, of the
current sequence element.
This macro may only be used within the body of a WITH-ITERATORS macro. |
A symbol-macro, with identifier given by NAME
, is introduced, which
expands to the place, suitable for use with SETF
, of the element
at the iterator’s current position. This symbol-macro is visible to
the forms in BODY
.
If the iterator is already at the end of the sequence, a non-local
jump to the end of the WITH-ITERATORS
form, in which it was
introduced, is performed, unless a MOREP
variable name is given.
The iterator is also advanced to the next element of the sequence
after all forms in BODY
are evaluated. However, the iterator is only
guaranteed to be advanced on a normal exit from the WITH-ITER-PLACE
form. If a non-local jump is performed, via GO
, RETURN-FROM
or
THROW
, the iterator might not be advanced.
NAME
-
Identifier of the symbol-macro to introduce.
Unlike in WITH-ITER-VALUE this must be a symbol and cannot be a destructuring pattern. MOREP
-
Name of the variable, which is bound to true if there are more elements in the sequence following the iterator’s position, and to
NIL
if the end of the sequence has been reached.If given and it is non-
NIL
, no checks are performed for whether the iterator has reached the end of its sequence, and hence the forms inBODY
are not skipped. It is up to the programmer to check the value of this variable and performed whatever logic should be performed upon reaching the end of the sequence. ITER
-
Symbol identifying the iterator, that was given as the
ITER
argument to a parentWITH-ITERATORS
form. BODY
-
The body of the
WITH-ITER-PLACE
form, which consists of a list of forms optionally preceded by a number of declaration expressions.BODY ::= DECLARATION* FORM*
The forms are evaluated in an implicit
PROGN
, with the value of the last form returned from theWITH-ITER-PLACE
form.If there are no more elements in the sequence, and a MOREP
variable has not been given, the forms are not evaluated, and a non-local jump is performed to the end of theWITH-ITERATORS
, in which the iterator was introduced..
WITH-ITER-PLACES
Macro WITH-ITER-PLACES (&REST BINDINGS) &BODY BODY
Like WITH-ITER-PLACE except multiple places, for multiple sequences, are bound simultaneously.
If one of the iterators has reached the end of its sequence, and a
corresponding MOREP
variable has not been given, a non-local jump is
performed to the end of the WITH-ITERATORS form corresponding to
the first iterator which has reached the end of its sequence.
BINDINGS
-
A list of sequence element place bindings as if to
WITH-ITER-PLACE
, each of the form(NAME ITER)
or(NAME ITER MOREP)
.((name-1 iter-1) (name-2 iter-2) ... (name-n iter-n))
This is functionally equivalent to a series of nested
WITH-ITER-PLACE
forms.(with-iter-place (name-1 iter-1) (with-iter-place (name-2 iter-2) (... (with-iter-place (name-n iter-n) ,@body))))
However unlike simply nesting
WITH-ITER-PLACE
forms, declarations occurring inBODY
are handled properly and associated with the correctWITH-ITER-PLACE
form, depending on which variable(s) they apply to. BODY
-
The body of the
WITH-ITER-PLACES
form, which consists of a list of forms optionally preceded by a number of declaration expressions.BODY ::= DECLARATION* FORM*
The forms are evaluated in an implicit
PROGN
, with the value of the last form returned from theWITH-ITER-PLACES
form. The symbol-macro(s) introduced inBINDINGS
are visible to the forms.
DO-ITER-VALUES
Macro DO-ITER-VALUES (&REST ITERS) &BODY BODY
Iterate over the remaining elements following the positions of one or more iterators.
The list of forms in BODY
are evaluated at each iteration, until one
of the iterators reaches the end of its sequence.
May only be used inside a WITH-ITERATORS form. |
ITERS
-
List of element value bindings.
Each element is of the form
(PATTERN ITER)
, as if to WITH-ITER-VALUE, wherePATTERN
is the binding pattern, specifying the variable(s) which will receive the value of the current element andITER
is the identifier of the iterator, as given in theITER
argument of the WITH-ITERATORS form. BODY
-
The body of the
DO-ITER-VALUES
form, which consists of a list of forms optionally preceded by a number of declaration expressions.BODY ::= DECLARATION* FORM*
The forms are evaluated once for each element, after which each iterator is advanced to the next element in its sequence.
This form returns NIL
.
When the end of a sequence is reached, a non-local jump to
the WITH-ITERATORS form, corresponding to the sequence’s iterator,
is performed. Thus any forms following the DO-ITER-VALUES form are
skipped.
|
DO-ITER-PLACES
Macro DO-ITER-PLACES (&REST ITERS) &BODY BODY
Like DO-ITER-VALUES except the bindings to the places, with WITH-ITER-PLACE, are introduced, rather than bindings to the values of the sequence elements.
The list of forms in BODY
are evaluated at each iteration, until one
of the iterators reaches the end of its sequence.
May only be used inside a WITH-ITERATORS form. |
ITERS
-
List of element place bindings.
Each element is of the form
(NAME ITER)
, as if to WITH-ITER-PLACE, whereNAME
is the name of the symbol-macro expanding to the element place, andITER
is the identifier of the iterator, as given in theITER
argument of the WITH-ITERATORS form. BODY
-
The body of the
DO-ITER-PLACES
form, which consists of a list of forms optionally preceded by a number of declaration expressions.BODY ::= DECLARATION* FORM*
The forms are evaluated once for each element, after which each iterator is advanced to the next element in its sequence.
This form returns NIL
.
When the end of a sequence is reached, a non-local jump to
the WITH-ITERATORS form, corresponding to the sequence’s iterator,
is performed. Thus any forms following the DO-ITER-PLACES form are
skipped.
|
DOITERS
Macro: DOITERS (&REST ITERS) &BODY BODY
Iterate over one or more sequences with the sequence iterators bound to variables.
Each element of ITERS
is a list of the form (IT-VAR
SEQUENCE . ARGS)
, where IT-VAR
is the variable to which the
iterator is bound, SEQUENCE
is the sequence which will be iterated
over and ARGS
are the remaining arguments passed to the
ITERATOR function.
The bindings to the IT-VAR
's are visible to the forms in BODY
,
which are executed once for each element in the sequence. After each
iteration the sequence iterators are ADVANCE'd. The loop
terminates when the end of a sequence is reached.
DOITER
Macro: DOITER (ITER &REST ARGS) &BODY BODY
The is the same as DOITERS except only a single sequence is iterated over.
Implemented Interfaces
This interface adds methods, when the system implementing the
interface is loaded, specialized on ITERATOR
's to the following
functions:
LENGTH
Method: LENGTH (ITERATOR ITERATOR)
Returns the number of elements between the iterator’s current position (inclusive) and the end of the iterator’s subsequence.
This is implemented by advancing the iterator (by ADVANCE) till
ENDP returns true, thus is a linear O(n)
time operation.
More efficient specialized methods are provided for iterators to sequences for which the size is known.
SUBSEQ
Method: SUBSEQ (ITERATOR ITERATOR) START &OPTIONAL END
Returns a subsequence iterator which wraps a copy of the original iterator.
Optimization
The iteration macros, DOSEQ, DOSEQ!, and the corresponding macros for multiple sequences, can be optimized to generate specialized iteration code for a given sequence type so that the creation of iterator objects and the dynamic dispatch involving the iterator methods, can be avoided.
These are implemented in terms of the Low-Level Macros,
specifically the WITH-ITERATORS family of macros. WITH-ITERATORS
attempts to determine the type of each sequence and calls
MAKE-DOSEQ to generate specialized iteration code.
The symbols documented in this section are contained in the
GENERIC-CL.ITERATOR.OPTIMIZATION package, which is not exported by
GENERIC-CL . Thus it has to be manually imported. It doesn’t contain
nay shadowing symbols so it can simply be used.
|
MAKE-DOSEQ
Generic Function: MAKE-DOSEQ TYPE SEQUENCE ARGS TAG BODY ENVIRONMENT
Generate the WITH-ITERATORS expansion for a sequence of a given type.
Combination
This method has the SUBTYPE
method combination, thus each method
should have a single qualifier which is interpreted as a type
specifier symbol.
When the generic function is called with a given sequence type, passed
to the TYPE
argument, the method with the most derived type, given
in the qualifier, which is a subtype of TYPE
is called.
Most derived means that if there are two methods with qualifiers which
are a both subtypes of the type given in TYPE
, the method with the
qualifier that is a subtype of the other method’s qualifier, is
called.
CALL-NEXT-METHOD and auxiliary methods are not supported by
this combination.
|
Arguments
TYPE
-
The full sequence type as determined by the
WITH-ITERATORS
macro. SEQUENCE
-
The form which produces the sequence.
ARGS
-
Remaining iterator arguments following the sequence.
These should be interpreted as they are in the ITERATOR function, that is the keyword arguments
:START
,:END
and:FROM-END
should be supported. TAG
-
Name of the tag, in an enclosing
TAGBODY
form, to jump to, withGO
, when the end of the sequence is reached. BODY
-
List of forms comprising the body of the
WITH-ITERATORS
form. These may be preceded by a number of declaration expressions. ENV
-
The environment in which the
WITH-ITERATORS
form is found.
Return Values
Methods of this function should return the following values:
-
A list of bindings, as if by
LET*
, which are established before the first iteration and are visible to the body forms of theWITH-ITERATORS
form.Each binding, in this list, may optional provide the following keyword arguments, after the init-form:
:CONSTANT
-
Flag for whether the variable should be treated as a constant
If true and the init-form is a constant form, by
CONSTANTP
, the symbol is bound bySYMBOL-MACROLET
, rather thanLET*
.A constant binding may only reference other bindings, preceding it, for which this flag is also true.
-
The new body of the
WITH-ITERATORS
form. This body is passed to theMAKE-DOSEQ
methods of the other sequences. -
A lexical macro definition defining the expansion of the WITH-ITER-VALUE for the sequence’s iterator.
This should be a list of the form:
(LAMBDA-LIST . BODY)
where
LAMBDA-LIST
is the macro lambda-list andBODY
is the macro definition body. A name should not be provided since one is automatically generated.The lambda-list should have the following arguments:
(PATTERN &BODY BODY)
where
PATTERN
is the binding pattern, corresponding to thePATTERN
argument of WITH-ITER-VALUE, specifying the variable(s) which receive the value of the current sequence element.This may either be a symbol, naming a variable, or a list which should be interpreted as a
DESTRUCTURING-BIND
pattern.Use WITH-DESTRUCTURE-PATTERN to automatically support destructuring patterns. This also handles declarations correctly. BODY
is the list of body forms of theWITH-ITER-VALUE
form, corresponding to theBODY
argument. These may be preceded by declarations some of which, might apply to variables in outerWITH-ITER-VALUE
forms.The macro should expand to a form which:
-
Checks whether the end of the sequence has been reached. If so jumps, using
GO
, to the tag name given in theTAG
argument toMAKE-DOSEQ
. -
Binds the current sequence element to the variable(s) specified in
PATTERN
-
Advances the position of the iterator to the next element in the sequence
-
Evaluates the body forms.
Declarations not applying to the variable(s) in
PATTERN
, should be placed in aLOCALLY
form wrapping the macro expansion, in order for them to be processed by otherWITH-ITER-VALUE
forms. Additionally the macro should also recognize a body consisting of a singleLOCALLY
form, and process the declarations in that form as though they occurred directly in the body. WITH-DESTRUCTURE-PATTERN handles this automatically. -
-
A lexical macro definition defining the expansion of WITH-ITER-PLACE for the sequence’s iterator.
This should be a list of the form:
(LAMBDA-LIST . BODY)
where
LAMBDA-LIST
is the macro lambda-list andBODY
is the macro definition body. A name should not be provided since one is automatically generated.The lambda-list should have the following arguments:
(NAME MOREP &BODY BODY)
where
NAME
is the name of the symbol-macro to be introduced, expanding to the place of the current position of the iterator, corresponding to theNAME
argument of WITH-ITER-PLACE.MOREP
corresponds to theMOREP
argument of WITH-ITER-PLACE, which is the name of the variable receiving a flag for whether there are more elements in the sequence (true), or whether the end of the sequence has been reached (NIL
).BODY
is the list of body forms of theWITH-ITER-PLACE
form, corresponding to theBODY
argument. These may be preceded by declarations some of which, might apply to symbol-macros introduced by outerWITH-ITER-PLACE
forms.The macro should expand to a form which:
-
If
MOREP
isNIL
, checks whether the end of the sequence has been reached. If so jumps, usingGO
, to the tag name given in theTAG
argument toMAKE-DOSEQ
. IfMOREP
is non-NIL
binds the variable given inMOREP
to true if there are more elements in the sequence, or toNIL
if the end of the sequence has been reached. -
Creates a lexical symbol-macro, with identifier
NAME
that expands to the place of the current position of the iterator. -
Evaluates the body forms.
-
Advances the position of the iterator.
Declarations not applying to the symbol-macro, should be placed in a
LOCALLY
form wrapping the macro expansion, in order for them to be processed by otherWITH-ITER-PLACE
forms. Additionally the macro should also recognize a body consisting of a singleLOCALLY
form, and process the declarations in that form as though they occurred directly in the body. WITH-VARIABLE-DECLARATIONS handles this automatically. -
The macro ITER-MACRO, facilitates the creation of these
lexical macro definitions, removing the need for multiple nested
layers of backquotes. Use this macro when defining your own
MAKE-DOSEQ methods.
|
ITER-MACRO
Macro: ITER-MACRO (&REST VARS) (&REST LAMBDA-LIST) &BODY BODY
Utility macro for generating lexical macro definitions for WITH-ITER-VALUE and WITH-ITER-PLACE.
This macro is intended to be used within MAKE-DOSEQ to facilitate
the definition, by avoiding the need for nested backquotes, of the
lexical macros, serving as the expansion of WITH-ITER-VALUE
and
WITH-ITER-PLACE
for a given iterator type.
Arguments
VARS
-
List of variables to capture from the lexical scope of the
ITER-MACRO
form.Lexical variables are generated for each variable that is listed, accessible to the definition body, which are set to the values of the equivalent variables evaluated in the scope of the
ITER-MACRO
form. LAMBDA-LIST
-
Macro lambda-list (not evaluated).
BODY
-
The body of the macro definition, consisting of a list of forms optionally preceded by declaration expressions.
These are not evaluated but are literally inserted in the body of the macro definition. The forms have access to the variables listed in
VARS
, at the time the macro is expanded.
WITH-DESTRUCTURE-PATTERN
Macro WITH-DESTRUCTURE-PATTERN (VAR PATTERN) (FORMS-VAR DECL-VAR BODY-FORM) &BODY BODY
Automatically generate destructuring code if the binding pattern is a destructuring-bind pattern.
This macro allows a WITH-ITER-VALUE macro to be written whilst focusing only on the case where the binding pattern is a variable receiving the entire element value. The macro automatically generates destructuring code if the binding pattern is a list.
This macro also handles declarations automatically.
Arguments
VAR
-
Name of the variable receiving the name of the variable to which the element value is bound.
PATTERN
-
Form producing the binding pattern (evaluated).
FORMS-VAR
-
Name of the variable receiving the list of body forms of the
WITH-ITER-MACRO
. DECL-VAR
-
Name of the variable receiving the list of declarations applying to the variable in
VAR
. BODY-FORM
-
Form producing the
WITH-ITER-VALUE
body (evaluated). BODY
-
List of forms evaluated in an implicit
PROGN
. The return value of the last form is returned as the macroexpansion of theWITH-ITER-VALUE
, wrapped in the destructuring code if necessary.May be preceded by declaration expressions.
The expansion returned should bind the variable in
VAR
to the value of the next element in the sequence and evaluate the forms inFORMS-VAR
in the context of that binding.
Declarations
This macro takes care of handling declarations in the result returned
by BODY-FORM
. The declarations applying to the variables in the
destructuring pattern, are inserted in the resulting
destructuring-bind
form, DECL-VAR
is bound to the declarations
applying to the variable given in VAR
, and the remaining
declarations are inserted in a LOCALLY
form, wrapping the entire
expansion.
WITH-VARIABLE-DECLARATIONS
Macro: WITH-VARIABLE-DECLARATIONS (&REST BINDINGS) FORMS-VAR BODY-FORM &BODY BODY
Split a body into the declarations, applying to specific variables, and its forms.
Intended to be used in the lexical macro definition for WITH-ITER-PLACE for a sequence type. |
Arguments
BINDINGS
-
List of variables for which to extract the declarations.
Each element is of the form
(DECL-VAR VAR)
, whereDECL-VAR
is the name of the variable which is to receive the list of declarations applying to the variable given byVAR
(evaluated). FORMS-VAR
-
Name of the variable receiving the list of forms in the body.
BODY-FORM
-
Form producing the body.
BODY
-
List of forms evaluated in an implicit
PROGN
, with the result returned by the last form included in the resulting expansion.
Expansion
The value returned by the macro is a LOCALLY
form containing the
declarations not applying to any of the variables listed in BINDINGS
and the body of which is the form returned by the last form in BODY
.
Collector
System and package name GENERIC-CL.COLLECTOR
.
The collector interface is a generic interface for accumulating items into a sequence/container.
Implemented for lists and vectors.
While this interface is specified for sequences, it may also be implemented for unordered containers. |
;; Create collector for the sequence, in this case an empty list
(let ((c (make-collector nil)))
(accumulate c 1) ; Collect 1 into the sequence
(accumulate c 2) ; Collect 2 into the sequence
(extend c '(3 4 5)) ; Collect 3, 4, 5 into the sequence
(collector-sequence c)) ; Get the resulting sequence => '(1 2 3 4 5)
MAKE-COLLECTOR
Generic Function: MAKE-COLLECTOR SEQUENCE &KEY FRONT
Return a collector for accumulating items to the end of the sequence
SEQUENCE
.
If :FRONT
is provided and is true, the items are accumulated to the
front of the sequence rather than end.
The collector may destructively modify SEQUENCE however
it is not required to do so and may accumulate items into a copy of
SEQUENCE instead.
|
ACCUMULATE
Generic Function: ACCUMULATE COLLECTOR ITEM
Accumulate ITEM
into the sequence associated with the collector
COLLECTOR
.
COLLECTOR-SEQUENCE
Generic Function: COLLECTOR-SEQUENCE COLLECTOR
Return the underlying sequence associated with the collector
COLLECTOR
.
The sequence should contain all items accumulated up to the call to this function.
The effects of accumulating items into the sequence, by ACCUMULATE or EXTEND, after this function is called, are unspecified. |
The sequence returned might not be the same object passed to MAKE-COLLECTOR. |
EXTEND
Generic Function: EXTEND COLLECTOR SEQUENCE
Accumulate all elements of the sequence SEQUENCE
into the sequence
associated with the collector COLLECTOR
.
If SEQUENCE
is an iterator all elements up-to the end of the
iterator (till ENDP returns true) should be accumulated.
Implementing this method is optional as default methods are provided for iterators and sequences, which simply accumulate each element one by one using ACCUMULATE. |
Methods
-
T ITERATOR
Accumulates all elements returned by the iterator
SEQUENCE
(till(ENDP SEQUENCE)
returns true), into the sequence associated with the collector.The elements are accumulated one by one using ACCUMULATE.
The iterator is copied thus the position of the iterator passed as an argument is not modified. -
T T
Accumulates all elements of
SEQUENCE
, into the sequence associated with the collector.The elements are accumulated one by one using ACCUMULATE.
The sequence iteration is done using the Iterator interface.
Sequence
System and package name GENERIC-CL.SEQUENCE
Generic sequence operations.
Generic function wrappers, which are identical in behavior to their
counterparts in the COMMON-LISP
package, are provided for the
following sequence operations:
-
FILL
-
REPLACE
-
REDUCE
-
COUNT
-
COUNT-IF
-
COUNT-IF-NOT
-
FIND
-
FIND-IF
-
FIND-IF-NOT
-
POSITION
-
POSITION-IF
-
POSITION-IF-NOT
-
SEARCH
-
MISMATCH
-
REVERSE
-
NREVERSE
-
SUBSTITUTE
-
NSUBSTITUTE
-
SUBSTITUTE-IF
-
NSUBSTITUTE-IF
-
SUBSTITUTE-IF-NOT
-
NSUBSTITUTE-IF-NOT
-
REMOVE
-
DELETE
-
REMOVE-IF
-
DELETE-IF
-
REMOVE-IF-NOT
-
DELETE-IF-NOT
-
REMOVE-DUPLICATES
-
DELETE-DUPLICATES
Two methods are implemented, for all functions, which are specialized on the following types:
-
CL:SEQUENCE
Simply calls the corresponding function in the
COMMON-LISP
package. -
T
Implements the sequence operation for generic sequences using the Iterator interface.
The non-destructive functions only require that the Mandatory Iterator Functions, the Collector interface and CLEARED method are implemented for the sequence’s type.
The destructive versions may additionally require that the optional (SETF AT) method is implemented as well.
The default value of the :TEST keyword argument is
GENERIC-CL:EQUALP. This should be the default value when
implementing methods for user-defined sequence types. The :TEST-NOT
keyword arguments have been removed.
|
The following functions are identical in behavior to their CL
counterparts, however are re-implemented using the iterator
interface. Unlike the functions in the previous list, these are not
generic functions since they take an arbitrary number of sequences as
arguments.
-
EVERY
-
SOME
-
NOTEVERY
-
NOTANY
The following functions either have no CL
counterparts or differ
slightly in behavior from their CL
counterparts:
FIND-IT
Generic Function: FIND-IT ITEM SEQUENCE &KEY FROM-END START END TEST KEY
Find an element in a sequence and return an iterator to the position at which it was found.
This is the same as FIND except it returns an iterator to the
position at which an element is found rather than the element itself.
|
Arguments
ITEM
-
The item to find in the sequence.
SEQUENCE
-
The sequence to search.
FROM-END
-
If true the sequence is searched starting from the end.
START
-
Index of the starting position from which to search the sequence. By default searches from the start of the sequence.
END
-
Index of the position till which the sequence is searched. If
NIL
(the default) the entire sequence is searched. TEST
-
Test function to use when comparing
ITEM
to elements ofSEQUENCE
. By default EQUALP. KEY
-
Function which is applied on each element of
SEQUENCE
. The result returned is then compared toITEM
usingTEST
.
If the item was found in the sequence, returns the iterator to the
first position, or last if FROM-END
is true, at which it was
found. If no such item was found, NIL
is returned.
The iterator returned should point to the same sequence object that is passed to this function. This is to allow iterating over the remaining elements of the sequence and to allow for modifying the sequence. |
FIND-IT-IF
Generic Function: FIND-IT-IF PREDICATE SEQUENCE &KEY FROM-END START END KEY
Find an element, which satisfies a predicate, in a sequence and return an iterator to the position at which it was found.
This is the same as FIND-IF except it returns an iterator to the
position at which an element is found rather than the element itself.
|
Arguments
PREDICATE
-
A predicate function, of one argument, applied on each element of sequence. The element for which this function returns true, is returned.
SEQUENCE
-
The sequence to search.
FROM-END
-
If true the sequence is searched starting from the end.
START
-
Index of the starting position from which to search the sequence. By default searches from the start of the sequence.
END
-
Index of the position till which the sequence is searched. If
NIL
(the default) the entire sequence is searched.SEQUENCE
. KEY
-
Function which is applied on each element of
SEQUENCE
. The result returned is then passed to the predicate function.
Returns an iterator to the first item, or last if FROM-END
is true,
for which the predicate returns true. If no element is found, NIL
is
returned.
The iterator returned should point to the same sequence object that is passed to this function. This is to allow iterating over the remaining elements of the sequence and to allow for modifying the sequence. |
FIND-IT-IF-NOT
Generic Function: FIND-IT-IF PREDICATE SEQUENCE &KEY FROM-END START END KEY
Find an element, which does not satisfy a predicate, in a sequence and return an iterator to the position at which it was found.
This is the same as FIND-IF-NOT except it returns an iterator to the
position at which an element is found rather than the element itself.
|
Arguments
PREDICATE
-
A predicate function, of one argument, applied on each element of sequence. The element for which this function returns false (
NIL
), is returned. SEQUENCE
-
The sequence to search.
FROM-END
-
If true the sequence is searched starting from the end.
START
-
Index of the starting position from which to search the sequence. By default searches from the start of the sequence.
END
-
Index of the position till which the sequence is searched. If
NIL
(the default) the entire sequence is searched.SEQUENCE
. KEY
-
Function which is applied on each element of
SEQUENCE
. The result returned is then passed to the predicate function.
Returns an iterator to the first item, or last if FROM-END
is true,
for which the predicate returns false. If no element is found, NIL
is returned.
The iterator returned should point to the same sequence object that is passed to this function. This is to allow iterating over the remaining elements of the sequence and to allow for modifying the sequence. |
MERGE
Generic Function: MERGE SEQUENCE1 SEQUENCE2 PREDICATE &KEY
Return a new sequence, of the same type as SEQUENCE1
, containing the
elements of SEQUENCE1
and SEQUENCE2
.
The elements are ordered according to the function PREDICATE
.
Unlike CL:MERGE this function is non-destructive.
|
NMERGE
Generic Function: MERGE SEQUENCE1 SEQUENCE2 PREDICATE &KEY
Same as MERGE however is permitted to destructively modify either
SEQUENCE1
or SEQUENCE2
.
SORT
Generic Function: SORT SEQUENCE &KEY TEST KEY
Return a new sequence of the same type as SEQUENCE
, with the same
elements sorted according to the order determined by the function
TEST
.
TEST
is GENERIC-CL:LESSP by default.
Unlike CL:SORT this function is non-destructive.
|
STABLE-SORT
Generic Function: STABLE-SORT SEQUENCE &KEY TEST KEY
Same as SORT however the sort operation is guaranteed to be stable, that is the relative order of elements of which neither compares less than the other, is preserved.
TEST
is GENERIC-CL:LESSP by default.
Unlike CL:STABLE-SORT this function is non-destructive.
|
NSORT
Generic Function: NSORT SEQUENCE &KEY TEST KEY
Same as SORT however is permitted to destructively modify
SEQUENCE
.
STABLE-NSORT
Generic Function: STABLE-NSORT SEQUENCE &KEY TEST KEY
Same as STABLE-SORT however is permitted to destructively modify
SEQUENCE
.
CONCATENATE
Generic Function: CONCATENATE SEQUENCE &REST SEQUENCES
Return a new sequence, of the same type as SEQUENCE
, containing all
the elements of SEQUENCE
and of each sequence in SEQUENCES
, in the
order they are supplied.
Unlike CL:CONCATENATE does not take a result type
argument.
|
NCONCATENATE
Generic Function: NCONCATENATE RESULT &REST SEQUENCES
Destructively concatenate each sequence in SEQUENCES
to the sequence
RESULT
.
Returns the result of the concatenation.
Whilst this function is permitted to destructively modify
RESULT and SEQUENCES , it is not required and may return a new
sequence instead. Thus do not rely on this function for its side
effects.
|
CONCATENATE-TO
Generic Function: CONCATENATE-TO TYPE &REST SEQUENCES
Concatenate each sequence in SEQUENCES
into a new sequence of type
TYPE
.
The new sequence is created by passing TYPE
to SEQUENCE-OF-TYPE.
MAP
Generic Function: MAP FUNCTION SEQUENCE &REST SEQUENCES
Create a new sequence, of the same type as SEQUENCE
(by
CLEARED), containing the result of applying FUNCTION
to each
element of SEQUENCE and each element of each SEQUENCE
in
SEQUENCES
.
This function is equivalent (in behavior) to the CL:MAP
function except the resulting sequence is always of the same type as
the first sequence passed as an argument, rather than being determined
by a type argument.
|
NMAP
Generic Function: NMAP RESULT FUNCTION &REST SEQUENCES
Destructively replace each element of RESULT
with the result of
applying FUNCTION
to each element of RESULT
and each element of
each sequence in SEQUENCES.
Returns the resulting sequence.
Whilst this function is permitted to modify RESULT , it is
not required to do so and may return the result in a new sequence
instead. Thus do not rely on this function for its side effects.
|
MAP-INTO
Generic Function: MAP-INTO RESULT FUNCTION &REST SEQUENCES
Apply FUNCTION
on each element of each sequence in SEQUENCES
and
accumulate the result in RESULT, using the Collector interface.
Returns the resulting sequence.
Whilst this function is permitted to modify RESULT , it is
not required and may return the result in a new sequence instead. Thus
do not rely on this function for its side effects.
|
MAP-TO
Generic Function: MAP-TO TYPE FUNCTION &REST SEQUENCES
Apply FUNCTION
on each element of each sequence in SEQUENCES
and
store the result in a new sequence of type TYPE
(created using
SEQUENCE-OF-TYPE).
Returns the sequence in which the results of applying the function are stored.
This function is equivalent in arguments, and almost
equivalent in behavior, to CL:MAP . The only difference is that if
TYPE is a subtype of vector, the vector returned is adjustable with
a fill-pointer. A NIL type argument is not interpreted as do not
accumulate the results, use FOREACH for that.
|
MAP-EXTEND
Generic Function: MAP-EXTEND-TO FUNCTION SEQUENCE &REST SEQUENCES
Apply FUNCTION
on each respective element of SEQUENCE
, and of each
sequence in SEQUENCES
, accumulating, using the EXTEND method of
the Collector Interface, the elements of the result, which is
expected to be a sequence, in a sequence of the same type as
SEQUENCE
.
The resulting sequence is returned.
MAP-EXTEND-TO
Generic Function: MAP-EXTEND-TO TYPE FUNCTION &REST SEQUENCES
Apply FUNCTION
on each respective element of each sequence in
SEQUENCES
, and accumulate, using the EXTEND method of the
Collector Interface, the elements of the result, which is expected
to be a sequence, in a sequence of type TYPE
, created using
SEQUENCE-OF-TYPE.
The resulting sequence is returned.
MAP-EXTEND-INTO
Generic Function: MAP-EXTEND-INTO RESULT FUNCTION &REST SEQUENCES
Apply FUNCTION
on each respective element of each sequence in
SEQUENCES
, and accumulate, using the EXTEND method of the
Collector Interface, the elements of the result, which is expected
to be a sequence, in the sequence RESULT
.
The resulting sequence is returned.
RESULT may be destructively modified, however that is not
guaranteed thus this function should only be used for its return
value, not its side effects.
|
FOREACH
Function: FOREACH &REST SEQUENCES
Apply FUNCTION
on each element of each sequence in SEQUENCES
.
Returns NIL
.
Implemented Methods
This interface’s system also defines the following methods of the Container interface, implemented using the Iterator and Collector interfaces.
ELT
Method: ELT (SEQUENCE T) (INDEX T)
Creates an iterator for SEQUENCE
, with start position INDEX
,
and returns the first element returned by the iterator.
(SETF ELT)
Method: (SETF ELT) (VALUE T) (SEQUENCE T) (INDEX T)
Creates an iterator for SEQUENCE
, with start position INDEX
, and
sets the value of the element at the starting position of the
iterator.
LENGTH
Method: LENGTH (CONTAINER T)
Returns the size of the container by creating an iterator and calling
the LENGTH
method specialized on the ITERATOR structure.
This is a linear O(n)
, in time, operation unless a more efficient
method, which is specialized on the containers’s iterator type, is
implemented.
EMPTYP
Method: EMPTYP (CONTAINER T)
Returns true if ENDP returns true for a newly created
iterator for CONTAINER
.
ADJUST-SIZE
Method: ADJUST-SIZE (CONTAINER T) (N T) &KEY ELEMENT
NADJUST-SIZE
Method: NADJUST-SIZE (CONTAINER T) (N T) &KEY ELEMENT
SUBSEQ
Method: SUBSEQ (SEQUENCE T) (START T) &OPTIONAL END
Lazy Sequences
System and package name: GENERIC-CL.LAZY-SEQ
Lazy sequences are sequences in which the elements are only computed when they are actually referenced, rather than being computed immediately.
Lazy sequences are implemented with the LAZY-SEQ
structure which is
similar to a CONS
cell, however the CDR
, the TAIL
slot of the
LAZY-SEQ
structure, stores a function which computes and returns the
remainder of the sequence, rather than storing the sequence directly.
LAZY-SEQ Structure
Structure: LAZY-SEQ
Lazy sequence cell analogous to a CONS
.
HEAD
-
The first element of the sequence. Can be accessed with the
LAZY-SEQ-HEAD
accessor function. TAIL
-
A function of zero arguments which returns a
LAZY-SEQ
containing the remaining elements in the sequence. If there are no more elements the function returnsNIL
. Can be accessed with theLAZY-SEQ-TAIL
accessor function.
-
EQUALP
function. -
COPY
function. Accepts the:DEEP
keyword parameter which indicates whether the elements should also be copied. -
COERCE
function. -
Mandatory Functions, of the Iterator interface.
-
MAKE-COLLECTOR
function of the Collector interface.The method specialized on LAZY-SEQ
's returns a collector for aLIST
since it does not make sense to be collecting items, which have already been evaluated, into aLAZY-SEQ
. -
SUBSEQ function which returns the subsequence as a
LAZY-SEQ
. -
Methods, specialized on
LAZY-SEQ
, are implemented for the following Sequence Operations and their destructive counterparts:-
REMOVE
-
REMOVE-IF
-
REMOVE-IF-NOT
-
SUBSTITUTE
-
SUBSTITUTE-IF
-
SUBSTITUTE-IF-NOT
-
REMOVE-DUPLICATES
These methods return a
LAZY-SEQ
with the sequence operation 'lazily' applied to the sequence.The destructive versions are identical to the non-destructive versions. -
MAKE-LAZY-SEQ
Function: MAKE-LAZY-SEQ HEAD TAIL
Create a LAZY-SEQ
with the HEAD
slot initialized to HEAD
and the
TAIL
slot initialized to TAIL
.
TAIL must be a function of zero arguments that returns
either a LAZY-SEQ containing the remaining elements in the sequence
or NIL indicating there are no more elements.
|
For efficiency the function in TAIL should only compute the
remainder of the sequence the first time it is called. Remaining calls
to the function should simply return the previously computed result.
|
The LAZY-SEQ macro automatically wraps the
form, which returns the remainder of the sequence, in a function.
|
LAZY-SEQ Macro
Macro: LAZY-SEQ HEAD &OPTIONAL TAIL
Create a LAZY-SEQ
instance with the HEAD
slot initialized to
HEAD
and the TAIL
slot initialized to a function which evaluates
the form TAIL
.
The function only evaluates TAIL the first time it is
call. Subsequent calls will simply return the previously computed
result.
|
COERCE Methods
The following COERCE
methods are provided which specialize on
LAZY-SEQ
's.
-
LAZY-SEQ (EQL 'LIST)
Returns a list containing all the elements in the
LAZY-SEQ
.If the LAZY-SEQ
is an infinite sequence, this function will never terminate.
CONCATENATE Methods
Method: CONCATENATE LAZY-SEQ &REST SEQUENCES
Method: NCONCATENATE LAZY-SEQ &REST SEQUENCES
Method: CONCATENATE-TO (EQL 'LAZY-SEQ) &REST SEQUENCES
Concatenates sequences to a lazy sequence.
The concatenation is done lazily, that is the elements of the
sequences, in SEQUENCES
, are only added to the lazy sequence when
elements past the end of the LAZY-SEQ
, passed in the first argument,
are referenced.
The CONCATENATE-TO
method returns a lazy sequence containing the
concatenation of SEQUENCES
. Like CONCATENATE
and NCONCATENATE
the concatenation is done lazily.
NCONCATENATE is identical to CONCATENATE , that is the
LAZY-SEQ is not destructively modified.
|
MAP Methods
Method: MAP FUNCTION LAZY-SEQ &REST SEQUENCES
Method: NMAP FUNCTION LAZY-SEQ &REST SEQUENCES
Method: MAP-INTO LAZY-SEQ FUNCTION &REST SEQUENCES
Method: MAP-TO (EQL 'LAZY-SEQ) FUNCTION &REST SEQUENCES
Applies a function on each element of the LAZY-SEQ
and of each
sequence in SEQUENCES
.
The result is a LAZY-SEQ
with the function applied lazily to each
element, that is it is only applied when that element is referenced.
The MAP-TO
method returns the result, of lazily applying the
function on each element of each sequence in SEQUENCES
, in a
LAZY-SEQ
.
NMAP and MAP-INTO do not destructively modify the LAZY-SEQ
but return a new sequence instead.
|
Utilities
RANGE
Function: RANGE START &OPTIONAL END STEP
Returns a LAZY-SEQ
containing all numbers in the range [START,
END)
.
If END
is NIL
, an infinite sequence, without an upper bound, is
returned.
STEP
, defaults to 1
, is the delta by which each number is incremented
to obtain the next successive number in the sequence.
Generic Hash-Tables
System and package name: GENERIC-CL.MAP
This interface provides a hash-table data structure with the generic function HASH as the hash function and the generic function GENERIC-CL:EQUALP as the key comparison function. This allows the hash-tables to utilize keys of user-defined types, whereas the keys of standard hash tables are limited to numbers, characters, lists and strings.
The generic hash-tables are implemented using
CL-CUSTOM-HASH-TABLE. If
the Common Lisp implementation supports creating hash-tables with
user-defined hash and comparison functions, standard hash-tables are
used. However if the implementation does not support user-defined hash
and comparison functions, a fallback solution is used, which is a
custom hash-table implementation on top of standard hash-tables. The
HASH-MAP structure wraps the custom hash-table which allows
methods methods to be specialized on a single type HASH-MAP
regardless of whether standard or custom hash-tables are used.
The functions in this interface are specialized on the HASH-MAP
type, thus this type, created with MAKE-HASH-MAP, should be used
rather than built-in hash-tables. If a hash-table is obtained from an
external source, use HASH-MAP or ENSURE-HASH-MAP to convert it
to a HASH-MAP
.
CL:HASH-TABLE |
HASH-MAP |
---|---|
GETHASH |
GET |
HASH-TABLE-COUNT |
LENGTH |
REMHASH |
ERASE |
CLRHASH |
CLEAR |
HASH-MAP
Structure: HASH-MAP
-
TABLE
Function: HASH-MAP TABLE
The HASH-MAP
structure wraps a standard HASH-TABLE
, or
CUSTOM-HASH-TABLE
, contained in the TABLE
slot, which can be
accessed accessed with HASH-MAP-TABLE
.
The HASH-MAP
function takes a single argument, a hash-table, and
creates a HASH-MAP
wrapping it.
Implemented Interfaces
The CLEARED, MAKE-SEQUENCE-OF-TYPE, LENGTH, EMPTYP, CLEAR, ELT, (SETF ELT) and ERASE methods of the Container interface are implemented.
The Iterator interface is implemented for HASH-MAP
's. Each element
returned by the iterator is a CONS
with the key in the CAR
and the
corresponding value in the CDR
. The order in which the entries are
iterated over is unspecified. Likewise it is unspecified which entries
will be iterated over if START
is non-zero and/or END
is non-NIL,
the only guarantee being that END - START
entries are iterated
over. The reverse iterator iterates over the entries in the same order
as the normal iterator due to the order of iteration being
unspecified.
The (SETF AT) method for the HASH-MAP
iterator sets the value
corresponding to the key of the current entry, being iterated over, to
the value passed as the argument to SETF
.
The collector interface is implemented for HASH-MAP
's. The
ACCUMULATE method expects a CONS
where the CAR
is the key of
the entry to create and the CDR
is the corresponding value.
An EQUALP method is implemented for HASH-MAP
's which returns
true if both maps contain the same number of entries and each key in
the first map is present in the second map, with the corresponding
value in the first map equal (by EQUALP
) to the corresponding value
in the second
map.
If the two maps have different test functions, the EQUALP
method is not necessarily symmetric i.e. (EQUALP A B) does not imply
(EQUALP B A) .
|
A LIKEP method is implemented for HASH-MAP
's, which is similar
to the EQUALP
method, however the values are compared using LIKEP
.
A COPY method is implemented for HASH-MAP
's which by default
creates a new map with the same entries as the original map. If :DEEP
T
is provided the values (but not the keys as they should be
immutable) are copied by (COPY VALUE :DEEP T)
.
MAKE-HASH-MAP
Function: MAKE-HASH-MAP &KEY TEST &ALLOW-OTHER-KEYS
Create a HASH-MAP
wrapping a hash table with test function TEST
,
which defaults to #'GENERIC-CL:EQUALP
.
TEST
may be one of the following:
GENERIC-CL:EQUALP
-
A hash table with hash function HASH and comparison function GENERIC-CL:EQUALP is created.
LIKEP
-
A hash table with hash function LIKE-HASH and comparison function LIKEP is created.
TEST
may also be a standard hash-table test specifier, in which case
a native hash table is created, wrapped in a HASH-MAP
.
The function accepts all additional arguments (including
implementation specific arguments) accepted by CL:MAKE-HASH-TABLE
.
ENSURE-HASH-MAP
Function: ENSURE-HASH-MAP THING
If MAP
is a HASH-MAP returns it, otherwise if MAP
is a
HASH-TABLE
or CUSTOM-HASH-TABLE
returns a HASH-MAP
which wraps
it.
Signals an error if MAP is not of the aforementioned types.
|
HASH-MAP-TEST
Function: HASH-MAP-TEST MAP
Returns the test function, as a symbol, of the underlying hash table.
On some implementations the return value is not
GENERIC-CL:EQUALP , even if the hash table has HASH and
GENERIC-CL:EQUALP as its hash and comparison functions.
|
HASH
Generic Function: HASH OBJECT
Hash function for hash tables with the GENERIC-CL:EQUALP
test
specifier.
Return a hash code for OBJECT
, which should be a non-negative
fixnum.
If two objects are equal (under GENERIC-CL:EQUALP) then
the hash codes, for the two objects, returned by HASH
, should also
be equal.
The default method calls CL:SXHASH
which satisfies the constraint
that (CL:EQUAL X Y)
implies (= (CL:SXHASH X) (CL:SXHASH
Y))
.
Currently no specialized method is provided for container/sequence objects such as lists. The default method does not violate the constraint for lists (but does violate the constraints for non-string vectors) as keys, provided they only contain numbers, characters, symbols, strings and other lists as elements. |
LIKE-HASH
Generic Function: LIKE-HASH OBJECT
Hash function for hash tables with the LIKEP
test
specifier.
Return a hash code for OBJECT
, which should be a non-negative
fixnum.
If two objects are equal (under LIKEP) then the hash codes, for
the two objects, returned by LIKE-HASH
, should also be equal.
Methods which satisfy these constraints are provided for strings,
characters, lists, vectors and multi-dimensional arrays. The default
method calls the HASH
function.
GET
Generic Function: GET KEY MAP &OPTIONAL DEFAULT
Return the value of the entry corresponding to the key KEY
in the
map MAP
.
If the MAP
does not contain any entry with that key, DEFAULT
is
returned. The second return value is true if an entry with key KEY
was found in the map, false otherwise.
Methods are provided for HASH-MAP
's, standard HASH-TABLE
's,
association lists (ALISTS
) and property lists (PLISTS
). For
ALISTS
the EQUALP key comparison function is used. For PLISTS
the EQ
key comparison function is used.
(SETF GET)
Generic Function: (SETF GET) VALUE KEY MAP &OPTIONAL DEFAULT
Set the value of the entry corresponding to the key KEY
in the map
MAP
.
DEFAULT is ignored.
|
Only a method for HASH-MAPS and HASH-TABLES is
provided.
|
ENSURE-GET
Macro: ENSURE-GET KEY MAP &OPTIONAL DEFAULT
Like GET
however if KEY
is not found in MAP
it is added, by
(SETF GET)
with the value DEFAULT
.
The first return value is the value corresponding to the key KEY
, or
DEFAULT
if KEY
is not found in MAP
. The second return value is
true if KEY
was found in MAP
, false otherwise.
ELT Methods
The following ELT
methods are provided:
-
(MAP HASH-MAP) (KEY T)
Returns
(GENERIC-CL:GET KEY MAP)
. -
(MAP HASH-TABLE) (KEY T)
Returns
(GETHASH KEY MAP)
(SETF ELT) Methods
The following (SETF ELT)
methods are provided:
-
(VALUE T) (MAP HASH-MAP) (KEY T)
Calls
(SETF (GENERIC-CL:GET KEY MAP) VALUE)
-
(VALUE T) (MAP HASH-TABLE) (KEY T)
Calls
(SETF (GETHASH KEY MAP) VALUE)
ERASE Method
Method: ERASE (MAP HASH-MAP) (KEY T)
Remove the entry with key KEY
from MAP
.
Returns true if the map contained an entry with key KEY
.
HASH-MAP-ALIST
Function: HASH-MAP-ALIST MAP
Return an association list (ALIST
) containing all the entries in the
map MAP
.
ALIST-HASH-MAP
Function: ALIST-HASH-MAP ALIST &REST ARGS
Return a HASH-MAP containing all entries in the association list
ALIST
.
ARGS
are the additional arguments passed to MAKE-HASH-MAP.
MAP-KEYS
Generic Function: MAP-KEYS MAP
Return a sequence containing all the keys in the map MAP
.
Specialized only on HASH-MAP 's and CL:HASH-TABLE 's.
|
MAP-VALUES
Generic Function: MAP-VALUES MAP
Return a sequence containing all the values in the map MAP
.
Specialized only on HASH-MAP 's and CL:HASH-TABLE 's.
|
COERCE Methods
The following COERCE
methods are provided for HASH-MAPS
:
-
HASH-MAP (EQL 'ALIST)
Returns an association list (
ALIST
) containing all the entries in the map. Equivalent to HASH-MAP-ALIST. -
HASH-MAP (EQL 'PLIST)
Returns a property list (
PLIST
) containing all the entries in the map.
MAKE-SEQUENCE-OF-TYPE Method
Method: MAKE-SEQUENCE-OF-TYPE (TYPE (EQL 'HASH-MAP)) (ARGS NULL)
Return a new empty HASH-MAP
with test function GENERIC-CL:EQUALP
.
Sets
System and package name GENERIC-CL.SET
.
The set interface provides generic functions for performing set operations and implementations of those operations for a hash-set data structure.
Generic function wrappers are provided over the following Common Lisp set operation functions:
-
SUBSETP
-
ADJOIN
-
INTERSECTION
-
NINTERSECTION
-
SET-DIFFERENCE
-
NSET-DIFFERENCE
-
SET-EXCLUSIVE-OR
-
NSET-EXCLUSIVE-OR
-
UNION
-
NUNION
For each function, methods specializing on LISTS
, which simply call
the corresponding function in the CL
package, and HASH-MAP's are
implemented. Each function accepts all keyword arguments accepted by
the corresponding CL
functions however they are ignored by the
HASH-MAP
methods.
HASH-MAP's may be used as sets, in which case the set elements are stored in the keys. The values of the map’s entries are ignored by the set operations, thus the map values of the sets returned, by the set operation functions, are unspecified. |
ADJOIN
Generic Function: ADJOIN ITEM SET &KEY &ALLOW-OTHER-KEYS
Return a new set containing the elements of SET
, and of the same
type, with ITEM
added to it.
This function is non-destructive. A new set is always returned even if
SET is a HASH-MAP / HASH-SET.
|
Accepts all keyword arguments accepted by CL:ADJOIN however
they are ignored by the HASH-MAP method.
|
NADJOIN
Generic Function: ADJOIN ITEM SET &KEY &ALLOW-OTHER-KEYS
Same as ADJOIN however is permitted to destructively modify SET
.
The set returned is EQ to SET in the case of SET
being a HASH-MAP however this is not a requirement in the general
case, and is not EQ if SET is a list. Thus this function should
not be relied upon for its side effects.
|
Implemented for both lists and HASH-MAP's. |
MEMBERP
Generic Function: MEMBERP ITEM SET &KEY &ALLOW-OTHER-KEYS
Return true if ITEM
is an element of the set SET
.
Implemented for both lists and HASH-MAP's. All keyword arguments
accepted by CL:MEMBER are accepted, however are ignored by the
HASH-MAP method.
|
HASH-SET
Structure: HASH-SET
A HASH-SET
is a HASH-MAP however it is used to indicate that
only the keys are important. This allows the EQUALP and COPY
methods, specialized on `HASH-SET’s to be implemented more
efficiently, than the methods specialized on HASH-MAP
's, as the
map values are not compared/copied.
The implementation of the Iterator interface for HASH-SETS
differs
from the implementation for HASH-MAPS
in that only the set elements,
i.e. the keys of the underlying hash table, are returned rather than
the key-value pairs.
The set operations are implemented both for HASH-MAP 's and
HASH-SET 's.
|
HASH-TABLE-SET
Function: HASH-TABLE-SET TABLE
Return a HASH-SET
structure wrapping the standard HASH-TABLE
or
CUSTOM-HASH-TABLE
.
MAKE-HASH-SET
Function: MAKE-HASH-SET &KEY &ALLOW-OTHER-KEYS
Return a new empty HASH-SET.
Accepts the same keyword arguments as MAKE-HASH-MAP. The default
TEST
function is GENERIC-CL:EQUALP.
COERCE Methods
The following COERCE
Methods are provided:
-
LIST (EQL 'HASH-SET)
Return a
HASH-SET
containing the elements in the list.
Math
System and package name GENERIC-CL.MATH
.
This interface provides generic function wrappers over a number of
math functions. Methods specialized on NUMBER
are provided, which
simply call the corresponding functions in the CL
package. The
purpose of this interface is to allow the mathematical functions to be
extended to vectors and matrices.
This interface is not exported by the GENERIC-CL
package, as it’s
not as frequently used as the previous interfaces. The
GENERIC-MATH-CL
package exports all symbols exports by the
GENERIC-CL
package and the shadowed math functions in
GENERIC-CL.MATH
.
Generic function wrappers are provided for the following functions:
-
SIN
-
COS
-
TAN
-
ASIN
-
ACOS
-
ATAN
-
SINH
-
COSH
-
TANH
-
ASINH
-
ACOSH
-
ATANH
-
EXP
-
EXPT
-
LOG
-
SQRT
-
ISQRT
-
REALPART
-
IMAGPART
-
CIS
-
CONJUGATE
-
PHASE
-
NUMERATOR
-
DENOMINATOR
-
RATIONAL
-
RATIONALIZE
System GENERIC-CL.UTIL
The system GENERIC-CL.UTIL
provides additional utilities implemented
on top of GENERIC-CL
. These utilities are contained in the package
GENERIC-CL.UTIL
.
Lazy Sequence Utilities
REPEAT
Function: REPEAT X &OPTIONAL N TYPE
Create a lazy sequence containing N
elements with the value X
.
If N
is NIL
or is not provided, an infinite sequence is returned.
If TYPE
is non-NIL
a sequence of type TYPE
is returned. The
sequence is created using the SEQUENCE-OF-TYPE function, and the
elements are accumulated into the sequence using the Collector
interface.
REPEATEDLY
Function: REPEATEDLY F &OPTIONAL N TYPE
Create a lazy sequence containing N
elements, with each element
being the result of an application of the function F
with no
arguments.
If N
is NIL
or not provided, an infinite sequence is returned.
If TYPE
is non-NIL
a sequence of type TYPE
is returned. The
sequence is created using the SEQUENCE-OF-TYPE function, and the
elements are accumulated into the sequence using the Collector
interface.
ITERATE
Function: ITERATE F X &KEY INITIAL
Return an infinite lazy sequence where each element is the result of
applying the function F
on the previous element.
IF the keyword argument INITIAL
is true, the first element of the
sequence is X
, otherwise the first element is the result of applying
F
on X
.
FITERATE
Function: FITERATE F X &KEY INIITIAL
Deprecated alias for ITERATE
CYCLE
Function: CYCLE SEQUENCE
Return a lazy sequence containing an infinite repetition of the
elements in SEQUENCE
.
The resulting sequence contains the elements of SEQUENCE
in order,
with the last element of SEQUENCE
followed by the first, and
remaining, elements.
Optimization
There is an overhead associated with generic functions. Code making
use of the generic function interface will be slower than code which
calls the CL
functions directly, due to the cost of dynamic method
dispatch. For most cases this will not result in a noticeable decrease
in performance, however for those cases where it does there is an
optimization.
This library is built on top of STATIC-DISPATCH, which is a library that allows generic-function dispatch to be performed statically, at compile-time, rather than dynamically, at runtime. The library allows a call to a generic function to be replaced with the body of the appropriate method, or a call to an ordinary function implementing the method, which is selected based on the type declarations of its arguments.
For a generic function call to be inlined an OPTIMIZE
declaration
with a SPEED
level of 3
and with SAFETY
and DEBUG
levels less
than 3
has to be in place, in the environment of the
call. Additionally, it must also be possible to determine the types of
the arguments at compile-time. This means in general that the types of
variables and the return types of functions have to be declared. See
STATIC-DISPATCH and
CL-FORM-TYPES for
information on how the types of the arguments are determined and how
to make the type information available.
(let ((x 1))
(declare (optimize (speed 3) (safety 2))
(type number x))
(equalp x (the number (+ 3 4))))
This will result in the call to the EQUALP
function being replaced
with the body of the NUMBER NUMBER
method.
The n-argument equality, comparison and arithmetic functions also have
associated compiler-macros which replace the calls to the n-argument
functions with multiple inline calls to the binary functions, e.g. (=
1 2 3)
is replaced with (and (equalp 1 2) (equalp 1 3))
.
Thus the following should also result in the EQUALP
function calls
being statically dispatched:
(let ((x 1))
(declare (optimize (speed 3) (safety 2))
(type number x))
(= x (the number (+ 3 4))))
STATIC-DISPATCH requires the ability to extract TYPE and
INLINE declarations from implementation specific environment
objects. This is provided by the
CL-ENVIRONMENTS
library, which works in the general case however some
workarounds
are necessary in order for it to work on all implementations in all
cases.
|