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/>
(assign set1 set2)
function
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)
function
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)
function
POST:    (is-empty bset)
RETURN:  BSET.
bset
structure
A set of small integers, implemented as a vector of words.
(bset-to-list bset)
function
RETURN:  A list of all elements of BSET, sorted in increasing order.
(cardinal bset)
function
RETURN:  The number of elements in BSET.
(complement bset)
function
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)
function
RETURN: A new copy of the ORIGINAL bset.
(difference set1 set2)
function
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)
function
PRE:    (<= 0 element (size bset))
POST:   (not (is-element element bset))
RETURN: BSET
(exists bset proc)
function
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)
function
DO:       Call function PROC on all elements in the BSET.
RETURN:   Whether PROC returned non nil for exactly one element.
(extract bset)
function
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)
function
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)
function
DO:      Call PROC on all elements in BSET.
RETURN:  BSET.
(include bset element)
function
PRE:    (<= 0 element (size bset))
POST:   (is-element element bset)
RETURN: BSET
(intersection set1 set2)
function
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)
function
RETURN:  Whether element is in BSET.
(is-empty bset)
function
RETURN: (= 0 (cardinal bset))
(is-equal set1 set2)
function
RETURN:  Whether SET1 and SET2 contain the same elements.
  
(is-strict-subset set1 set2)
function
RETURN:  Whether SET1 is a strict subset of SET2.
(is-subset set1 set2)
function
RETURN:  Whether  SET1 is a subset of SET2.
(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 bset)
function
PRE:     (not (is-empty bset))
RETURN:  The greatest element of BSET.
(minimum bset)
function
PRE:     (not (is-empty bset))
RETURN:  The smallest element of BSET.
(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 bset)
function
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)
function
RETURN:  The maximum element BSET can hold.
(sym-diff set1 set2)
function
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)
function
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)
function
DO:     Writes to the stream the elements in BSET.
RETURN: BSET.