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.

    --print("orderedNext: state = "..tostring(state) )
    if state == nil then
        -- the first time, generate the index
        t.__orderedIndex = __genOrderedIndex( t )
        key = t.__orderedIndex[1]
        return key, t[key]
    end
    -- fetch the next value
    key = nil
    for i = 1,table.getn(t.__orderedIndex) do
        if t.__orderedIndex[i] == state then
            key = t.__orderedIndex[i+1]
        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" and type2 == "number"
        or type1 == "string" and type2 == "string" then
        return op1 < op2 --comp by default
    elseif type1 == "boolean" and type2 == "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)


RecentChanges · preferences
edit · history
Last edited February 11, 2010 2:25 pm GMT (diff)