diff options
Diffstat (limited to '')
-rw-r--r-- | testes/sort.lua | 310 |
1 files changed, 310 insertions, 0 deletions
diff --git a/testes/sort.lua b/testes/sort.lua new file mode 100644 index 00000000..d52feee8 --- /dev/null +++ b/testes/sort.lua | |||
@@ -0,0 +1,310 @@ | |||
1 | -- $Id: sort.lua,v 1.38 2016/11/07 13:11:28 roberto Exp $ | ||
2 | -- See Copyright Notice in file all.lua | ||
3 | |||
4 | print "testing (parts of) table library" | ||
5 | |||
6 | print "testing unpack" | ||
7 | |||
8 | local unpack = table.unpack | ||
9 | |||
10 | local maxI = math.maxinteger | ||
11 | local minI = math.mininteger | ||
12 | |||
13 | |||
14 | local function checkerror (msg, f, ...) | ||
15 | local s, err = pcall(f, ...) | ||
16 | assert(not s and string.find(err, msg)) | ||
17 | end | ||
18 | |||
19 | |||
20 | checkerror("wrong number of arguments", table.insert, {}, 2, 3, 4) | ||
21 | |||
22 | local x,y,z,a,n | ||
23 | a = {}; lim = _soft and 200 or 2000 | ||
24 | for i=1, lim do a[i]=i end | ||
25 | assert(select(lim, unpack(a)) == lim and select('#', unpack(a)) == lim) | ||
26 | x = unpack(a) | ||
27 | assert(x == 1) | ||
28 | x = {unpack(a)} | ||
29 | assert(#x == lim and x[1] == 1 and x[lim] == lim) | ||
30 | x = {unpack(a, lim-2)} | ||
31 | assert(#x == 3 and x[1] == lim-2 and x[3] == lim) | ||
32 | x = {unpack(a, 10, 6)} | ||
33 | assert(next(x) == nil) -- no elements | ||
34 | x = {unpack(a, 11, 10)} | ||
35 | assert(next(x) == nil) -- no elements | ||
36 | x,y = unpack(a, 10, 10) | ||
37 | assert(x == 10 and y == nil) | ||
38 | x,y,z = unpack(a, 10, 11) | ||
39 | assert(x == 10 and y == 11 and z == nil) | ||
40 | a,x = unpack{1} | ||
41 | assert(a==1 and x==nil) | ||
42 | a,x = unpack({1,2}, 1, 1) | ||
43 | assert(a==1 and x==nil) | ||
44 | |||
45 | do | ||
46 | local maxi = (1 << 31) - 1 -- maximum value for an int (usually) | ||
47 | local mini = -(1 << 31) -- minimum value for an int (usually) | ||
48 | checkerror("too many results", unpack, {}, 0, maxi) | ||
49 | checkerror("too many results", unpack, {}, 1, maxi) | ||
50 | checkerror("too many results", unpack, {}, 0, maxI) | ||
51 | checkerror("too many results", unpack, {}, 1, maxI) | ||
52 | checkerror("too many results", unpack, {}, mini, maxi) | ||
53 | checkerror("too many results", unpack, {}, -maxi, maxi) | ||
54 | checkerror("too many results", unpack, {}, minI, maxI) | ||
55 | unpack({}, maxi, 0) | ||
56 | unpack({}, maxi, 1) | ||
57 | unpack({}, maxI, minI) | ||
58 | pcall(unpack, {}, 1, maxi + 1) | ||
59 | local a, b = unpack({[maxi] = 20}, maxi, maxi) | ||
60 | assert(a == 20 and b == nil) | ||
61 | a, b = unpack({[maxi] = 20}, maxi - 1, maxi) | ||
62 | assert(a == nil and b == 20) | ||
63 | local t = {[maxI - 1] = 12, [maxI] = 23} | ||
64 | a, b = unpack(t, maxI - 1, maxI); assert(a == 12 and b == 23) | ||
65 | a, b = unpack(t, maxI, maxI); assert(a == 23 and b == nil) | ||
66 | a, b = unpack(t, maxI, maxI - 1); assert(a == nil and b == nil) | ||
67 | t = {[minI] = 12.3, [minI + 1] = 23.5} | ||
68 | a, b = unpack(t, minI, minI + 1); assert(a == 12.3 and b == 23.5) | ||
69 | a, b = unpack(t, minI, minI); assert(a == 12.3 and b == nil) | ||
70 | a, b = unpack(t, minI + 1, minI); assert(a == nil and b == nil) | ||
71 | end | ||
72 | |||
73 | do -- length is not an integer | ||
74 | local t = setmetatable({}, {__len = function () return 'abc' end}) | ||
75 | assert(#t == 'abc') | ||
76 | checkerror("object length is not an integer", table.insert, t, 1) | ||
77 | end | ||
78 | |||
79 | print "testing pack" | ||
80 | |||
81 | a = table.pack() | ||
82 | assert(a[1] == nil and a.n == 0) | ||
83 | |||
84 | a = table.pack(table) | ||
85 | assert(a[1] == table and a.n == 1) | ||
86 | |||
87 | a = table.pack(nil, nil, nil, nil) | ||
88 | assert(a[1] == nil and a.n == 4) | ||
89 | |||
90 | |||
91 | -- testing move | ||
92 | do | ||
93 | |||
94 | checkerror("table expected", table.move, 1, 2, 3, 4) | ||
95 | |||
96 | local function eqT (a, b) | ||
97 | for k, v in pairs(a) do assert(b[k] == v) end | ||
98 | for k, v in pairs(b) do assert(a[k] == v) end | ||
99 | end | ||
100 | |||
101 | local a = table.move({10,20,30}, 1, 3, 2) -- move forward | ||
102 | eqT(a, {10,10,20,30}) | ||
103 | |||
104 | -- move forward with overlap of 1 | ||
105 | a = table.move({10, 20, 30}, 1, 3, 3) | ||
106 | eqT(a, {10, 20, 10, 20, 30}) | ||
107 | |||
108 | -- moving to the same table (not being explicit about it) | ||
109 | a = {10, 20, 30, 40} | ||
110 | table.move(a, 1, 4, 2, a) | ||
111 | eqT(a, {10, 10, 20, 30, 40}) | ||
112 | |||
113 | a = table.move({10,20,30}, 2, 3, 1) -- move backward | ||
114 | eqT(a, {20,30,30}) | ||
115 | |||
116 | a = {} -- move to new table | ||
117 | assert(table.move({10,20,30}, 1, 3, 1, a) == a) | ||
118 | eqT(a, {10,20,30}) | ||
119 | |||
120 | a = {} | ||
121 | assert(table.move({10,20,30}, 1, 0, 3, a) == a) -- empty move (no move) | ||
122 | eqT(a, {}) | ||
123 | |||
124 | a = table.move({10,20,30}, 1, 10, 1) -- move to the same place | ||
125 | eqT(a, {10,20,30}) | ||
126 | |||
127 | -- moving on the fringes | ||
128 | a = table.move({[maxI - 2] = 1, [maxI - 1] = 2, [maxI] = 3}, | ||
129 | maxI - 2, maxI, -10, {}) | ||
130 | eqT(a, {[-10] = 1, [-9] = 2, [-8] = 3}) | ||
131 | |||
132 | a = table.move({[minI] = 1, [minI + 1] = 2, [minI + 2] = 3}, | ||
133 | minI, minI + 2, -10, {}) | ||
134 | eqT(a, {[-10] = 1, [-9] = 2, [-8] = 3}) | ||
135 | |||
136 | a = table.move({45}, 1, 1, maxI) | ||
137 | eqT(a, {45, [maxI] = 45}) | ||
138 | |||
139 | a = table.move({[maxI] = 100}, maxI, maxI, minI) | ||
140 | eqT(a, {[minI] = 100, [maxI] = 100}) | ||
141 | |||
142 | a = table.move({[minI] = 100}, minI, minI, maxI) | ||
143 | eqT(a, {[minI] = 100, [maxI] = 100}) | ||
144 | |||
145 | a = setmetatable({}, { | ||
146 | __index = function (_,k) return k * 10 end, | ||
147 | __newindex = error}) | ||
148 | local b = table.move(a, 1, 10, 3, {}) | ||
149 | eqT(a, {}) | ||
150 | eqT(b, {nil,nil,10,20,30,40,50,60,70,80,90,100}) | ||
151 | |||
152 | b = setmetatable({""}, { | ||
153 | __index = error, | ||
154 | __newindex = function (t,k,v) | ||
155 | t[1] = string.format("%s(%d,%d)", t[1], k, v) | ||
156 | end}) | ||
157 | table.move(a, 10, 13, 3, b) | ||
158 | assert(b[1] == "(3,100)(4,110)(5,120)(6,130)") | ||
159 | local stat, msg = pcall(table.move, b, 10, 13, 3, b) | ||
160 | assert(not stat and msg == b) | ||
161 | end | ||
162 | |||
163 | do | ||
164 | -- for very long moves, just check initial accesses and interrupt | ||
165 | -- move with an error | ||
166 | local function checkmove (f, e, t, x, y) | ||
167 | local pos1, pos2 | ||
168 | local a = setmetatable({}, { | ||
169 | __index = function (_,k) pos1 = k end, | ||
170 | __newindex = function (_,k) pos2 = k; error() end, }) | ||
171 | local st, msg = pcall(table.move, a, f, e, t) | ||
172 | assert(not st and not msg and pos1 == x and pos2 == y) | ||
173 | end | ||
174 | checkmove(1, maxI, 0, 1, 0) | ||
175 | checkmove(0, maxI - 1, 1, maxI - 1, maxI) | ||
176 | checkmove(minI, -2, -5, -2, maxI - 6) | ||
177 | checkmove(minI + 1, -1, -2, -1, maxI - 3) | ||
178 | checkmove(minI, -2, 0, minI, 0) -- non overlapping | ||
179 | checkmove(minI + 1, -1, 1, minI + 1, 1) -- non overlapping | ||
180 | end | ||
181 | |||
182 | checkerror("too many", table.move, {}, 0, maxI, 1) | ||
183 | checkerror("too many", table.move, {}, -1, maxI - 1, 1) | ||
184 | checkerror("too many", table.move, {}, minI, -1, 1) | ||
185 | checkerror("too many", table.move, {}, minI, maxI, 1) | ||
186 | checkerror("wrap around", table.move, {}, 1, maxI, 2) | ||
187 | checkerror("wrap around", table.move, {}, 1, 2, maxI) | ||
188 | checkerror("wrap around", table.move, {}, minI, -2, 2) | ||
189 | |||
190 | |||
191 | print"testing sort" | ||
192 | |||
193 | |||
194 | -- strange lengths | ||
195 | local a = setmetatable({}, {__len = function () return -1 end}) | ||
196 | assert(#a == -1) | ||
197 | table.sort(a, error) -- should not compare anything | ||
198 | a = setmetatable({}, {__len = function () return maxI end}) | ||
199 | checkerror("too big", table.sort, a) | ||
200 | |||
201 | -- test checks for invalid order functions | ||
202 | local function check (t) | ||
203 | local function f(a, b) assert(a and b); return true end | ||
204 | checkerror("invalid order function", table.sort, t, f) | ||
205 | end | ||
206 | |||
207 | check{1,2,3,4} | ||
208 | check{1,2,3,4,5} | ||
209 | check{1,2,3,4,5,6} | ||
210 | |||
211 | |||
212 | function check (a, f) | ||
213 | f = f or function (x,y) return x<y end; | ||
214 | for n = #a, 2, -1 do | ||
215 | assert(not f(a[n], a[n-1])) | ||
216 | end | ||
217 | end | ||
218 | |||
219 | a = {"Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", | ||
220 | "Oct", "Nov", "Dec"} | ||
221 | |||
222 | table.sort(a) | ||
223 | check(a) | ||
224 | |||
225 | function perm (s, n) | ||
226 | n = n or #s | ||
227 | if n == 1 then | ||
228 | local t = {unpack(s)} | ||
229 | table.sort(t) | ||
230 | check(t) | ||
231 | else | ||
232 | for i = 1, n do | ||
233 | s[i], s[n] = s[n], s[i] | ||
234 | perm(s, n - 1) | ||
235 | s[i], s[n] = s[n], s[i] | ||
236 | end | ||
237 | end | ||
238 | end | ||
239 | |||
240 | perm{} | ||
241 | perm{1} | ||
242 | perm{1,2} | ||
243 | perm{1,2,3} | ||
244 | perm{1,2,3,4} | ||
245 | perm{2,2,3,4} | ||
246 | perm{1,2,3,4,5} | ||
247 | perm{1,2,3,3,5} | ||
248 | perm{1,2,3,4,5,6} | ||
249 | perm{2,2,3,3,5,6} | ||
250 | |||
251 | function timesort (a, n, func, msg, pre) | ||
252 | local x = os.clock() | ||
253 | table.sort(a, func) | ||
254 | x = (os.clock() - x) * 1000 | ||
255 | pre = pre or "" | ||
256 | print(string.format("%ssorting %d %s elements in %.2f msec.", pre, n, msg, x)) | ||
257 | check(a, func) | ||
258 | end | ||
259 | |||
260 | limit = 50000 | ||
261 | if _soft then limit = 5000 end | ||
262 | |||
263 | a = {} | ||
264 | for i=1,limit do | ||
265 | a[i] = math.random() | ||
266 | end | ||
267 | |||
268 | timesort(a, limit, nil, "random") | ||
269 | |||
270 | timesort(a, limit, nil, "sorted", "re-") | ||
271 | |||
272 | a = {} | ||
273 | for i=1,limit do | ||
274 | a[i] = math.random() | ||
275 | end | ||
276 | |||
277 | x = os.clock(); i=0 | ||
278 | table.sort(a, function(x,y) i=i+1; return y<x end) | ||
279 | x = (os.clock() - x) * 1000 | ||
280 | print(string.format("Invert-sorting other %d elements in %.2f msec., with %i comparisons", | ||
281 | limit, x, i)) | ||
282 | check(a, function(x,y) return y<x end) | ||
283 | |||
284 | |||
285 | table.sort{} -- empty array | ||
286 | |||
287 | for i=1,limit do a[i] = false end | ||
288 | timesort(a, limit, function(x,y) return nil end, "equal") | ||
289 | |||
290 | for i,v in pairs(a) do assert(v == false) end | ||
291 | |||
292 | A = {"álo", "\0first :-)", "alo", "then this one", "45", "and a new"} | ||
293 | table.sort(A) | ||
294 | check(A) | ||
295 | |||
296 | table.sort(A, function (x, y) | ||
297 | load(string.format("A[%q] = ''", x), "")() | ||
298 | collectgarbage() | ||
299 | return x<y | ||
300 | end) | ||
301 | |||
302 | |||
303 | tt = {__lt = function (a,b) return a.val < b.val end} | ||
304 | a = {} | ||
305 | for i=1,10 do a[i] = {val=math.random(100)}; setmetatable(a[i], tt); end | ||
306 | table.sort(a) | ||
307 | check(a, tt.__lt) | ||
308 | check(a) | ||
309 | |||
310 | print"OK" | ||