back

bb

Description:

Integer sets.

Author:

Alex Shinn

Version:

Usage:

(require-extension iset)

Download:

iset.egg

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

The following procedures can be used to create and test bit-vectors:

(make-bit-vector size)    ; a 'zero' bit-vector, with a hint that we
                          ; wish to use SIZE bits
(make-bit-vector size #t) ; same as above but initialize the all bit
                          ; elements to #t (= the integer 2^SIZE-1)
(integer->bit-vector n)   ; create a bit-vector with bits initialized
                          ; to the corresponds bits in fixnum N
(bit-vector-copy bv)      ; make a copy of the bit-vector BV

(bit-vector? obj)         ; #t iff OBJ is a valid bit-vector, which
                          ; is not necessarily a disjoint type
(bit-vector-empty? bv)    ; #t iff BV has no bits set (the bit-vector
                          ; equivalent of the ZERO? 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:

(bit-vector-ref bv i)     ; #t if the I-th bit in BV is set, else #f
(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)
(bit-vector-set! bv i x)  ; in-place update version of the above, is
                          ; allowed but not required to mutate BV

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

(bit-vector-length bv)    ; integer-length
                          ;   the index of the largest bit set in BV
(bit-vector-count bv)     ; bit-count
                          ;   the number of set bits in BV
(bit-vector-shift bv n)   ; arithmetic-shift
(bit-vector-and bv ...)   ; bitwise-and
(bit-vector-ior bv ...)   ; bitwise-ior
(bit-vector-xor bv ...)   ; bitwise-xor
(bit-vector-eqv bv ...)   ; bitwise-eqv
(bit-vector-nand bv ...)  ; bitwise-nand
(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:

(bit-vector-shift! bv n)
(bit-vector-and! bv ...)
(bit-vector-ior! bv ...)
(bit-vector-xor! bv ...)
(bit-vector-eqv! bv ...)
(bit-vector-nand! bv ...)
(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:

(make-iset)     ; an empty integer set
(make-iset n)   ; a set of the single integer N
(make-iset n m) ; a set of the range of all integers from N-M inclusive

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:

Creating isets:

(iset-copy is)            ; a new copy of IS
(iset n ...)              ; an iset containing the elements N...
(list->iset ls [base-is]) ; an iset containing all the integers in
                          ; list LS, union BASE-IS if provided
(list->iset! ls base-is)  ; same as above, allowed but not required to
                          ; modify base-is

Querying isets:

(iset-size is)          ; return the # of elements in IS
(iset-contains? is n)   ; test N for membership in IS
(iset->list is)         ; returns a list of all integers in IS
(iset-any pred is)      ; apply PRED to every element of IS, returning
                        ; the first element it finds (order unspecified)
(iset-every pred is)    ; returns #t if every element of IS satisfies
                        ; the predicate PRED (order unspecified)

Predicates:

(iset? obj)     ; #t iff obj is an integer set
(iset= is ...)  ; #t iff all arguments are equivalent integer sets
(iset<= is ...) ; #t iff the arguments are monotonically increasing sets
(iset>= is ...) ; #t iff the arguments are monotonically decreasing sets

Iteration:

(iset-fold kons knil is)       ; char-set-fold
(iset-unfold f p g [base-is])  ; char-set-unfold
(iset-unfold! f p g base-is)   ; char-set-unfold!
(iset-for-each proc is)        ; char-set-for-each
(iset-map proc is)             ; char-set-for-each
(iset-filter pred is [bas-is]) ; char-set-filter
(iset-filter! pred is base-is) ; char-set-filter!

Cursors:

(iset-cursor iset)
(iset-ref iset cursor)
(iset-cursor-next iset cursor)
(end-of-iset? iset)

Set operations:

(iset-adjoin is n ...)         ; char-set-adjoin
(iset-delete is n ...)         ; char-set-delete

(iset-adjoin! is n ...)        ; char-set-adjoin!
(iset-delete! is n ...)        ; char-set-delete!

(iset-union is1 ...)                  ; char-set-union
(iset-intersection is1 ...)           ; char-set-intersection
(iset-difference is1 is2 ...)         ; char-set-difference
(iset-xor is1 ...)                    ; char-set-xor
(iset-diff+intersection is1 is2 ...)  ; char-set-diff+intersection

(iset-union! is1 ...)                 ; char-set-union!
(iset-intersection! is1 ...)          ; char-set-intersection!
(iset-difference! is1 is2 ...)        ; char-set-difference!
(iset-xor! is1 ...)                   ; char-set-xor!
(iset-diff+intersection! is1 is2 ...) ; char-set-diff+intersection!

License:

Copyright (c) 2004-2006 Alex Shinn. All rights reserved.
BSD-style license: http://synthcode.com/license.txt
back