Sorted Iteration
lua-users home
wiki

The following code allows you to iterate in the sorted sequence of the keys of the table. The algorithm used is table.sort() with the default function. Using a custom sort algorithm is trivial--just modify the __genOrderedIndex. 

--[[
Ordered table iterator, allow to iterate on the natural order of the keys of a
table.

Example:
]]

function __genOrderedIndex( t )
    local orderedIndex = {}
    for key in pairs(t) do
        table.insert( orderedIndex, key )
    end
    table.sort( orderedIndex )
    return orderedIndex
end

function orderedNext(t, state)
    -- Equivalent of the next function, but returns the keys in the alphabetic
    -- order. We use a temporary ordered key table that is stored in the
    -- table being iterated.

    local key = nil
    --print("orderedNext: state = "..tostring(state) )
    if state == nil then
        -- the first time, generate the index
        t.__orderedIndex = __genOrderedIndex( t )
        key = t.__orderedIndex[1]
    else
        -- fetch the next value
        for i = 1,table.getn(t.__orderedIndex) do
            if t.__orderedIndex[i] == state then
                key = t.__orderedIndex[i+1]
            end
        end
    end

    if key then
        return key, t[key]
    end

    -- no more value to return, cleanup
    t.__orderedIndex = nil
    return
end

function orderedPairs(t)
    -- Equivalent of the pairs() function on tables. Allows to iterate
    -- in order
    return orderedNext, t, nil
end

Example usage: 

t = {
    ['a'] = 'xxx',
    ['b'] = 'xxx',
    ['c'] = 'xxx',
    ['d'] = 'xxx',
    ['e'] = 'xxx',
}

print("Normal iterating with pairs")
for key, val in pairs(t) do
    print(key.." : "..val)
end

print("Ordered iterating")
for key, val in orderedPairs(t) do
    print(key.." : "..val)
end

--[[ Result:
Normal iterating with pairs
a : xxx
c : xxx
b : xxx
e : xxx
d : xxx
Ordered iterating
a : xxx
b : xxx
c : xxx
d : xxx
e : xxx
]]

There is also a compressed version, but it will replace pairs with orderedPairs. 

_10=pairs function _1(_6)local _2={}for _4 in _10(_6)do table.insert(_2,_4)end table.sort(_2)return _2 end function _3(_6,_5)if _5==nil then _6._7=_1(_6)_4=_6._7[1]return _4,_6[_4]end _4=nil for _8 = 1,table.getn(_6._7)do if _6._7[_8]==_5 then _4=_6._7[_8+1]end end if _4 then return _4,_6[_4]end _6._7=nil return end function _9(_6)return _3,_6,nil end pairs=_9

Comparison function for mixed table

When multiple type of key exists in a table, you can use the following comparison function: 

function cmp_multitype(op1, op2)
    local type1, type2 = type(op1), type(op2)
    if type1 ~= type2 then --cmp by type
        return type1 < type2
    elseif type1 == "number" or type1 == "string" then --type2 is equal to type1
        return op1 < op2 --comp by default
    elseif type1 == "boolean" then
        return op1 == true
    else
        return tostring(op1) < tostring(op2) --cmp by address
    end
end

function __genOrderedIndex( t )
    local orderedIndex = {}
    for key in pairs(t) do
        table.insert( orderedIndex, key )
    end
    table.sort( orderedIndex, cmp_multitype ) --### CANGE ###
    return orderedIndex
end

Example usage: 

t = { b="xxx", a="xxx", 100, [-5]=100 }

print("Ordered iterating")
for key, val in orderedPairs(t) do
    print(key.." : "..val)
end

--[[ Result:
Ordered iterating
-5 : 100
1 : 100
a : xxx
b : xxx
]]

Alternate Implementation (by BobC, Lua newbie, using wxLua 2.6.3): 

--------------------------------------
-- Insert value of any type into array
--------------------------------------
local function arrayInsert( ary, val, idx )
    -- Needed because table.insert has issues
    -- An "array" is a table indexed by sequential
    -- positive integers (no empty slots)
    local lastUsed = #ary + 1
    local nextAvail = lastUsed + 1

    -- Determine correct index value
    local index = tonumber(idx) -- Don't use idx after this line!
    if (index == nil) or (index > nextAvail) then
        index = nextAvail
    elseif (index < 1) then
        index = 1
    end

    -- Insert the value
    if ary[index] == nil then
        ary[index] = val
    else
        -- TBD: Should we try to allow for skipped indices?
        for j = nextAvail,index,-1 do
            ary[j] = ary[j-1]
        end
        ary[index] = val
    end
