diff options
author | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2018-12-17 14:46:37 -0200 |
---|---|---|
committer | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2018-12-17 14:46:37 -0200 |
commit | 063d4e4543088e7a21965bda8ee5a0f952a9029e (patch) | |
tree | 6c3f2f8e98c26f071a94a32f9f2754396a66a9de /testes/sort.lua | |
parent | e354c6355e7f48e087678ec49e340ca0696725b1 (diff) | |
download | lua-5.3.5.tar.gz lua-5.3.5.tar.bz2 lua-5.3.5.zip |
Lua 5.3.5 ported to gitv5.3.5
This is the first commit for the branch Lua 5.3. All source files
were copied from the official distribution of 5.3.5 in the Lua site.
The test files are the same of 5.3.4. The manual came from the
previous RCS repository, revision 1.167.1.2.
Diffstat (limited to 'testes/sort.lua')
-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" | ||