Ordered Associative Table
lua-users home
wiki

The following code provides a simple and efficient way to maintain a sorted index over the keys in a table and then iterate over the table using that sorted index. We first examine the simpler case when deletions are prohibited.

TAKE ONE

--// CHILL CODE ™ //--
-- table.ordered( [comp] ) 
--
-- Lua 5.x add-on for the table library.
-- Table using sorted index.  Uses binary table for fast Lookup.
-- http://lua-users.org/wiki/OrderedTable by PhilippeFremy 

-- table.ordered( [comp] )
-- Returns an ordered table. Can only take strings as index.
-- fcomp is a comparison function behaves behaves just like
-- fcomp in table.sort( t [, fcomp] ).
function table.ordered(fcomp)
  local newmetatable = {}
  
  -- sort func
  newmetatable.fcomp = fcomp

  -- sorted subtable
  newmetatable.sorted = {}

  -- behavior on new index
  function newmetatable.__newindex(t, key, value)
    if type(key) == "string" then
      local fcomp = getmetatable(t).fcomp
      local tsorted = getmetatable(t).sorted
      table.binsert(tsorted, key , fcomp)
      rawset(t, key, value)
    end
  end

  -- behaviour on indexing
  function newmetatable.__index(t, key)
    if key == "n" then
      return table.getn( getmetatable(t).sorted )
    end
    local realkey = getmetatable(t).sorted[key]
    if realkey then
      return realkey, rawget(t, realkey)
    end
  end

  local newtable = {}

  -- set metatable
  return setmetatable(newtable, newmetatable)
end 
		
--// table.binsert( table, value [, comp] )
--
-- LUA 5.x add-on for the table library.
-- Does binary insertion of a given value into the table
-- sorted by [,fcomp]. fcomp is a comparison function
-- that behaves like fcomp in in table.sort(table [, fcomp]).
-- This method is faster than doing a regular
-- table.insert(table, value) followed by a table.sort(table [, comp]).
function table.binsert(t, value, fcomp)
  -- Initialise Compare function
  local fcomp = fcomp or function( a, b ) return a < b end

  --  Initialise Numbers
  local iStart, iEnd, iMid, iState =  1, table.getn( t ), 1, 0

  -- Get Insertposition
  while iStart <= iEnd do
    -- calculate middle
    iMid = math.floor( ( iStart + iEnd )/2 )

    -- compare
    if fcomp( value , t[iMid] ) then
      iEnd = iMid - 1
      iState = 0
    else
      iStart = iMid + 1
      iState = 1
    end
  end

  local pos = iMid+iState
  table.insert( t, pos, value )
  return pos
end

-- Iterate in ordered form
-- returns 3 values i, index, value
-- ( i = numerical index, index = tableindex, value = t[index] )
function orderedPairs(t)
  return orderedNext, t
end
function orderedNext(t, i)
  i = i or 0
  i = i + 1
  local index = getmetatable(t).sorted[i]
  if index then
    return i, index, t[index]
  end
end

Tests: 

t2= table.ordered()
t2["A"] = 1
t2.B = 2
t2.C = 3
t2.D = 4
t2.E = 5
t2.F = 6
t2.G = 7
t2.H = 8

print("Normal iteration ordered table")
-- will iterate over the table by next index
table.foreach( t2, print )

Results: 

Normal iteration ordered table
A       1
C       3
B       2
E       5
D       4
G       7
F       6
H       8

Tests: 

print("Ordered Iteration")
for i,index,v in orderedPairs(t2) do
  print(index, v)
end

Results: 

Ordered Iteration
A       1
B       2
C       3
D       4
E       5
F       6
G       7
H       8

Tests: 

-- same example but reveres ordered
t2= table.ordered( function(a,b) return b < a end )
t2["A"] = 1
t2.B = 2
t2.C = 3
t2.D = 4
t2.E = 5
t2.F = 6
t2.G = 7
t2.H = 8


print("Ordered Iteration of Reverse")
for i,index,v in orderedPairs(t2) do
  print(index, v)
end

Results: 

Ordered Iteration of Reverse
H       8
G       7
F       6
E       5
D       4
C       3
B       2
A       1

TAKE TWO

Now due to the problem that one cannot delete any entries, another option is to totally switch to a binary table and accessing it through t[index], while doing the sorting things in metatables. 

--// CHILL CODE ™ //--
-- table.ordered( [sorted reverse], [type] )  v 2

-- Lua 5.x add-on for the table library
-- Table using sorted index, with binary table for fast lookup.
-- http://lua-users.org/wiki/OrderedTable by PhilippeFremy 

