sort.lsp 3.92 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
;-*- Mode:     Lisp -*-
;;;; Author:   Paul Dietz
;;;; Created:  Wed Aug 21 00:11:24 2002
;;;; Contains: Tests for SORT

(in-package :cl-test)

(deftest sort-list.1
  (let ((a (list 1 4 2 5 3)))
    (sort a #'<))
  (1 2 3 4 5))

(deftest sort-list.2
  (let ((a (list 1 4 2 5 3)))
    (sort a #'< :key #'-))
  (5 4 3 2 1))

(deftest sort-list.3
  (let ((a (list 1 4 2 5 3)))
    (sort a #'(lambda (x y) nil))
    (sort a #'<))
  (1 2 3 4 5))

24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
;;;
;;; Confirm that sort only permutes the sequence, even when given
;;; a comparison function that does not define a total order.
;;;
(deftest sort-list.4
  (loop
   repeat 100
   always
   (let ((a (list 1 2 3 4 5 6 7 8 9 0))
	 (cmp (make-array '(10 10))))
     (loop for i from 0 to 9 do
	   (loop for j from 0 to 9 do
		 (setf (aref cmp i j) (zerop (logand (random 1024) 512)))))
     (setq a (sort a #'(lambda (i j) (aref cmp i j))))
     (and (eqlt (length a) 10)
	  (equalt (sort a #'<) '(0 1 2 3 4 5 6 7 8 9)))))
  t)	

42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
(deftest sort-vector.1
  (let ((a (copy-seq #(1 4 2 5 3))))
    (sort a #'<))
  #(1 2 3 4 5))

(deftest sort-vector.2
  (let ((a (copy-seq #(1 4 2 5 3))))
    (sort a #'< :key #'-))
  #(5 4 3 2 1))

(deftest sort-vector.3
  (let ((a (copy-seq #(1 4 2 5 3))))
    (sort a #'(lambda (x y) nil))
    (sort a #'<))
  #(1 2 3 4 5))

58
59
60
61
62
63
(deftest sort-vector.4
  (let ((a (make-array 10 :initial-contents '(10 40 20 50 30 15 45 25 55 35)
		       :fill-pointer 5)))
    (sort a #'<))
  #(10 20 30 40 50))

64
65
66
67
68
69
70
71
72
73
74
75
76
77
(deftest sort-vector.5
  (loop
   repeat 100
   always
   (let ((a (vector 1 2 3 4 5 6 7 8 9 0))
	 (cmp (make-array '(10 10))))
     (loop for i from 0 to 9 do
	   (loop for j from 0 to 9 do
		 (setf (aref cmp i j) (zerop (logand (random 1024) 512)))))
     (setq a (sort a #'(lambda (i j) (aref cmp i j))))
     (and (eqlt (length a) 10)
	  (equalpt (sort a #'<) #(0 1 2 3 4 5 6 7 8 9)))))
  t)	

78
79
80
81
82
83
84
85
86
87
88
(deftest sort-bit-vector.1
  (let ((a (copy-seq #*10011101)))
    (sort a #'<))
  #*00011111)

(deftest sort-bit-vector.2
  (let ((a (copy-seq #*10011101)))
    (values (sort a #'< :key #'-) a))
  #*11111000
  #*11111000)

89
90
91
92
93
94
95
(deftest sort-bit-vector.3
  (let ((a (make-array 10 :initial-contents '(1 0 0 1 1 1 1 0 1 1)
		       :element-type 'bit
		       :fill-pointer 5)))
    (sort a #'<))
  #*00111)

96
97
98
99
100
101
102
103
104
105
106
107
(deftest sort-string.1
  (let ((a (copy-seq "10011101")))
    (values (sort a #'char<) a))
  "00011111"
  "00011111")

(deftest sort-string.2
  (let ((a (copy-seq "10011101")))
    (values (sort a #'char< :key #'(lambda (c) (if (eql c #\0) #\1 #\0))) a))
  "11111000"
  "11111000")

108
(deftest sort-string.3
109
  (let ((a (make-array 10 :initial-contents "1001111011"
110
111
112
113
114
		       :element-type 'character
		       :fill-pointer 5)))
    (sort a #'char<))
  "00111")

115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
;;; Order of evaluation tests

(deftest sort.order.1
  (let ((i 0) x y)
    (values
     (sort (progn (setf x (incf i)) (list 1 7 3 2))
	   (progn (setf y (incf i)) #'<))
     i x y))
  (1 2 3 7) 2 1 2)

(deftest sort.order.2
  (let ((i 0) x y z)
    (values
     (sort (progn (setf x (incf i)) (list 1 7 3 2))
	   (progn (setf y (incf i)) #'<)
	   :key (progn (setf z (incf i)) #'-))
     i x y z))
  (7 3 2 1) 3 1 2 3)


135
;;; Error cases
136

137
138
139
(deftest sort.error.1
  (classify-error (sort))
  program-error)
140

141
142
143
(deftest sort.error.2
  (classify-error (sort nil))
  program-error)
144

145
146
147
(deftest sort.error.3
  (classify-error (sort nil #'< :key))
  program-error)
148

149
150
151
(deftest sort.error.4
  (classify-error (sort nil #'< 'bad t))
  program-error)
152

153
154
155
(deftest sort.error.5
  (classify-error (sort nil #'< 'bad t :allow-other-keys nil))
  program-error)
156

157
158
159
(deftest sort.error.6
  (classify-error (sort nil #'< 1 2))
  program-error)
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175

(deftest sort.error.7
  (classify-error (sort (list 1 2 3 4) #'identity))
  program-error)

(deftest sort.error.8
  (classify-error (sort (list 1 2 3 4) #'< :key #'cons))
  program-error)

(deftest sort.error.9
  (classify-error (sort (list 1 2 3 4) #'< :key #'car))
  type-error)

(deftest sort.error.10
  (classify-error (sort (list 1 2 3 4) #'elt))
  type-error)