RE: Preserving Table Order

[RLake@...]

I'm intrigued to see that other people have faced this issue.

Joshua Jensen escribió:

> Unfortunately, there is no built-in way to do this is the hashed system
> of Lua tables.  A possible way to handle this, though, would be to:

> function table_add(table, key, value)
>    table[getn(table) + 1] = key
>    table[key] = value
> end

> function table_iterate(table, func)
>    for index = 1, getn(table) do
>         func(table[index], table[table[index]])
>    end
> end

Of course, that only works if the table does not have numeric keys, and if
you never use table_add when you meant to just set an existing key, or vice
versa. Part of the second problem could be solved, though:

function table_add(table, key, value)
     if not table[key] then table[getn(table) + 1] = key end
     table[key] = value
end

You don't actually need newindex to maintain such a table; you can do it
with settable. You simply use the above table_add function. I think
newindex is a good idea, but in this case I would use a settable tag method
because I think it would be better to not have to think about whether you
wanted to say tab.foo = 42 or table_add(tab, foo, 42);
anyway, tab.foo = 42 looks better. The settable method could also make sure
that you weren't inserting numeric keys, which would completely destroy the
integrity of the datastructure.

Another problem (sorry, I don't mean to be too critical) is that there is
no way of finding the "insertion order number" of a key, which means that
you may not be able to properly handle the case: table.foo = nil. If you
want the table to preserve insertion order even for reinsertion, even if
the value was deleted, then there's no problem, except that the deleted
keys will never be garbage collected. If you want the table to readjust
itself when the value of a key is modified, though, you've got a problem.

An alternative would be the table-of-tables approach I outlined in a
message last month regarding preserving nil values in tables. In summary:
table =
    {key_to_index = {theAnswer = 1, anotherAnswer = 2},
     index_to_key = {"theAnswer", "anotherAnswer"; n = 2},
     index_to_val = {42, 3.14159}
    }

-- WARNING: I just typed this into the message, so it may not work (or even
compile)
I don't happen to have Lua on this machine and the stuff I wrote to solve
this problem is at home, but I'll e-mail it to you if you like (and if this
doesn't work :-)

-- preserve insertion order in all cases (not a good idea imho)
function table_set(table, key, val)
 if key then
  local index = table.key_to_index[key]
  if index then
     table.index_to_val[index] = val
  else
     local n = table.index_to_key.n + 1
     table.index_to_key.n, table.key_to_index[key],
       table.index_to_key[n], table.index_to_val[n] =
       n, n, key, val
  end
 end
end

-- preserve insertion order except for deletion
function table_better_set(table, key, val)
 if key then
  local index = table.key_to_index[key]
  if index then
     if val then
       table.index_to_val[index] = val
     else
       table.key_to_index[key],
         table.index_to_key[index],
         table.index_to_val[index] =
           nil, nil, nil     -- how definite can you get
       if index == table.index_to_key.n then
        -- keep n small if possible
         table.index_to_key.n = nil
         table.index_to_key.n = getn(table.index_to_key)
       end
     end
  elseif val then
     local n = table.index_to_key.n + 1
     table.index_to_key.n, table.key_to_index[key],
       table.index_to_key[n], table.index_to_val[n] =
       n, n, key, val
  end
 end
end

function table_get(table, key)
  if key then
    local index = table.key_to_index[key]
    if index then
      return table.index_to_val[index]
    end
  end
end

function table_next(table, key)
  local index = 0
  if key then
    index = table.key_to_index[key]
    if not index then error("Invalid key in next") end
  end
  return table.index_to_key[index + 1], table.index_to_val[index + 1]
end

function table_new()
  return self = {key_to_index = {}, index_to_key = {n = 0}, index_to_val =
{}}
end

This involves a lot more overhead, but it's got some advantages (it can
preserve
insertion order or not if that's important to you, and it handles arbitrary
keys). However, it requires a gettable method as well, so it's going to
slug a bit.

> To be able to set up a tag method for this, though, to make it more
> natural, would require Edgar's idea of a newindex tag (I believe).

see above

> Plus, there is no way to replace the iteration for a for loop... That
> would be cool, though.

see <http://lua-users.org/wiki/ExtendingForAndNext>

Rici