-- table.ordered( [sorted reverse], [type] )
-- Gives you back a ordered table, can only take entered type
-- as index returned by type(index), by default "string"
-- sorted reverse, sorts the table in reverse order, else normal
-- stype is the deault index type returned by type( index ),
-- by default "string", it is only pssible to set one type as index
-- will effectively create a binary table, and will always lookup
-- through binary when an index is called
function table.ordered(ireverse, stype)
  local newmetatable = {}
  
  -- set sort function
  if ireverse then
    newmetatable._ireverse = 1
    function newmetatable.fcomp(a, b) return b[1] < a[1] end
  else
    function newmetatable.fcomp(a, b) return a[1] < b[1] end
  end

  -- set type by default "string"
  newmetatable.stype = stype or "string"

  -- fcomparevariable
  function newmetatable.fcompvar(value)
    return value[1]
  end

  -- sorted subtable
  newmetatable._tsorted = {}

  -- behaviour on new index
  function newmetatable.__newindex(t, key, value)
    if type(key) == getmetatable(t).stype then
      local fcomp = getmetatable(t).fcomp
      local fcompvar = getmetatable(t).fcompvar
      local tsorted = getmetatable(t)._tsorted
      local ireverse = getmetatable(t)._ireverse
      -- value is given so either update or insert newly
      if value then
        local pos, _ = table.bfind(tsorted, key, fcompvar, ireverse)
        -- if pos then update the index
        if pos then
          tsorted[pos] = {key, value}
        -- else insert new value
        else
          table.binsert(tsorted, {key, value}, fcomp)
        end
      -- value is nil so remove key
      else
        local pos, _ = table.bfind(tsorted, key, fcompvar, ireverse)
        if pos then
          table.remove(tsorted, pos)
        end
      end
    end
  end

  -- behavior on index
  function newmetatable.__index(t, key)
    if type(key) == getmetatable(t).stype then
      local fcomp = getmetatable(t).fcomp
      local fcompvar = getmetatable(t).fcompvar
      local tsorted = getmetatable(t)._tsorted
      local ireverse = getmetatable(t)._ireverse
      -- value if key exists
      local pos, value = table.bfind(tsorted, key, fcompvar, ireverse)
      if pos then
        return value[2]
      end
    end
  end

  -- set metatable
  return setmetatable({}, newmetatable)
end
		
--// table.binsert( table, value [, comp] )

-- Lua 5.x add-on for the table library
-- Binary inserts given value into the table sorted by [,fcomp]
-- fcomp is a comparison function that behaves just like
-- fcomp in table.sort( table [, comp] ).
-- This method is faster than doing a regular
-- table.insert(table, value) followed by a table.sort(table [, comp]).
function table.binsert(t, value, fcomp)
  -- Initialize compare function
  local fcomp = fcomp or function(a, b) return a < b end

  -- Initialize numbers
  local iStart, iEnd, iMid, iState =  1, table.getn( t ), 1, 0

  -- Get insert position
  while iStart <= iEnd do
    -- calculate middle
    iMid = math.floor((iStart + iEnd) / 2)

    -- compare
    if fcomp(value , t[iMid]) then
      iEnd = iMid - 1
      iState = 0
    else
      iStart = iMid + 1
      iState = 1
    end
  end

  local pos = iMid+iState
  table.insert(t, pos, value)
  return pos
end


--// table.bfind(table, value [, compvalue] [, reverse])

-- Lua 5.x add-on for the table library.
-- Binary searches the table for value.
-- If the value is found it returns the index and the value of
-- the table where it was found.
-- fcompval, if given, is a function that takes one value and
-- returns a second value2 to be compared with the input value,
-- e.g. compvalue = function(value) return value[1] end
-- If reverse is given then the search assumes that the table
-- is sorted with the biggest value on position 1.

function table.bfind(t, value, fcompval, reverse)
  -- Initialize functions
  fcompval = fcompval or function(value) return value end
  fcomp = function(a, b) return a < b end
  if reverse then
    fcomp = function(a, b) return a > b end
  end

  -- Initialize Numbers
  local iStart, iEnd, iMid = 1, table.getn(t), 1

  -- Binary Search
  while (iStart <= iEnd) do
    -- calculate middle
    iMid = math.floor((iStart + iEnd) / 2)

    -- get compare value
    local value2 = fcompval(t[iMid])

    if value == value2 then
      return iMid, t[iMid]
    end

    if fcomp(value , value2) then
      iEnd = iMid - 1
    else
      iStart = iMid + 1
    end
  end
end

-- Iterate in ordered form
-- returns 3 values i , index, value
-- ( i = numerical index, index = tableindex, value = t[index] )
function orderedPairs(t)
  return orderedNext, t
