summaryrefslogtreecommitdiff
path: root/testes/sort.lua
diff options
context:
space:
mode:
authorRoberto Ierusalimschy <roberto@inf.puc-rio.br>2018-12-17 14:46:37 -0200
committerRoberto Ierusalimschy <roberto@inf.puc-rio.br>2018-12-17 14:46:37 -0200
commit063d4e4543088e7a21965bda8ee5a0f952a9029e (patch)
tree6c3f2f8e98c26f071a94a32f9f2754396a66a9de /testes/sort.lua
parente354c6355e7f48e087678ec49e340ca0696725b1 (diff)
downloadlua-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.lua310
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
4print "testing (parts of) table library"
5
6print "testing unpack"
7
8local unpack = table.unpack
9
10local maxI = math.maxinteger
11local minI = math.mininteger
12
13
14local function checkerror (msg, f, ...)
15 local s, err = pcall(f, ...)
16 assert(not s and string.find(err, msg))
17end
18
19
20checkerror("wrong number of arguments", table.insert, {}, 2, 3, 4)
21
22local x,y,z,a,n
23a = {}; lim = _soft and 200 or 2000
24for i=1, lim do a[i]=i end
25assert(select(lim, unpack(a)) == lim and select('#', unpack(a)) == lim)
26x = unpack(a)
27assert(x == 1)
28x = {unpack(a)}
29assert(#x == lim and x[1] == 1 and x[lim] == lim)
30x = {unpack(a, lim-2)}
31assert(#x == 3 and x[1] == lim-2 and x[3] == lim)
32x = {unpack(a, 10, 6)}
33assert(next(x) == nil) -- no elements
34x = {unpack(a, 11, 10)}
35assert(next(x) == nil) -- no elements
36x,y = unpack(a, 10, 10)
37assert(x == 10 and y == nil)
38x,y,z = unpack(a, 10, 11)
39assert(x == 10 and y == 11 and z == nil)
40a,x = unpack{1}
41assert(a==1 and x==nil)
42a,x = unpack({1,2}, 1, 1)
43assert(a==1 and x==nil)
44
45do
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)
71end
72
73do -- 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)
77end
78
79print "testing pack"
80
81a = table.pack()
82assert(a[1] == nil and a.n == 0)
83
84a = table.pack(table)
85assert(a[1] == table and a.n == 1)
86
87a = table.pack(nil, nil, nil, nil)
88assert(a[1] == nil and a.n == 4)
89
90
91-- testing move
92do
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)
161end
162
163do
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
180end
181
182checkerror("too many", table.move, {}, 0, maxI, 1)
183checkerror("too many", table.move, {}, -1, maxI - 1, 1)
184checkerror("too many", table.move, {}, minI, -1, 1)
185checkerror("too many", table.move, {}, minI, maxI, 1)
186checkerror("wrap around", table.move, {}, 1, maxI, 2)
187checkerror("wrap around", table.move, {}, 1, 2, maxI)
188checkerror("wrap around", table.move, {}, minI, -2, 2)
189
190
191print"testing sort"
192
193
194-- strange lengths
195local a = setmetatable({}, {__len = function () return -1 end})
196assert(#a == -1)
197table.sort(a, error) -- should not compare anything
198a = setmetatable({}, {__len = function () return maxI end})
199checkerror("too big", table.sort, a)
200
201-- test checks for invalid order functions
202local 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)
205end
206
207check{1,2,3,4}
208check{1,2,3,4,5}
209check{1,2,3,4,5,6}
210
211
212function 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
217end
218
219a = {"Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep",
220 "Oct", "Nov", "Dec"}
221
222table.sort(a)
223check(a)
224
225function 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
238end
239
240perm{}
241perm{1}
242perm{1,2}
243perm{1,2,3}
244perm{1,2,3,4}
245perm{2,2,3,4}
246perm{1,2,3,4,5}
247perm{1,2,3,3,5}
248perm{1,2,3,4,5,6}
249perm{2,2,3,3,5,6}
250
251function 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)
258end
259
260limit = 50000
261if _soft then limit = 5000 end
262
263a = {}
264for i=1,limit do
265 a[i] = math.random()
266end
267
268timesort(a, limit, nil, "random")
269
270timesort(a, limit, nil, "sorted", "re-")
271
272a = {}
273for i=1,limit do
274 a[i] = math.random()
275end
276
277x = os.clock(); i=0
278table.sort(a, function(x,y) i=i+1; return y<x end)
279x = (os.clock() - x) * 1000
280print(string.format("Invert-sorting other %d elements in %.2f msec., with %i comparisons",
281 limit, x, i))
282check(a, function(x,y) return y<x end)
283
284
285table.sort{} -- empty array
286
287for i=1,limit do a[i] = false end
288timesort(a, limit, function(x,y) return nil end, "equal")
289
290for i,v in pairs(a) do assert(v == false) end
291
292A = {"álo", "\0first :-)", "alo", "then this one", "45", "and a new"}
293table.sort(A)
294check(A)
295
296table.sort(A, function (x, y)
297 load(string.format("A[%q] = ''", x), "")()
298 collectgarbage()
299 return x<y
300 end)
301
302
303tt = {__lt = function (a,b) return a.val < b.val end}
304a = {}
305for i=1,10 do a[i] = {val=math.random(100)}; setmetatable(a[i], tt); end
306table.sort(a)
307check(a, tt.__lt)
308check(a)
309
310print"OK"