Debian Codegraph @

lib/data/heap.scm

raw
1 ;;;
2 ;;; data.heap - Heaps
3 ;;;
4 ;;; Copyright (c) 2014-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 (define-module data.heap
35 (use gauche.sequence)
36 (use gauche.uvector)
37 (use scheme.list)
38 (export <binary-heap>
39 make-binary-heap build-binary-heap
40 binary-heap-comparator binary-heap-key-procedure
41 binary-heap-capacity
42 binary-heap-empty? binary-heap-num-entries
43 binary-heap-copy binary-heap-check binary-heap-clear!
44 binary-heap-push!
45 binary-heap-find-min binary-heap-find-max
46 binary-heap-pop-min! binary-heap-pop-max!
47 binary-heap-swap-min! binary-heap-swap-max!
48 binary-heap-find binary-heap-remove! binary-heap-delete!
49 ))
50 (select-module data.heap)
51
52 ;; we use sparse-vector by default; we just make it autoload
53 ;; so that the tests won't depend on data.sparse.
54 (autoload data.sparse make-sparse-vector <sparse-vector-base>
55 sparse-vector-num-entries sparse-vector-exists?
56 sparse-vector-copy sparse-vector-clear!)
57
58 ;;;
59 ;;; Binary Heap
60 ;;;
61
62 ;; We use min-max heap; whatever gain earned by limiting to min-heap
63 ;; or max-heap would be small compared to other overhead.
64
65 ;; M.D. Atkinson, J.-R. Sack, N. Santoro, T. Strothotte,
66 ;; Min-max heaps and generalized priority queues, CACM 29(10) pp.996-1000
67 ;; Oct. 1986, http://dx.doi.org/10.1145/6617.6621
68
69 ;; Binary heap is stored in an array, S[].
70 ;;
71 ;; - S[1] is the root.
72 ;; - S[i]'s child is S[2i] and S[2i+1]
73 ;; - S[i]'s parent is S[floor(i/2)] when i > 1.
74 ;; - Stored data can be anything comparable.
75 ;;
76 ;; Since S[0] won't be used, we treat the backing storage as 1-based;
77 ;; that is, S[1] is stored in the first element, and so on.
78 ;;
79 ;; Backing storage can be either a flat vector (vector, uvector) or
80 ;; a sparse vector. If it is a flat vector, the heap has maximum size
81 ;; (we don't extend the buffer automatically).
82
83 (define-inline (Ix x) (- x 1)) ; convert 1-base to 0-base
84
85 (define-syntax swap!
86 (syntax-rules ()
87 [(_ storage i j)
88 (let1 v (~ storage (Ix i))
89 (set! (~ storage (Ix i)) (~ storage (Ix j)))
90 (set! (~ storage (Ix j)) v))]))
91
92 ;; When an item is removed, we fill the slot with this value to be GC friendly.
93 ;; 0 is chosen that all supported types of backing storage can hold it; if we
94 ;; extend the support of backing storage, we may need to reconsider this.
95 (define-constant *filler* 0)
96
97 (define-class <binary-heap> ()
98 ((comparator :init-keyword :comparator)
99 (key :init-keyword :key)
100 (capacity :init-keyword :capacity) ; +inf.0 if storage is a sparse vector
101 ;; internal
102 (<: :init-keyword :<:) ; cached less-than proc
103 (>: :init-keyword :>:) ; cached greater-than proc
104 (storage :init-keyword :storage)
105 (next-leaf :init-keyword :next-leaf :init-value 1) ; next leaf index
106 ))
107
108 (define (make-binary-heap :key (comparator default-comparator)
109 (storage (make-sparse-vector))
110 (key identity))
111 (unless (comparator-ordered? comparator)
112 (error "make-binary-heap requires ordered comparator, \
113 but got:" comparator))
114 (receive (<: >:)
115 (ecase (comparator-flavor comparator)
116 [(ordering) (values (comparator-ordering-predicate comparator)
117 (^[a b] (>? comparator a b)))]
118 [(comparison) (values (^[a b] (<? comparator a b))
119 (^[a b] (>? comparator a b)))])
120 (make <binary-heap> :comparator comparator
121 :storage (if (or (vector? storage) (uvector? storage)
122 (is-a? storage <sparse-vector-base>))
123 storage
124 (error "make-binary-heap requires a vector, a uvector \
125 or a sparse vector as a storage, but got:"
126 storage))
127 :key key
128 :capacity (cond [(vector? storage) (vector-length storage)]
129 [(uvector? storage) (uvector-length storage)]
130 [else +inf.0])
131 :<: <:
132 :>: >:)))
133
134 ;; heapify
135 (define (build-binary-heap storage :key (num-entries #f)
136 (comparator default-comparator)
137 (key identity))
138 (unless (comparator-ordered? comparator)
139 (error "build-binary-heap requires ordered comparator, \
140 but got:" comparator))
141 (let* ([xlen (cond
142 [(vector? storage) (vector-length storage)]
143 [(uvector? storage) (uvector-length storage)]
144 [(is-a? storage <sparse-vector-base>)
145 (sparse-vector-num-entries storage)]
146 [else (error "build-binary-heap requires a vector, a uvector \
147 or a sparse vector as a storage, but got:"
148 storage)])]
149 [size (cond [(not num-entries) xlen]
150 [(and (integer? num-entries) (>= num-entries 0))
151 (min num-entries xlen)]
152 [else
153 (error "invalid num-entries value for build-binary-heap:"
154 num-entries)])])
155 (receive (<: >:)
156 (ecase (comparator-flavor comparator)
157 [(ordering) (values (comparator-ordering-predicate comparator)
158 (^[a b] (>? comparator a b)))]
159 [(comparison) (values (^[a b] (<? comparator a b))
160 (^[a b] (>? comparator a b)))])
161 (bh-heapify! storage <: >: size)
162 (make <binary-heap> :comparator comparator :storage storage :key key
163 :<: <: :>: >: :next-leaf (+ size 1)
164 :capacity (cond [(vector? storage) (vector-length storage)]
165 [(uvector? storage) (uvector-length storage)]
166 [else +inf.0])))))
167
168 (define (binary-heap-copy hp)
169 (make <binary-heap>
170 :comparator (~ hp'comparator)
171 :storage (let1 s (~ hp'storage)
172 (cond [(vector? s) (vector-copy s)]
173 [(uvector? s) (uvector-copy s)]
174 [(is-a? s <sparse-vector-base>) (sparse-vector-copy s)]
175 [else (error "[internal] binary-heap-copy: invalid storage:" s)]))
176 :key (~ hp'key)
177 :capaticy (~ hp'capacity)
178 :<: (~ hp'<:)
179 :>: (~ hp'>:)
180 :next-leaf (~ hp'next-leaf)))
181
182 (define (binary-heap-comparator hp) (~ hp'comparator))
183 (define (binary-heap-key-procedure hp) (~ hp'key))
184 (define (binary-heap-capacity hp) (~ hp'capacity))
185
186 (define (binary-heap-clear! hp)
187 (set! (~ hp'next-leaf) 1)
188 ;; These are theoretically unnecessary, but works nicely with GC.
189 (let1 st (~ hp'storage)
190 (cond [(vector? st) (vector-fill! st #f)]
191 [(is-a? st <sparse-vector-base>) (sparse-vector-clear! st)])))
192
193 (define (binary-heap-push! hp item)
194 (let1 next (~ hp'next-leaf)
195 (when (>= (- next 1) (~ hp'capacity))
196 (errorf "binary heap ~s is full: couldn't insert ~s" hp item))
197 (comparator-check-type (~ hp'comparator) ((~ hp'key) item))
198 (set! (~ hp'storage (Ix next)) item)
199 (set! (~ hp'next-leaf) (+ next 1))
200 (when (> next 1)
201 (bh-bubble-up (~ hp'storage) (~ hp'<:) (~ hp'>:) next))))
202
203 (define (binary-heap-num-entries hp) (- (~ hp'next-leaf) 1))
204
205 (define (binary-heap-empty? hp) (= (~ hp'next-leaf) 1))
206
207 (define (binary-heap-find-min hp :optional (fallback (undefined)))
208 (if (= (~ hp'next-leaf) 1)
209 (if (undefined? fallback)
210 (error "binary heap is empty:" hp)
211 fallback)
212 (~ hp'storage (Ix 1))))
213
214 (define (binary-heap-find-max hp :optional (fallback (undefined)))
215 (case (~ hp'next-leaf)
216 [(1) (if (undefined? fallback)
217 (error "binary heap is empty:" hp)
218 fallback)]
219 [(2) (~ hp'storage (Ix 1))]
220 [(3) (~ hp'storage (Ix 2))]
221 [else (let ([a (~ hp'storage (Ix 2))]
222 [b (~ hp'storage (Ix 3))])
223 (if ((~ hp'>:) a b) a b))]))
224
225 (define (binary-heap-pop-min! hp)
226 (let ([nelts (binary-heap-num-entries hp)]
227 [storage (~ hp'storage)])
228 (when (= nelts 0) (error "binary heap is empty:" hp))
229 (rlet1 r (~ storage (Ix 1))
230 (set! (~ storage (Ix 1)) (~ storage (Ix nelts)))
231 (set! (~ storage (Ix nelts)) *filler*)
232 (set! (~ hp'next-leaf) nelts)
233 (bh-trickle-down storage (~ hp'<:) (~ hp'>:) 1 nelts))))
234
235 (define (binary-heap-pop-max! hp)
236 (let ([nelts (binary-heap-num-entries hp)]
237 [storage (~ hp'storage)])
238 (define (swap-and-adjust index)
239 (set! (~ storage (Ix index)) (~ storage (Ix nelts)))
240 (set! (~ storage (Ix nelts)) *filler*)
241 (set! (~ hp'next-leaf) nelts)
242 (bh-trickle-down storage (~ hp'<:) (~ hp'>:) index nelts))
243 (case nelts
244 [(0) (error "binary heap is empty:" hp)]
245 [(1 2) (set! (~ hp'next-leaf) nelts) (~ storage (Ix nelts))]
246 [else
247 (let ([a (~ storage (Ix 2))]
248 [b (~ storage (Ix 3))])
249 (if ((~ hp'>:) a b)
250 (begin (swap-and-adjust 2) a)
251 (begin (swap-and-adjust 3) b)))])))
252
253 ;; (binary-heap-swap-* hp item) is operationally equivalent to
254 ;; (rlet1 entry (binary-heap-pop-* hp) (binary-heap-push! hp item))
255 ;; but it is more efficient.
256 (define (binary-heap-swap-min! hp item)
257 (let1 storage (~ hp'storage)
258 (when (binary-heap-empty? hp) (error "binary heap is empty:" hp))
259 (rlet1 r (~ storage (Ix 1))
260 (set! (~ storage (Ix 1)) item)
261 (let1 n (binary-heap-num-entries hp)
262 (when (> n 1)
263 (bh-trickle-down storage (~ hp'<:) (~ hp'>:) 1 (+ n 1)))))))
264
265 (define (binary-heap-swap-max! hp item)
266 (let ([storage (~ hp'storage)]
267 [nelts (binary-heap-num-entries hp)])
268 (define (store-and-adjust index)
269 (let1 a (~ storage (Ix 1))
270 (set! (~ storage (Ix index)) item)
271 (when ((~ hp'>:) a item)
272 (swap! storage 1 index))
273 (bh-trickle-down storage (~ hp'<:) (~ hp'>:) index (+ nelts 1))))
274 (case nelts
275 [(0) (error "binary heap is empty:" hp)]
276 [(1) (rlet1 r (~ storage (Ix 1))
277 (set! (~ storage (Ix 1)) item))]
278 [(2) (rlet1 r (~ storage (Ix 2))
279 (let1 a (~ storage (Ix 1))
280 (set! (~ storage (Ix 2)) item)
281 (when ((~ hp'>:) a item)
282 (swap! storage 1 2))))]
283 [else
284 (let ([a (~ storage (Ix 2))]
285 [b (~ storage (Ix 3))])
286 (if ((~ hp'>:) a b)
287 (begin (store-and-adjust 2) a)
288 (begin (store-and-adjust 3) b)))])))
289
290 ;; not exactly heap operations, but useful...
291
292 ;; Up to 0.9.10, we have (binary-heap-find <heap> <pred>) but that doesn't
293 ;; align with other *-find procedures. In 0.9.11 we change it to
294 ;; (binary-heap-find <pred> <heap> :optional <failure>), while supporting
295 ;; old API as well.
296 (define (binary-heap-find pred hp :optional (failure (^[] #f)))
297 (if (is-a? pred <binary-heap>)
298 (binary-heap-find hp pred failure) ; backward compatibility
299 (or (and-let* ([storage (~ hp'storage)]
300 [i (find-index (^i (pred (~ storage i)))
301 (liota (binary-heap-num-entries hp)))])
302 ;; NB: This i is 0-base, so we don't need Ix.
303 (~ storage i))
304 (failure))))
305
306 (define (binary-heap-remove! hp pred)
307 (let1 storage (~ hp'storage)
308
309 (define (finish-up next)
310 (unless (= next (~ hp'next-leaf)) ;; some keys are removed
311 (bh-heapify! storage (~ hp'<:) (~ hp'>:) (- next 1))
312 (do ([i next (+ i 1)]
313 [lim (~ hp'next-leaf)])
314 [(>= i lim)]
315 (set! (~ hp'storage (Ix i)) *filler*))
316 (set! (~ hp'next-leaf) next))
317 hp)
318
319 (let loop ([i 1] [next (~ hp'next-leaf)])
320 (if (>= i next)
321 (finish-up next)
322 (if (pred (~ storage (Ix i)))
323 (if (= (+ i 1) next)
324 (finish-up i) ; this is the last item
325 (begin
326 (swap! storage i (- next 1))
327 (loop i (- next 1))))
328 (loop (+ i 1) next))))))
329
330 (define (binary-heap-delete! hp item)
331 (let ([cmp (~ hp'comparator)]
332 [key (~ hp'key)])
333 (binary-heap-remove! hp (^e (=? cmp (key item) (key e))))))
334
335 ;; Internal procedures
336 (define-inline (min-node? index) (odd? (integer-length index)))
337
338 (define (binary-heap-check hp)
339 (unless (>= (~ hp'next-leaf) 1)
340 (error "next-leaf index is less than 1"))
341 (let rec ((i 1))
342 (let ([kids (take-while (cute < <> (~ hp'next-leaf)) (iota 2 (* i 2)))]
343 [gkids (take-while (cute < <> (~ hp'next-leaf)) (iota 4 (* i 4)))]
344 [cmp (if (min-node? i) (~ hp'<:) (~ hp'>:))])
345 (unless (every (^k (cmp (~ hp'storage(Ix i)) (~ hp'storage(Ix k)))) kids)
346 (errorf "parent-kid relation violated: ~a-node[~a]=~s, kids[~a]=~s"
347 (if (min-node? i) 'min 'max)
348 i (~ hp'storage (Ix i)) kids
349 (map (^k (~ hp'storage (Ix k))) kids)))
350 (unless (every (^k (cmp (~ hp'storage(Ix i)) (~ hp'storage(Ix k)))) gkids)
351 (errorf "grandparent-grandkid relation violated: ~a-node[~a]=~s, grandkids[~a]=~s"
352 (if (min-node? i) 'min 'max)
353 i (~ hp'storage (Ix i)) gkids
354 (map (^k (~ hp'storage (Ix k))) gkids)))
355 (for-each rec kids)
356 #t)))
357
358 ;; index
359 ;; 1 : min(2,3)
360 ;; 2,3 : max(4,5) and max(6,7)
361 ;; 4-7 : min(8,9) ... min(14,15)
362 ;; 8-15: max(16,17) ... max(30,31)
363 ;; etc.
364 ;; if (integer-length i) is odd, we have min node
365 ;; else we have max node
366
367 ;; called with index > 1
368 (define (bh-bubble-up storage <: >: index)
369
370 (define (bubble-up-rec >< index)
371 (when (> index 3)
372 (let1 grandparent-index (ash index -2)
373 (unless (>< (~ storage (Ix grandparent-index)) (~ storage (Ix index)))
374 (swap! storage grandparent-index index)
375 (bubble-up-rec >< grandparent-index)))))
376
377 (let1 parent-index (ash index -1)
378 (if (min-node? parent-index)
379 (if (<: (~ storage (Ix parent-index)) (~ storage (Ix index)))
380 (bubble-up-rec >: index)
381 (begin
382 (swap! storage parent-index index)
383 (bubble-up-rec <: parent-index)))
384 (if (>: (~ storage (Ix parent-index)) (~ storage (Ix index)))
385 (bubble-up-rec <: index)
386 (begin
387 (swap! storage parent-index index)
388 (bubble-up-rec >: parent-index))))))
389
390 (define (bh-heapify! storage <: >: size)
391 (do ([i 2 (+ i 1)])
392 [(>= i (+ 1 size))]
393 (when (is-a? storage <sparse-vector-base>)
394 (unless (sparse-vector-exists? storage (Ix i))
395 (errorf "can't heapify a sparse vector with a hole (at index ~s): ~s"
396 (Ix i) storage)))
397 (bh-bubble-up storage <: >: i)))
398
399 (define (bh-trickle-down storage <: >: index size)
400
401 (define-syntax getval (syntax-rules () [(getval i) (~ storage (Ix i))]))
402 (define-syntax in-bound? (syntax-rules () [(in-bound? i) (< i size)]))
403
404 ;; We need to check up to 2 kids and 4 grandkids. This returns appropriate
405 ;; index for n in 0..5; that is, n=0,1 for kids, n=2,3,4,5 for grandkids.
406 (define (descendant n index)
407 (if (< n 2)
408 (+ (ash index 1) n)
409 (+ (ash index 2) (- n 2))))
410
411 ;; Among self, children and grandchildren, find an index that has
412 ;; the minimum or maximum value.
413 ;; NB: This can be witten more cleanly by making the list of kids index
414 ;; and folding over it; but we want to avoid allocation in it, for this
415 ;; will be called log(n) times in average for every deletion.
416 (define (find-extreme >< index)
417 (let loop ([minval (getval index)]
418 [minidx index]
419 [n 0])
420 (if (> n 5)
421 minidx
422 (let1 i (descendant n index)
423 (if (not (in-bound? i))
424 minidx
425 (let1 v (getval i)
426 (if (>< v minval)
427 (loop v i (+ n 1))
428 (loop minval minidx (+ n 1)))))))))
429
430 (define (trickle-down-rec >< index)
431 (let1 pick (find-extreme >< index)
432 (unless (= pick index)
433 (swap! storage pick index)
434 (when (>= pick (ash index 2)) ; grandchild
435 (unless (>< (getval pick) (getval (ash pick -1)))
436 (swap! storage (ash pick -1) pick))
437 (trickle-down-rec >< pick)))))
438
439 (trickle-down-rec (if (min-node? index) <: >:) index))