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