| 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)))) |