Debian Codegraph @

lib/scheme/sort.scm

raw
1 ;;;
2 ;;; scheme.sort - Sort library (R7RS Red)
3 ;;;
4 ;;; Copyright (c) 2017-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 ;; Originally SRFI-132
35 (define-module scheme.sort
36 (use gauche.sequence)
37 (use gauche.generator)
38 (use srfi.27) ; we use random selection in vector-select
39 (use scheme.vector)
40 (export list-sorted? vector-sorted?
41 list-sort list-stable-sort
42 list-sort! list-stable-sort!
43 vector-sort vector-stable-sort
44 vector-sort! vector-stable-sort!
45 list-merge list-merge!
46 vector-merge vector-merge!
47 list-delete-neighbor-dups
48 list-delete-neighbor-dups!
49 vector-delete-neighbor-dups
50 vector-delete-neighbor-dups!
51 vector-find-median
52 vector-find-median!
53 vector-select!
54 vector-separate!
55 ))
56 (select-module scheme.sort)
57
58 (define (list-sort < lis) (assume-type lis <list>) (sort lis <))
59 (define (list-sort! < lis) (assume-type lis <list>) (sort! lis <))
60 (define (list-stable-sort < lis) (assume-type lis <list>) (stable-sort lis <))
61 (define (list-stable-sort! < lis) (assume-type lis <list>) (stable-sort! lis <))
62 (define (list-sorted? < lis) (assume-type lis <list>) (sorted? lis <))
63 (define (list-merge < lis1 lis2) (merge lis1 lis2 <))
64 (define (list-merge! < lis1 lis2) (merge! lis1 lis2 <))
65
66 ;; NB: We could get range-restricted linear-update version more efficient.
67
68 (define-inline (%check-range v start end)
69 (assume-type start <integer>)
70 (assume-type end <integer>)
71 (unless (<= 0 start end (vector-length v))
72 (errorf "Start/end arguments must be nonnegative exact integers, \
73 and must be (<= 0 start end (- (vector-length v) 1)). \
74 We got (start end): (~s ~s)" start end)))
75
76 (define (%vector-sorter %sort!)
77 (^[< v :optional (s 0) (e (vector-length v))]
78 (assume-type v <vector>)
79 (%check-range v s e)
80 (%sort! (subseq v s e) <)))
81
82 (define (%vector-sorter! %sort!)
83 (^[< v :optional (s 0) (e (vector-length v))]
84 (assume-type v <vector>)
85 (%check-range v s e)
86 (if (and (= s 0) (= e (vector-length v)))
87 (%sort! v <)
88 (set! (subseq v s e) (%sort! (subseq v s e) <)))
89 (undefined)))
90
91 (define vector-sort (%vector-sorter sort!))
92 (define vector-sort! (%vector-sorter! sort!))
93 (define vector-stable-sort (%vector-sorter stable-sort!))
94 (define vector-stable-sort! (%vector-sorter! stable-sort!))
95
96 (define (%maybe-subseq v s e)
97 (if (and (= s 0) (= e (vector-length v)))
98 v
99 (subseq v s e)))
100
101 (define (vector-sorted? < v :optional (s 0) (e (vector-length v)))
102 (assume-type v <vector>)
103 (%check-range v s e)
104 (sorted? (%maybe-subseq v s e) <))
105
106 (define (%vector-merge! < dst start v1 v2)
107 (let ([len1 (vector-length v1)]
108 [len2 (vector-length v2)])
109 (cond [(zero? len1) (vector-copy! dst start v2)]
110 [(zero? len2) (vector-copy! dst start v1)]
111 [else (let loop ([e1 (vector-ref v1 0)]
112 [e2 (vector-ref v2 0)]
113 [i1 1]
114 [i2 1]
115 [d start])
116 (cond [(< e2 e1)
117 (vector-set! dst d e2)
118 (if (= i2 len2)
119 (vector-copy! dst (+ d 1) v1 (- i1 1))
120 (loop e1 (vector-ref v2 i2) i1 (+ i2 1) (+ d 1)))]
121 [else
122 (vector-set! dst d e1)
123 (if (= i1 len1)
124 (vector-copy! dst (+ d 1) v2 (- i2 1))
125 (loop (vector-ref v1 i1) e2 (+ i1 1) i2 (+ d 1)))]))]
126 )))
127
128 (define (vector-merge < v1 v2 :optional (s1 0) (e1 (vector-length v1))
129 (s2 0) (e2 (vector-length v2)))
130 (assume-type v1 <vector>)
131 (assume-type v2 <vector>)
132 (%check-range v1 s1 e1)
133 (%check-range v2 s2 e2)
134 (rlet1 vr (make-vector (+ (- e1 s1) (- e2 s2)))
135 (%vector-merge! < vr 0 (%maybe-subseq v1 s1 e1) (%maybe-subseq v2 s2 e2))))
136
137 (define (vector-merge! < vr v1 v2 :optional (sr 0)
138 (s1 0) (e1 (vector-length v1))
139 (s2 0) (e2 (vector-length v2)))
140 (assume-type vr <vector>)
141 (assume-type v1 <vector>)
142 (assume-type v2 <vector>)
143 (%check-range v1 s1 e1)
144 (%check-range v2 s2 e2)
145 (unless (>= (vector-length vr) (+ sr (- e1 s1) (- e2 s2)))
146 (errorf "Destination vector is too short (length=~s, required=~s)"
147 (vector-length vr) (+ sr (- e1 s1) (- e2 s2))))
148 (%vector-merge! < vr sr (%maybe-subseq v1 s1 e1) (%maybe-subseq v2 s2 e2))
149 (undefined))
150
151 ;; duplicate elimination
152
153 (define (list-delete-neighbor-dups = lis)
154 (assume-type lis <list>)
155 (delete-neighbor-dups lis :test =))
156 (define (list-delete-neighbor-dups! = lis)
157 (assume-type lis <list>)
158 (delete-neighbor-dups-squeeze! lis :test =))
159 (define (vector-delete-neighbor-dups = vec :optional (start 0) (end #f))
160 (assume-type vec <vector>)
161 (delete-neighbor-dups vec :test = :start start :end end))
162 (define (vector-delete-neighbor-dups! = vec :optional (start 0) (end #f))
163 (assume-type vec <vector>)
164 (delete-neighbor-dups! vec :test = :start start :end end))
165
166 ;;;
167 ;;; Median finding / k-th largest element
168 ;;;
169
170 ;; Returns k-th smallest element in v.
171 (define (vector-select! elt< v k :optional (start 0) (end (vector-length v)))
172 (assume-type v <vector>)
173 (assume-type k <integer>)
174 (%check-range v start end)
175 (assume (<= 0 k (- end start 1)))
176 (vector-select-1! elt< v k start end))
177
178 ;; Make initial k element of v contain k-smallest elements, sorted.
179 ;; we can't use vector-select-1! directly, for partition-in-place! excludes
180 ;; pivot values.
181 (define (vector-separate! elt< v k :optional (start 0) (end (vector-length v)))
182 (assume-type v <vector>)
183 (assume-type k <integer>)
184 (%check-range v start end)
185 (assume (<= 0 k (- end start 1)))
186 (partition-in-place-full! elt< v k start end))
187
188 (define (vector-find-median elt< v knil :optional (mean arithmetic-mean))
189 (assume-type v <vector>)
190 (case (vector-length v)
191 [(0) knil]
192 [(1) (vector-ref v 0)]
193 [(2) (mean (vector-ref v 0) (vector-ref v 1))]
194 [else
195 => (^[len]
196 (if (odd? len)
197 (vector-select-1! elt< (vector-copy v) (ash len -1) 0 len)
198 (receive (a b) (vector-select-2! elt< (vector-copy v)
199 (- (ash len -1) 1) 0 len)
200 (mean a b))))]))
201
202 ;; srfi text reads we must leave v sorted. without that condition,
203 ;; we could directly use vector-select-[12]!.
204 (define (vector-find-median! elt< v knil :optional (mean arithmetic-mean))
205 (assume-type v <vector>)
206 (vector-sort! elt< v)
207 (let1 len (vector-length v)
208 (cond [(zero? len) knil]
209 [(odd? len) (vector-ref v (quotient len 2))]
210 [else (mean (vector-ref v (- (quotient len 2) 1))
211 (vector-ref v (quotient len 2)))])))
212
213 ;; Default mean procedure
214 (define (arithmetic-mean a b) (/ (+ a b) 2))
215
216 ;; We use our own random-source to avoid unexpected interference
217 (define *random-source*
218 (rlet1 r (make-random-source)
219 (random-source-randomize! r)))
220 (define %random-integer
221 (random-source-make-integers *random-source*))
222
223 ;; Rearrange elements of VEC between start and end, so that all elements
224 ;; smaller than the pivot are gathered at the front, followed
225 ;; by elements greater than the pivot.
226 ;;
227 ;; #(G S P G S G G P S S) ; S:smaller, P:pivot, G:greater
228 ;;
229 ;; to:
230 ;; a b
231 ;; #(S S S S G G G G X X) ; X: don't care
232 ;;
233 ;; Returns a and b.
234 ;;
235 ;; In the implementation, we use typical two-index scan, where i moves from
236 ;; start to right, while j moves from the end to left. Elements
237 ;; equal to pivot are removed, which is done by shrinking the region
238 ;; with moving end to left.
239 ;;
240 ;; Invariances:
241 ;; vec[start] .. vec[i-1] are always smaller than the pivot
242 ;; vec[k] .. vec[end-1] are always greater than the pivot
243 ;; start <= i <= k <= end
244 ;; vec[end-1] is not equal to pivot (we make it so at the beginning)
245 ;;
246 ;; i j E
247 ;; #(S G S P G S P G S P G) ; forward
248 ;; i j E
249 ;; #(S G S P G S P G S P G) ; backward
250 ;; i j E
251 ;; #(S G S P G S P G S P G) ; shrink v[j] = v[E-1]
252 ;; i j E
253 ;; #(S G S P G S P G S G _) ; backward
254 ;; i j E
255 ;; #(S G S P G S P G S G _) ; swap v[i] <=> v[j]
256 ;; i j E
257 ;; #(S S S P G S P G G G _) ; forward
258 ;; i j E
259 ;; #(S S S P G S P G G G _) ; forward
260 ;; i j E
261 ;; #(S S S P G S P G G G _) ; forward
262 ;; i j E
263 ;; #(S S S P G S P G G G _) ; shrink v[i] = v[E-1]
264 ;; i j E
265 ;; #(S S S G G S P G G _ _) ; backward
266 ;; i j E
267 ;; #(S S S G G S P G G _ _) ; backward
268 ;; i j E
269 ;; #(S S S G G S P G G _ _) ; shrink v[j] = v[E-1]
270 ;; i j E
271 ;; #(S S S G G S G G _ _ _) ; backward
272 ;; i j E
273 ;; #(S S S G G S G G _ _ _) ; swap v[i] <=> v[j]
274 ;; i j E
275 ;; #(S S S S G G G G _ _ _) ; forward
276 ;; i j E
277 ;; #(S S S S G G G G _ _ _) ; backward
278 ;; ij E
279 ;; #(S S S S G G G G _ _ _) ; end
280
281 (define (partition-in-place! elt< pivot vec start end)
282 (define (forward i j end)
283 (cond [(> i j) (values i end)]
284 [(elt< (vector-ref vec i) pivot) (forward (+ i 1) j end)]
285 [(elt< pivot (vector-ref vec i)) (backward i j end)]
286 [else ;shrink
287 (vector-set! vec i (vector-ref vec (- end 1))) ; now v[i] > pivot
288 (if (= j (- end 1))
289 (adjust i (- j 1))
290 (backward i j (- end 1)))]))
291 (define (backward i j end) ; v[i] > pivot
292 (cond [(>= i j) (values i end)]
293 [(elt< (vector-ref vec j) pivot)
294 (vector-swap! vec i j)
295 (forward (+ i 1) (- j 1) end)]
296 [(elt< pivot (vector-ref vec j)) (backward i (- j 1) end)]
297 [else ; shrink
298 (vector-set! vec j (vector-ref vec (- end 1)))
299 (backward i j (- end 1))]))
300 (define (adjust i end-1) ; keep invariance of v[end-1] > pivot. v[i] > pivot
301 (cond [(> i end-1) (values i i)]
302 [(elt< pivot (vector-ref vec end-1))
303 (backward i end-1 (+ end-1 1))]
304 [(elt< (vector-ref vec end-1) pivot)
305 (vector-swap! vec i end-1)
306 (forward i end-1 (+ end-1 1))]
307 [else (adjust i (- end-1 1))]))
308 ;; We first scan from the end to satisfy the condition that v[end-1] > pivot.
309 (let init ([m (- end 1)])
310 (cond [(> start m) (values start start)]
311 [(elt< pivot (vector-ref vec m))
312 (forward start m (+ m 1))]
313 [(elt< (vector-ref vec m) pivot)
314 ;; We should find at least one element greater than pivot.
315 ;; Scanning vector back, keeping the invariance that
316 ;; elements not equal to the pivot is contained between [start,m]
317 (let init2 ([m m]
318 [n (- m 1)])
319 (cond [(> start n) (values (+ m 1) (+ m 1))]
320 [(elt< pivot (vector-ref vec n))
321 (vector-swap! vec n m)
322 (forward start m (+ m 1))]
323 [(elt< (vector-ref vec n) pivot)
324 (init2 m (- n 1))]
325 [else
326 (vector-set! vec n (vector-ref vec m))
327 (init2 (- m 1) (- n 1))]))]
328 [else (init (- m 1))])))
329
330 (define (vector-select-1! elt< vec k start end)
331 (let loop ([k k] [start start] [end end])
332 (define size (- end start))
333 (case size
334 [(1) (vector-ref vec start)] ; k must be 0
335 [(2) (let ([a (vector-ref vec start)]
336 [b (vector-ref vec (+ start 1))])
337 (if (elt< a b)
338 (if (zero? k) a b)
339 (if (zero? k) b a)))]
340 [else
341 (let* ([ip (%random-integer size)]
342 [pivot (vector-ref vec (+ ip start))])
343 (receive (i j) (partition-in-place! elt< pivot vec start end)
344 (let1 nsmaller (- i start)
345 (if (< k nsmaller)
346 (loop k start i)
347 (let1 nsmaller-or-equal (+ nsmaller (- end j))
348 (if (< k nsmaller-or-equal)
349 pivot
350 (loop (- k nsmaller-or-equal) i j)))))))])))
351
352 ;; precondition: (- end start) >= 2
353 (define (vector-select-2! elt< vec k start end)
354 (let loop ([k k] [start start] [end end])
355 (define size (- end start))
356 (if (= size 2)
357 (let ([a (vector-ref vec start)]
358 [b (vector-ref vec (+ start 1))])
359 (if (elt< a b) (values a b) (values b a)))
360 (let* ([ip (%random-integer size)]
361 [pivot (vector-ref vec (+ ip start))])
362 (receive (i j) (partition-in-place! elt< pivot vec start end)
363 (let1 nsmaller (- i start)
364 (cond [(= (+ k 1) nsmaller)
365 (values (vector-select-1! elt< vec k start i) pivot)]
366 [(< k nsmaller) (loop k start i)]
367 [else
368 (let1 nsmaller-or-equal (+ nsmaller (- end j))
369 (cond [(= (+ k 1) nsmaller-or-equal)
370 (values pivot (vector-select-1! elt< vec 0 i j))]
371 [(< k nsmaller-or-equal)
372 (values pivot pivot)]
373 [else (loop (- k nsmaller-or-equal) i j)]))])))))))
374
375 ;; Used by vector-separate!.
376 (define (partition-in-place-full! elt< vec k start end)
377 (let loop ([k k] [start start] [end end])
378 (define size (- end start))
379 (case size
380 [(1)]
381 [(2) (when (and (>= k 1)
382 (elt< (vector-ref vec (+ start 1))
383 (vector-ref vec start)))
384 (vector-swap! vec start (+ start 1)))]
385 [else
386 (let* ([ip (%random-integer size)]
387 [pivot (vector-ref vec (+ ip start))])
388 (receive (i j) (partition-in-place! elt< pivot vec start end)
389 (let1 nsmaller (- i start)
390 (if (< k nsmaller)
391 (begin
392 ;; recover pivot elements at the end.
393 (dotimes (t (- end j)) (vector-set! vec (+ j t) pivot))
394 (loop k start i))
395 (let1 nsmaller-or-equal (+ nsmaller (- end j))
396 ;; recover pivot elements between smaller and greater elts.
397 (dotimes (t (- j i))
398 (vector-set! vec (- end t 1) (vector-ref vec (- j t 1))))
399 (dotimes (t (- end j))
400 (vector-set! vec (+ i t) pivot))
401 (when (> k nsmaller-or-equal)
402 (loop (- k nsmaller-or-equal)
403 nsmaller-or-equal
404 end)))))))])))