-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathutils-test.lisp
199 lines (186 loc) · 8.64 KB
/
utils-test.lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
(in-package :jp-utils-test)
;; Set to T when debugging:
;;(setf lisp-unit::*use-debugger* :ask)
(define-test test-binary-search ()
(multiple-value-bind (result found) (binary-search 234 #(1 3 10 100 234 500 1234))
(assert-eql result 4)
(assert-eql found t))
(multiple-value-bind (result found) (binary-search 1 #(1 3 10 100 234 500 1234))
(assert-eql result 0)
(assert-eql found t))
(multiple-value-bind (result found) (binary-search 1234 #(1 3 10 100 234 500 1234))
(assert-eql result 6)
(assert-eql found t))
(multiple-value-bind (result found) (binary-search 9 #(1 3 10 100 234 500 1234) :not-found t)
(assert-eql result 2)
(assert-eql found nil))
(multiple-value-bind (result found) (binary-search 99 #(1 3 10 100 234 500 1234) :not-found t)
(assert-eql result 3)
(assert-eql found nil))
(multiple-value-bind (result found) (binary-search 233 #(1 3 10 100 234 500 1234) :not-found t)
(assert-eql result 4)
(assert-eql found nil))
(multiple-value-bind (result found) (binary-search 250 #(1 3 10 100 234 500 1234) :not-found t)
(assert-eql result 5)
(assert-eql found nil))
(multiple-value-bind (result found) (binary-search 501 #(1 3 10 100 234 500 1234) :not-found t)
(assert-eql result 6)
(assert-eql found nil))
(multiple-value-bind (result found) (binary-search 234 #(1 3 10 100 234 500 1234) :test= #'equal)
(assert-eql result 4)
(assert-eql found t))
(multiple-value-bind (result found) (binary-search 3 #(1 3 10 100 234 500 1234) :start 3 :not-found -12.1)
(assert-eql result -12.1)
(assert-eql found nil))
(multiple-value-bind (result found) (binary-search 3 #(1 3 10 100 234 500 1234) :start 1 :end 0 :not-found 'oranges)
(assert-eql result 'oranges)
(assert-eql found nil))
(multiple-value-bind (result found) (binary-search 3 #(1 3 10 100 234 500 1234) :start 1)
(assert-eql result 1)
(assert-eql found t))
(multiple-value-bind (result found) (binary-search 3 #(1234 500 234 100 10 3 1) :test< #'>)
(assert-eql result 5)
(assert-eql found t))
(multiple-value-bind (result found) (binary-search #\f "abcdefghijkl" :get-element #'aref)
(assert-eql result 5)
(assert-eql found t))
t)
(define-test test-nonrec-binary-search ()
(multiple-value-bind (result found) (nonrec-binary-search 234 #(1 3 10 100 234 500 1234))
(assert-eql result 4)
(assert-eql found t))
(multiple-value-bind (result found) (nonrec-binary-search 1 #(1 3 10 100 234 500 1234))
(assert-eql result 0)
(assert-eql found t))
(multiple-value-bind (result found) (nonrec-binary-search 1234 #(1 3 10 100 234 500 1234))
(assert-eql result 6)
(assert-eql found t))
(multiple-value-bind (result found) (nonrec-binary-search 9 #(1 3 10 100 234 500 1234) :not-found t)
(assert-eql result 2)
(assert-eql found nil))
(multiple-value-bind (result found) (nonrec-binary-search 99 #(1 3 10 100 234 500 1234) :not-found t)
(assert-eql result 3)
(assert-eql found nil))
(multiple-value-bind (result found) (nonrec-binary-search 233 #(1 3 10 100 234 500 1234) :not-found t)
(assert-eql result 4)
(assert-eql found nil))
(multiple-value-bind (result found) (nonrec-binary-search 250 #(1 3 10 100 234 500 1234) :not-found t)
(assert-eql result 5)
(assert-eql found nil))
(multiple-value-bind (result found) (nonrec-binary-search 501 #(1 3 10 100 234 500 1234) :not-found t)
(assert-eql result 6)
(assert-eql found nil))
(multiple-value-bind (result found) (nonrec-binary-search 234 #(1 3 10 100 234 500 1234) :test= #'equal)
(assert-eql result 4)
(assert-eql found t))
(multiple-value-bind (result found) (nonrec-binary-search 3 #(1 3 10 100 234 500 1234) :start 3 :not-found -12.1)
(assert-eql result -12.1)
(assert-eql found nil))
(multiple-value-bind (result found) (nonrec-binary-search 3 #(1 3 10 100 234 500 1234) :start 1 :end 0 :not-found 'oranges)
(assert-eql result 'oranges)
(assert-eql found nil))
(multiple-value-bind (result found) (nonrec-binary-search 3 #(1 3 10 100 234 500 1234) :start 1)
(assert-eql result 1)
(assert-eql found t))
(multiple-value-bind (result found) (nonrec-binary-search 3 #(1234 500 234 100 10 3 1) :test< #'>)
(assert-eql result 5)
(assert-eql found t))
(multiple-value-bind (result found) (nonrec-binary-search #\f "abcdefghijkl" :get-element #'aref)
(assert-eql result 5)
(assert-eql found t))
t)
(define-test test-get-binary-search ()
(let ((bsearch-fixnum (get-binary-search :element-type fixnum))
(bsearch-fixnum-pos (get-binary-search :element-type fixnum :not-found t))
(bsearch-double (get-binary-search :element-type double-float))
(bsearch-double-pos (get-binary-search :element-type double-float :not-found t))
(bsearch-char (get-binary-search :element-type character))
;; apparently, SBCL does not understand the type of the MAKE-ARRAY below as
;; the same as the one expected by the GET-BINARY-SEARCH function with fixnum
;; type.
;; (vector-fixnum (make-array 7 :element-type 'fixnum
;; :adjustable nil
;; :initial-contents #(1 3 10 100 234 500 1234)))
;; :start 1 :end 0)
(vector-fixnum (coerce #(1 3 10 100 234 500 1234)
'(simple-array fixnum (*))))
(vector-double (make-array 7 :element-type 'double-float
:adjustable nil
:initial-contents #(1d0 3d0 10d0 100d0 234d0 500d0 1234d0)))
(vector-character (make-array 12 :element-type 'character
:adjustable nil
:initial-contents "abcdefghijkl")))
(multiple-value-bind (result found) (funcall bsearch-fixnum 234 vector-fixnum)
(assert-eql result 4)
(assert-eql found t))
(multiple-value-bind (result found) (funcall bsearch-fixnum 1 vector-fixnum)
(assert-eql result 0)
(assert-eql found t))
(multiple-value-bind (result found) (funcall bsearch-fixnum 1234 vector-fixnum)
(assert-eql result 6)
(assert-eql found t))
(multiple-value-bind (result found) (funcall bsearch-fixnum-pos 9 vector-fixnum)
(assert-eql result 2)
(assert-eql found nil))
(multiple-value-bind (result found) (funcall bsearch-fixnum-pos 99 vector-fixnum)
(assert-eql result 3)
(assert-eql found nil))
(multiple-value-bind (result found) (funcall bsearch-fixnum-pos 233 vector-fixnum)
(assert-eql result 4)
(assert-eql found nil))
(multiple-value-bind (result found) (funcall bsearch-double-pos 250d0 vector-double)
(assert-eql result 5)
(assert-eql found nil))
(multiple-value-bind (result found) (funcall bsearch-char #\f vector-character)
(assert-eql result 5)
(assert-eql found t))
(multiple-value-bind (result found) (funcall bsearch-fixnum 3 (coerce #(1 3 10 100 234 500 1234 2000)
'(simple-array fixnum (*)))
:start 1 :end 0)
(assert-eql result nil)
(assert-eql found nil)))
t)
(define-test test-hash-table-keys ()
(loop repeat 10 do
(let* ((b (make-hash-table))
(k 0)
(keylist (loop repeat 60 do
(setf k (random 10000))
(setf (gethash k b) (random 10))
collect k)))
(assert-equalp (remove-duplicates (sort keylist #'<))
(remove-duplicates (sort (hash-table-keys b) #'<))))))
(define-test test-counting-sort ()
(multiple-value-bind (sorted count-array)
(counting-sort (make-array 16
:element-type 'fixnum
:initial-contents '(1 3 5 5 4 8 1 2 2 9 1 1 3 0 3 4))
10 :start 0 :end 15)
(assert-equalp sorted #(0 1 1 1 1 2 2 3 3 3 4 4 5 5 8 9))
(assert-equalp count-array #(0 1 5 7 10 12 14 14 14 15)))
(dotimes (i 50)
(let* ((size (1+ (random 1000))) ;; the "1+" is there because (aref #() 0) wouldn't work
(a (make-array size :element-type 'fixnum :adjustable nil))
(max-element (random 10000)))
(dotimes (j size)
(setf (aref a j) (random max-element)))
(let ((sorted (counting-sort a max-element)))
(assert-true (sortedp sorted))
(dotimes (j size)
(assert-true (< (aref sorted j) max-element)))))))
(define-test test-counting-sort-all ()
(loop repeat 10 do
(let* ((a (generate-random-array 1000 0 10))
(b (make-array 1000 :element-type 'fixnum :adjustable nil :initial-contents a))
(c (make-array 1000 :element-type 'fixnum :adjustable nil :initial-contents a))
(sa nil)
(sb nil)
(sc (make-array 1000 :element-type 'fixnum :adjustable nil)))
(setf sa (counting-sort a 10))
(counting-sort-g c sc 10 0 999)
(setf sb (sort b #'<))
(assert-true (sortedp sa))
(assert-true (sortedp sb))
(assert-true (sortedp sc))
(assert-equalp sa sb)
(assert-equalp sa sc))))