## iset

Integer sets.

Alex Shinn

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
make-bit-vector sizeprocedure

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

make-bit-vector size #tprocedure

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

integer->bit-vector nprocedure

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

bit-vector-copy bvprocedure

Make a copy of the bit-vector BV

##### Bit-vector predicates
bit-vector? objprocedure

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

bit-vector-empty? bvprocedure

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

bit-vector-full? bv toprocedure

#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
bit-vector-ref bv iprocedure

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

bit-vector-set bv i xprocedure

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

bit-vector-set! bv i xprocedure

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:

bit-vector-length bvprocedure

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

bit-vector-count bvprocedure

bit-count: the number of set bits in BV

bit-vector-shift bv nprocedure

arithmetic-shift

bit-vector-and bv ...procedure

bitwise-and

bit-vector-ior bv ...procedure

bitwise-ior

bit-vector-xor bv ...procedure

bitwise-xor

bit-vector-eqv bv ...procedure

bitwise-eqv

bit-vector-nand bv ...procedure

bitwise-nand

bit-vector-nor bv ...procedure

bitwise-nor

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

bit-vector-shift! bv nprocedure
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 ...procedure

#### 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
make-isetprocedure

An empty integer set.

make-iset nprocedure

A set of the single integer N.

make-iset n mprocedure

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:

iset-copy isprocedure

A new copy of IS

iset n ...procedure

An iset containing the elements N...

list->iset ls #!optional base-isprocedure

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

list->iset! ls base-isprocedure

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

iset-size isprocedure

Return the # of elements in IS

iset-contains? is nprocedure

Test N for membership in IS

iset->list isprocedure

Returns a list of all integers in IS

iset-any pred isprocedure

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

iset-every pred isprocedure

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

iset? objprocedure

#t iff obj is an integer set.

iset= is ...procedure

#t iff all arguments are equivalent integer sets.

iset<= is ...procedure

#t iff the arguments are monotonically increasing sets.

iset>= is ...procedure

#t iff the arguments are monotonically decreasing sets.

iset-fold kons knil isprocedure

char-set-fold

iset-unfold f p g #!optional base-isprocedure

char-set-unfold

iset-unfold! f p g base-isprocedure

char-set-unfold!

iset-for-each proc isprocedure

char-set-for-each

iset-map proc isprocedure

char-set-map

iset-filter pred is #!optional bas-isprocedure

char-set-filter

iset-filter! pred is base-isprocedure

char-set-filter!

iset-cursor isetprocedure
iset-ref iset cursorprocedure
iset-cursor-next iset cursorprocedure
end-of-iset? isetprocedure

Cursor-based traversal of isets.

iset-delete is n ...procedure

char-set-delete

iset-delete! is n ...procedure

char-set-delete!

iset-union is1 ...procedure

char-set-union

iset-intersection is1 ...procedure

char-set-intersection

iset-difference is1 is2 ...procedure

char-set-difference

iset-xor is1 ...procedure

char-set-xor

iset-diff+intersection is1 is2 ...procedure

char-set-diff+intersection

iset-union! is1 ...procedure

char-set-union!

iset-intersection! is1 ...procedure

char-set-intersection!

iset-difference! is1 is2 ...procedure

char-set-difference!

iset-xor! is1 ...procedure

char-set-xor!

iset-diff+intersection! is1 is2 ...procedure

char-set-diff+intersection!

### Changelog

• 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.0 Initial release

``` Copyright (c) 2004-2006, Alex Shinn

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.```