end

--------------------------------
-- Compare two items of any type
--------------------------------
local function compareAnyTypes( op1, op2 ) -- Return the comparison result
    -- Inspired by http://lua-users.org/wiki/SortedIteration
    local type1, type2 = type(op1),     type(op2)
    local num1,  num2  = tonumber(op1), tonumber(op2)
    
    if ( num1 ~= nil) and (num2 ~= nil) then  -- Number or numeric string
        return  num1 < num2                     -- Numeric compare
    elseif type1 ~= type2 then                -- Different types
        return type1 < type2                    -- String compare of type name
    -- From here on, types are known to match (need only single compare)
    elseif type1 == "string"  then            -- Non-numeric string
        return op1 < op2                        -- Default compare
    elseif type1 == "boolean" then
        return op1                              -- No compare needed!
         -- Handled above: number, string, boolean
    else -- What's left:   function, table, thread, userdata
        return tostring(op1) < tostring(op2)  -- String representation
    end
end

-------------------------------------------
-- Iterate over a table in sorted key order
-------------------------------------------
local function pairsByKeys (tbl, func)
    -- Inspired by http://www.lua.org/pil/19.3.html
    -- and http://lua-users.org/wiki/SortedIteration

    if func == nil then
        func = compareAnyTypes
    end

    -- Build a sorted array of the keys from the passed table
    -- Use an insertion sort, since table.sort fails on non-numeric keys
    local ary = {}
    local lastUsed = 0
    for key --[[, val--]] in pairs(tbl) do
        if (lastUsed == 0) then
            ary[1] = key
        else
            local done = false
            for j=1,lastUsed do  -- Do an insertion sort
                if (func(key, ary[j]) == true) then
                    arrayInsert( ary, key, j )
                    done = true
                    break
                end
            end
            if (done == false) then
                ary[lastUsed + 1] = key
            end
        end
        lastUsed = lastUsed + 1
    end

    -- Define (and return) the iterator function
    local i = 0                -- iterator variable
    local iter = function ()   -- iterator function
        i = i + 1
        if ary[i] == nil then
            return nil
        else
            return ary[i], tbl[ary[i]]
        end
    end
    return iter
end
For testing, here's a generic table pretty-printer: 

---------------------------------------------
-- Return indentation string for passed level
---------------------------------------------
local function tabs(i)
    return string.rep(".",i).." "   -- Dots followed by a space
end

-----------------------------------------------------------
-- Return string representation of parameter's value & type
-----------------------------------------------------------
local function toStrType(t)
    local function fttu2hex(t) -- Grab hex value from tostring() output
        local str = tostring(t);
        if str == nil then
            return "tostring() failure! \n"
        else
            local str2 = string.match(str,"[ :][ (](%x+)")
            if str2 == nil then
                return "string.match() failure: "..str.."\n"
            else
                return "0x"..str2
            end
        end
    end
    -- Stringify a value of a given type using a table of functions keyed
    -- by the name of the type (Lua's version of C's switch() statement).
    local stringify = {
        -- Keys are all possible strings that type() may return,
        -- per http://www.lua.org/manual/5.1/manual.html#pdf-type.
        ["nil"]			= function(v) return "nil (nil)"			    end,
        ["string"]		= function(v) return '"'..v..'" (string)'	    end,
        ["number"]		= function(v) return v.." (number)"			    end,
        ["boolean"]		= function(v) return tostring(v).." (boolean)"  end,
        ["function"]	= function(v) return fttu2hex(v).." (function)" end,
        ["table"]		= function(v) return fttu2hex(v).." (table)"	end,
        ["thread"]		= function(v) return fttu2hex(v).." (thread)"	end,
        ["userdata"]	= function(v) return fttu2hex(v).." (userdata)" end
    }
    return stringify[type(t)](t)
end

-------------------------------------
-- Count elements in the passed table
-------------------------------------
local function lenTable(t)		-- What Lua builtin does this simple thing?
    local n=0                   -- '#' doesn't work with mixed key types
    if ("table" == type(t)) then
        for key in pairs(t) do  -- Just count 'em
            n = n + 1
        end
        return n
    else
        return nil
    end
