Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: code/branches/ceguilua/src/lua/ltablib.c @ 1809

Last change on this file since 1809 was 1806, checked in by rgrieder, 16 years ago

added single 5.1.3 directory for lua since CEGUILua 0.5 can also build against lua 5.1

  • Property svn:eol-style set to native
File size: 6.9 KB
Line 
1/*
2** $Id: ltablib.c,v 1.38.1.2 2007/12/28 15:32:23 roberto Exp $
3** Library for Table Manipulation
4** See Copyright Notice in lua.h
5*/
6
7
8#include <stddef.h>
9
10#define ltablib_c
11#define LUA_LIB
12
13#include "lua.h"
14
15#include "lauxlib.h"
16#include "lualib.h"
17
18
19#define aux_getn(L,n)   (luaL_checktype(L, n, LUA_TTABLE), luaL_getn(L, n))
20
21
22static int foreachi (lua_State *L) {
23  int i;
24  int n = aux_getn(L, 1);
25  luaL_checktype(L, 2, LUA_TFUNCTION);
26  for (i=1; i <= n; i++) {
27    lua_pushvalue(L, 2);  /* function */
28    lua_pushinteger(L, i);  /* 1st argument */
29    lua_rawgeti(L, 1, i);  /* 2nd argument */
30    lua_call(L, 2, 1);
31    if (!lua_isnil(L, -1))
32      return 1;
33    lua_pop(L, 1);  /* remove nil result */
34  }
35  return 0;
36}
37
38
39static int foreach (lua_State *L) {
40  luaL_checktype(L, 1, LUA_TTABLE);
41  luaL_checktype(L, 2, LUA_TFUNCTION);
42  lua_pushnil(L);  /* first key */
43  while (lua_next(L, 1)) {
44    lua_pushvalue(L, 2);  /* function */
45    lua_pushvalue(L, -3);  /* key */
46    lua_pushvalue(L, -3);  /* value */
47    lua_call(L, 2, 1);
48    if (!lua_isnil(L, -1))
49      return 1;
50    lua_pop(L, 2);  /* remove value and result */
51  }
52  return 0;
53}
54
55
56static int maxn (lua_State *L) {
57  lua_Number max = 0;
58  luaL_checktype(L, 1, LUA_TTABLE);
59  lua_pushnil(L);  /* first key */
60  while (lua_next(L, 1)) {
61    lua_pop(L, 1);  /* remove value */
62    if (lua_type(L, -1) == LUA_TNUMBER) {
63      lua_Number v = lua_tonumber(L, -1);
64      if (v > max) max = v;
65    }
66  }
67  lua_pushnumber(L, max);
68  return 1;
69}
70
71
72static int getn (lua_State *L) {
73  lua_pushinteger(L, aux_getn(L, 1));
74  return 1;
75}
76
77
78static int setn (lua_State *L) {
79  luaL_checktype(L, 1, LUA_TTABLE);
80#ifndef luaL_setn
81  luaL_setn(L, 1, luaL_checkint(L, 2));
82#else
83  luaL_error(L, LUA_QL("setn") " is obsolete");
84#endif
85  lua_pushvalue(L, 1);
86  return 1;
87}
88
89
90static int tinsert (lua_State *L) {
91  int e = aux_getn(L, 1) + 1;  /* first empty element */
92  int pos;  /* where to insert new element */
93  switch (lua_gettop(L)) {
94    case 2: {  /* called with only 2 arguments */
95      pos = e;  /* insert new element at the end */
96      break;
97    }
98    case 3: {
99      int i;
100      pos = luaL_checkint(L, 2);  /* 2nd argument is the position */
101      if (pos > e) e = pos;  /* `grow' array if necessary */
102      for (i = e; i > pos; i--) {  /* move up elements */
103        lua_rawgeti(L, 1, i-1);
104        lua_rawseti(L, 1, i);  /* t[i] = t[i-1] */
105      }
106      break;
107    }
108    default: {
109      return luaL_error(L, "wrong number of arguments to " LUA_QL("insert"));
110    }
111  }
112  luaL_setn(L, 1, e);  /* new size */
113  lua_rawseti(L, 1, pos);  /* t[pos] = v */
114  return 0;
115}
116
117
118static int tremove (lua_State *L) {
119  int e = aux_getn(L, 1);
120  int pos = luaL_optint(L, 2, e);
121  if (!(1 <= pos && pos <= e))  /* position is outside bounds? */
122   return 0;  /* nothing to remove */
123  luaL_setn(L, 1, e - 1);  /* t.n = n-1 */
124  lua_rawgeti(L, 1, pos);  /* result = t[pos] */
125  for ( ;pos<e; pos++) {
126    lua_rawgeti(L, 1, pos+1);
127    lua_rawseti(L, 1, pos);  /* t[pos] = t[pos+1] */
128  }
129  lua_pushnil(L);
130  lua_rawseti(L, 1, e);  /* t[e] = nil */
131  return 1;
132}
133
134
135static int tconcat (lua_State *L) {
136  luaL_Buffer b;
137  size_t lsep;
138  int i, last;
139  const char *sep = luaL_optlstring(L, 2, "", &lsep);
140  luaL_checktype(L, 1, LUA_TTABLE);
141  i = luaL_optint(L, 3, 1);
142  last = luaL_opt(L, luaL_checkint, 4, luaL_getn(L, 1));
143  luaL_buffinit(L, &b);
144  for (; i <= last; i++) {
145    lua_rawgeti(L, 1, i);
146    luaL_argcheck(L, lua_isstring(L, -1), 1, "table contains non-strings");
147    luaL_addvalue(&b);
148    if (i != last)
149      luaL_addlstring(&b, sep, lsep);
150  }
151  luaL_pushresult(&b);
152  return 1;
153}
154
155
156
157/*
158** {======================================================
159** Quicksort
160** (based on `Algorithms in MODULA-3', Robert Sedgewick;
161**  Addison-Wesley, 1993.)
162*/
163
164
165static void set2 (lua_State *L, int i, int j) {
166  lua_rawseti(L, 1, i);
167  lua_rawseti(L, 1, j);
168}
169
170static int sort_comp (lua_State *L, int a, int b) {
171  if (!lua_isnil(L, 2)) {  /* function? */
172    int res;
173    lua_pushvalue(L, 2);
174    lua_pushvalue(L, a-1);  /* -1 to compensate function */
175    lua_pushvalue(L, b-2);  /* -2 to compensate function and `a' */
176    lua_call(L, 2, 1);
177    res = lua_toboolean(L, -1);
178    lua_pop(L, 1);
179    return res;
180  }
181  else  /* a < b? */
182    return lua_lessthan(L, a, b);
183}
184
185static void auxsort (lua_State *L, int l, int u) {
186  while (l < u) {  /* for tail recursion */
187    int i, j;
188    /* sort elements a[l], a[(l+u)/2] and a[u] */
189    lua_rawgeti(L, 1, l);
190    lua_rawgeti(L, 1, u);
191    if (sort_comp(L, -1, -2))  /* a[u] < a[l]? */
192      set2(L, l, u);  /* swap a[l] - a[u] */
193    else
194      lua_pop(L, 2);
195    if (u-l == 1) break;  /* only 2 elements */
196    i = (l+u)/2;
197    lua_rawgeti(L, 1, i);
198    lua_rawgeti(L, 1, l);
199    if (sort_comp(L, -2, -1))  /* a[i]<a[l]? */
200      set2(L, i, l);
201    else {
202      lua_pop(L, 1);  /* remove a[l] */
203      lua_rawgeti(L, 1, u);
204      if (sort_comp(L, -1, -2))  /* a[u]<a[i]? */
205        set2(L, i, u);
206      else
207        lua_pop(L, 2);
208    }
209    if (u-l == 2) break;  /* only 3 elements */
210    lua_rawgeti(L, 1, i);  /* Pivot */
211    lua_pushvalue(L, -1);
212    lua_rawgeti(L, 1, u-1);
213    set2(L, i, u-1);
214    /* a[l] <= P == a[u-1] <= a[u], only need to sort from l+1 to u-2 */
215    i = l; j = u-1;
216    for (;;) {  /* invariant: a[l..i] <= P <= a[j..u] */
217      /* repeat ++i until a[i] >= P */
218      while (lua_rawgeti(L, 1, ++i), sort_comp(L, -1, -2)) {
219        if (i>u) luaL_error(L, "invalid order function for sorting");
220        lua_pop(L, 1);  /* remove a[i] */
221      }
222      /* repeat --j until a[j] <= P */
223      while (lua_rawgeti(L, 1, --j), sort_comp(L, -3, -1)) {
224        if (j<l) luaL_error(L, "invalid order function for sorting");
225        lua_pop(L, 1);  /* remove a[j] */
226      }
227      if (j<i) {
228        lua_pop(L, 3);  /* pop pivot, a[i], a[j] */
229        break;
230      }
231      set2(L, i, j);
232    }
233    lua_rawgeti(L, 1, u-1);
234    lua_rawgeti(L, 1, i);
235    set2(L, u-1, i);  /* swap pivot (a[u-1]) with a[i] */
236    /* a[l..i-1] <= a[i] == P <= a[i+1..u] */
237    /* adjust so that smaller half is in [j..i] and larger one in [l..u] */
238    if (i-l < u-i) {
239      j=l; i=i-1; l=i+2;
240    }
241    else {
242      j=i+1; i=u; u=j-2;
243    }
244    auxsort(L, j, i);  /* call recursively the smaller one */
245  }  /* repeat the routine for the larger one */
246}
247
248static int sort (lua_State *L) {
249  int n = aux_getn(L, 1);
250  luaL_checkstack(L, 40, "");  /* assume array is smaller than 2^40 */
251  if (!lua_isnoneornil(L, 2))  /* is there a 2nd argument? */
252    luaL_checktype(L, 2, LUA_TFUNCTION);
253  lua_settop(L, 2);  /* make sure there is two arguments */
254  auxsort(L, 1, n);
255  return 0;
256}
257
258/* }====================================================== */
259
260
261static const luaL_Reg tab_funcs[] = {
262  {"concat", tconcat},
263  {"foreach", foreach},
264  {"foreachi", foreachi},
265  {"getn", getn},
266  {"maxn", maxn},
267  {"insert", tinsert},
268  {"remove", tremove},
269  {"setn", setn},
270  {"sort", sort},
271  {NULL, NULL}
272};
273
274
275LUALIB_API int luaopen_table (lua_State *L) {
276  luaL_register(L, LUA_TABLIBNAME, tab_funcs);
277  return 1;
278}
279
Note: See TracBrowser for help on using the repository browser.