This package defines an abstract set class API.
The minimum implementation should define methods for: INCLUDE,
EXCLUDE, CONTAINS, CARDINAL, SELECT, MINIMUM, MAXIMUM, MAP-ELEMENTS
and MAKE-COLLECTOR.
But an efficient implementation will have to implement specializations
for the other generic functions too.
Methods of MAKE-COLLECTOR specify which RESULT-TYPE sets are
available. Methods are defined for NIL, LIST and VECTOR, to make
null collector (ignoring the collected elements), a list collector or
a vector collector.
License:
AGPL3
Copyright Pascal J. Bourguignon 2013 - 2013
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU Affero General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU Affero General Public License for more details.
You should have received a copy of the GNU Affero General Public License
along with this program.
If not, see <http://www.gnu.org/licenses/>
|
(always predicate set) |
generic-function |
RETURN: Whether the PREDICATE is true for all the elements of
the SET.
|
(assign destination-set source-set) |
generic-function |
POST: (and (set-equal DESTINATION-SET SOURCE-SET)
(set-equal (old SOURCE-SET) SOURCE-SET))
RETURN: DESTINATION-SET
|
(assign-empty destination-set) |
generic-function |
POST: (emptyp DESTINATION-SET)) RETURN: DESTINATION-SET
|
(assign-singleton destination-set element) |
generic-function |
POST: (and (= 1 (cardinal DESTINATION-SET)) (contains DESTINATION-SET ELEMENT)) RETURN: DESTINATION-SET
|
(cardinal set) |
generic-function |
RETURN: The number of elements in the SET. NOTE: We only consider finite sets.
|
(collecting-result (collect-operator-name result-type) &body body) |
macro |
DO: Evaluate BODY in an environment where a function named by
COLLECT-OPERATOR-NAME is defined to take one argument and to
add it to a set of type RESULT-TYPE.
RETURN: The collected set of elements.
|
(contains set element) |
generic-function |
RETURN: Whether the SET contains the ELEMENT.
|
(copy set &key &allow-other-keys) |
generic-function |
RETURN: A new set of same class as SET, containing the same
elements as SET.
|
(difference result-type set1 set2) |
generic-function |
RETURN: A new set of type RESULT-TYPE containing the
difference between set1 and set2.
|
(elements set) |
generic-function |
The elements in the set.
|
(emptyp set) |
generic-function |
RETURN: (zerop (cardinal set)) NOTE: Implementations of EMPTYP may be more efficient than CARDINAL.
|
(exclude destination-set element) |
generic-function |
POST: (not (contains DESTINATION-SET ELEMENT)) RETURN: DESTINATION-SET
|
(include destination-set element) |
generic-function |
POST: (contains DESTINATION-SET ELEMENT) RETURN: DESTINATION-SET
|
(intension result-type predicate set) |
generic-function |
RETURN: A new set containing only the elements of SET that
have PREDICATE true.
|
(intersect destination-set source-set) |
generic-function |
POST: (and (set-equal DESTINATION-SET (intersection (old DESTINATION-SET) SOURCE-SET))
(set-equal (old SOURCE-SET) SOURCE-SET))
RETURN: DESTINATION-SET
|
(intersection result-type set1 set2) |
generic-function |
RETURN: A new set of type RESULT-TYPE containing the
intersection of the two sets.
|
(is-strict-subset subset set) |
generic-function |
RETURN: Whether SUBSET is a strict subset of SET.
|
(is-subset subset set) |
generic-function |
RETURN: Whether SUBSET is a subset of SET.
LIST-SET
|
(make-collector result-type) |
generic-function |
RETURN: A collector for the RESULT-TYPE.
A collector is a function that takes optionnaly two arguments,
a set and an element.
When called with no argument, it should return a fresh empty
set object.
When called with a set and an element argument, it should
include the element into the set, and return the (possibly
new) set.
|
(map-elements result-type mapper set) |
generic-function |
DO: Calls MAPPER on each element of the SET in turn (no
specified order), collecting the results in a set of
type RESULT-TYPE.
RESULT-TYPE: A symbol denoting a set class, or LIST or VECTOR.
MAPPER: A function taking an element of SET as argument, and
returning an element for the set of type RESULT-TYPE.
SET: A set.
RETURN: A set of type RESULT-TYPE containing the elements
returned by MAPPER.
|
(maximum set) |
generic-function |
PRE: (not (emptyp SET)) RETURN: the biggest element of the SET.
|
(merge destination-set source-set) |
generic-function |
POST: (and (is-subset SOURCE-SET DESTINATION-SET)
(set-equal (old SOURCE-SET) SOURCE-SET))
RETURN: DESTINATION-SET
|
(minimum set) |
generic-function |
PRE: (not (emptyp SET)) RETURN: the smallest element of the SET.
|
(set-equal set1 set2) |
generic-function |
RETURN: Whether the two sets contains the same elements.
|
(subtract destination-set source-set) |
generic-function |
POST: (and (set-equal DESTINATION-SET (difference (old DESTINATION-SET) SOURCE-SET))
(set-equal (old SOURCE-SET) SOURCE-SET))
RETURN: DESTINATION-SET
|
(symetric-difference result-type set1 set2) |
generic-function |
RETURN: A new set of type RESULT-TYPE containing the
symetric difference between the two sets.
|
(thereis predicate set) |
generic-function |
RETURN: Whether there is an element in the SET for which the
PREDICATE is true.
|
(thereis1 predicate set) |
generic-function |
RETURN: Whether there is exactly one element in the SET for
which the PREDICATE is true.
|
(union result-type set1 set2) |
generic-function |
RETURN: A new set of type RESULT-TYPE containing the union of
the two sets.