Re: Lua Basics: tables as lists?

[Rici Lake <lua@...>]

On 23-Aug-05, at 12:04 PM, Warren Merrifield wrote:

> you could then, if you wanted to get a bit more fancy, set up
> metamethods on mytable so that it creates and stores the reverselist
> internally and updates it automatically when mylist is changed.

Sure. The point of my example was that it may not actually be necessary 
to do that, since in many common cases you don't care about the 
iteration order of the list, so just using a set make sense. (This is 
also true in Python, now that Python has Sets.)

The only awkwardness in Lua is creating the set in the first place (but 
see below); the table constructor syntax is awkward for sets unless the 
objects are strings which qualify as Lua names.

But everything else is quite simple:

1) Is `obj' in `set':  if set[obj] then ...
2) Put `obj' into `set': set[obj] = true
3) Iterate `set': for obj in pairs(set) do ...

In particular, step (2) is considerably faster than the equivalent for 
lists:
2a) Put `obj' into 'list': table.insert(list, obj)

So that leaves us with the problem of creating the set in the first 
place.

A couple of functions I find useful:

function wordset(s)
  local rv = {}
  for w in string.gfind(s, "%S+") do
    rv[w] = true
  end
  return rv
end
local binops = wordset"and or + - * / % > >= < <= =="

function lset(s)
  local rv = {}
  for w in string.gfind(s, "%s*([^\n]+)") do
    rv[w] = true
  end
  return rv
end
local cliches = lset[[
  We have to learn to adjust to the new realities.
  The situation is lamentable but we must be patient.
]]

In some cases, though, it is more convenient to use the following C 
function, which simply constructs a set from its arguments:

int makeset (lua_State *L) {
  int n = lua_gettop(L); /* Number of arguments */
  lua_newtable(L);
  lua_insert(L, 1);
  while (n--) {
    lua_pushboolean(L, 1);
    lua_settable(L, 1);
  }
  return 1;
}

local primes = makeset(2, 3, 5, 7, 11, 13, 17)

A slightly more efficient implementation if you're expecting a lot of 
arguments:

int makeset (lua_State *L) {
  int n = lua_gettop(L); /* Number of arguments */
  lua_newtable(L);
  if (n > 0) {
    lua_pushvalue(L, 1);
    lua_pushboolean(L, 1);
    lua_settable(L, -3);
    if (n > 1) {
      --n;
      lua_replace(L, 1);
      do {
        lua_pushboolean(L, 1);
        lua_settable(L, 1);
      } while (--n);
    }
  }
  return 1;
}