Debian Codegraph @

lib/data/priority-map.scm

raw
1 ;;;
2 ;;; priority-map.scm - a map, with ability to pull highest/lowest value
3 ;;;
4 ;;; Copyright (c) 2016-2024 Shiro Kawai <[email protected]>
5 ;;;
6 ;;; Redistribution and use in source and binary forms, with or without
7 ;;; modification, are permitted provided that the following conditions
8 ;;; are met:
9 ;;;
10 ;;; 1. Redistributions of source code must retain the above copyright
11 ;;; notice, this list of conditions and the following disclaimer.
12 ;;;
13 ;;; 2. Redistributions in binary form must reproduce the above copyright
14 ;;; notice, this list of conditions and the following disclaimer in the
15 ;;; documentation and/or other materials provided with the distribution.
16 ;;;
17 ;;; 3. Neither the name of the authors nor the names of its contributors
18 ;;; may be used to endorse or promote products derived from this
19 ;;; software without specific prior written permission.
20 ;;;
21 ;;; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 ;;; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 ;;; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 ;;; A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 ;;; OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 ;;; SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
27 ;;; TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28 ;;; PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29 ;;; LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30 ;;; NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31 ;;; SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 ;;;
33
34 ;; Priority map is a map whose entries are sorted by their values.
35 ;; If what you need is just a priority queue, use data.heap.
36 ;; Priority map is useful when you also need a quick lookup based on key.
37
38 (define-module data.priority-map
39 (use gauche.sequence)
40 (use gauche.dictionary)
41 (use gauche.generator)
42 (use util.match)
43 (export <priority-map>
44 make-priority-map dict->priority-map alist->priority-map
45 priority-map-min
46 priority-map-max
47 priority-map-min-all
48 priority-map-max-all
49 priority-map-pop-min!
50 priority-map-pop-max!))
51 (select-module data.priority-map)
52
53 (define-class <priority-map> (<ordered-dictionary>)
54 (;; private
55 (key-map :init-keyword :key-map) ; key -> value hashtable/treemap
56 (key-cmpr :init-keyword :key-cmpr) ; key comparator
57 (value-map :init-keyword :value-map) ; value -> [key] treemap
58 (value-cmpr :init-keyword :value-cmpr) ; value comparator, needs order
59 ))
60
61 (define (make-priority-map :key
62 (key-comparator default-comparator)
63 (value-comparator default-comparator))
64 (make <priority-map>
65 :key-map (if (comparator-hashable? key-comparator)
66 (make-hash-table key-comparator)
67 (make-tree-map key-comparator))
68 :key-cmpr key-comparator
69 :value-map (make-tree-map value-comparator)
70 :value-cmpr value-comparator))
71
72 ;; Sequence protocol
73 ;; Iterator iterates increasing order of values
74 (define-method size-of ((pm <priority-map>))
75 (size-of (~ pm'key-map)))
76
77 (define-method call-with-iterator ((coll <priority-map>) proc :allow-other-keys)
78 (define gen (x->generator (~ coll'value-map)))
79 (define keys '())
80 (define val #f)
81 (define (get1)
82 (let1 buf (gen)
83 (if (eof-object? buf)
84 (set!-values (keys val) (values buf buf))
85 (set!-values (keys val) (values (car buf) (cdr buf))))))
86 (get1)
87 (proc (cut eof-object? keys)
88 (^[] (rlet1 p (cons (pop! keys) val)
89 (when (null? keys)
90 (get1))))))
91
92 ;; Dictionary protocol
93 (define-method dict-get ((pmap <priority-map>) key :optional default)
94 (if (undefined? default)
95 (dict-get (~ pmap 'key-map) key)
96 (dict-get (~ pmap 'key-map) key default)))
97
98 (define-method dict-exists? ((pmap <priority-map>) key)
99 (dict-exists? (~ pmap 'key-map) key))
100
101 (define (%pmap-put! kmap kcmp vmap vcmp key value)
102 (and-let* ([v (dict-get kmap key #f)]
103 [ (not (=? vcmp v value)) ])
104 ($ tree-map-update! vmap v
105 (cute remove key <> (comparator-equality-predicate kcmp)) '()))
106 (tree-map-push! vmap value key)
107 (dict-put! kmap key value))
108
109 (define-method dict-put! ((pmap <priority-map>) key value)
110 (%pmap-put! (~ pmap 'key-map)
111 (~ pmap 'key-cmpr)
112 (~ pmap 'value-map)
113 (~ pmap 'value-cmpr)
114 key value))
115
116 (define-method dict-delete! ((pmap <priority-map>) key)
117 (let ([kmap (~ pmap 'key-map)]
118 [kcmp (~ pmap'key-cmpr)]
119 [vmap (~ pmap 'value-map)])
120 (and-let1 val (dict-get kmap key #f)
121 (let1 ks (tree-map-get vmap val)
122 (if (null? (cdr ks))
123 (tree-map-delete! vmap val)
124 (tree-map-put! vmap val (remove (cut =? kcmp key <>) ks)))))
125 (dict-delete! kmap key)))
126
127 (define-method dict-clear! ((pmap <priority-map>))
128 (dict-clear! (~ pmap'key-map))
129 (dict-clear! (~ pmap'value-map)))
130
131 (define-method dict-comparator ((pmap <priority-map>))
132 (dict-comparator (~ pmap'key-map)))
133
134 (define-method dict-fold ((pmap <priority-map>) proc seed)
135 ($ tree-map-fold (~ pmap 'value-map)
136 (^[v ks s] (fold (^[k s] (proc k v s)) s ks)) seed))
137
138 (define-method dict-fold-right ((pmap <priority-map>) proc seed)
139 ($ tree-map-fold-right (~ pmap 'value-map)
140 (^[v ks s] (fold-right (^[k s] (proc k v s)) s ks)) seed))
141
142 ;; specific stuff
143 (define (dict->priority-map dict
144 :optional (value-comparator default-comparator))
145 (rlet1 pmap (make-priority-map :key-comparator (dict-comparator dict)
146 :value-comparator value-comparator)
147 (let ([kmap (~ pmap 'key-map)]
148 [kcmp (~ pmap 'key-cmpr)]
149 [vmap (~ pmap 'value-map)]
150 [vcmp (~ pmap 'value-cmpr)])
151 (dict-for-each dict (^[k v] (%pmap-put! kmap kcmp vmap vcmp k v))))))
152
153 (define (alist->priority-map alist
154 :optional
155 (key-comparator default-comparator)
156 (value-comparator default-comparator))
157 (rlet1 pmap (make-priority-map :key-comparator key-comparator
158 :value-comparator value-comparator)
159 (let ([kmap (~ pmap 'key-map)]
160 [kcmp (~ pmap 'key-cmpr)]
161 [vmap (~ pmap 'value-map)]
162 [vcmp (~ pmap 'value-cmpr)])
163 (dolist [p alist]
164 (%pmap-put! kmap kcmp vmap vcmp (car p) (cdr p))))))
165
166 ;; Returns (k . v) where v is min or max; #f if pmap is empty
167 (define (priority-map-min pmap)
168 (and-let* ([p (tree-map-min (~ pmap'value-map))])
169 ;; p := ([key] . value)
170 ;; we just take the first key.
171 (cons (cadr p) (car p))))
172
173 (define (priority-map-max pmap)
174 (and-let* ([p (tree-map-max (~ pmap'value-map))])
175 ;; p := ([key] . value)
176 ;; we just take the first key.
177 (cons (cadr p) (car p))))
178
179 ;; Returns ((k k2 ...) . v); #f if pmap is empty
180 (define (priority-map-min-all pmap)
181 (and-let* ([p (tree-map-min (~ pmap'value-map))])
182 (cons (cdr p) (car p))))
183
184 (define (priority-map-max-all pmap)
185 (and-let* ([p (tree-map-max (~ pmap'value-map))])
186 (cons (cdr p) (car p))))
187
188 (define (priority-map-pop-min! pmap)
189 (let ([kmap (~ pmap 'key-map)]
190 [vmap (~ pmap 'value-map)])
191 (match (tree-map-min vmap)
192 [(val . (key . keys))
193 (if (null? keys)
194 (tree-map-delete! vmap val)
195 (tree-map-put! vmap val keys))
196 (dict-delete! kmap key)
197 (cons key val)]
198 [#f #f])))
199
200 (define (priority-map-pop-max! pmap)
201 (let ([kmap (~ pmap 'key-map)]
202 [vmap (~ pmap 'value-map)])
203 (match (tree-map-max vmap)
204 [(val . (key . keys))
205 (if (null? keys)
206 (tree-map-delete! vmap val)
207 (tree-map-put! vmap val keys))
208 (dict-delete! kmap key)
209 (cons key val)]
210 [#f #f])))