Outdated egg!

This is an egg for CHICKEN 4, the unsupported old release. You're almost certainly looking for the CHICKEN 5 version of this egg, if it exists.

If it does not exist, there may be equivalent functionality provided by another egg; have a look at the egg index. Otherwise, please consider porting this egg to the current version of CHICKEN.

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.

  1. Outdated egg!
  2. Compact integer sets
  3. Usage
  4. Documentation
    1. Constants
    2. Procedures
  5. Examples
  6. About this egg
    1. Author
    2. Version history
    3. License

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.2
Bug fix in union
1.1
Updated test script to return proper exit code
1.0
Initial release

License

 
Copyright 2010-2012 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/>.