end
function orderedNext(t, i)
  i = i or 0
  i = i + 1
  local indexvalue = getmetatable(t)._tsorted[i]
  if indexvalue then
    return i, indexvalue[1], indexvalue[2]
  end
end

Tests: 

t2 = table.ordered()
if t2 then
  print( t2 )
end
t2["A"] = 1
t2.B = 2
t2.C = 3
t2.D = 4
t2.E = 5
t2.F = 6
t2.G = 7
t2.H = 8

print("Ordered Iteration")
for i,index,v in orderedPairs(t2) do
  print( index, v )
end

Results: 

table: 07864640
Ordered Iteration
A       1
B       2
C       3
D       4
E       5
F       6
G       7
H       8

Tests: 

-- same example but reveres ordered
t2= table.ordered( "reverse" )
t2["A"] = 1
t2.B = 2
t2.C = 3
t2.D = 4
t2.E = 5
t2.F = 6
t2.G = 7
t2.H = 8

print("Ordered Iteration of Reverse")
for i,index,v in orderedPairs(t2) do
  print(index, v)
end

Results: 

Ordered Iteration of Reverse
H       8
G       7
F       6
E       5
D       4
C       3
B       2
A       1

Tests: 

print("Set one Letter nil")
t2.E = nil
print("Ordered Iteration of Reverse")
for i,index,v in orderedPairs(t2) do
  print(index, v)
end

Results: 

Set one Letter nil
Ordered Iteration of Reverse
H       8
G       7
F       6
D       4
C       3
B       2
A       1

Tests: 

print("Update one value")
t2.F = "updated"
print("Ordered Iteration of Reverse")
for i,index,v in orderedPairs(t2) do
  print(index, v)
end

Results: 

Update one value
Ordered Iteration of Reverse
H       8
G       7
F       updated
D       4
C       3
B       2
A       1

Tests: 

print("Add with a no confirm key")
-- will simply be not added
t2[6] = "add"

print( "Add a key" )
t2.a = "new key1"
t2.Z = "new key 2"
t2.d = "??"

print( "Ordered Iteration of Reverse" )
for i,index,v in orderedPairs( t2 ) do
	print( index, v )
end

-- get a key
print( t2.Z )

Results: 

Add with a no confirm key
Add a key
Ordered Iteration of Reverse
d       ??
a       new key1
Z       new key 2
H       8
G       7
F       updated
D       4
C       3
B       2
A       1
new key 2

Tests: 

-- Speed testing
-- build a n big inassociative table
-- search it n2 times by hash clac used tim
n1 = 100000
n2 = 100000

t = {}
i0 = os.clock()
for i = 1, n1 do
  t[tostring(i)] = i
end
local i1 = os.clock()
for i = 1, n2 do
  local v = i, t[tostring(i)]
  --print(v , i)
end
print("Normal test of inassociative table")
print("Time to add  "..n2.." Items: "..(i1-i0))
print(os.clock())
print(i1)
print(os.clock() - i1)
print("Time to search  "..n1.." Items: "..(os.clock() - i1))
-- do one sort
i0 = os.clock()
local ts = {}
table.foreach(t, function(i,v) table.insert(ts, {i,i}) end)
table.sort(ts, function(a, b) return b[1] < a[1] end )
print("Normalsort time: "..(os.clock()-i0))

-- Speed test with a ordered table
t = table.ordered()
i0 = os.clock()
for i = 1, n1 do
  t[tostring(i)] = i
end
local i1 = os.clock()
for i = 1, n2 do
  local v = i, t[tostring(i)]
  --print(v , i)
end
print("Normal test of Ordered inassociative table")
print("Time to add  "..n2.." Items: "..(i1-i0))
print(os.clock())
print(i1)
print("Time to search  "..n1.." Items: "..(os.clock() - i1))

Results: 

Normal test of inassociative table
Time to add  100000 Items: 1.6409999999996
19960.765
19960.125
0.63999999999942
Time to search  100000 Items: 0.63999999999942
Normalsort time: 2.8280000000013
Normal test of Ordered inassociative table
Time to add  100000 Items: 52.281999999999
20021.593
20015.875
Time to search  100000 Items: 5.7180000000008

As shown, the code become very slow when adding new keys compared to the normal adding by index, around 100 times, and we are around 10 times slower when searching for a index, that is acceptable I think. Then I created a sorted array of the index from the normal table, and the result was again faster than the number of searches on the binary table. That brings me back to SortedIteration, which is the best way of doing what we want unless you need to run through your table more often than you check or add a value. Only in that specific case would this method be faster. Well, at least good to know :)

RecentChanges · preferences
edit · history
Last edited February 22, 2007 4:47 am GMT (diff)