1-- $Id: testes/sort.lua $
  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 = {}; local 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] == undef 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
225local 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
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
251local 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)
258end
259
260local limit = 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
277local x = os.clock(); local 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
292AA = {"\xE1lo", "\0first :-)", "alo", "then this one", "45", "and a new"}
293table.sort(AA)
294check(AA)
295
296table.sort(AA, function (x, y)
297          load(string.format("AA[%q] = ''", x), "")()
298          collectgarbage()
299          return x<y
300        end)
301
302_G.AA = nil
303
304local tt = {__lt = function (a,b) return a.val < b.val end}
305a = {}
306for i=1,10 do  a[i] = {val=math.random(100)}; setmetatable(a[i], tt); end
307table.sort(a)
308check(a, tt.__lt)
309check(a)
310
311print"OK"