Ordered Table Simple

wiki

We don't use a nextindex table, since it takes to long to traverse compared to a inassociative table holding the keys, also the table holding the keys is placed insided the __index table for a fast lookup, in simple tests this method had a better benchmark compared to the other, plus we can delete items via <this>:del( key )

--[[

   LUA 5.1 compatible

   

   Ordered Table

   keys added will be also be stored in a metatable to recall the insertion oder

   metakeys can be seen with for i,k in ( <this>:ipairs()  or ipairs( <this>._korder ) ) do

   ipairs( ) is a bit faster

   

   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 = {}

   -- set methods

   mt.__index = {

      -- set key order table inside __index for faster lookup

      _korder = {},

      -- traversal of hidden values

      hidden = function() return pairs( mt.__index ) end,

      -- traversal of table ordered: returning index, key

      ipairs = function( self ) return ipairs( self._korder ) end,

      -- traversal of table

      pairs = function( self ) return pairs( self ) end,

      -- traversal of table ordered: returning key,value

      opairs = function( self )

         local i = 0

         local function iter( self )

            i = i + 1

            local k = self._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 )

         if self[key] then

            self[key] = nil

            for i,k in ipairs( self._korder ) do

               if k == key then

                  table.remove( self._korder, i )

                  return

               end

            end

         end

      end,

   }

   -- set new index handling

   mt.__newindex = function( self,k,v )

      if k ~= "del" and v then

         rawset( self,k,v )

         table.insert( self._korder, k )

      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:opairs()")

for i,v in t:opairs() do

   print( i,v )

end

print(">> t:del( 3 )")

t:del( 3 )

print(">> t:del( \"abc\" )")

t:del( "abc" )

print(">> t:opairs()")

for i,v in t:opairs() do

   print( i,v )

end

print(">> t.abc = 11")

t.abc = 11

print(">> t:opairs()")

for i,v in t:opairs() do

   print( i,v )

end

print(">> t.del = nil")

t.del = nil

print(">> t:del( 1 )")

t:del( 1 )

print(">> t:opairs()")

for i,v in t:opairs() 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       a       1

2       ab      2

3       abc     3

4       abcd    4

5       abcde   5

6       1       6

7       2       7

8       3       8

9       4       9

10      5       10

>> t:opairs()

a       1

ab      2

abc     3

abcd    4

abcde   5

1       6

2       7

3       8

4       9

5       10

>> t:del( 3 )

>> t:del( "abc" )

>> t:opairs()

a       1

ab      2

abcd    4

abcde   5

1       6

2       7

4       9

5       10

>> t.abc = 11

>> t:opairs()

a       1

ab      2

abcd    4

abcde   5

1       6

2       7

4       9

5       10

abc     11

>> t.del = nil

>> t:del( 1 )

>> t:opairs()

a       1

ab      2

abcd    4

abcde   5

2       7

4       9

5       10

abc     11

Other iterations, including iteration sorted by key

• OrderedTable
• SortedIteration
• SortedIterationSimple