Debian Codegraph @

src/libcmp.scm

raw
1 ;;;
2 ;;; libcmp.scm - compare and sort
3 ;;;
4 ;;; Copyright (c) 2000-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 (select-module gauche.internal)
35 (inline-stub
36 (.include "gauche/priv/configP.h"))
37
38 ;;;
39 ;;; Comparator (a la SRFI-114/128)
40 ;;;
41
42 ;; Our built-in comparator is compatible to *both* SRFI-114 and SRFI-128;
43 ;; we automatically "fill-in" the difference (comparison-proc vs ordering-pred)
44 ;; as needed. The only incompatibility is the constructor---both srfi
45 ;; uses the same name but the mearning of arguments differ. We provide
46 ;; SRFI-114 constructor under different name (make-comparator/compare).
47 ;;
48 ;; Because of this on-demand filling, the internal accessors are a
49 ;; bit complicated; it is justified by the simple api with low overhead
50 ;; (we don't calculate until needed).
51 ;;
52 ;; Note: Some builtin comparator stuff are in libomega.scm, for they
53 ;; depends on other builtin mechanisms.
54
55 (select-module gauche.internal)
56 (define (default-type-test _) #t)
57
58 (define-cproc %make-comparator (type-test equality-test
59 comparison-proc ; or order-proc
60 hash name
61 any-type::<boolean> use-cmp::<boolean>
62 srfi-128::<boolean>)
63 (let* ([flags::u_long (logior (?: srfi-128 SCM_COMPARATOR_SRFI_128 0)
64 (?: (SCM_EQ comparison-proc SCM_FALSE)
65 SCM_COMPARATOR_NO_ORDER 0)
66 (?: (SCM_EQ hash SCM_FALSE)
67 SCM_COMPARATOR_NO_HASH 0)
68 (?: any-type SCM_COMPARATOR_ANY_TYPE 0)
69 (?: use-cmp SCM_COMPARATOR_USE_COMPARISON 0))])
70 (return
71 (Scm_MakeComparator type-test equality-test comparison-proc hash
72 name flags))))
73
74 ;; Argument checkers for constructors.
75 ;; We use <bottom> for applicability check except type-test, since
76 ;; those procs are only required to handle objects that passes type-test.
77 (define (ensure-type-test type-test)
78 (cond [(eq? type-test #t) default-type-test]
79 [(applicable? type-test <top>) type-test]
80 [else (error "make-comparator needs a one-argument procedure or #t as type-test, but got:" type-test)]))
81 (define (ensure-equality-test equality-test comparison-proc)
82 (cond [(eq? equality-test #t)
83 (if (applicable? comparison-proc <bottom> <bottom>)
84 (^[a b] (= (comparison-proc a b) 0))
85 (error "make-comparator needs a procedure as comparison-proc if equality-test is #t, but got:" comparison-proc))]
86 [(applicable? equality-test <bottom> <bottom>) equality-test]
87 [else (error "make-comparator needs a procedure or #t as equality-test, but got:" equality-test)]))
88 (define (ensure-hash-func hash)
89 (cond [(or (eq? hash #f) (applicable? hash <bottom>)) hash]
90 [else (error "make-comparator needs a procedure or #f as hash, but got:" hash)]))
91
92 ;; API - SRFI-114 constructor
93 (define-in-module gauche (make-comparator/compare type-test equality-test
94 comparison-proc hash
95 :optional (name #f))
96 (let1 type (ensure-type-test type-test)
97 (%make-comparator type
98 (ensure-equality-test equality-test comparison-proc)
99 (if (or (eq? comparison-proc #f)
100 (applicable? comparison-proc <bottom> <bottom>))
101 comparison-proc
102 (error "make-comparator/compare needs a procedure \
103 or #f as comparison-proc, but got:"
104 comparison-proc))
105 (ensure-hash-func hash)
106 name
107 (eq? type default-type-test)
108 (eq? equality-test #t)
109 #f)))
110
111 ;; API - SRFI-128 constructor
112 (define-in-module gauche (make-comparator type-test equality-test
113 ordering-pred hash
114 :optional (name #f))
115 (let1 type (ensure-type-test type-test)
116 (%make-comparator type
117 (ensure-equality-test equality-test #f)
118 (if (or (eq? ordering-pred #f)
119 (applicable? ordering-pred <bottom> <bottom>))
120 ordering-pred
121 (error "make-comparator needs a procedure or #f as \
122 ordering-pred, but got:" ordering-pred))
123 (ensure-hash-func hash)
124 name
125 (eq? type default-type-test)
126 (eq? equality-test #t)
127 #t)))
128
129 (select-module gauche)
130 (define-cproc comparator? (obj) ::<boolean> SCM_COMPARATORP)
131 (define-cproc comparator-flavor (c::<comparator>) :constant
132 (if (logand (-> c flags) SCM_COMPARATOR_SRFI_128)
133 (return 'ordering)
134 (return 'comparison)))
135
136 (define-cproc comparator-ordered? (c::<comparator>) ::<boolean>
137 (return (not (logand (-> c flags) SCM_COMPARATOR_NO_ORDER))))
138 (define-cproc comparator-hashable? (c::<comparator>) ::<boolean>
139 (return (not (logand (-> c flags) SCM_COMPARATOR_NO_HASH))))
140 (define-cproc comparator-type-test-predicate (c::<comparator>) :constant
141 (return (-> c typeFn)))
142 (define-cproc comparator-equality-predicate (c::<comparator>) :constant
143 (return (-> c eqFn)))
144
145 ;; comparator-comparison-procedure
146 ;; For SRFI-128 comparator, we auto-generate comparison procedure.
147 (define-cproc comparator-comparison-procedure (c::<comparator>) :constant
148 Scm_ComparatorComparisonProcedure)
149
150 (inline-stub
151 (define-cfn fallback-compare (argv::ScmObj* _::int data::void*) :static
152 (let* ([c::ScmComparator* (SCM_COMPARATOR data)]
153 [a (aref argv 0)]
154 [b (aref argv 1)])
155 (unless (logand (-> c flags) SCM_COMPARATOR_SRFI_128) (goto err))
156 (when (SCM_FALSEP (-> c orderFn)) (goto err))
157 (let1/cps r (Scm_VMApply2 (-> c orderFn) a b)
158 [c a b]
159 (if (not (SCM_FALSEP r))
160 (return (SCM_MAKE_INT -1))
161 (let1/cps r (Scm_VMApply2 (-> (SCM_COMPARATOR c) eqFn) a b)
162 []
163 (if (not (SCM_FALSEP r))
164 (return (SCM_MAKE_INT 0))
165 (return (SCM_MAKE_INT 1))))))
166 (label err)
167 (Scm_Error "can't compare objects by %S: %S vs %S" (SCM_OBJ c) a b)
168 (return SCM_UNDEFINED))) ;dummy
169
170 (define-cfn Scm_ComparatorComparisonProcedure (c::ScmComparator*)
171 (let* ([cmp (-> c compareFn)])
172 (when (SCM_FALSEP cmp)
173 (set! cmp (Scm_MakeSubr fallback-compare (cast (void*) c) 2 0
174 '(fallback-compare a b)))
175 (set! (-> c compareFn) cmp))
176 (return cmp)))
177 )
178
179 ;; comparator-ordering-predicate
180 ;; For SRFI-114 comparator, we auto-generate ordering predicate.
181 (define-cproc comparator-ordering-predicate (c::<comparator>) :constant
182 Scm_ComparatorOrderingPredicate)
183
184 (inline-stub
185 (define-cfn fallback-order (argv::ScmObj* _::int data::void*) :static
186 (let* ([c::ScmComparator* (SCM_COMPARATOR data)]
187 [a (aref argv 0)]
188 [b (aref argv 1)])
189 (when (logand (-> c flags) SCM_COMPARATOR_SRFI_128) (goto err))
190 (when (SCM_FALSEP (-> c compareFn)) (goto err))
191 (let1/cps r (Scm_VMApply2 (-> c compareFn) a b)
192 []
193 (return (SCM_MAKE_BOOL (< (SCM_INT_VALUE r) 0))))
194 (label err)
195 (Scm_Error "can't order objects by %S: %S vs %S" (SCM_OBJ c) a b)
196 (return SCM_UNDEFINED))) ;dummy
197
198 (define-cfn Scm_ComparatorOrderingPredicate (c::ScmComparator*)
199 (let* ([ord (-> c orderFn)])
200 (when (SCM_FALSEP ord)
201 (set! ord (Scm_MakeSubr fallback-order (cast (void*) c) 2 0
202 '(fallback-order a b)))
203 (set! (-> c orderFn) ord))
204 (return ord)))
205 )
206
207 ;;
208 (define-cproc comparator-hash-function (c::<comparator>) :constant
209 Scm_ComparatorHashFunction)
210
211 (inline-stub
212 (define-cfn fallback-hash (_::ScmObj* _::int data::void*) :static
213 (let* ([c::ScmComparator* (SCM_COMPARATOR data)])
214 (Scm_Error "%S doesn't have hash function" (SCM_OBJ c))
215 (return SCM_UNDEFINED))) ;dummy
216
217 (define-cfn Scm_ComparatorHashFunction (c::ScmComparator*)
218 (let* ([h (-> c hashFn)])
219 (when (SCM_FALSEP h)
220 (set! h (Scm_MakeSubr fallback-hash (cast (void*) c) 1 0
221 '(fallback-has obj)))
222 (set! (-> c hashFn) h))
223 (return h)))
224 )
225
226 ;;;
227 ;;; Comparator comparison operators
228 ;;; They can be written more concisely in Scheme, but we don't want
229 ;;; them to be too slow compared to bare procedures (e.g. '=', '<' etc)
230 ;;; so we fiddle with C.
231 ;;;
232
233 ;; Common routine
234 ;; TODO: Ideally, we want to use trampoline to call typeFn so that
235 ;; we won't recurse to VM loop.
236 (inline-stub
237 (define-cfn cmpr-typecheck (c::ScmComparator* a b rest) ::void :static
238 (when (SCM_FALSEP (Scm_ApplyRec1 (-> c typeFn) a))
239 (Scm_Error "Object is not suitable for a comparator %S: %S" c a))
240 (when (SCM_FALSEP (Scm_ApplyRec1 (-> c typeFn) b))
241 (Scm_Error "Object is not suitable for a comparator %S: %S" c b))
242 (for-each
243 (lambda (z)
244 (unless (Scm_ApplyRec1 (-> c typeFn) z)
245 (Scm_Error "Object is not suitable for a comparator %S: %S" c z)))
246 rest)))
247
248 ;;; =?
249 (inline-stub
250 (define-cfn cmpr-eq (c::ScmComparator* a b more) :static
251 (if (SCM_PAIRP more)
252 (let1/cps r (Scm_VMApply2 (-> c eqFn) a b)
253 [c::ScmComparator* b more]
254 (if (SCM_FALSEP r)
255 (return r)
256 (return (cmpr-eq c b (SCM_CAR more) (SCM_CDR more)))))
257 (return (Scm_VMApply2 (-> c eqFn) a b))))
258
259 (define-cproc =? (c::<comparator> a b :rest more)
260 (cmpr-typecheck c a b more)
261 (return (cmpr-eq c a b more))))
262
263 ;;; <?
264 (inline-stub
265 (define-cfn cmpr-lt-128 (c::ScmComparator* a b more) :static
266 (if (SCM_PAIRP more)
267 (let1/cps r (Scm_VMApply2 (-> c orderFn) a b)
268 [c::ScmComparator* b more]
269 (if (SCM_FALSEP r)
270 (return r)
271 (return (cmpr-lt-128 c b (SCM_CAR more) (SCM_CDR more)))))
272 (return (Scm_VMApply2 (-> c orderFn) a b))))
273
274 (define-cfn cmpr-lt-114 (c::ScmComparator* a b more) :static
275 (if (SCM_PAIRP more)
276 (let1/cps r (Scm_VMApply2 (-> c compareFn) a b)
277 [c::ScmComparator* b more]
278 (if (< (SCM_INT_VALUE r) 0)
279 (return (cmpr-lt-114 c b (SCM_CAR more) (SCM_CDR more)))
280 (return SCM_FALSE)))
281 (let1/cps r (Scm_VMApply2 (-> c compareFn) a b)
282 []
283 (return (SCM_MAKE_BOOL (< (SCM_INT_VALUE r) 0))))))
284
285 (define-cproc <? (c::<comparator> a b :rest more)
286 (cmpr-typecheck c a b more)
287 (cond [(logand (-> c flags) SCM_COMPARATOR_SRFI_128)
288 (when (SCM_FALSEP (-> c orderFn))
289 (Scm_Error "%S doesn't have ordering predicate" (SCM_OBJ c)))
290 (return (cmpr-lt-128 c a b more))]
291 [else
292 (when (SCM_FALSEP (-> c compareFn))
293 (Scm_Error "%S doesn't have comparison procedure" (SCM_OBJ c)))
294 (return (cmpr-lt-114 c a b more))])))
295
296 ;;; <=?
297 (inline-stub
298 (define-cfn cmpr-le-128 (c::ScmComparator* a b more) :static
299 (if (SCM_PAIRP more)
300 (let1/cps r (Scm_VMApply2 (-> c orderFn) a b)
301 [c::ScmComparator* a b more]
302 (if (SCM_FALSEP r)
303 (let1/cps r (Scm_VMApply2 (-> c eqFn) a b)
304 [c::ScmComparator* b more]
305 (if (SCM_FALSEP r)
306 (return r)
307 (return (cmpr-le-128 c b (SCM_CAR more) (SCM_CDR more)))))
308 (return (cmpr-le-128 c b (SCM_CAR more) (SCM_CDR more)))))
309 (let1/cps r (Scm_VMApply2 (-> c orderFn) a b)
310 [c::ScmComparator* a b]
311 (if (SCM_FALSEP r)
312 (return (Scm_VMApply2 (-> c eqFn) a b))
313 (return SCM_TRUE)))))
314
315 (define-cfn cmpr-le-114 (c::ScmComparator* a b more) :static
316 (if (SCM_PAIRP more)
317 (let1/cps r (Scm_VMApply2 (-> c compareFn) a b)
318 [c::ScmComparator* b more]
319 (if (<= (SCM_INT_VALUE r) 0)
320 (return (cmpr-le-114 c b (SCM_CAR more) (SCM_CDR more)))
321 (return SCM_FALSE)))
322 (let1/cps r (Scm_VMApply2 (-> c compareFn) a b)
323 []
324 (return (SCM_MAKE_BOOL (<= (SCM_INT_VALUE r) 0))))))
325
326 (define-cproc <=? (c::<comparator> a b :rest more)
327 (cmpr-typecheck c a b more)
328 (cond [(logand (-> c flags) SCM_COMPARATOR_SRFI_128)
329 (when (SCM_FALSEP (-> c orderFn))
330 (Scm_Error "%S doesn't have ordering predicate" (SCM_OBJ c)))
331 (return (cmpr-le-128 c a b more))]
332 [else
333 (when (SCM_FALSEP (-> c compareFn))
334 (Scm_Error "%S doesn't have comparison procedure" (SCM_OBJ c)))
335 (return (cmpr-le-114 c a b more))])))
336
337 ;;; >?
338 (inline-stub
339 (define-cfn cmpr-gt-128 (c::ScmComparator* a b more) :static
340 (if (SCM_PAIRP more)
341 (let1/cps r (Scm_VMApply2 (-> c orderFn) a b)
342 [c::ScmComparator* a b more]
343 (if (SCM_FALSEP r)
344 (let1/cps r (Scm_VMApply2 (-> c eqFn) a b)
345 [c::ScmComparator* b more]
346 (if (SCM_FALSEP r)
347 (return (cmpr-gt-128 c b (SCM_CAR more) (SCM_CDR more)))
348 (return SCM_FALSE)))
349 (return SCM_FALSE)))
350 (let1/cps r (Scm_VMApply2 (-> c orderFn) a b)
351 [c::ScmComparator* a b]
352 (if (SCM_FALSEP r)
353 (let1/cps r (Scm_VMApply2 (-> c eqFn) a b)
354 []
355 (return (SCM_MAKE_BOOL (SCM_FALSEP r))))
356 (return SCM_FALSE)))))
357
358 (define-cfn cmpr-gt-114 (c::ScmComparator* a b more) :static
359 (if (SCM_PAIRP more)
360 (let1/cps r (Scm_VMApply2 (-> c compareFn) a b)
361 [c::ScmComparator* b more]
362 (if (> (SCM_INT_VALUE r) 0)
363 (return (cmpr-gt-114 c b (SCM_CAR more) (SCM_CDR more)))
364 (return SCM_FALSE)))
365 (let1/cps r (Scm_VMApply2 (-> c compareFn) a b)
366 []
367 (return (SCM_MAKE_BOOL (> (SCM_INT_VALUE r) 0))))))
368
369 (define-cproc >? (c::<comparator> a b :rest more)
370 (cmpr-typecheck c a b more)
371 (cond [(logand (-> c flags) SCM_COMPARATOR_SRFI_128)
372 (when (SCM_FALSEP (-> c orderFn))
373 (Scm_Error "%S doesn't have ordering predicate" (SCM_OBJ c)))
374 (return (cmpr-gt-128 c a b more))]
375 [else
376 (when (SCM_FALSEP (-> c compareFn))
377 (Scm_Error "%S doesn't have comparison procedure" (SCM_OBJ c)))
378 (return (cmpr-gt-114 c a b more))])))
379
380 ;;; >=?
381 (inline-stub
382 (define-cfn cmpr-ge-128 (c::ScmComparator* a b more) :static
383 (if (SCM_PAIRP more)
384 (let1/cps r (Scm_VMApply2 (-> c orderFn) a b)
385 [c::ScmComparator* b more]
386 (if (SCM_FALSEP r)
387 (return (cmpr-ge-128 c b (SCM_CAR more) (SCM_CDR more)))
388 (return SCM_FALSE)))
389 (let1/cps r (Scm_VMApply2 (-> c orderFn) a b)
390 []
391 (return (SCM_MAKE_BOOL (SCM_FALSEP r))))))
392
393 (define-cfn cmpr-ge-114 (c::ScmComparator* a b more) :static
394 (if (SCM_PAIRP more)
395 (let1/cps r (Scm_VMApply2 (-> c compareFn) a b)
396 [c::ScmComparator* b more]
397 (if (>= (SCM_INT_VALUE r) 0)
398 (return (cmpr-ge-114 c b (SCM_CAR more) (SCM_CDR more)))
399 (return SCM_FALSE)))
400 (let1/cps r (Scm_VMApply2 (-> c compareFn) a b)
401 []
402 (return (SCM_MAKE_BOOL (>= (SCM_INT_VALUE r) 0))))))
403
404 (define-cproc >=? (c::<comparator> a b :rest more)
405 (cmpr-typecheck c a b more)
406 (cond [(logand (-> c flags) SCM_COMPARATOR_SRFI_128)
407 (when (SCM_FALSEP (-> c orderFn))
408 (Scm_Error "%S doesn't have ordering predicate" (SCM_OBJ c)))
409 (return (cmpr-ge-128 c a b more))]
410 [else
411 (when (SCM_FALSEP (-> c compareFn))
412 (Scm_Error "%S doesn't have comparison procedure" (SCM_OBJ c)))
413 (return (cmpr-ge-114 c a b more))])))
414
415 (select-module gauche.internal)
416 ;; Used by (object-equal? <comparator> <comparator>), defined in libomega.scm
417 (define-cproc comparator-equality-use-comparison? (c::<comparator>) ::<boolean>
418 (return (logand (-> c flags) SCM_COMPARATOR_USE_COMPARISON)))
419
420 ;; Expose as a class
421 (select-module gauche)
422 (inline-stub
423 (define-cclass <comparator>
424 "ScmComparator*" "Scm_ComparatorClass"
425 (c "SCM_CLASS_DEFAULT_CPL")
426 ((name :setter #f)
427 (type-test :c-name "typeFn" :setter #f)
428 (equality-test :c-name "eqFn" :setter #f)
429 (ordering :c-name "orderFn" :setter #f)
430 (comparison :c-name "compareFn" :setter #f)
431 (hash :c-name "hashFn" :setter #f))
432 (printer (let* ([c::ScmComparator* (SCM_COMPARATOR obj)])
433 (if (SCM_FALSEP (-> c name))
434 (Scm_Printf port "#<comparator %p>" c)
435 (Scm_Printf port "#<comparator %S>" (-> c name)))))
436 (comparer (begin
437 (unless equalp
438 (Scm_Error "%S and %S can't be ordered" x y))
439 (let* ([r (Scm_ApplyRec2 (SCM_OBJ (& Scm_GenericObjectEqualP))
440 x y)])
441 (return (?: (SCM_FALSEP r) 1 0)))))
442 ))
443
444 ;; We implement these in C for performance.
445 ;; TODO: We might be able to do shortcut in comparator-equal? by recognizing
446 ;; the equality predicate to be eq? or eqv?.
447 (define-cproc comparator-test-type (c::<comparator> obj) :constant
448 (if (logand (-> c flags) SCM_COMPARATOR_ANY_TYPE)
449 (return SCM_TRUE)
450 (return (Scm_VMApply1 (-> c typeFn) obj))))
451
452 (define-cproc comparator-check-type (c::<comparator> obj) :constant
453 (if (logand (-> c flags) SCM_COMPARATOR_ANY_TYPE)
454 (return SCM_TRUE)
455 (let1/cps result (Scm_VMApply1 (-> c typeFn) obj)
456 [c::ScmComparator* obj]
457 (when (SCM_FALSEP result)
458 (Scm_Error "Comparator %S cannot accept object %S" c obj))
459 (return SCM_TRUE))))
460
461 ;; TODO: We can avoid using Scm_ComparatorHashFunction and
462 ;; Scm_ComparatorComparisonProcedure that may call Scm_ApplyRec.
463
464 (define-cproc comparator-hash (c::<comparator> x) :constant
465 (if (logand (-> c flags) SCM_COMPARATOR_ANY_TYPE)
466 (return (Scm_VMApply1 (Scm_ComparatorHashFunction c) x))
467 (let1/cps result (Scm_VMApply1 (-> c typeFn) x)
468 [c::ScmComparator* x]
469 (when (SCM_FALSEP result)
470 (Scm_Error "Comparator %S cannot accept object %S" c x))
471 (return (Scm_VMApply1 (Scm_ComparatorHashFunction c) x)))))
472
473 (define-cproc comparator-compare (c::<comparator> a b) :constant
474 (if (logand (-> c flags) SCM_COMPARATOR_ANY_TYPE)
475 (return (Scm_VMApply2 (Scm_ComparatorComparisonProcedure c) a b))
476 (let1/cps r (Scm_VMApply1 (-> c typeFn) a)
477 [c::ScmComparator* a b]
478 (when (SCM_FALSEP r)
479 (Scm_Error "Comparator %S cannot accept object %S" c a))
480 (let1/cps r (Scm_VMApply1 (-> c typeFn) b)
481 [c::ScmComparator* a b]
482 (when (SCM_FALSEP r)
483 (Scm_Error "Comparator %S cannot accept object %S" c b))
484 (return (Scm_VMApply2 (Scm_ComparatorComparisonProcedure c) a b))))))
485
486 ;;;
487 ;;; Generic comparison
488 ;;;
489
490 (select-module gauche)
491 ;; returns -1, 0 or 1
492 (define-cproc compare (x y) ::<fixnum> Scm_Compare)
493
494 ;; eq-compare has two properties:
495 ;; Gives a total order to every Scheme object (within a single run of process)
496 ;; Returns 0 iff (eq? x y) => #t
497 (define-cproc eq-compare (x y) ::<fixnum>
498 (if (SCM_EQ x y)
499 (return 0)
500 (return (?: (< (SCM_WORD x) (SCM_WORD y)) -1 1))))
501
502 ;;;
503 ;;; Sorting
504 ;;;
505
506 (select-module gauche.internal)
507
508 (define-cproc %sort (seq)
509 (cond [(SCM_VECTORP seq)
510 (let* ([r (Scm_VectorCopy (SCM_VECTOR seq) 0 -1 SCM_UNDEFINED)])
511 (Scm_SortArray (SCM_VECTOR_ELEMENTS r) (SCM_VECTOR_SIZE r) '#f)
512 (return r))]
513 [(>= (Scm_Length seq) 0) (return (Scm_SortList seq '#f))]
514 [else (SCM_TYPE_ERROR seq "proper list or vector")
515 (return SCM_UNDEFINED)]))
516
517 (define-cproc %sort! (seq)
518 (cond [(SCM_VECTORP seq)
519 (Scm_SortArray (SCM_VECTOR_ELEMENTS seq) (SCM_VECTOR_SIZE seq) '#f)
520 (return seq)]
521 [(>= (Scm_Length seq) 0) (return (Scm_SortListX seq '#f))]
522 [else (SCM_TYPE_ERROR seq "proper list or vector")
523 (return SCM_UNDEFINED)]))
524
525 ;; internal macro
526 (define-syntax define-less?
527 (syntax-rules ()
528 [(_ less? cmp this)
529 (define less?
530 (cond [(comparator? cmp) (^[a b] (< (comparator-compare cmp a b) 0))]
531 [(not cmp) (^[a b] (< (compare a b) 0))]
532 [(applicable? cmp <bottom> <bottom>) cmp]
533 [else (errorf "~a requires a comparator or a procedure that \
534 takes two-arguments, but got: ~s" this cmp)]))]))
535
536 ;; sorted?, merge, merge!, stable-sort!, stable-sort are based on
537 ;; the public domain code by Richard A. O'Keefe, which in turn based
538 ;; on Prolog code by D.H.D.Warren. See lib/gauche/sort.orig.scm for
539 ;; the original code.
540
541 ;;; (sorted? sequence :optional less? key)
542
543 (define-in-module gauche (sorted? seq :optional (cmp #f) (key identity))
544 (define-less? less? cmp 'sorted?)
545 (cond
546 [(null? seq) #t]
547 [(vector? seq)
548 (let1 n (vector-length seq)
549 (if (<= n 1)
550 #t
551 (let loop ([i 1]
552 [last (key (vector-ref seq 0))])
553 (or (= i n)
554 (let1 next (key (vector-ref seq i))
555 (and (not (less? next last))
556 (loop (+ i 1) next)))))))]
557 [(pair? seq) ; avoid list? for scanning the entire list
558 (let loop ([last (key (car seq))] [rest (cdr seq)])
559 (or (null? rest)
560 (let1 next (key (car rest))
561 (and (not (less? next last))
562 (loop next (cdr rest))))))]
563 [(string? seq)
564 (if (<= (string-length seq) 1)
565 #t
566 (let* ([p (open-input-string seq)]
567 [last (key (read-char p))])
568 (let loop ([last last] [next (read-char p)])
569 (or (eof-object? next)
570 (let1 knext (key next)
571 (and (not (less? knext last))
572 (loop knext (read-char p))))))))]
573 [(is-a? seq <sequence>) (%generic-sorted? seq less? key)]
574 [else (error "sequence required, but got:" seq)]))
575
576 ;;; (merge a b less?)
577 ;;; takes two lists a and b such that (sorted? a less?) and (sorted? b less?)
578 ;;; and returns a new list in which the elements of a and b have been stably
579 ;;; interleaved so that (sorted? (merge a b less?) less?).
580 ;;; Note: this does _not_ accept vectors. See below.
581
582 (define-in-module gauche (merge a b :optional (cmp #f) (key identity))
583 (define-less? less? cmp 'merge)
584 (cond
585 [(null? a) b]
586 [(null? b) a]
587 [else (let loop ([x (car a)] [kx (key (car a))] [a (cdr a)]
588 [y (car b)] [ky (key (car b))] [b (cdr b)])
589 ;; The loop handles the merging of non-empty lists. It has
590 ;; been written this way to save testing and car/cdring.
591 (if (less? ky kx)
592 (if (null? b)
593 (cons y (cons x a))
594 (cons y (loop x kx a (car b) (key (car b)) (cdr b))))
595 ;; x <= y
596 (if (null? a)
597 (cons x (cons y b))
598 (cons x (loop (car a) (key (car a)) (cdr a) y ky b)))))]))
599
600 ;;; (merge! a b less?)
601 ;;; takes two sorted lists a and b and smashes their cdr fields to form a
602 ;;; single sorted list including the elements of both.
603 ;;; Note: this does _not_ accept vectors.
604
605 (define-in-module gauche (merge! a b :optional (cmp #f) (key identity))
606 (define-less? less? cmp 'merge!)
607 (define (loop r a kx b ky)
608 (if (less? ky kx)
609 (begin
610 (set-cdr! r b)
611 (if (null? (cdr b))
612 (set-cdr! b a)
613 (loop b a kx (cdr b) (key (cadr b)))))
614 (begin
615 (set-cdr! r a)
616 (if (null? (cdr a))
617 (set-cdr! a b)
618 (loop a (cdr a) (key (cadr a)) b ky)))))
619 (cond
620 [(null? a) b]
621 [(null? b) a]
622 [else (let ([kx (key (car a))]
623 [ky (key (car b))])
624 (if (less? ky kx)
625 (begin
626 (if (null? (cdr b))
627 (set-cdr! b a)
628 (loop b a kx (cdr b) (key (cadr b))))
629 b)
630 (begin
631 (if (null? (cdr a))
632 (set-cdr! a b)
633 (loop a (cdr a) (key (cadr a)) b ky))
634 a)))]))
635
636 ;;; (sort! sequence :optional less? key)
637 ;;; sorts the list or vector sequence destructively. It uses a version
638 ;;; of merge-sort invented, to the best of my knowledge, by David H. D.
639 ;;; Warren, and first used in the DEC-10 Prolog system. R. A. O'Keefe
640 ;;; adapted it to work destructively in Scheme.
641
642 (define-in-module gauche (sort! seq . args)
643 (if (and (or (pair? seq) (vector? seq)) (null? args))
644 (%sort! seq) ; use internal version
645 (apply stable-sort! seq args)))
646
647 (define-in-module gauche (stable-sort! seq :optional (cmp #f) (key identity))
648 (let1 sorted (%stable-sort! seq cmp key)
649 (if (and (pair? sorted) (not (eq? sorted seq)))
650 ;; %stable-sort! on a list may return a cell that's not the same
651 ;; cell as the head of input. We have to ensure we preserve the
652 ;; identity.
653 (let loop ([p sorted])
654 (if (eq? (cdr p) seq)
655 (let ([sorted-car (car sorted)]
656 [sorted-cdr (cdr sorted)]
657 [seq-car (car seq)]
658 [seq-cdr (cdr seq)])
659 (set! (car sorted) seq-car)
660 (set! (cdr sorted) seq-cdr)
661 (set! (car seq) sorted-car)
662 (if (eq? p sorted)
663 (set! (cdr seq) sorted)
664 (begin
665 (set! (cdr seq) sorted-cdr)
666 (set! (cdr p) sorted)))
667 seq)
668 (loop (cdr p))))
669 sorted)))
670
671 ;; Internal stable sorter. If key is identity we use merge sort
672 ;; straightforwardly. Otherwise, we extract keys first, sort
673 ;; by the key, and strip the keys.
674 ;; Note that if SEQ is a list, the returned cell doesn't need to
675 ;; be the same cell as the head of SEQ.
676 (define (%stable-sort! seq :optional (cmp #f) (key identity))
677 (define-less? less? cmp 'sort!)
678 (if (memq key `(,identity ,values))
679 ;; shortcut
680 (letrec ([step (^n (cond [(> n 2) (let* ([j (ash n -1)]
681 [a (step j)]
682 [k (- n j)]
683 [b (step k)])
684 (merge! a b less?))]
685 [(= n 2) (let ([x (car seq)]
686 [y (cadr seq)]
687 [p seq])
688 (set! seq (cddr seq))
689 (when (less? y x)
690 (set-car! p y)
691 (set-car! (cdr p) x))
692 (set-cdr! (cdr p) '())
693 p)]
694 [(= n 1) (let ([p seq])
695 (set! seq (cdr seq))
696 (set-cdr! p '())
697 p)]
698 [else '()]))])
699 (cond [(null? seq) seq]
700 [(pair? seq) (step (length seq))]
701 [(vector? seq)
702 (let ([n (vector-length seq)]
703 [vector seq])
704 (set! seq (vector->list seq))
705 (do ([p (step n) (cdr p)]
706 [i 0 (+ i 1)])
707 [(null? p) vector]
708 (vector-set! vector i (car p))))]
709 [(is-a? seq <sequence>) (%generic-sort! seq less?)]
710 [else (error "sequence required, but got:" seq)]))
711 ;; Avoid making intermediate structure, for the point of stable-sort!
712 ;; is to avoid allocation.
713 (letrec ([kless? (^[a b] (less? (cdr a) (cdr b)))])
714 (cond [(null? seq) seq]
715 [(pair? seq)
716 (do ([spine seq (cdr spine)])
717 [(null? spine)]
718 (set-car! spine (cons (car spine) (key (car spine)))))
719 (let1 spine (%stable-sort! seq kless?)
720 (do ([lis spine (cdr lis)])
721 [(null? lis)]
722 (set-car! lis (caar lis)))
723 spine)]
724 [(vector? seq)
725 (let1 len (vector-length seq)
726 (do ([i 0 (+ i 1)])
727 [(= i len)]
728 (vector-set! seq i (cons (vector-ref seq i)
729 (key (vector-ref seq i)))))
730 (do ([seq (%stable-sort! seq kless?)]
731 [i 0 (+ i 1)])
732 [(= i len)]
733 (vector-set! seq i (car (vector-ref seq i))))
734 seq)]
735 [(is-a? seq <sequence>) (%generic-sort! seq less? key)]
736 [else (error "sequence required, but got:" seq)]))))
737
738 ;;; (sort sequence less?)
739 ;;; sorts a vector or list non-destructively. It does this by sorting a
740 ;;; copy of the sequence.
741
742 (define-in-module gauche (sort seq . args)
743 (if (and (or (pair? seq) (vector? seq)) (null? args))
744 (%sort seq) ;; use internal version
745 (apply stable-sort seq args)))
746
747 (define-in-module gauche (stable-sort seq :optional (cmp #f) (key identity))
748 (define-less? less? cmp 'sort)
749 (if (memq key `(,identity ,values))
750 (cond [(null? seq) seq]
751 [(pair? seq) (%stable-sort! (list-copy seq) less?)]
752 [(vector? seq) (list->vector (sort! (vector->list seq) less?))]
753 [(is-a? seq <sequence>) (%generic-sort seq less?)]
754 [else (error "sequence required, but got:" seq)])
755 (cond [(null? seq) seq]
756 [(pair? seq) (%stable-sort! (list-copy seq) less? key)]
757 [(vector? seq) (%stable-sort! (vector-copy seq) less? key)]
758 [(is-a? seq <sequence>) (%generic-sort seq less? key)]
759 [else (error "sequence required, but got:" seq)])))
760
761 (select-module gauche)
762 ;; For the backward compatibility
763 (define (sort-by seq key :optional (cmp #f)) (sort seq cmp key))
764 (define stable-sort-by sort-by)
765 (define (sort-by! seq key :optional (cmp #f)) (sort! seq cmp key))
766 (define stable-sort-by! sort-by!)