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