lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]



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;
}