## iset

### Description

Integer sets.

### Author

### Repository

This egg is hosted on the CHICKEN Subversion repository:

https://anonymous@code.call-cc.org/svn/chicken-eggs/release/5/iset

If you want to check out the source code repository of this egg and you are not familiar with Subversion, see this page.

### Requirements

None

### Documentation

#### Bit-vectors

Bit-vectors provide an abstract interface to bitwise operations typically done with integers. They may in fact be implemented as integers on implementations with bignums, or they may be implemented by other means such as vectors which may be more efficient. These vectors are meant to be used as flags and sets, not integer values, and thus are operations are ones-complement (there are no negative bit-vectors).

##### Creating bit-vectors

*[procedure]*

`(make-bit-vector size)`

A 'zero' bit-vector, with a hint that we wish to use `SIZE` bits.

*[procedure]*

`(make-bit-vector size #t)`

Same as above but initialize the all bit elements to `#t` (= the integer 2^SIZE-1)

*[procedure]*

`(integer->bit-vector n)`

Create a bit-vector with bits initialized to the corresponds bits in fixnum N

*[procedure]*

`(bit-vector-copy bv)`

Make a copy of the bit-vector BV

##### Bit-vector predicates

*[procedure]*

`(bit-vector? obj)`

`#t` iff OBJ is a valid bit-vector, which is not necessarily a disjoint type

*[procedure]*

`(bit-vector-empty? bv)`

`#t` iff BV has no bits set (the bit-vector equivalent of the ZERO? procedure)

*[procedure]*

`(bit-vector-full? bv to)`

`#t` iff BV has all bits lower than TO set (the low end is 2^i-1)

The individual bits in the vector are accessed and set as boolean values:

##### Accessing bit-vector elements

*[procedure]*

`(bit-vector-ref bv i)`

`#t` if the I-th bit in BV is set, else `#f`

*[procedure]*

`(bit-vector-set bv i x)`

Return a new copy of BV with the I-th bit set to boolean x (off iff X is `#f`)

*[procedure]*

`(bit-vector-set! bv i x)`

In-place update version of the above, is allowed but not required to mutate BV

##### Bitwise operations on bit-vectors

The following procedures are direct analogues of the corresponding SRFI-33 bitwise operations:

*[procedure]*

`(bit-vector-length bv)`

`integer-length`: the index of the largest bit set in BV

*[procedure]*

`(bit-vector-count bv)`

`bit-count`: the number of set bits in BV

*[procedure]*

`(bit-vector-shift bv n)`

`arithmetic-shift`

*[procedure]*

`(bit-vector-and bv ...)`

`bitwise-and`

*[procedure]*

`(bit-vector-ior bv ...)`

`bitwise-ior`

*[procedure]*

`(bit-vector-xor bv ...)`

`bitwise-xor`

*[procedure]*

`(bit-vector-eqv bv ...)`

`bitwise-eqv`

*[procedure]*

`(bit-vector-nand bv ...)`

`bitwise-nand`

*[procedure]*

`(bit-vector-nor bv ...)`

`bitwise-nor`

The following in-place update equivalents are also available, which are allowed, but not required, to mutate their first argument only:

*[procedure]*

`(bit-vector-shift! bv n)`

*[procedure]*

`(bit-vector-and! bv ...)`

*[procedure]*

`(bit-vector-ior! bv ...)`

*[procedure]*

`(bit-vector-xor! bv ...)`

*[procedure]*

`(bit-vector-eqv! bv ...)`

*[procedure]*

`(bit-vector-nand! bv ...)`

*[procedure]*

`(bit-vector-nor! bv ...)`

#### Integer sets

An integer set is a set of exact integers optimized for minimal space usage and fast membership lookup. General set operations are provided based on the character set operations found in SRFI-14.

##### Creating isets

*[procedure]*

`(make-iset)`

An empty integer set.

*[procedure]*

`(make-iset n)`

A set of the single integer N.

*[procedure]*

`(make-iset n m)`

A set of the range of all integers from N-M inclusive.

##### SRFI-14 analogues

The following procedures are provided as direct analogs of the SRFI-14 procedures, accepting and returning isets and integers in place of char-sets and characters:

*[procedure]*

`(iset-copy is)`

A new copy of IS

