Debian Codegraph @

test/sort.scm

raw
1 ;;;
2 ;;; Testing built-in sort functions
3 ;;;
4
5 (use gauche.test)
6 (test-start "sort procedures")
7
8 (test-section "loading and binding")
9
10 (use gauche.generic-sortutil)
11 (test-module 'gauche.generic-sortutil)
12
13 (test-section "sort")
14
15 (define-method integer>? ((x <integer>) (y <integer>))
16 (> x y))
17
18 (define-method boolean<? ((x <boolean>) (y <boolean>))
19 (< (compare x y) 0))
20
21 (test* "sorted?" #t (sorted? '(1 2 3 4 4 5)))
22 (test* "sorted?" #f (sorted? '(1 2 3 4 3 5)))
23 (test* "sorted? (less)" #t (sorted? '(5 4 3 3 2 1) >))
24 (test* "sorted? (less)" #f (sorted? '(5 4 3 1 2 1) >))
25 (test* "sorted? (less)" #t (sorted? '(5 4 3 3 2 1) integer>?))
26 (test* "sorted? (less)" #f (sorted? '(5 4 3 1 2 1) integer>?))
27 (test* "sorted? (cmpr)" #t (sorted? '(1 2 3 4 4 5) integer-comparator))
28 (test* "sorted? (cmpr)" #f (sorted? '(1 2 3 5 4 2) integer-comparator))
29 (test* "sorted? (key)" #t (sorted? '(1 3 1 2 4 2) boolean<? even?))
30 (test* "sorted? (key)" #f (sorted? '(1 3 1 2 1 3) boolean<? even?))
31 (test* "sorted? (key)" #t (sorted? '(1 3 1 2 4 2) boolean-comparator even?))
32 (test* "sorted? (key)" #f (sorted? '(1 3 1 2 1 3) boolean-comparator even?))
33
34 (test* "sort (base)" '() (sort '()))
35 (test* "sort (base)" '#() (sort '#()))
36 (test* "sort (base)" '"" (sort '""))
37
38 (define (sort-test name fn fn! xargs in exp)
39 (define (test1 kind fn destructive? gensrc copy genexp)
40 (test* (format "~a (~a) ~a" name kind (if destructive? "!" ""))
41 exp
42 (let* ([src (gensrc in)]
43 [src2 (copy src)]
44 [res (apply fn src2 xargs)]
45 [res-list (genexp res)])
46 (and (if destructive?
47 (eq? src2 res) ; ensure identity preserved
48 (equal? src src2)) ; ensure src2 isn't destroyed
49 res-list))))
50 (define (test2 fn destructive?)
51 (test1 "list" fn destructive? values list-copy values)
52 (test1 "vector" fn destructive? list->vector vector-copy vector->list)
53 (when (every char? in)
54 (test1 "string" fn destructive? list->string string-copy string->list)))
55
56 (test2 fn #f)
57 (test2 fn! #t)
58 )
59
60 (define (sort-test2 name fn fn! stname stfn stfn! xargs in exp)
61 (sort-test name fn fn! xargs in exp)
62 (sort-test stname stfn stfn! xargs in exp))
63
64 (define (sort-nocmp . in&exps)
65 (for-each (lambda (in&exp)
66 (sort-test2 "sort - nocmp" sort sort!
67 "stable-sort - nocmp" stable-sort stable-sort!
68 '()
69 (car in&exp) (cadr in&exp)))
70 in&exps))
71
72 (sort-nocmp
73 '((3 4 8 2 0 1 5 9 7 6) (0 1 2 3 4 5 6 7 8 9))
74 '((0 1 2 3 4 5 6 7 8 9) (0 1 2 3 4 5 6 7 8 9))
75 '((1/2 -3/4 0.1) (-3/4 0.1 1/2))
76 '((0) (0))
77 '((#\a #\l #\o #\h #\a) (#\a #\a #\h #\l #\o))
78 '(("tic" "tac" "toe") ("tac" "tic" "toe")))
79
80 (define (sort-cmp cmpfn . in&exps)
81 (for-each (lambda (in&exp)
82 (sort-test2 "sort - cmp" sort sort!
83 "stable-sort - cmp" stable-sort stable-sort!
84 (list cmpfn)
85 (car in&exp) (cadr in&exp)))
86 in&exps))
87
88 (sort-cmp
89 (lambda (a b) (> (abs a) (abs b)))
90 '((3 -4 8 -2 0 -1 5 -9 7 -6) (-9 8 7 -6 5 -4 3 -2 -1 0))
91 '((-9 -8 -7 -6 -5 -4 -3 -2 -1 0) (-9 -8 -7 -6 -5 -4 -3 -2 -1 0))
92 '((0 1 2 3 4 5 6 7 8 9) (9 8 7 6 5 4 3 2 1 0))
93 '(() ())
94 '((0) (0))
95 '((1/2 -3/4 0.1) (-3/4 1/2 0.1)))
96
97 (sort-cmp
98 string-ci<?
99 '(("Tic" "taC" "tOe") ("taC" "Tic" "tOe")))
100
101 (sort-cmp
102 char-ci<?
103 '((#\M #\a #\i #\P #\o #\n) (#\a #\i #\M #\n #\o #\P)))
104
105 (sort-cmp
106 char-ci-comparator
107 '((#\M #\a #\i #\P #\o #\n) (#\a #\i #\M #\n #\o #\P)))
108
109 (sort-cmp
110 integer>?
111 '((0 1 2 3 4 5 6 7 8 9) (9 8 7 6 5 4 3 2 1 0)))
112
113 (sort-cmp
114 boolean<?
115 '((#t #f #t #f #f) (#f #f #f #t #t)))
116
117 ;; stability
118
119 (sort-test "stable-sort stability"
120 stable-sort stable-sort! (list string-ci<?)
121 '("bbb" "CCC" "AAA" "aaa" "BBB" "ccc")
122 '("AAA" "aaa" "bbb" "BBB" "CCC" "ccc"))
123
124 (sort-test "stable-sort stability"
125 stable-sort stable-sort! (list string-ci>?)
126 '("bbb" "CCC" "AAA" "aaa" "BBB" "ccc")
127 '("CCC" "ccc" "bbb" "BBB" "AAA" "aaa"))
128
129 (test-section "sort-by")
130
131 (define (sort-by-nocmp key . in&exps)
132 (for-each (lambda (in&exp)
133 (sort-test2 "sort-by - nocmp" sort-by sort-by!
134 "stable-sort-by - nocmp" stable-sort-by stable-sort-by!
135 (list key)
136 (car in&exp) (cadr in&exp)))
137 in&exps))
138
139 (sort-by-nocmp
140 car
141 '(((3 . 1) (2 . 8) (5 . 9) (4 . 7) (6 . 0))
142 ((2 . 8) (3 . 1) (4 . 7) (5 . 9) (6 . 0))))
143
144 (sort-by-nocmp
145 cdr
146 '(((3 . 1) (2 . 8) (5 . 9) (4 . 7) (6 . 0))
147 ((6 . 0) (3 . 1) (4 . 7) (2 . 8) (5 . 9))))
148
149 (define (sort-by-cmp key cmp . in&exps)
150 (for-each (lambda (in&exp)
151 (sort-test2 "sort-by - cmp" sort-by sort-by!
152 "stable-sort-by - cmp" stable-sort-by stable-sort-by!
153 (list key cmp)
154 (car in&exp) (cadr in&exp)))
155 in&exps))
156
157 (sort-by-cmp
158 cdr char-ci<?
159 '(((#\a . #\q) (#\T . #\B) (#\s . #\S) (#\k . #\d))
160 ((#\T . #\B) (#\k . #\d) (#\a . #\q) (#\s . #\S))))
161
162 (sort-by-cmp
163 char->integer >
164 '((#\a #\Z #\3 #\q #\P) (#\q #\a #\Z #\P #\3)))
165
166 (sort-by-cmp
167 even?
168 boolean<?
169 '((1 3 1 2 4 2) (1 3 1 2 4 2)))
170
171 ;; ensure in-place list sort
172 ;; https://twitter.com/kmizu/status/1192614125647482882
173 (let ()
174 (define nexts (list '(3 2 0) '(3 1 1) '(2 0 1)))
175 (test* "in-place list sort identity preservation"
176 '((2 0 1) (3 2 0) (3 1 1))
177 (begin
178 (sort! nexts < car)
179 nexts)))
180
181 (test-end)