diff options
author | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2015-11-06 14:07:14 -0200 |
---|---|---|
committer | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2015-11-06 14:07:14 -0200 |
commit | 02340375bee903fe68830cf86c2c207db16ada6b (patch) | |
tree | 9218360067aaa664e5e6b73b29ffcc14a9bd92d2 /ltablib.c | |
parent | 5100bc8aa1c05b1c967567c09d0c70b7c339cc28 (diff) | |
download | lua-02340375bee903fe68830cf86c2c207db16ada6b.tar.gz lua-02340375bee903fe68830cf86c2c207db16ada6b.tar.bz2 lua-02340375bee903fe68830cf86c2c207db16ada6b.zip |
janitor work on 'table.sort': added comments, partition code moved
to a separated function, code conventions updated, etc. No changes
at all in the logic/algorithm
Diffstat (limited to 'ltablib.c')
-rw-r--r-- | ltablib.c | 130 |
1 files changed, 76 insertions, 54 deletions
@@ -1,5 +1,5 @@ | |||
1 | /* | 1 | /* |
2 | ** $Id: ltablib.c,v 1.82 2015/09/09 15:42:30 roberto Exp roberto $ | 2 | ** $Id: ltablib.c,v 1.83 2015/09/17 15:53:50 roberto Exp roberto $ |
3 | ** Library for Table Manipulation | 3 | ** Library for Table Manipulation |
4 | ** See Copyright Notice in lua.h | 4 | ** See Copyright Notice in lua.h |
5 | */ | 5 | */ |
@@ -12,6 +12,7 @@ | |||
12 | 12 | ||
13 | #include <limits.h> | 13 | #include <limits.h> |
14 | #include <stddef.h> | 14 | #include <stddef.h> |
15 | #include <time.h> | ||
15 | 16 | ||
16 | #include "lua.h" | 17 | #include "lua.h" |
17 | 18 | ||
@@ -253,67 +254,88 @@ static int sort_comp (lua_State *L, int a, int b) { | |||
253 | return lua_compare(L, a, b, LUA_OPLT); | 254 | return lua_compare(L, a, b, LUA_OPLT); |
254 | } | 255 | } |
255 | 256 | ||
256 | static void auxsort (lua_State *L, int l, int u) { | 257 | |
257 | while (l < u) { /* for tail recursion */ | 258 | /* |
258 | int i, j; | 259 | ** Does the partition: Pivot P is at the top of the stack. |
259 | /* sort elements a[l], a[(l+u)/2] and a[u] */ | 260 | ** precondition: a[lo] <= P == a[up-1] <= a[up], |
260 | lua_geti(L, 1, l); | 261 | ** so it only needs to do the partition from lo + 1 to up - 2. |
261 | lua_geti(L, 1, u); | 262 | ** Pos-condition: a[lo .. i - 1] <= a[i] == P <= a[i + 1 .. up] |
262 | if (sort_comp(L, -1, -2)) /* a[u] < a[l]? */ | 263 | ** returns 'i'. |
263 | set2(L, l, u); /* swap a[l] - a[u] */ | 264 | */ |
265 | static int partition (lua_State *L, int lo, int up) { | ||
266 | int i = lo; /* will be incremented before first use */ | ||
267 | int j = up - 1; /* will be decremented before first use */ | ||
268 | /* loop invariant: a[lo .. i] <= P <= a[j .. up] */ | ||
269 | for (;;) { | ||
270 | /* next loop: repeat ++i while a[i] < P */ | ||
271 | while (lua_geti(L, 1, ++i), sort_comp(L, -1, -2)) { | ||
272 | if (i >= up) | ||
273 | luaL_error(L, "invalid order function for sorting"); | ||
274 | lua_pop(L, 1); /* remove a[i] */ | ||
275 | } | ||
276 | /* after the loop, a[i] >= P and a[lo .. i - 1] < P */ | ||
277 | /* next loop: repeat --j while P < a[j] */ | ||
278 | while (lua_geti(L, 1, --j), sort_comp(L, -3, -1)) { | ||
279 | if (j < lo) | ||
280 | luaL_error(L, "invalid order function for sorting"); | ||
281 | lua_pop(L, 1); /* remove a[j] */ | ||
282 | } | ||
283 | /* after the loop, a[j] <= P and a[j + 1 .. up] >= P */ | ||
284 | if (j < i) { /* no elements out of place? */ | ||
285 | /* a[lo .. i - 1] <= P <= a[j + 1 .. i .. up] */ | ||
286 | lua_pop(L, 1); /* pop a[j] */ | ||
287 | /* swap pivot (a[up - 1]) with a[i] to satisfy pos-condition */ | ||
288 | set2(L, up - 1, i); | ||
289 | return i; | ||
290 | } | ||
291 | /* otherwise, swap a[i] - a[j] to restore invariant and repeat */ | ||
292 | set2(L, i, j); | ||
293 | } | ||
294 | } | ||
295 | |||
296 | |||
297 | static void auxsort (lua_State *L, int lo, int up) { | ||
298 | while (lo < up) { /* loop for tail recursion */ | ||
299 | int p; | ||
300 | /* sort elements 'lo', '(lo + up)/2' and 'up' */ | ||
301 | lua_geti(L, 1, lo); | ||
302 | lua_geti(L, 1, up); | ||
303 | if (sort_comp(L, -1, -2)) /* a[up] < a[lo]? */ | ||
304 | set2(L, lo, up); /* swap a[lo] - a[up] */ | ||
264 | else | 305 | else |
265 | lua_pop(L, 2); | 306 | lua_pop(L, 2); /* remove both values */ |
266 | if (u-l == 1) break; /* only 2 elements */ | 307 | if (up - lo == 1) /* only 2 elements? */ |
267 | i = (l+u)/2; | 308 | return; /* already sorted */ |
268 | lua_geti(L, 1, i); | 309 | p = (lo + up)/2; |
269 | lua_geti(L, 1, l); | 310 | lua_geti(L, 1, p); |
270 | if (sort_comp(L, -2, -1)) /* a[i]<a[l]? */ | 311 | lua_geti(L, 1, lo); |
271 | set2(L, i, l); | 312 | if (sort_comp(L, -2, -1)) /* a[p] < a[lo]? */ |
313 | set2(L, p, lo); /* swap a[p] - a[lo] */ | ||
272 | else { | 314 | else { |
273 | lua_pop(L, 1); /* remove a[l] */ | 315 | lua_pop(L, 1); /* remove a[lo] */ |
274 | lua_geti(L, 1, u); | 316 | lua_geti(L, 1, up); |
275 | if (sort_comp(L, -1, -2)) /* a[u]<a[i]? */ | 317 | if (sort_comp(L, -1, -2)) /* a[up] < a[p]? */ |
276 | set2(L, i, u); | 318 | set2(L, p, up); /* swap a[up] - a[p] */ |
277 | else | 319 | else |
278 | lua_pop(L, 2); | 320 | lua_pop(L, 2); |
279 | } | 321 | } |
280 | if (u-l == 2) break; /* only 3 elements */ | 322 | if (up - lo == 2) /* only 3 elements? */ |
281 | lua_geti(L, 1, i); /* Pivot */ | 323 | return; /* already sorted */ |
282 | lua_pushvalue(L, -1); | 324 | lua_geti(L, 1, p); /* get middle element (Pivot) */ |
283 | lua_geti(L, 1, u-1); | 325 | lua_pushvalue(L, -1); /* push Pivot */ |
284 | set2(L, i, u-1); | 326 | lua_geti(L, 1, up - 1); /* push a[up - 1] */ |
285 | /* a[l] <= P == a[u-1] <= a[u], only need to sort from l+1 to u-2 */ | 327 | set2(L, p, up - 1); /* swap Pivot (a[p]) with a[up - 1] */ |
286 | i = l; j = u-1; | 328 | p = partition(L, lo, up); |
287 | for (;;) { /* invariant: a[l..i] <= P <= a[j..u] */ | 329 | /* a[lo .. p - 1] <= a[p] == P <= a[p + 1 .. up] */ |
288 | /* repeat ++i until a[i] >= P */ | 330 | if (p - lo < up - p) { /* lower interval is smaller? */ |
289 | while (lua_geti(L, 1, ++i), sort_comp(L, -1, -2)) { | 331 | auxsort(L, lo, p - 1); /* call recursively for lower interval */ |
290 | if (i>=u) luaL_error(L, "invalid order function for sorting"); | 332 | lo = p + 1; /* tail call for [p + 1 .. up] (upper interval) */ |
291 | lua_pop(L, 1); /* remove a[i] */ | ||
292 | } | ||
293 | /* repeat --j until a[j] <= P */ | ||
294 | while (lua_geti(L, 1, --j), sort_comp(L, -3, -1)) { | ||
295 | if (j<=l) luaL_error(L, "invalid order function for sorting"); | ||
296 | lua_pop(L, 1); /* remove a[j] */ | ||
297 | } | ||
298 | if (j<i) { | ||
299 | lua_pop(L, 3); /* pop pivot, a[i], a[j] */ | ||
300 | break; | ||
301 | } | ||
302 | set2(L, i, j); | ||
303 | } | ||
304 | lua_geti(L, 1, u-1); | ||
305 | lua_geti(L, 1, i); | ||
306 | set2(L, u-1, i); /* swap pivot (a[u-1]) with a[i] */ | ||
307 | /* a[l..i-1] <= a[i] == P <= a[i+1..u] */ | ||
308 | /* adjust so that smaller half is in [j..i] and larger one in [l..u] */ | ||
309 | if (i-l < u-i) { | ||
310 | j=l; i=i-1; l=i+2; | ||
311 | } | 333 | } |
312 | else { | 334 | else { |
313 | j=i+1; i=u; u=j-2; | 335 | auxsort(L, p + 1, up); /* call recursively for upper interval */ |
336 | up = p - 1; /* tail call for [lo .. p - 1] (lower interval) */ | ||
314 | } | 337 | } |
315 | auxsort(L, j, i); /* call recursively the smaller one */ | 338 | } /* tail call auxsort(L, lo, up) */ |
316 | } /* repeat the routine for the larger one */ | ||
317 | } | 339 | } |
318 | 340 | ||
319 | static int sort (lua_State *L) { | 341 | static int sort (lua_State *L) { |