1. sparse-vectors
    1. Introduction
    2. Usage
    3. API
      1. make-sparse-vector
      2. sparse-vector?
      3. check-sparse-vector
      4. sparse-vector-count
      5. sparse-vector-ref
      6. *sparse-vector-ref
      7. sparse-vector-set!
      8. *sparse-vector-set!
      9. sparse-vector-unset!
      10. *sparse-vector-unset!
    4. Higher Order Functions
    5. Usage
      1. sparse-vector-copy
      2. sparse-vector-equal?
      3. sparse-vector-fold
      4. sparse-vector-map
      5. sparse-vector-for-each
    6. Printing
    7. Usage
      1. sparse-vector-print-style?
      2. sparse-vector-print-style
      3. sparse-vector-print
    8. Debugging
    9. Usage
      1. sparse-vector-info
      2. sparse-vector-tree-fold
      3. sparse-vector-value-kind
    10. Extras
    11. Usage
      1. sparse-vector->alist
      2. alist->sparse-vector
      3. sparse-vector->list
      4. list->sparse-vector
      5. sparse-vector->vector
      6. vector->sparse-vector
      7. fill-sparse-vector!
      8. *fill-sparse-vector!
      9. sparse-vector-reserve!
  2. Authors
  3. Requirements
    1. Repository
    2. License
    3. Version history

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

[procedure] (make-sparse-vector [DEFAULT [BITS]]) -> sparse-vector
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?

[procedure] (sparse-vector? OBJ) -> boolean
OBJ ; * ; some object to test.

check-sparse-vector

[procedure] (check-sparse-vector LOC OBJ) -> sparse-vector

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

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

sparse-vector-count

[procedure] (sparse-vector-count SPARSE-VECTOR) -> fixnum

Returns the number of bound elements in SPARSE-VECTOR. An O(1) operation.

sparse-vector-ref

*sparse-vector-ref

[procedure] (sparse-vector-ref SPARSE-VECTOR INDEX) -> *
[procedure] (*sparse-vector-ref SPARSE-VECTOR INDEX) -> *

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!

[procedure] (sparse-vector-set! SPARSE-VECTOR INDEX VALUE)
[procedure] (*sparse-vector-set! SPARSE-VECTOR INDEX VALUE)

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!

[procedure] (sparse-vector-unset! SPARSE-VECTOR INDEX [SILENT?])
[procedure] (*sparse-vector-unset! SPARSE-VECTOR INDEX SILENT?)

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

[procedure] (sparse-vector-copy SPARSE-VECTOR) -> sparse-vector

Returns a copy of the SPARSE-VECTOR.

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

sparse-vector-equal?

[procedure] (sparse-vector-equal? SPARSE-VECTOR-1 SPARSE-VECTOR-2 [EQAL?]) -> boolean

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

[procedure] (sparse-vector-fold SPARSE-VECTOR FUNC SEED [SKIP?]) -> T'

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.

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

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

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

[procedure] (sparse-vector-for-each SPARSE-VECTOR FUNC [SKIP?])

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?

[procedure] (sparse-vector-print-style? OBJ) -> boolean

sparse-vector-print-style

[procedure] (sparse-vector-print-style [STYLE]) -> symbol
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

[procedure] (sparse-vector-print SPARSE-VECTOR [PORT])

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

[procedure] (sparse-vector-info SPARSE-VECTOR) -> integer fixnum fixnum

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

(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

[procedure] (sparse-vector-tree-fold SPARSE-VECTOR FUNC SEED) -> symbol
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

[procedure] (sparse-vector-value-kind OBJ) -> symbol

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

[procedure] (sparse-vector->alist SPARSE-VECTOR) -> (list-of (pair integer *))

Returns an ALIST for the SPARSE-VECTOR.

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

alist->sparse-vector

[procedure] (alist->sparse-vector ALIST [DEFAULT]) -> sparse-vector

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

[procedure] (sparse-vector->list SPARSE-VECTOR [START [END]]) -> list

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

[procedure] (list->sparse-vector LIST [START [DEFAULT [BITS]]]) -> sparse-vector

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

[procedure] (sparse-vector->vector SPARSE-VECTOR [START [END]]) -> vector

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

[procedure] (vector->sparse-vector VECTOR [START [DEFAULT [BITS]]]) -> sparse-vector

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!

[procedure] (fill-sparse-vector! SPARSE-VECTOR SOURCE [START])
[procedure] (*fill-sparse-vector! SPARSE-VECTOR SOURCE START)

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!

[procedure] (sparse-vector-reserve! SPARSE-VECTOR END [LOW])

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!

Authors

Richard Kelsey and Jonathan Rees, ported to CHICKEN by /users/ivan-raikov, extended by /users/kon-lovett.

Requirements

srfi-1 record-variants

test test-utils

Repository

This egg is hosted on the CHICKEN Subversion repository:

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

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