#include
#include
#include
static int
lnewindex(lua_State *L) {
luaL_checktype(L, 1, LUA_TTABLE);
lua_Integer idx = luaL_checkinteger(L, 2);
if (idx <= 0) {
return luaL_error(L, "The index should be positive (%d)", (int)idx);
}
lua_settop(L, 3);
lua_rawseti(L, 1, idx);
size_t rawlen = lua_rawlen(L, 1);
if (rawlen >= idx) {
return 0;
}
lua_rawgeti(L, 1, 0);
lua_Integer sparselen = luaL_checkinteger(L, -1);
if (sparselen < 0)
sparselen = -sparselen;
++sparselen;
lua_pushinteger(L, sparselen);
lua_rawseti(L, 1, 0);
lua_pushinteger(L, idx);
lua_rawseti(L, 1, -sparselen);
return 0;
}
static int
insert(lua_State *L, lua_Integer key, int n) {
int begin = 0, end = n;
int mid;
while (begin < end) {
mid = (begin + end)/2;
lua_rawgeti(L, 1, -mid-1);
lua_Integer v = luaL_checkinteger(L, -1);
lua_pop(L, 1);
if (v == key)
return 0; // replicate
if (v < key)
begin = mid + 1;
else
end = mid;
}
// insert before end
int i;
for (i=n;i>end;i--) {
lua_rawgeti(L, 1, -i);
lua_rawseti(L, 1, -i-1);
}
lua_pushinteger(L, key);
lua_rawseti(L, 1, -end-1);
return 1;
}
static lua_Integer
sort_sparse(lua_State *L, lua_Integer sparselen) {
size_t rawlen = lua_rawlen(L, 1);
lua_Integer i, n=0;
// insertion sort
for (i=0; i= idx) {
size_t i;
for (i = idx + 1; i <= rawlen; i++) {
if (lua_rawgeti(L, 1, i) != LUA_TNIL) {
lua_pushinteger(L, i);
lua_pushvalue(L, -2);
return 2;
}
lua_pop(L, 1);
}
return luaL_error(L, "Invalid index %d", (int)idx);
}
if (lua_rawgeti(L, 1, 0) != LUA_TNUMBER)
return luaL_error(L, "Invalid array");
lua_Integer sparselen = lua_tointeger(L, -1);
lua_pop(L, 1);
if (sparselen == 0)
return 0;
if (sparselen > 0) {
lua_pushcfunction(L, lsort);
lua_pushvalue(L, 1);
lua_pushinteger(L, sparselen);
lua_call(L, 2, 1); // resort sparse array
sparselen = lua_tointeger(L, -1);
lua_pop(L, 1);
} else {
sparselen = -sparselen;
}
// binary search
lua_Integer begin = 0, end = sparselen;
while (begin < end) {
lua_Integer mid = (begin + end)/2;
lua_rawgeti(L, 1, -mid-1);
lua_Integer v = luaL_checkinteger(L, -1);
lua_pop(L, 1);
if (v > idx) {
end = mid;
} else if (v < idx) {
begin = mid + 1;
} else {
begin = mid;
break;
}
}
if (begin >= sparselen)
return 0;
lua_rawgeti(L, 1, -begin-1);
idx = luaL_checkinteger(L, -1);
lua_rawgeti(L, 1, idx);
return 2;
}
static int
lpairs(lua_State *L) {
luaL_checktype(L, 1, LUA_TTABLE);
lua_rawgeti(L, 1, 0);
lua_Integer sparselen = luaL_checkinteger(L, -1);
if (sparselen > 0) {
sort_sparse(L, sparselen);
}
lua_pushcfunction(L, lnext);
lua_pushvalue(L, 1);
lua_pushnil(L);
return 3;
}
static int
llen(lua_State *L) {
luaL_checktype(L, 1, LUA_TTABLE);
lua_rawgeti(L, 1, 0);
lua_Integer sparselen = luaL_checkinteger(L, -1);
if (sparselen > 0) {
sparselen = sort_sparse(L, sparselen);
} else {
sparselen = -sparselen;
}
if (sparselen == 0) {
lua_pushinteger(L, lua_rawlen(L, 1));
return 1;
}
lua_rawgeti(L, 1, -sparselen);
return 1;
}
static int
lnewarray(lua_State *L) {
int n = lua_gettop(L);
lua_createtable(L, n, 0);
lua_pushvalue(L, lua_upvalueindex(1));
lua_setmetatable(L, -2);
int i;
for (i=1;i<=n;i++) {
lua_pushvalue(L, i);
lua_rawseti(L, -2, i);
}
lua_pushinteger(L, 0);
lua_rawseti(L, -2, 0);
return 1;
}
LUAMOD_API int
luaopen_array(lua_State *L) {
luaL_checkversion(L);
luaL_Reg metatable[] = {
{ "__newindex", lnewindex },
{ "__pairs", lpairs },
{ "__len", llen },
{ NULL, NULL },
};
luaL_newlib(L, metatable);
lua_pushcclosure(L, lnewarray, 1);
return 1;
}