1 | [[tags: egg]] |
---|
2 | [[toc:]] |
---|
3 | |
---|
4 | == sparse-vectors |
---|
5 | |
---|
6 | === Introduction |
---|
7 | |
---|
8 | Sparse vectors are vectors that grow as large as they need to. That is, they |
---|
9 | can be indexed by arbitrarily large nonnegative integers. The |
---|
10 | implementation allows for arbitrarily large gaps by arranging the |
---|
11 | entries in a tree. |
---|
12 | |
---|
13 | === Usage |
---|
14 | |
---|
15 | (require-extension sparse-vectors) |
---|
16 | |
---|
17 | If you have the [[http://wiki.call-cc.org/eggref/4/numbers|numbers]] |
---|
18 | extension installed then this extension will be built with an additional |
---|
19 | variant that supports bignum indices: |
---|
20 | |
---|
21 | (require-extension big-sparse-vectors) |
---|
22 | |
---|
23 | === API |
---|
24 | |
---|
25 | <procedure> (make-sparse-vector [DEFAULT])</procedure> -> sparse-vector |
---|
26 | <procedure> (sparse-vector? x)</procedure> -> boolean |
---|
27 | <procedure> (sparse-vector-ref sparse-vector k)</procedure> -> value |
---|
28 | <procedure> (sparse-vector-set! sparse-vector k value)</procedure> |
---|
29 | <procedure> (sparse-vector->list sparse-vector)</procedure> -> list |
---|
30 | |
---|
31 | {{make-sparse-vector}}, {{sparse-vector-ref}} and {{sparse-vector-set!}} are |
---|
32 | analogous to {{make-vector}}, {{vector-ref}} and {{vector-set!}}, except that the |
---|
33 | indices passed to {{sparse-vector-ref}} and {{sparse-vector-set!}} can be |
---|
34 | arbitrarily large. |
---|
35 | |
---|
36 | The optional {{DEFAULT}} argument to the {{make-sparse-vector}} procedure specifies the default value for indices whose elements have not been set. |
---|
37 | If the element at index {{i}} has not been set, {{(sparse-vector-ref i)}} returns {{DEFAULT}} or #f, if {{DEFAULT}} was not specified when creating the vector. |
---|
38 | |
---|
39 | {{sparse-vector->list}} is for debugging: It returns a list of the |
---|
40 | consecutive elements in a sparse vector from 0 to the highest element |
---|
41 | that has been set. Note that the list will also include all the #f |
---|
42 | elements for the unset elements. |
---|
43 | |
---|
44 | {{(set! (sparse-vector-ref sparse-vector index) value)}} is supported. |
---|
45 | |
---|
46 | === Authors |
---|
47 | |
---|
48 | Richard Kelsey and Jonathan Rees, ported to CHICKEN by [[/users/ivan-raikov]]. |
---|
49 | |
---|
50 | === License |
---|
51 | |
---|
52 | Copyright (c) 1993-2006 Richard Kelsey and Jonathan Rees |
---|
53 | All rights reserved. |
---|
54 | |
---|
55 | Redistribution and use in source and binary forms, with or without |
---|
56 | modification, are permitted provided that the following conditions |
---|
57 | are met: |
---|
58 | 1. Redistributions of source code must retain the above copyright |
---|
59 | notice, this list of conditions and the following disclaimer. |
---|
60 | 2. Redistributions in binary form must reproduce the above copyright |
---|
61 | notice, this list of conditions and the following disclaimer in the |
---|
62 | documentation and/or other materials provided with the distribution. |
---|
63 | 3. The name of the authors may not be used to endorse or promote products |
---|
64 | derived from this software without specific prior written permission. |
---|
65 | |
---|
66 | THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR |
---|
67 | IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
---|
68 | OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
---|
69 | IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY DIRECT, INDIRECT, |
---|
70 | INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
---|
71 | NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
---|
72 | DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
---|
73 | THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
---|
74 | (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
---|
75 | THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
---|
76 | |
---|
77 | === Version history |
---|
78 | |
---|
79 | ; 0.4 : Fixed installation-script problems, added tests (thanks to Jim Pryor) |
---|
80 | ; 0.3 : Ported to Chicken 4 |
---|
81 | ; 0.2 : Added functionality to support default values other than #f |
---|
82 | ; 0.1 : Initial release |
---|