sparse-vectors

Introduction

Sparse vectors are vectors that grow as large as they need to. That is, they can be indexed by arbitrarily large nonnegative integers. The implementation allows for arbitrarily large gaps by arranging the entries in a tree.

Usage

(import sparse-vectors)

API

A sparse-vector is analogous to a vector, except that the indices can be arbitrarily large.

make-sparse-vector

make-sparse-vector #!optional DEFAULT BITSprocedure

DEFAULT ; * ; value for indices whose elements have not been set, default #f.
BITS ; fixnum ; node length power of 2, default 8.

The DEFAULT must be disjoint from the set-of element types, see VALUE below.

sparse-vector?

sparse-vector? OBJprocedure

OBJ ; * ; some object to test.

check-sparse-vector

check-sparse-vector LOC OBJprocedure

Returns the OBJ when a sparse-vector, and raises an error otherwise.

LOC ; symbol ; caller identifier.
OBJ ; * ; some object to check.

sparse-vector-count

sparse-vector-count SPARSE-VECTORprocedure: Returns the number of bound elements in SPARSE-VECTOR. An O(1) operation.

sparse-vector-ref

*sparse-vector-ref

sparse-vector-ref SPARSE-VECTOR INDEXprocedure

*sparse-vector-ref SPARSE-VECTOR INDEXprocedure

Returns the element at INDEX. If the element at INDEX has not been set, (sparse-vector-ref INDEX) returns the DEFAULT. The *sparse-vector-ref variant does not perform argument checking.

INDEX ; uinteger ; integer in [0 ...).

An O(m) operation where m is ((log/base storage-node-size) INDEX).

sparse-vector-set!

*sparse-vector-set!

sparse-vector-set! SPARSE-VECTOR INDEX VALUEprocedure

*sparse-vector-set! SPARSE-VECTOR INDEX VALUEprocedure

Binds the element at INDEX to VALUE. The *sparse-vector-set! variant does not perform argument checking.

INDEX ; uinteger ; integer in [0 ...).
VALUE ; * ; but not DEFAULT.

(set! (sparse-vector-ref SPARSE-VECTOR INDEX) VALUE) is supported.

An O(m) operation where m is ((log/base storage-node-size) INDEX).

sparse-vector-unset!

*sparse-vector-unset!

sparse-vector-unset! SPARSE-VECTOR INDEX #!optional SILENT?procedure

*sparse-vector-unset! SPARSE-VECTOR INDEX SILENT?procedure

Unbinds the element at INDEX. Should SILENT? be #f then raise an error condition upon reseting an unset element. The *sparse-vector-unset! variant does not perform argument checking.

INDEX ; uinteger ; integer in [0 ...).
SILENT? ; boolean ; error when unbound?

An O(m) operation where m is ((log/base storage-node-size) INDEX).

Higher Order Functions

Usage

(import (sparse-vectors hof))

sparse-vector-copy

sparse-vector-copy SPARSE-VECTORprocedure

Returns a copy of the SPARSE-VECTOR.

An O(n) operation, where n is total-count.

sparse-vector-equal?

sparse-vector-equal? SPARSE-VECTOR-1 SPARSE-VECTOR-2 #!optional EQAL?procedure

Does SPARSE-VECTOR-1 = SPARSE-VECTOR-2?

EQAL? ; (* * --> boolean) ; equality function, default is equal?.

Note that the EQAL? function must deal with the, possible, non-domain sparse-vector default object.

An O(n) operation, where n is total-count.

sparse-vector-fold

sparse-vector-fold SPARSE-VECTOR FUNC SEED #!optional SKIP?procedure

When SKIP? is #t unbound elements are skipped, otherwise the FUNC is treated to all elements; an implementation detail.

