Ordered Table

wiki

New version

-- Ordered Table

-- Written by Rici Lake. The author disclaims all rights and responsibilities,

-- and relinquishes the software below to the public domain.

-- Have fun with it.

--

-- The function Ordered creates a table which can iterate in order of its

-- entries. You'll need to modify pairs as indicated on the Lua wiki

-- (GeneralizedPairsAndIpairs) in order to use this feature.

--

-- Since stock Lua does not have constructors, you cannot "seed" the

-- table with an initializer. A patch for this is forthcoming; this function

-- was extracted from the tests for that patch.

--

-- The table does not allow deletion, so it might not be appropriate

-- for all cases. You can set a key to nil, which removes it from

-- the iteration, but the key is actually permanently in the table,

-- and setting it to a new value will restore it to its original place

-- in the table. Obviously, that's not ideal, but it was simple and

-- efficient, and it is always possible to compact a table by copying it.

--

-- Rather than use what seems to be the classic implementation, with

-- three tables: <key->ordinal, ordinal->key, ordinal->value>, we

-- use a regular key->value table, with an auxiliary linked list

-- key->nextkey.

-- 

-- The advantage of this setup is that we don't need to invoke a

-- metamethod for any case other than setting a new key (or a key

-- which has been previously set to nil), which is a significant

-- speed-up. It also makes it easy to implement the stability

-- guarantee. The disadvantage is that there is effectively a

-- memory-leak.

--

-- The table is fully stable; during an iteration, you can perform

-- an arbitrary modification (since keys are not ever actually deleted).

 

local function Ordered()

  -- nextkey and firstkey are used as markers; nextkey[firstkey] is

  -- the first key in the table, and nextkey[nextkey] is the last key.

  -- nextkey[nextkey[nextkey]] should always be nil.

 

  local key2val, nextkey, firstkey = {}, {}, {}

  nextkey[nextkey] = firstkey

 

  local function onext(self, key)

    while key ~= nil do

      key = nextkey[key]

      local val = self[key]

      if val ~= nil then return key, val end

    end

  end

 

  -- To save on tables, we use firstkey for the (customised)

  -- metatable; this line is just for documentation

  local selfmeta = firstkey

 

  -- record the nextkey table, for routines lacking the closure

  selfmeta.__nextkey = nextkey

 

  -- setting a new key (might) require adding the key to the chain

  function selfmeta:__newindex(key, val)

    rawset(self, key, val)

    if nextkey[key] == nil then -- adding a new key

      nextkey[nextkey[nextkey]] = key

      nextkey[nextkey] = key

    end

  end

 

  -- if you don't have the __pairs patch, use this:

  -- local _p = pairs; function pairs(t, ...)

  --    return (getmetatable(t).__pairs or _p)(t, ...) end

  function selfmeta:__pairs() return onext, self, firstkey end

 

  return setmetatable(key2val, selfmeta)

end

Iterating in the order of key insertion (old version)

The old version requires that keys not be numeric, although it doesn't check that. It also does not permit deletion. The constructor takes a table argument which is used as the base of the orderedTable. Entries in the preexisting table are not indexed, which means that they do not get iterated over by the provided iterator. This is often useful. The example shows just one application of this:

function orderedTable(t)

  local currentIndex = 1

  local metaTable = {}

    

  function metaTable:__newindex(key,value)

    rawset(self, key, value)

    rawset(self, currentIndex, key)

    currentIndex = currentIndex + 1

  end

  return setmetatable(t or {}, metaTable)

end



function ordered(t)

  local currentIndex = 0

  local function iter(t)

    currentIndex = currentIndex + 1

    local key = t[currentIndex]

    if key then return key, t[key] end

  end

  return iter, t

end

Example usage:

function show(t)

  print (t.__name .. ":")

  for k, v in ordered(t) do print(k, v) end

end



tab = orderedTable {__name = "table 1"}

tab.firstName = "Rici"

tab.lastName = "Lake"

tab.maternalLastName = "Papert"

show(tab)

Other implementations of key-insertion order iteration

Both of the following versions do allow key deletion but will fail if a key is deleted during iteration. Also, they use table.remove to remove keys and values, which can lead to quadratic slow-down.

• MakingLuaLikePhp (Section on PHP tables)
• Beginning Lua Programming, p. 262 (see LuaBooks). The code is online via the download link at [1] (see Chapter 08/orderedtbl.lua). Note, however, that this code requires a correction (noted on p. 306) to make {__mode = "k"} the metatable for the RealTbls, NumToKeys, and KeyToNums tables.

Other iterations, including iteration sorted by key

• OrderedAssociativeTable
• SortedIteration
• OrderedTableSimple