# Sorted Iteration Simple

A simple approach using metatables to store the keys added in a table that can be sorted and then traversed vis <this>:ipairs() or <this>:spairs();

If one would need to access the table one could add a reference; holding the access functios in a metatable hides these from a normal traversal of the table but not from the lookup; still access is quite fast;

An implemention to view the table by sorted by values would be no problem if one doesn't delete any entries.

```--[[
LUA 5.1 compatible

Sorted Ordered Table
keys added will also be stored in a metatable
they can be called via for i,k in <this>:ipairs() do
where k is they key of <this> sorted by fsort
the table holding sorted keys is placed outside the metatable, so one cannot reach it except over the functions

variable names inside __index shouldn't be added, if so you must delete these again to access the metavariable
or change the metavariable names, , except for the 'del' command. thats the reason why one cannot change its value
]]--
function newT( t )
local mt,_korder = {},{}
local isSorted = true
-- set methods
-- index gets only called if the value is not found in the original table
-- overridden values can be accessed again by deleting the variable over t[key] = nil
mt.__index = {
-- traversal of hidden values
hidden = function() return pairs( mt.__index ) end,
-- traversal of table ordered: returning index, key
ipairs = function( self )
if not isSorted then
table.sort( _korder,fsort )
isSorted = true
end
return ipairs( _korder )
end,
-- traversal of table
pairs = function( self ) return pairs( self ) end,
-- traversal of table sorted: returning key,value
spairs = function( self )
if not isSorted then
table.sort( _korder,fsort )
isSorted = true
end
local i = 0
local function iter( self )
i = i + 1
local k = _korder[i]
if k then
return k,self[k]
end
end
return iter,self
end,
-- to be able to delete entries we must write a delete function
del = function( self,key )
-- check if key exists beforestarting the traversal
if self[key] then
self[key] = nil
for i,k in ipairs( _korder ) do
if k == key then
table.remove( _korder,i )
return
end
end
end
end,
}
-- set new index handling, is really on new index !!!
-- setting an non exisitng key to nil will pass here
mt.__newindex = function( self,k,v )
if k ~= "del" and v then
rawset( self,k,v )
table.insert( _korder,k )
isSorted = false
end
end
return setmetatable( t or {},mt )
end
-- CHILLCODE™
```
Testsuit:
```t = newT()

t["a"] = "1"
t["ab"] = "2"
t["abc"] = "3"
t["abcd"] = "4"
t["abcde"] = "5"
t[1] = 6
t[2] = 7
t[3] = 8
t[4] = 9
t[5] = 10

print(">> t:pairs()")
for k,v in t:pairs() do
print( k,v )
end
print(">> t:ipairs()")
for i,k in t:ipairs() do
print( i,k,t[k] )
end
print(">> t:spairs()")
for i,v in t:spairs() do
print( i,v )
end
print(">> t:del( 3 )")
t:del( 3 )
print(">> t:del( \"abc\" )")
t:del( "abc" )
print(">> t:spairs()")
for i,v in t:spairs() do
print( i,v )
end
print(">> t.abc = 11")
t.abc = 11
print(">> t:spairs()")
for i,v in t:spairs() do
print( i,v )
end
```
Output:
```>> t:pairs()
1       6
2       7
3       8
4       9
a       1
ab      2
abcd    4
abcde   5
5       10
abc     3
>> t:ipairs()
1       1       6
2       2       7
3       3       8
4       4       9
5       5       10
6       a       1
7       ab      2
8       abc     3
9       abcd    4
10      abcde   5
>> t:spairs()
1       6
2       7
3       8
4       9
5       10
a       1
ab      2
abc     3
abcd    4
abcde   5
>> t:del( 3 )
>> t:del( "abc" )
>> t:spairs()
1       6
2       7
4       9
5       10
a       1
ab      2
abcd    4
abcde   5
>> t.abc = 11
>> t:spairs()
1       6
2       7
4       9
5       10
a       1
ab      2
abc     11
abcd    4
abcde   5
```

### Other iterations, including iteration sorted by key

RecentChanges · preferences
edit · history
Last edited June 5, 2007 12:12 am GMT (diff)