Sorted Iteration
 |
||
|
Sorted Iteration |
|
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
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
--------------------------------------------- -- 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
-- 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)
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)