Sorted Iteration

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
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
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,
["function"]	= function(v) return fttu2hex(v).." (function)" end,
["table"]		= function(v) return fttu2hex(v).." (table)"	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)