[[tags: egg]]
[[toc:]]
== 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 [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?
(sparse-vector? OBJ) -> boolean
; {{OBJ}} ; {{*}} ; some object to test.
==== check-sparse-vector
(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
(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
(sparse-vector-ref SPARSE-VECTOR INDEX) -> *
(*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!
(sparse-vector-set! SPARSE-VECTOR INDEX VALUE)
(*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!
(sparse-vector-unset! SPARSE-VECTOR INDEX [SILENT?])
(*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)}}.
=== Printing
=== Usage
(import (sparse-vectors hof))
==== sparse-vector-copy
(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?
(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
(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}}.
* 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')
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 [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}}.
==== alist->sparse-vector
(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->alist
(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}}.
=== Printing
=== Usage
(import (sparse-vectors print))
==== sparse-vector-print-style?
(sparse-vector-print-style? OBJ) -> boolean
==== sparse-vector-print-style
(sparse-vector-print-style [STYLE]) -> symbol
; {{STYLE}} ; {{symbol}} ; one-of {{describe}}, {{contents}}, or {{debug}}, default {{describe}}.
: {{describe}} ; {{#}} ; see {{sparse-vector-count}}.
: {{contents}} ; {{#}} ; see {{sparse-vector->alist}}.
Currently no method to edit the set of {{print-style}}.
==== sparse-vector-print
(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
(sparse-vector-info SPARSE-VECTOR) -> integer fixnum fixnum
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->list
(sparse-vector->list SPARSE-VECTOR) -> list
Returns a list of the consecutive elements in a sparse vector from 0 to the
highest element that has been used.
Note that the list will also include all the {{DEFAULT}} elements for those
unset.
==== sparse-vector-tree-fold
(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
(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}}.
=== 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|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 [[/egg-svn-checkout|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.0.0 : Extend with ''HOF'', print, alist serial form, count, element unset.
; 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