Common Lisp Package: COM.INFORMATIMAGO.COMMON-LISP.CESARUM.BSET

This package implements sets of (integer 0 *) as arrays of bitsets. (Inspired by Modula-2 cocktail-9309/reuse/src/Set.md) License: AGPL3 Copyright Pascal J. Bourguignon 2004 - 2012 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/>

README:

FUNCTION

Public

ASSIGN (SET1 SET2)

DO: Accumulate in set1 the elements of set2 that are less than (size set1). POST: (is-equal set1 (intersection (complement (make-bset (size set1)))set2)) RETURN: SET1

ASSIGN-ELEMENT (BSET ELEMENT)

DO: Empties BSET and include element. PRE: (<= 0 element (size bset)) POST: (and (exists bset (lambda (x) (= x element))) (for-all bset (lambda (x) (= x element)))) RETURN: BSET

ASSIGN-EMPTY (BSET)

POST: (is-empty bset) RETURN: BSET.

BSET-TO-LIST (BSET)

RETURN: A list of all elements of BSET, sorted in increasing order.

CARDINAL (BSET)

RETURN: The number of elements in BSET.

COMPLEMENT (BSET)

DO: set1 := (complement (make-bset (size set1))) - set1 Accumulate in set1 the complement of set1 (elements in not set1) modulo the allocated size of set1. RETURN: SET1

COPY-BSET (ORIGINAL)

RETURN: A new copy of the ORIGINAL bset.

DIFFERENCE (SET1 SET2)

DO: set1 := set1 - ( set2 inter (complement (make-bset (size set1))) ) Accumulate in set1 the difference of set1 and set2 (elements in set1 not in set2) modulo the allocated size of set1. RETURN: SET1

EXCLUDE (BSET ELEMENT)

PRE: (<= 0 element (size bset)) POST: (not (is-element element bset)) RETURN: BSET

EXISTS (BSET PROC)

DO: Call function PROC for each element in the BSET until PROC returns non nil. RETURN: Whether PROC returned non nil.

EXISTS-1 (BSET PROC)

DO: Call function PROC on all elements in the BSET. RETURN: Whether PROC returned non nil for exactly one element.

EXTRACT (BSET)

PRE: (not (is-empty bset)) POST: (not (is-element (extract bset) bset)) DO: Select an element from the BSET and removes it from the BSET. RETURN: An element that was in BSET.

FOR-ALL (BSET PROC)

DO: Call function PROC for each element in the BSET until PROC returns NIL. RETURN: Whether no call to PROC returned NIL.

FOR-ALL-DO (BSET PROC)

DO: Call PROC on all elements in BSET. RETURN: BSET.

INCLUDE (BSET ELEMENT)

PRE: (<= 0 element (size bset)) POST: (is-element element bset) RETURN: BSET

INTERSECTION (SET1 SET2)

DO: set1 := set1 inter set2 inter Accumulate in set1 the intersection of set1 and set2 (elements in set1 and in set2). RETURN: SET1

IS-ELEMENT (ELEMENT BSET)

RETURN: Whether element is in BSET.

IS-EMPTY (BSET)

RETURN: (= 0 (cardinal bset))

IS-EQUAL (SET1 SET2)

RETURN: Whether SET1 and SET2 contain the same elements.

IS-STRICT-SUBSET (SET1 SET2)

RETURN: Whether SET1 is a strict subset of SET2.

IS-SUBSET (SET1 SET2)

RETURN: Whether SET1 is a subset of SET2.

LIST-TO-BSET (LIST)

PRE: LIST is a list of positive integer. RETURN: A new bset containing all the elements in the list.

MAKE-BSET (MAX-SIZE)

PRE: (<= 0 max-size) POST: (<= max-size (size (make-bset max-size))) RETURN: A new bset allocated to hold at least elements from 0 to max-size.

MAXIMUM (BSET)

