# Ordered Associative Table

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.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
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 3:47 am GMT (diff)