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.