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