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

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

ASSIGN

ASSIGN-ELEMENT

ASSIGN-EMPTY

bset

structure

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

BSET-TO-LIST

CARDINAL

COMPLEMENT

(copy-bset original)

function

RETURN: A new copy of the ORIGINAL bset.

DIFFERENCE

EMPTYP

EXCLUDE

EXISTS

EXISTS-1

EXTRACT

FOR-ALL

FOR-ALL-DO

INCLUDE

INTERSECTION

IS-ELEMENT

IS-EMPTY

IS-EQUAL

IS-NOT-EQUAL

IS-STRICT-SUBSET

IS-SUBSET

(list-to-bset list)

function

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

(make-bset max-size)

function

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

MINIMUM

(read-bset stream bset)

function

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

(resize-bset bset max-size)

function

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

SIZE

STRICT-SUBSETP

SUBSETP

SYM-DIFF

UNION

(write-bset stream bset)

function

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