Debian Codegraph @

%3a67/compare.scm

raw
1 ; Copyright (c) 2005 Sebastian Egner and Jens Axel S{\o}gaard.
2 ;
3 ; Permission is hereby granted, free of charge, to any person obtaining
4 ; a copy of this software and associated documentation files (the
5 ; ``Software''), to deal in the Software without restriction, including
6 ; without limitation the rights to use, copy, modify, merge, publish,
7 ; distribute, sublicense, and/or sell copies of the Software, and to
8 ; permit persons to whom the Software is furnished to do so, subject to
9 ; the following conditions:
10 ;
11 ; The above copyright notice and this permission notice shall be
12 ; included in all copies or substantial portions of the Software.
13 ;
14 ; THE SOFTWARE IS PROVIDED ``AS IS'', WITHOUT WARRANTY OF ANY KIND,
15 ; EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
16 ; MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
17 ; NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
18 ; LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
19 ; OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
20 ; WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
21 ;
22 ; -----------------------------------------------------------------------
23 ;
24 ; Compare procedures SRFI (reference implementation)
25 ; [email protected], [email protected]
26 ; history of this file:
27 ; SE, 14-Oct-2004: first version
28 ; SE, 18-Oct-2004: 1st redesign: axioms for 'compare function'
29 ; SE, 29-Oct-2004: 2nd redesign: higher order reverse/map/refine/unite
30 ; SE, 2-Nov-2004: 3rd redesign: macros cond/refine-compare replace h.o.f's
31 ; SE, 10-Nov-2004: (im,re) replaced by (re,im) in complex-compare
32 ; SE, 11-Nov-2004: case-compare by case (not by cond); select-compare added
33 ; SE, 12-Jan-2005: pair-compare-cdr
34 ; SE, 15-Feb-2005: stricter typing for compare-<type>; pairwise-not=?
35 ; SE, 16-Feb-2005: case-compare -> if-compare -> if3; <? </<? chain<? etc.
36 ; JS, 24-Feb-2005: selection-compare added
37 ; SE, 25-Feb-2005: selection-compare -> kth-largest modified; if<? etc.
38 ; JS, 28-Feb-2005: kth-largest modified - is "stable" now
39 ; SE, 28-Feb-2005: simplified pairwise-not=?/kth-largest; min/max debugged
40 ; SE, 07-Apr-2005: compare-based type checks made explicit
41 ; SE, 18-Apr-2005: added (rel? compare) and eq?-test
42 ; SE, 16-May-2005: naming convention changed; compare-by< etc. optional x y
43
44 ; =============================================================================
45
46 ; Reference Implementation
47 ; ========================
48 ;
49 ; in R5RS (including hygienic macros)
50 ; + SRFI-16 (case-lambda)
51 ; + SRFI-23 (error)
52 ; + SRFI-27 (random-integer)
53
54 ; Implementation remarks:
55 ; * In general, the emphasis of this implementation is on correctness
56 ; and portability, not on efficiency.
57 ; * Variable arity procedures are expressed in terms of case-lambda
58 ; in the hope that this will produce efficient code for the case
59 ; where the arity is statically known at the call site.
60 ; * In procedures that are required to type-check their arguments,
61 ; we use (compare x x) for executing extra checks. This relies on
62 ; the assumption that eq? is used to catch this case quickly.
63 ; * Care has been taken to reference comparison procedures of R5RS
64 ; only at the time the operations here are being defined. This
65 ; makes it possible to redefine these operations, if need be.
66 ; * For the sake of efficiency, some inlining has been done by hand.
67 ; This is mainly expressed by macros producing defines.
68 ; * Identifiers of the form compare:<something> are private.
69 ;
70 ; Hints for low-level implementation:
71 ; * The basis of this SRFI are the atomic compare procedures,
72 ; i.e. boolean-compare, char-compare, etc. and the conditionals
73 ; if3, if=?, if<? etc., and default-compare. These should make
74 ; optimal use of the available type information.
75 ; * For the sake of speed, the reference implementation does not
76 ; use a LET to save the comparison value c for the ERROR call.
77 ; This can be fixed in a low-level implementation at no cost.
78 ; * Type-checks based on (compare x x) are made explicit by the
79 ; expression (compare:check result compare x ...).
80 ; * Eq? should can used to speed up built-in compare procedures,
81 ; but it can only be used after type-checking at least one of
82 ; the arguments.
83
84 (define (compare:checked result compare . args)
85 (for-each (lambda (x) (compare x x)) args)
86 result)
87
88
89 ; 3-sided conditional
90
91 (define-syntax if3
92 (syntax-rules ()
93 ((if3 c less equal greater)
94 (case c
95 ((-1) less)
96 (( 0) equal)
97 (( 1) greater)
98 (else (error "comparison value not in {-1,0,1}"))))))
99
100
101 ; 2-sided conditionals for comparisons
102
103 (define-syntax compare:if-rel?
104 (syntax-rules ()
105 ((compare:if-rel? c-cases a-cases c consequence)
106 (compare:if-rel? c-cases a-cases c consequence (if #f #f)))
107 ((compare:if-rel? c-cases a-cases c consequence alternate)
108 (case c
109 (c-cases consequence)
110 (a-cases alternate)
111 (else (error "comparison value not in {-1,0,1}"))))))
112
113 (define-syntax if=?
114 (syntax-rules ()
115 ((if=? arg ...)
116 (compare:if-rel? (0) (-1 1) arg ...))))
117
118 (define-syntax if<?
119 (syntax-rules ()
120 ((if<? arg ...)
121 (compare:if-rel? (-1) (0 1) arg ...))))
122
123 (define-syntax if>?
124 (syntax-rules ()
125 ((if>? arg ...)
126 (compare:if-rel? (1) (-1 0) arg ...))))
127
128 (define-syntax if<=?
129 (syntax-rules ()
130 ((if<=? arg ...)
131 (compare:if-rel? (-1 0) (1) arg ...))))
132
133 (define-syntax if>=?
134 (syntax-rules ()
135 ((if>=? arg ...)
136 (compare:if-rel? (0 1) (-1) arg ...))))
137
138 (define-syntax if-not=?
139 (syntax-rules ()
140 ((if-not=? arg ...)
141 (compare:if-rel? (-1 1) (0) arg ...))))
142
143
144 ; predicates from compare procedures
145
146 (define-syntax compare:define-rel?
147 (syntax-rules ()
148 ((compare:define-rel? rel? if-rel?)
149 (define rel?
150 (case-lambda
151 (() (lambda (x y) (if-rel? (default-compare x y) #t #f)))
152 ((compare) (lambda (x y) (if-rel? (compare x y) #t #f)))
153 ((x y) (if-rel? (default-compare x y) #t #f))
154 ((compare x y)
155 (if (procedure? compare)
156 (if-rel? (compare x y) #t #f)
157 (error "not a procedure (Did you mean rel/rel??): " compare))))))))
158
159 (compare:define-rel? =? if=?)
160 (compare:define-rel? <? if<?)
161 (compare:define-rel? >? if>?)
162 (compare:define-rel? <=? if<=?)
163 (compare:define-rel? >=? if>=?)
164 (compare:define-rel? not=? if-not=?)
165
166
167 ; chains of length 3
168
169 (define-syntax compare:define-rel1/rel2?
170 (syntax-rules ()
171 ((compare:define-rel1/rel2? rel1/rel2? if-rel1? if-rel2?)
172 (define rel1/rel2?
173 (case-lambda
174 (()
175 (lambda (x y z)
176 (if-rel1? (default-compare x y)
177 (if-rel2? (default-compare y z) #t #f)
178 (compare:checked #f default-compare z))))
179 ((compare)
180 (lambda (x y z)
181 (if-rel1? (compare x y)
182 (if-rel2? (compare y z) #t #f)
183 (compare:checked #f compare z))))
184 ((x y z)
185 (if-rel1? (default-compare x y)
186 (if-rel2? (default-compare y z) #t #f)
187 (compare:checked #f default-compare z)))
188 ((compare x y z)
189 (if-rel1? (compare x y)
190 (if-rel2? (compare y z) #t #f)
191 (compare:checked #f compare z))))))))
192
193 (compare:define-rel1/rel2? </<? if<? if<?)
194 (compare:define-rel1/rel2? </<=? if<? if<=?)
195 (compare:define-rel1/rel2? <=/<? if<=? if<?)
196 (compare:define-rel1/rel2? <=/<=? if<=? if<=?)
197 (compare:define-rel1/rel2? >/>? if>? if>?)
198 (compare:define-rel1/rel2? >/>=? if>? if>=?)
199 (compare:define-rel1/rel2? >=/>? if>=? if>?)
200 (compare:define-rel1/rel2? >=/>=? if>=? if>=?)
201
202
203 ; chains of arbitrary length
204
205 (define-syntax compare:define-chain-rel?
206 (syntax-rules ()
207 ((compare:define-chain-rel? chain-rel? if-rel?)
208 (define chain-rel?
209 (case-lambda
210 ((compare)
211 #t)
212 ((compare x1)
213 (compare:checked #t compare x1))
214 ((compare x1 x2)
215 (if-rel? (compare x1 x2) #t #f))
216 ((compare x1 x2 x3)
217 (if-rel? (compare x1 x2)
218 (if-rel? (compare x2 x3) #t #f)
219 (compare:checked #f compare x3)))
220 ((compare x1 x2 . x3+)
221 (if-rel? (compare x1 x2)
222 (let chain? ((head x2) (tail x3+))
223 (if (null? tail)
224 #t
225 (if-rel? (compare head (car tail))
226 (chain? (car tail) (cdr tail))
227 (apply compare:checked #f
228 compare (cdr tail)))))
229 (apply compare:checked #f compare x3+))))))))
230
231 (compare:define-chain-rel? chain=? if=?)
232 (compare:define-chain-rel? chain<? if<?)
233 (compare:define-chain-rel? chain>? if>?)
234 (compare:define-chain-rel? chain<=? if<=?)
235 (compare:define-chain-rel? chain>=? if>=?)
236
237
238 ; pairwise inequality
239
240 (define pairwise-not=?
241 (let ((= =) (<= <=))
242 (case-lambda
243 ((compare)
244 #t)
245 ((compare x1)
246 (compare:checked #t compare x1))
247 ((compare x1 x2)
248 (if-not=? (compare x1 x2) #t #f))
249 ((compare x1 x2 x3)
250 (if-not=? (compare x1 x2)
251 (if-not=? (compare x2 x3)
252 (if-not=? (compare x1 x3) #t #f)
253 #f)
254 (compare:checked #f compare x3)))
255 ((compare . x1+)
256 (let unequal? ((x x1+) (n (length x1+)) (unchecked? #t))
257 (if (< n 2)
258 (if (and unchecked? (= n 1))
259 (compare:checked #t compare (car x))
260 #t)
261 (let* ((i-pivot (random-integer n))
262 (x-pivot (list-ref x i-pivot)))
263 (let split ((i 0) (x x) (x< '()) (x> '()))
264 (if (null? x)
265 (and (unequal? x< (length x<) #f)
266 (unequal? x> (length x>) #f))
267 (if (= i i-pivot)
268 (split (+ i 1) (cdr x) x< x>)
269 (if3 (compare (car x) x-pivot)
270 (split (+ i 1) (cdr x) (cons (car x) x<) x>)
271 (if unchecked?
272 (apply compare:checked #f compare (cdr x))
273 #f)
274 (split (+ i 1) (cdr x) x< (cons (car x) x>)))))))))))))
275
276
277 ; min/max
278
279 (define min-compare
280 (case-lambda
281 ((compare x1)
282 (compare:checked x1 compare x1))
283 ((compare x1 x2)
284 (if<=? (compare x1 x2) x1 x2))
285 ((compare x1 x2 x3)
286 (if<=? (compare x1 x2)
287 (if<=? (compare x1 x3) x1 x3)
288 (if<=? (compare x2 x3) x2 x3)))
289 ((compare x1 x2 x3 x4)
290 (if<=? (compare x1 x2)
291 (if<=? (compare x1 x3)
292 (if<=? (compare x1 x4) x1 x4)
293 (if<=? (compare x3 x4) x3 x4))
294 (if<=? (compare x2 x3)
295 (if<=? (compare x2 x4) x2 x4)
296 (if<=? (compare x3 x4) x3 x4))))
297 ((compare x1 x2 . x3+)
298 (let min ((xmin (if<=? (compare x1 x2) x1 x2)) (xs x3+))
299 (if (null? xs)
300 xmin
301 (min (if<=? (compare xmin (car xs)) xmin (car xs))
302 (cdr xs)))))))
303
304 (define max-compare
305 (case-lambda
306 ((compare x1)
307 (compare:checked x1 compare x1))
308 ((compare x1 x2)
309 (if>=? (compare x1 x2) x1 x2))
310 ((compare x1 x2 x3)
311 (if>=? (compare x1 x2)
312 (if>=? (compare x1 x3) x1 x3)
313 (if>=? (compare x2 x3) x2 x3)))
314 ((compare x1 x2 x3 x4)
315 (if>=? (compare x1 x2)
316 (if>=? (compare x1 x3)
317 (if>=? (compare x1 x4) x1 x4)
318 (if>=? (compare x3 x4) x3 x4))
319 (if>=? (compare x2 x3)
320 (if>=? (compare x2 x4) x2 x4)
321 (if>=? (compare x3 x4) x3 x4))))
322 ((compare x1 x2 . x3+)
323 (let max ((xmax (if>=? (compare x1 x2) x1 x2)) (xs x3+))
324 (if (null? xs)
325 xmax
326 (max (if>=? (compare xmax (car xs)) xmax (car xs))
327 (cdr xs)))))))
328
329
330 ; kth-largest
331
332 (define kth-largest
333 (let ((= =) (< <))
334 (case-lambda
335 ((compare k x0)
336 (case (modulo k 1)
337 ((0) (compare:checked x0 compare x0))
338 (else (error "bad index" k))))
339 ((compare k x0 x1)
340 (case (modulo k 2)
341 ((0) (if<=? (compare x0 x1) x0 x1))
342 ((1) (if<=? (compare x0 x1) x1 x0))
343 (else (error "bad index" k))))
344 ((compare k x0 x1 x2)
345 (case (modulo k 3)
346 ((0) (if<=? (compare x0 x1)
347 (if<=? (compare x0 x2) x0 x2)
348 (if<=? (compare x1 x2) x1 x2)))
349 ((1) (if3 (compare x0 x1)
350 (if<=? (compare x1 x2)
351 x1
352 (if<=? (compare x0 x2) x2 x0))
353 (if<=? (compare x0 x2) x1 x0)
354 (if<=? (compare x0 x2)
355 x0
356 (if<=? (compare x1 x2) x2 x1))))
357 ((2) (if<=? (compare x0 x1)
358 (if<=? (compare x1 x2) x2 x1)
359 (if<=? (compare x0 x2) x2 x0)))
360 (else (error "bad index" k))))
361 ((compare k x0 . x1+) ; |x1+| >= 1
362 (if (not (and (integer? k) (exact? k)))
363 (error "bad index" k))
364 (let ((n (+ 1 (length x1+))))
365 (let kth ((k (modulo k n))
366 (n n) ; = |x|
367 (rev #t) ; are x<, x=, x> reversed?
368 (x (cons x0 x1+)))
369 (let ((pivot (list-ref x (random-integer n))))
370 (let split ((x x) (x< '()) (n< 0) (x= '()) (n= 0) (x> '()) (n> 0))
371 (if (null? x)
372 (cond
373 ((< k n<)
374 (kth k n< (not rev) x<))
375 ((< k (+ n< n=))
376 (if rev
377 (list-ref x= (- (- n= 1) (- k n<)))
378 (list-ref x= (- k n<))))
379 (else
380 (kth (- k (+ n< n=)) n> (not rev) x>)))
381 (if3 (compare (car x) pivot)
382 (split (cdr x) (cons (car x) x<) (+ n< 1) x= n= x> n>)
383 (split (cdr x) x< n< (cons (car x) x=) (+ n= 1) x> n>)
384 (split (cdr x) x< n< x= n= (cons (car x) x>) (+ n> 1))))))))))))
385
386
387 ; compare functions from predicates
388
389 (define compare-by<
390 (case-lambda
391 ((lt) (lambda (x y) (if (lt x y) -1 (if (lt y x) 1 0))))
392 ((lt x y) (if (lt x y) -1 (if (lt y x) 1 0)))))
393
394 (define compare-by>
395 (case-lambda
396 ((gt) (lambda (x y) (if (gt x y) 1 (if (gt y x) -1 0))))
397 ((gt x y) (if (gt x y) 1 (if (gt y x) -1 0)))))
398
399 (define compare-by<=
400 (case-lambda
401 ((le) (lambda (x y) (if (le x y) (if (le y x) 0 -1) 1)))
402 ((le x y) (if (le x y) (if (le y x) 0 -1) 1))))
403
404 (define compare-by>=
405 (case-lambda
406 ((ge) (lambda (x y) (if (ge x y) (if (ge y x) 0 1) -1)))
407 ((ge x y) (if (ge x y) (if (ge y x) 0 1) -1))))
408
409 (define compare-by=/<
410 (case-lambda
411 ((eq lt) (lambda (x y) (if (eq x y) 0 (if (lt x y) -1 1))))
412 ((eq lt x y) (if (eq x y) 0 (if (lt x y) -1 1)))))
413
414 (define compare-by=/>
415 (case-lambda
416 ((eq gt) (lambda (x y) (if (eq x y) 0 (if (gt x y) 1 -1))))
417 ((eq gt x y) (if (eq x y) 0 (if (gt x y) 1 -1)))))
418
419 ; refine and extend construction
420
421 (define-syntax refine-compare
422 (syntax-rules ()
423 ((refine-compare)
424 0)
425 ((refine-compare c1)
426 c1)
427 ((refine-compare c1 c2 cs ...)
428 (if3 c1 -1 (refine-compare c2 cs ...) 1))))
429
430 (define-syntax select-compare
431 (syntax-rules (else)
432 ((select-compare x y clause ...)
433 (let ((x-val x) (y-val y))
434 (select-compare (x-val y-val clause ...))))
435 ; used internally: (select-compare (x y clause ...))
436 ((select-compare (x y))
437 0)
438 ((select-compare (x y (else c ...)))
439 (refine-compare c ...))
440 ((select-compare (x y (t? c ...) clause ...))
441 (let ((t?-val t?))
442 (let ((tx (t?-val x)) (ty (t?-val y)))
443 (if tx
444 (if ty (refine-compare c ...) -1)
445 (if ty 1 (select-compare (x y clause ...)))))))))
446
447 (define-syntax cond-compare
448 (syntax-rules (else)
449 ((cond-compare)
450 0)
451 ((cond-compare (else cs ...))
452 (refine-compare cs ...))
453 ((cond-compare ((tx ty) cs ...) clause ...)
454 (let ((tx-val tx) (ty-val ty))
455 (if tx-val
456 (if ty-val (refine-compare cs ...) -1)
457 (if ty-val 1 (cond-compare clause ...)))))))
458
459
460 ; R5RS atomic types
461
462 (define-syntax compare:type-check
463 (syntax-rules ()
464 ((compare:type-check type? type-name x)
465 (if (not (type? x))
466 (error (string-append "not " type-name ":") x)))
467 ((compare:type-check type? type-name x y)
468 (begin (compare:type-check type? type-name x)
469 (compare:type-check type? type-name y)))))
470
471 (define-syntax compare:define-by=/<
472 (syntax-rules ()
473 ((compare:define-by=/< compare = < type? type-name)
474 (define compare
475 (let ((= =) (< <))
476 (lambda (x y)
477 (if (type? x)
478 (if (eq? x y)
479 0
480 (if (type? y)
481 (if (= x y) 0 (if (< x y) -1 1))
482 (error (string-append "not " type-name ":") y)))
483 (error (string-append "not " type-name ":") x))))))))
484
485 (define (boolean-compare x y)
486 (compare:type-check boolean? "boolean" x y)
487 (if x (if y 0 1) (if y -1 0)))
488
489 (compare:define-by=/< char-compare char=? char<? char? "char")
490
491 (compare:define-by=/< char-compare-ci char-ci=? char-ci<? char? "char")
492
493 (compare:define-by=/< string-compare string=? string<? string? "string")
494
495 (compare:define-by=/< string-compare-ci string-ci=? string-ci<? string? "string")
496
497 (define (symbol-compare x y)
498 (compare:type-check symbol? "symbol" x y)
499 (string-compare (symbol->string x) (symbol->string y)))
500
501 (compare:define-by=/< integer-compare = < integer? "integer")
502
503 (compare:define-by=/< rational-compare = < rational? "rational")
504
505 (compare:define-by=/< real-compare = < real? "real")
506
507 (define (complex-compare x y)
508 (compare:type-check complex? "complex" x y)
509 (if (and (real? x) (real? y))
510 (real-compare x y)
511 (refine-compare (real-compare (real-part x) (real-part y))
512 (real-compare (imag-part x) (imag-part y)))))
513
514 (define (number-compare x y)
515 (compare:type-check number? "number" x y)
516 (complex-compare x y))
517
518
519 ; R5RS compound data structures: dotted pair, list, vector
520
521 (define (pair-compare-car compare)
522 (lambda (x y)
523 (compare (car x) (car y))))
524
525 (define (pair-compare-cdr compare)
526 (lambda (x y)
527 (compare (cdr x) (cdr y))))
528
529 (define pair-compare
530 (case-lambda
531
532 ; dotted pair
533 ((pair-compare-car pair-compare-cdr x y)
534 (refine-compare (pair-compare-car (car x) (car y))
535 (pair-compare-cdr (cdr x) (cdr y))))
536
537 ; possibly improper lists
538 ((compare x y)
539 (cond-compare
540 (((null? x) (null? y)) 0)
541 (((pair? x) (pair? y)) (compare (car x) (car y))
542 (pair-compare compare (cdr x) (cdr y)))
543 (else (compare x y))))
544
545 ; for convenience
546 ((x y)
547 (pair-compare default-compare x y))))
548
549 (define list-compare
550 (case-lambda
551 ((compare x y empty? head tail)
552 (cond-compare
553 (((empty? x) (empty? y)) 0)
554 (else (compare (head x) (head y))
555 (list-compare compare (tail x) (tail y) empty? head tail))))
556
557 ; for convenience
558 (( x y empty? head tail)
559 (list-compare default-compare x y empty? head tail))
560 ((compare x y )
561 (list-compare compare x y null? car cdr))
562 (( x y )
563 (list-compare default-compare x y null? car cdr))))
564
565 (define list-compare-as-vector
566 (case-lambda
567 ((compare x y empty? head tail)
568 (refine-compare
569 (let compare-length ((x x) (y y))
570 (cond-compare
571 (((empty? x) (empty? y)) 0)
572 (else (compare-length (tail x) (tail y)))))
573 (list-compare compare x y empty? head tail)))
574
575 ; for convenience
576 (( x y empty? head tail)
577 (list-compare-as-vector default-compare x y empty? head tail))
578 ((compare x y )
579 (list-compare-as-vector compare x y null? car cdr))
580 (( x y )
581 (list-compare-as-vector default-compare x y null? car cdr))))
582
583 (define vector-compare
584 (let ((= =))
585 (case-lambda
586 ((compare x y size ref)
587 (let ((n (size x)) (m (size y)))
588 (refine-compare
589 (integer-compare n m)
590 (let compare-rest ((i 0)) ; compare x[i..n-1] y[i..n-1]
591 (if (= i n)
592 0
593 (refine-compare (compare (ref x i) (ref y i))
594 (compare-rest (+ i 1))))))))
595
596 ; for convenience
597 (( x y size ref)
598 (vector-compare default-compare x y size ref))
599 ((compare x y )
600 (vector-compare compare x y vector-length vector-ref))
601 (( x y )
602 (vector-compare default-compare x y vector-length vector-ref)))))
603
604 (define vector-compare-as-list
605 (let ((= =))
606 (case-lambda
607 ((compare x y size ref)
608 (let ((nx (size x)) (ny (size y)))
609 (let ((n (min nx ny)))
610 (let compare-rest ((i 0)) ; compare x[i..n-1] y[i..n-1]
611 (if (= i n)
612 (integer-compare nx ny)
613 (refine-compare (compare (ref x i) (ref y i))
614 (compare-rest (+ i 1))))))))
615
616 ; for convenience
617 (( x y size ref)
618 (vector-compare-as-list default-compare x y size ref))
619 ((compare x y )
620 (vector-compare-as-list compare x y vector-length vector-ref))
621 (( x y )
622 (vector-compare-as-list default-compare x y vector-length vector-ref)))))
623
624
625 ; default compare
626
627 (define (default-compare x y)
628 (select-compare
629 x y
630 (null? 0)
631 (pair? (default-compare (car x) (car y))
632 (default-compare (cdr x) (cdr y)))
633 (boolean? (boolean-compare x y))
634 (char? (char-compare x y))
635 (string? (string-compare x y))
636 (symbol? (symbol-compare x y))
637 (number? (number-compare x y))
638 (vector? (vector-compare default-compare x y))
639 (else (error "unrecognized type in default-compare" x y))))
640
641 ; Note that we pass default-compare to compare-{pair,vector} explictly.
642 ; This makes sure recursion proceeds with this default-compare, which
643 ; need not be the one in the lexical scope of compare-{pair,vector}.
644
645
646 ; debug compare
647
648 (define (debug-compare c)
649
650 (define (checked-value c x y)
651 (let ((c-xy (c x y)))
652 (if (or (eqv? c-xy -1) (eqv? c-xy 0) (eqv? c-xy 1))
653 c-xy
654 (error "compare value not in {-1,0,1}" c-xy (list c x y)))))
655
656 (define (random-boolean)
657 (zero? (random-integer 2)))
658
659 (define q ; (u v w) such that u <= v, v <= w, and not u <= w
660 '#(
661 ;x < y x = y x > y [x < z]
662 0 0 0 ; y < z
663 0 (z y x) (z y x) ; y = z
664 0 (z y x) (z y x) ; y > z
665
666 ;x < y x = y x > y [x = z]
667 (y z x) (z x y) 0 ; y < z
668 (y z x) 0 (x z y) ; y = z
669 0 (y x z) (x z y) ; y > z
670
671 ;x < y x = y x > y [x > z]
672 (x y z) (x y z) 0 ; y < z
673 (x y z) (x y z) 0 ; y = z
674 0 0 0 ; y > z
675 ))
676
677 (let ((z? #f) (z #f)) ; stored element from previous call
678 (lambda (x y)
679 (let ((c-xx (checked-value c x x))
680 (c-yy (checked-value c y y))
681 (c-xy (checked-value c x y))
682 (c-yx (checked-value c y x)))
683 (if (not (zero? c-xx))
684 (error "compare error: not reflexive" c x))
685 (if (not (zero? c-yy))
686 (error "compare error: not reflexive" c y))
687 (if (not (zero? (+ c-xy c-yx)))
688 (error "compare error: not anti-symmetric" c x y))
689 (if z?
690 (let ((c-xz (checked-value c x z))
691 (c-zx (checked-value c z x))
692 (c-yz (checked-value c y z))
693 (c-zy (checked-value c z y)))
694 (if (not (zero? (+ c-xz c-zx)))
695 (error "compare error: not anti-symmetric" c x z))
696 (if (not (zero? (+ c-yz c-zy)))
697 (error "compare error: not anti-symmetric" c y z))
698 (let ((ijk (vector-ref q (+ c-xy (* 3 c-yz) (* 9 c-xz) 13))))
699 (if (list? ijk)
700 (apply error
701 "compare error: not transitive"
702 c
703 (map (lambda (i) (case i ((x) x) ((y) y) ((z) z)))
704 ijk)))))
705 (set! z? #t))
706 (set! z (if (random-boolean) x y)) ; randomized testing
707 c-xy))))