end

--------------------------------
-- Pretty-print the passed table
--------------------------------
local function do_dumptable(t, indent, seen)
    -- "seen" is an initially empty table used to track all tables
    -- that have been dumped so far.  No table is dumped twice.
    -- This also keeps the code from following self-referential loops,
    -- the need for which was found when first dumping "_G".
    if ("table" == type(t)) then	-- Dump passed table
        seen[t] = 1
        if (indent == 0) then
            print ("The passed table has "..lenTable(t).." entries:")
            indent = 1
        end
        for f,v in pairsByKeys(t) do
            if ("table" == type(v)) and (seen[v] == nil) then    -- Recurse
                print( tabs(indent)..toStrType(f).." has "..lenTable(v).." entries: {")
                do_dumptable(v, indent+1, seen)
                print( tabs(indent).."}" )
            else
                print( tabs(indent)..toStrType(f).." = "..toStrType(v))
            end
        end
    else
        print (tabs(indent).."Not a table!")
    end
end

--------------------------------
-- Wrapper to handle persistence
--------------------------------
function dumptable(t)   -- Only global declaration in the package
    -- This wrapper exists only to set the environment for the first run:
    -- The second param is the indentation level.
    -- The third param is the list of tables dumped during this call.
    -- Getting this list allocated and freed was a pain, and this
    -- wrapper was the best solution I came up with...
    return do_dumptable(t, 0, {})
end
Finally, some test cases: 
-- The Whole Enchillada
print("\ndumptable(_G=", _G, "):")
dumptable(_G)

-- Empty table --
print("\ndumptable({}):")
dumptable({})

-- Confusing table --
null={}
null[0]=[[0]]
null[ [[0]]]=0		-- Space after first open bracket is required
null[{}]={}
print("\ndumptable(null=", null, "):")
dumptable(null)

-- Module table --
print("\ndumptable(os=", os, "):")
dumptable(os)
With results: 
dumptable(_G=	table: 00324F88	):
The passed table has 41 entries:
 < WAY too long - snipped >

dumptable({}):
The passed table has 0 entries:

dumptable(null=	table: 00413F90	):
The passed table has 3 entries:
. 0 (number) = "0" (string)
. "0" (string) = 0 (number)
. 0x00413FB8 (table) has 0 entries: {
. }

dumptable(os=	table: 00327F60	):
The passed table has 11 entries:
. "clock" (string) = 0x00328190 (function)
. "date" (string) = 0x003281D0 (function)
. "difftime" (string) = 0x00328210 (function)
. "execute" (string) = 0x00328660 (function)
. "exit" (string) = 0x003286A0 (function)
. "getenv" (string) = 0x003286E0 (function)
. "remove" (string) = 0x00328720 (function)
. "rename" (string) = 0x00328740 (function)
. "setlocale" (string) = 0x00328780 (function)
. "time" (string) = 0x003287C8 (function)
. "tmpname" (string) = 0x00328808 (function)

This sorted iteration function is used on English Wiktionary ([Module:table]; [examples]). The default key sorting function assumes keys are numbers or strings, and that has not caused problems because few tables on Wiktionary use other types of keys. But it is easy to input your own key-sorting function. 

-- Warning! This function is only guaranteed to work if all keys are strings or numbers.
local function defaultKeySort(key1, key2)
  -- "number" < "string", so numbers will be sorted before strings.
  local type1, type2 = type(key1), type(key2)
  if type1 ~= type2 then
    return type1 < type2
  else
    return key1 < key2
  end
end

local function keysToList(t, keySort)
  local list = {}
  local index = 1
  for key in pairs(t) do
    list[index] = key
    index = index + 1
  end
  
  keySort = keySort or defaultKeySort
  
  table.sort(list, keySort)
  
  return list
end

-- Input a custom keySort function in the second parameter, or use the default one.
-- Creates a new table and closure every time it is called.
local function sortedPairs(t, keySort)
  local list = keysToList(t, keySort, true)
  
  local i = 0
  return function()
    i = i + 1
    local key = list[i]
    if key ~= nil then
      return key, t[key]
    else
      return nil, nil
    end
  end
end
RecentChanges · preferences
edit · history
Last edited April 4, 2018 8:42 am GMT (diff)