1 | ; Copyright (c) 2004, Jonah Nathaniel Beckford |
---|
2 | ; All rights reserved. |
---|
3 | ; |
---|
4 | ; Redistribution and use in source and binary forms, with or without |
---|
5 | ; modification, are permitted provided that the following conditions |
---|
6 | ; are met: |
---|
7 | ; |
---|
8 | ; Redistributions of source code must retain the above copyright |
---|
9 | ; notice, this list of conditions and the following disclaimer. |
---|
10 | ; |
---|
11 | ; Redistributions in binary form must reproduce the above copyright |
---|
12 | ; notice, this list of conditions and the following disclaimer in |
---|
13 | ; the documentation and/or other materials provided with the |
---|
14 | ; distribution. |
---|
15 | ; |
---|
16 | ; Neither the name of the author nor the names of its contributors |
---|
17 | ; may be used to endorse or promote products derived from this |
---|
18 | ; software without specific prior written permission. |
---|
19 | ; |
---|
20 | ; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
---|
21 | ; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
---|
22 | ; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS |
---|
23 | ; FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE |
---|
24 | ; COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, |
---|
25 | ; INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES |
---|
26 | ; (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR |
---|
27 | ; SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
---|
28 | ; HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, |
---|
29 | ; STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
---|
30 | ; ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED |
---|
31 | ; OF THE POSSIBILITY OF SUCH DAMAGE. |
---|
32 | ; |
---|
33 | ; jonah@usermail.com |
---|
34 | |
---|
35 | ;;;; A <strong>property getter</strong> is a procedure <code>(lambda |
---|
36 | ;;;; (graph vertex-or-edge))</code> that gets an arbitrary scheme |
---|
37 | ;;;; object that is associated with the vertex-or-edge in graph.<br> |
---|
38 | ;;;; |
---|
39 | ;;;; A <strong>property setter</strong> is a procedure <code>(lambda |
---|
40 | ;;;; (graph vertex-or-edge value))</code> that associates an arbitrary |
---|
41 | ;;;; scheme object to the vertex-or-edge in graph.<br> |
---|
42 | ;;;; |
---|
43 | ;;;; A <strong>property map</strong> is a pair <code>(cons |
---|
44 | ;;;; property-getter property-setter!)</code>, whose car is a property |
---|
45 | ;;;; getter and whose cdr is a property setter.<br> |
---|
46 | ;;;; |
---|
47 | ;;;; A <strong>property key</strong> is a vertex or an edge, dependent |
---|
48 | ;;;; upon whether the context is a vertex property or an edge |
---|
49 | ;;;; property, respectively.<br> |
---|
50 | |
---|
51 | ;;; Properties. |
---|
52 | ;;; |
---|
53 | ;;; <p>The internal properties are defined when you define the graph. |
---|
54 | ;;; See <a href="rgraph-al.scm">Adjacency List</a> for an example.</p> |
---|
55 | |
---|
56 | ;; Create an external property map on top of a hashtable. |
---|
57 | ;; |
---|
58 | ;; .form (prop-external-hash eq? [num]) |
---|
59 | ;; .parameter eq? A procedure that will equality compare two property keys. |
---|
60 | ;; .parameter num Optional. The initial size of the hash-table. |
---|
61 | ;; .returns A property map. |
---|
62 | (define (prop-external-hash eq? . num) |
---|
63 | (let ([store (if (null? num) |
---|
64 | (make-hash-table eq?) |
---|
65 | (make-hash-table eq? (car num)))]) |
---|
66 | (cons |
---|
67 | (lambda (g k) (hash-table-ref store k)) |
---|
68 | (lambda (g k v) (hash-table-set! store k v))))) |
---|
69 | |
---|
70 | ;; Create an external property map on top of a vector. The property |
---|
71 | ;; key must be an integer. |
---|
72 | ;; |
---|
73 | ;; .form (prop-external-vector [num]) |
---|
74 | ;; .parameter num Optional. The initial size of the vector |
---|
75 | ;; .returns A property map. |
---|
76 | (define (prop-external-vector . num) |
---|
77 | (let ([store (if (null? num) |
---|
78 | (make-vector) |
---|
79 | (make-vector (car num)))]) |
---|
80 | (cons |
---|
81 | (lambda (g k) (vector-ref store k)) |
---|
82 | (lambda (g k v) |
---|
83 | (when (> k (vector-length store)) |
---|
84 | (set! store (vector-resize! store (max 2 (* 1.7 k))))) |
---|
85 | (vector-set! store k v))))) |
---|