PRE: (not (is-empty bset)) RETURN: The greatest element of BSET.

MINIMUM (BSET)

PRE: (not (is-empty bset)) RETURN: The smallest element of BSET.

READ-BSET (STREAM BSET)

DO: Accumulate in BSET the elements read from the stream. RETURN: BSET.

RESIZE-BSET (BSET MAX-SIZE)

PRE: (<= 0 max-size) POST: (<= max-size (size (resize-bset bset max-size))) (if (< max-size (size old-bset)) (is-equal bset (intersection old-bset (complement (make-bset max-size)))) (is-equal bset old-bset)) DO: Reallocate bset to have it able to hold at least elements from 0 to max-size. RETURN: bset

SELECT (BSET)

PRE: (not (is-empty bset)) RETURN: An element of BSET. WARNING: May return always the same element if it's not removed from the BSET.

SIZE (BSET)

RETURN: The maximum element BSET can hold.

SYM-DIFF (SET1 SET2)

DO: set1 := set1 delta ( set2 inter (complement (make-bset (size set1))) ) Accumulate in set1 the symetrical difference of set1 and set2 (elements in set1 not in set2 or in set2 not in bset 1) modulo the allocated size of set1. RETURN: SET1

UNION (SET1 SET2)

DO: set1 := set1 U ( set2 inter (complement (make-bset (size set1))) ) Accumulate in set1 the union of set1 and set2 modulo the allocated size of set1. RETURN: SET1

WRITE-BSET (STREAM BSET)

DO: Writes to the stream the elements in BSET. RETURN: BSET.

Private

BITSET-TO-ELEM (INDEX)

RETURN: The maximum element + 1 that can be stored in the bitset at INDEX. NOTE: 0 --> 32 1 --> 64 2 --> 96

BSET-BITSETS (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

BSET-CARDINAL (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

BSET-FIRST-ELEMENT (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

BSET-LAST-ELEMENT (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

ELEM-TO-BITSET (ELEMENT)

RETURN: The index of the bitset where element is stored. NOTE: 0 --> 0 31 --> 0 32 --> 1 63 --> 1 64 --> 2

IS-NOT-EQUAL (SET1 SET2)

RETURN: (not (is-equal set1 set2))

LAST-BITSET (BITSETS)

RETURN: The index of the last bitset in the BITSETS array.

VECTOR-INIT (VECTOR CONSTRUCTOR)

DO: Sets all the slots in vector to the successive results of the function CONSTRUCTOR called with integers from 0 up to the dimension of the VECTOR. RETURN: VECTOR

Undocumented

%MAKE-BSET (&KEY ((BITSETS DUM5) (MAKE-ARRAY (LIST 0) ELEMENT-TYPE 'BITSET INITIAL-ELEMENT 0 ADJUSTABLE T)) ((CARDINAL DUM6) NIL) ((FIRST-ELEMENT DUM7) 0) ((LAST-ELEMENT DUM8) 0))

SETFBSET-BITSETS (NEW-VALUE INSTANCE)

SETFBSET-CARDINAL (NEW-VALUE INSTANCE)

SETFBSET-FIRST-ELEMENT (NEW-VALUE INSTANCE)

SETFBSET-LAST-ELEMENT (NEW-VALUE INSTANCE)

BSET-P (OBJECT)

ELEM-TO-BIT (ELEMENT)

MACRO

Private

FOR ((VAR FIRST LAST . REST) &BODY BODY)

For loop. DO: Repeat BODY with VAR bound to successive integer values from FIRST to LAST inclusive. If the optional STEP argument is abstent, then it is taken as 1 or -1 depending on the order of FIRST and LAST. VAR is incremented by STEP and it stops when VAR goes above or below LAST depending on the sign of STEP.

Undocumented

BSREF (BSA I)

CLASS

Public

BSET

A set of small integers, implemented as a vector of words.

CONSTANT

Private

Undocumented

+BIT-PER-BITSET+