Sorted Iteration Simple

wiki

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 fsort = function( a,b ) return tostring(a) < tostring(b) end
   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™

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

>> 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

• OrderedTable
• OrderedTableSimple
• SortedIteration