[[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

<enscript language=scheme>
(import sparse-vectors)
</enscript>

=== 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]])</procedure> -> 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)</procedure> -> boolean

; {{OBJ}} ; {{*}} ; some object to test.

==== check-sparse-vector

<procedure>(check-sparse-vector LOC OBJ)</procedure> -> 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)</procedure> -> 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> -> *
<procedure>(*sparse-vector-ref SPARSE-VECTOR INDEX)</procedure> -> *

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>
<procedure>(*sparse-vector-set! SPARSE-VECTOR INDEX VALUE)</procedure>

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

=== Printing

=== Usage

<enscript language=scheme>
(import (sparse-vectors hof))
</enscript>

==== sparse-vector-copy

<procedure>(sparse-vector-copy SPARSE-VECTOR)</procedure> -> 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?])</procedure> -> 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?])</procedure> -> 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:
<enscript language=scheme>
(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) )
</enscript>

* Example, using a {{SKIP?}} of {{#f}}:
<enscript language=scheme>
(define (sparse-vector-unoccupied-count sv)
  (sparse-vector-fold sv (lambda (i a v) (if (not v) (add1 a) a)) 0 #f) )
</enscript>

==== sparse-vector-map

<procedure>(sparse-vector-map SPARSE-VECTOR FUNC [SKIP?]</procedure> -> (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?])</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}}.

==== alist->sparse-vector

<procedure>(alist->sparse-vector ALIST [DEFAULT])</procedure> -> 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

<procedure>(sparse-vector->alist SPARSE-VECTOR)</procedure> -> (list-of (pair integer *))

Returns an {{ALIST}} for the {{SPARSE-VECTOR}}.

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

=== Printing

=== Usage

<enscript language=scheme>
(import (sparse-vectors print))
</enscript>

==== sparse-vector-print-style?

<procedure>(sparse-vector-print-style? OBJ)</procedure> -> boolean

==== sparse-vector-print-style

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

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

<enscript language=scheme>
(import (sparse-vectors debug))
</enscript>

==== sparse-vector-info

<procedure>(sparse-vector-info SPARSE-VECTOR)</procedure> -> integer fixnum fixnum

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

* Example:
<enscript language=scheme>
(define (sparse-vector-efficiency sv)
  (let-values (((nodcnt nodht nodsiz) (sparse-vector-info sv)))
    (exact->inexact (/ (sparse-vector-count sv) (* nodcnt nodsiz))) ) )
</enscript>

==== sparse-vector->list

<procedure>(sparse-vector->list SPARSE-VECTOR)</procedure> -> 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

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