You are looking at historical revision 20655 of this page. It may differ significantly from its current revision.

## Compact integer sets

The `cis` library implements compact integer sets, represented as a list of integer intervals. The usual set operations are provided. The advantage compared to ordered lists is that when many elements are contiguous, the actual size of the data structure may be much smaller than the cardinality of the set being represented. Most set operations are linear w.r.t. the size, not the cardinality of the set.

## Usage

(require-extension cis)

## Documentation

### Constants

empty :: CIS

The empty integer set.

### Procedures

*[procedure]*

`cis? :: OBJECT -> BOOL`

Returns `#t` if the given object is a compact integer set, `#f` otherwise.

*[procedure]*

`empty? :: CIS -> BOOL`

Returns `#t` if the given integer set is empty, `#f` otherwise.

*[procedure]*

`subset? :: CIS * CIS -> BOOL`

Returns `#t` if the first given integer set is a subset of the second given integer set, `#f` otherwise.

*[procedure]*

`cardinal :: CIS -> INTEGER`

Returns the cardinality of the given set.

*[procedure]*

`in? :: INTEGER * CIS -> BOOL`

Returns `#t` if the the given integer is contained in the given set, `#f` otherwise.

*[procedure]*

`singleton :: INTEGER -> CIS`

Returns an integer set consisting of the given element.

*[procedure]*

`interval :: INTEGER * INTEGER -> CIS`

Returns an integer set consisting of the given interval of elements.

*[procedure]*

`add :: INTEGER * CIS -> CIS`

Adds the given element to the given set and returns the new set.

*[procedure]*

`remove :: INTEGER * CIS -> CIS`

Removes the given element from the given set and returns the new set.

*[procedure]*

`shift :: INTEGER * CIS -> CIS`

Adds the given integer to all elements in the set and returns the new set.

*[procedure]*

`union :: CIS * CIS -> CIS`

Returns the union of the two sets.

*[procedure]*

`intersection :: CIS * CIS -> CIS`

Returns the intersection fo the two sets.

*[procedure]*

`difference :: CIS * CIS -> CIS`

Subtracts the elements of the second given set from the elements of the first given set, and returns the resulting set.

*[procedure]*

`get-min :: CIS -> INTEGER`

Returns the minumum element of the set.

*[procedure]*

`get-max :: CIS -> INTEGER`

Returns the maximum element of the set.

*[procedure]*

`foreach :: PROCEDURE * CIS -> VOID`

Applies the given procedure to every element of the set.

*[procedure]*

`fold-left :: PROCEDURE * INIT * CIS -> VALUE`

Left fold on the elements of the set.

*[procedure]*

`fold-right :: PROCEDURE * INIT * CIS -> VALUE`

Right fold on the elements of the set.

*[procedure]*

`elements :: CIS -> LIST`

Returns a list containing all elements of the given set.

## Examples

(define a (add 4 (add 1 (add 5 empty)))) (define b (add 3 (add 2 (add 8 empty)))) (elements a) ==> (5 4 1) (elements b) ==> (8 3 2) (elements (union a b)) ==> (8 5 4 3 2 1)

## About this egg

### Author

`cis` is based on the Ocaml `Cis` library by SÃ©bastien FerrÃ©. The Chicken Scheme variant of `cis` is implemented by Ivan Raikov.

### Version history

- 1.0
- Initial release

### License

Copyright 2010 Ivan Raikov and the Okinawa Institute of Science and Technology This program is free software: you can redistribute it and/or modify it under the terms of the GNU 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 General Public License for more details. A full copy of the GPL license can be found at <http://www.gnu.org/licenses/>.