TOC »
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
(import cis)
Documentation
Constants
empty :: CIS
The empty integer set.
Procedures
- cis?procedure
Returns #t if the given object is a compact integer set, #f otherwise.
- empty?procedure
Returns #t if the given integer set is empty, #f otherwise.
- subset?procedure
Returns #t if the first given integer set is a subset of the second given integer set, #f otherwise.
- cardinalprocedure
Returns the cardinality of the given set.
- in?procedure
Returns #t if the the given integer is contained in the given set, #f otherwise.
- singletonprocedure
Returns an integer set consisting of the given element.
- intervalprocedure
Returns an integer set consisting of the given interval of elements.
- addprocedure
Adds the given element to the given set and returns the new set.
- removeprocedure
Removes the given element from the given set and returns the new set.
- shiftprocedure
Adds the given integer to all elements in the set and returns the new set.
- unionprocedure
Returns the union of the two sets.
- intersectionprocedure
Returns the intersection fo the two sets.
- differenceprocedure
Subtracts the elements of the second given set from the elements of the first given set, and returns the resulting set.
- get-minprocedure
Returns the minumum element of the set.
- get-maxprocedure
Returns the maximum element of the set.
- foreachprocedure
Applies the given procedure to every element of the set.
- fold-leftprocedure
Left fold on the elements of the set.
- fold-rightprocedure
Right fold on the elements of the set.
- elementsprocedure
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.
Repository
This egg is hosted on the CHICKEN Subversion repository:
https://anonymous@code.call-cc.org/svn/chicken-eggs/release/5/cis
If you want to check out the source code repository of this egg and you are not familiar with Subversion, see this page.
Version history
- 1.4
- Bug fixes in difference [thanks to Andre Sa]
- 1.3
- Ported to CHICKEN 5
- 1.2
- Bug fix in union
- 1.1
- Updated test script to return proper exit code
- 1.0
- Initial release
License
Copyright 2010-2019 Ivan Raikov 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/>.