FUNC ; (INDEX ACC VALUE -> T') ; element function.
T' ; defined-type ; type-of the SEED & ACC.
INDEX ; uinteger ; integer in [0 ...).
VALUE ; * ; but not DEFAULT.
SEED ; T' ; initial value.
ACC ; T' ; accumulated value.
SKIP? ; boolean ; skip unbound? default is #t.

An O(n) operation, where n is total-count.

Example:

(define (sparse-vector-reduce sv func seed)
  (sparse-vector-fold sv (lambda (i a v) (func a v)) seed) )

(define (sparse-vector-sum sv) (sparse-vector-reduce sv + 0))

(define (sparse-vector-folded-count sv)
  (sparse-vector-fold sv (lambda (i a v) (add1 a)) 0) )

Example, using a SKIP? of #f:

(define (sparse-vector-unoccupied-count sv)
  (sparse-vector-fold sv (lambda (i a v) (if (not v) (add1 a) a)) 0 #f) )

sparse-vector-map

(sparse-vector-map SPARSE-VECTOR FUNC [SKIP?] -> (list-of T')procedure

When SKIP? is #t unbound elements are skipped, otherwise the FUNC is treated to all elements; an implementation detail.

FUNC ; (INDEX VALUE -> T') ; element function.
T' ; defined-type ; type-of the SEED & ACC.
INDEX ; uinteger ; integer in [0 ...).
VALUE ; * ; but not DEFAULT.
SKIP? ; boolean ; skip unbound?

An O(n) operation, where n is total-count.

sparse-vector-for-each

sparse-vector-for-each SPARSE-VECTOR FUNC #!optional SKIP?procedure

When SKIP? is #t unbound elements are skipped, otherwise the FUNC is treated to all elements; an implementation detail.

FUNC ; (INDEX VALUE -> void) ; element function.
INDEX ; uinteger ; integer in [0 ...).
VALUE ; * ; but not DEFAULT.
SKIP? ; boolean ; skip unbound?

An O(n) operation, where n is total-count.

Printing

Usage

(import (sparse-vectors print))

sparse-vector-print-style?

sparse-vector-print-style? OBJprocedure

sparse-vector-print-style

sparse-vector-print-style #!optional STYLEprocedure

STYLE ; symbol ; one-of describe, contents, or debug, default describe.

: describe ; #<sparse-vector |DEFAULT| COUNT> ; see sparse-vector-count. : contents ; #<sparse-vector ALIST> ; see sparse-vector->alist.

Currently no method to edit the set of print-style.

sparse-vector-print

sparse-vector-print SPARSE-VECTOR #!optional PORTprocedure

Displays a (sparse-vector-print-style) representaiton of the SPARSE-VECTOR on the PORT

PORT ; output-port ; default current-output-port.

Debugging

Note that this module provides access to the representation of a sparse-vector. As such it is subject to change.

Usage

(import (sparse-vectors debug))

sparse-vector-info

sparse-vector-info SPARSE-VECTORprocedure

Returns the sparse-vector tree representation node (count, depth & size.

Example:

(define (sparse-vector-efficiency sv)
  (let-values (((nodcnt nodht nodsiz) (sparse-vector-info sv)))
    (exact->inexact (/ (sparse-vector-count sv) (* nodcnt nodsiz))) ) )

sparse-vector-tree-fold

sparse-vector-tree-fold SPARSE-VECTOR FUNC SEEDprocedure

FUNC: (SEED NODE HEIGHT PARENT INDEX -> NEW-SEED) ; function called for each node.
SEED: * : initial value.
NODE: sparse-vector-node : current node.
HEIGHT: fixnum : tree height.
PARENT: (or false sparse-vector-node) : parent node.
INDEX: (or false fixnum) : parent node index.

Note that the sparse-vector-node is opaque, in that no access functions are exported. For now it is a vector without any internal structure.

sparse-vector-value-kind

sparse-vector-value-kind OBJprocedure

Returns a symbol, one of node, unset!, set!, for the category of sparse-vector node element OBJ.

For use with sparse-vector-tree-fold.

Extras

Usage

(import (sparse-vectors extras))

sparse-vector->alist

sparse-vector->alist SPARSE-VECTORprocedure

Returns an ALIST for the SPARSE-VECTOR.

An O(n) operation, where n is total-count.

alist->sparse-vector

alist->sparse-vector ALIST #!optional DEFAULTprocedure

Returns a new sparse-vector for the ALIST.

ALIST ; (list-of (pair INDEX VALUE))
DEFAULT ; * ; value for indices whose elements have not been set, default #f.

The DEFAULT should be disjoint from the set-of element types, see VALUE.

An O(n) operation, where n is (length ALIST).

sparse-vector->list

sparse-vector->list SPARSE-VECTOR #!optional START ENDprocedure

Returns a list of the consecutive elements in the SPARSE-VECTOR from START to the END or highest element that has been used, if no END specified.

START: integer ; starting spare-vector index, defaults to 0.
END: (or false integer) ; ending spare-vector index, defaults to #f.

Note that the list will also include all the DEFAULT elements for those unset.

list->sparse-vector

list->sparse-vector LIST #!optional START DEFAULT BITSprocedure

Returns a sparse-vector with consecutive elements, beginning with START, from those of the LIST.

START: integer ; starting spare-vector index, defaults to 0.
DEFAULT ; * ; value for indices whose elements have not been set, default #f.
BITS ; fixnum ; node length power of 2, default 8.

sparse-vector->vector

sparse-vector->vector SPARSE-VECTOR #!optional START ENDprocedure

Returns a vector from the consecutive elements in the SPARSE-VECTOR from START to the END or highest element that has been used, if no END specified.

START: integer ; starting spare-vector index, defaults to 0.
END: (or false integer) ; ending index, defaults to #f.

Note that the vector will also include all the DEFAULT elements for those unset.

vector->sparse-vector

vector->sparse-vector VECTOR #!optional START DEFAULT BITSprocedure

Returns a sparse-vector with consecutive elements, beginning with START, from those of the VECTOR.

START: integer ; starting spare-vector index, defaults to 0.
DEFAULT ; * ; value for indices whose elements have not been set, default #f.
BITS ; fixnum ; node length power of 2, default 8.

fill-sparse-vector!

*fill-sparse-vector!

fill-sparse-vector! SPARSE-VECTOR SOURCE #!optional STARTprocedure

*fill-sparse-vector! SPARSE-VECTOR SOURCE STARTprocedure

Set the consecutive elements of the SPARSE-VECTOR, beginning with START, from the SOURCE. The *fill-sparse-vector! variant does not perform argument type checking.

SOURCE: (or list vector) ; element source.
START: integer ; starting spare-vector index, defaults to 0.

sparse-vector-reserve!

sparse-vector-reserve! SPARSE-VECTOR END #!optional LOWprocedure

Perform any internal construction necessary to contain elements in the half-open range [LOW END).

END: integer ; sparse-vectorindex range limit.
LOW: integer ; sparse-vectorindex range start, default 0.

Note the SPARSE-VECTOR must be empty!

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

License

Copyright (c) 1993-2006 Richard Kelsey and Jonathan Rees
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 authors may not be used to endorse or promote products
   derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``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 AUTHORS 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.

Version history

1.1.1: Fix sparse-vector-equal? purity. (by Kon Lovett)
1.1.0: Add fill-sparse-vector!, vector->sparse-vector, sparse-vector->vector, list->sparse-vector, & sparse-vector->list to extras. (by Kon Lovett)
1.0.1: . (by Kon Lovett)
1.0.0: Extend with HOF, print, alist serial form, count, element unset (by Kon Lovett)
0.5: Ported to Chicken 5
0.4: Fixed installation-script problems, added tests (thanks to Jim Pryor)
0.3: Ported to Chicken 4
0.2: Added functionality to support default values other than #f
0.1: Initial release

chickadee » sparse-vectors

Identifier search

TOC »

Contents »