*[procedure]*

`(iset n ...)`

An iset containing the elements N...

*[procedure]*

`(list->iset ls [base-is])`

An iset containing all the integers in list LS, union BASE-IS if provided

*[procedure]*

`(list->iset! ls base-is)`

Same as above, allowed but not required to modify base-is

*[procedure]*

`(iset-size is)`

Return the # of elements in IS

*[procedure]*

`(iset-contains? is n)`

Test N for membership in IS

*[procedure]*

`(iset->list is)`

Returns a list of all integers in IS

*[procedure]*

`(iset-any pred is)`

Apply PRED to every element of IS, returning the first value returned by PRED that is not `#f`, if any (order unspecified)

*[procedure]*

`(iset-every pred is)`

Returns `#t` if every element of IS satisfies the predicate PRED (order unspecified)

*[procedure]*

`(iset? obj)`

`#t` iff obj is an integer set.

*[procedure]*

`(iset= is ...)`

`#t` iff all arguments are equivalent integer sets.

*[procedure]*

`(iset<= is ...)`

`#t` iff the arguments are monotonically increasing sets.

*[procedure]*

`(iset>= is ...)`

`#t` iff the arguments are monotonically decreasing sets.

*[procedure]*

`(iset-fold kons knil is)`

`char-set-fold`

*[procedure]*

`(iset-unfold f p g [base-is])`

`char-set-unfold`

*[procedure]*

`(iset-unfold! f p g base-is)`

`char-set-unfold!`

*[procedure]*

`(iset-for-each proc is)`

`char-set-for-each`

*[procedure]*

`(iset-map proc is)`

`char-set-map`

*[procedure]*

`(iset-filter pred is [bas-is])`

`char-set-filter`

*[procedure]*

`(iset-filter! pred is base-is)`

`char-set-filter!`

*[procedure]*

`(iset-cursor iset)`

*[procedure]*

`(iset-ref iset cursor)`

*[procedure]*

`(iset-cursor-next iset cursor)`

*[procedure]*

`(end-of-iset? iset)`

Cursor-based traversal of isets.

*[procedure]*

`(iset-adjoin is n ...)`

`char-set-adjoin`

*[procedure]*

`(iset-delete is n ...)`

`char-set-delete`

*[procedure]*

`(iset-adjoin! is n ...)`

`char-set-adjoin!`

*[procedure]*

`(iset-delete! is n ...)`

`char-set-delete!`

*[procedure]*

`(iset-union is1 ...)`

`char-set-union`

*[procedure]*

`(iset-intersection is1 ...)`

`char-set-intersection`

*[procedure]*

`(iset-difference is1 is2 ...)`

`char-set-difference`

*[procedure]*

`(iset-xor is1 ...)`

`char-set-xor`

*[procedure]*

`(iset-diff+intersection is1 is2 ...)`

`char-set-diff+intersection`

*[procedure]*

`(iset-union! is1 ...)`

`char-set-union!`

*[procedure]*

`(iset-intersection! is1 ...)`

`char-set-intersection!`

*[procedure]*

`(iset-difference! is1 is2 ...)`

`char-set-difference!`

*[procedure]*

`(iset-xor! is1 ...)`

`char-set-xor!`

*[procedure]*

`(iset-diff+intersection! is1 is2 ...)`

`char-set-diff+intersection!`

### Changelog

- 2.2 Fixes for the test suite
- 1.7 Fix bug that caused some
`iset-union`operations to fail in case of overlapping sets. Fix another bug that caused a negative bit-vector-shift of a multi-byte bitvector to clobber the least significant byte with zero. - 1.6 Converted to tags/trunk/branches structure in svn
- 1.5 Port to hygienic chicken, fix overflow bug in bit-vector-full? [Peter Bex]
- 1.4 Workaround in
`bit-vector-copy`for zero-length vectors. - 1.3 Fixed
`bit-vector-copy`export but no define [by Kon Lovett] - 1.2 Added
`iset-optimize`and`iset-balance`, fixed some bugs - 1.1 Added cursors
- 1.0 Initial release

### License

Copyright (c) 2004-2018, Alex Shinn All rights reserved. Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. 2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. 3. The name of the author may not be used to endorse or promote products derived from this software without specific prior written permission. THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.