What techniques that everyone should know?

[Wojak]

This is an implementation without #:

Code: Select all

function isArray(tab)
    local countT = 0
    local countA = 0
    local i = 1
    for k,_ in pairs(tab) do
    	countT = countT + 1
    	if tab[i] then
        	countA = countA + 1
        end
    	if countT ~= countA then
        	return false
        end
        i = i + 1
    end
    return true
end

And this is a duel between # and no#:

Code: Select all

t = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}
t2 = {5,4,8,w=5,6,4,8}

function isArray(tab)
    local countT = 0
    local countA = 0
    local i = 1
    for k,_ in pairs(tab) do
    	countT = countT + 1
    	if tab[i] then
        	countA = countA + 1
        end
    	if countT ~= countA then
        	return false
        end
        i = i + 1
    end
    return true
end
local function is_array(t)
      local count = 0
      for k, _ in pairs(t) do
        if type(k) ~= 'number' or k < 1 or math.floor(k) ~= k then return false end
        count = count + 1
      end
      return count == #t
end
print(isArray(t)) --true
print(is_array(t)) --true
print(isArray(t2)) --flase
print(is_array(t2)) --false
t[2] = nil
print(#t) --20
print(isArray(t)) --false
print(is_array(t)) --false
t[20]=nil
t[18]=nil
print(#t) --17?
print(isArray(t)) --false
print(is_array(t)) --true

no# should always treat arrays with embedded nil as not arrays while # can change it's mind...
(tested with lua 5.1, 5.2 JIT 2.0.0,2.0.1,2.0.2 – same thing)

[kikito]

Well, that confirms my initial suspicions. # can't be trusted

Your implementation is interesting, but note that it will return false on some arrays (those with false in their values):

Code: Select all

print(isArray({1,2,false,4})) -- false, but should be true

Also, it uses too many variables - 'i', 'countT' and 'countA' work almost the same way. Here's an implementation that uses the same principle (increasing an integer to check each key), with less variables, and with the false values bug fixed:

Code: Select all

function isArray(t)
    local i = 0
    for _ in pairs(t) do
       i = i + 1
       if t[i] == nil then return false end
    end
    return true
end

I like this one a lot. It is efficient and clean. It needs a bit more testing, but I think it might be better than my original implementation.

Code: Select all

print(isArray({1,2,false,4})) -- true, false-values now work
print(isArray({5,4,8,w=5,6,4,8})) --false, hash keys make it fail

t = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}

print(isArray(t)) --true
t[2] = nil
print(#t) --20
print(isArray(t)) --false
t[20]=nil
t[18]=nil
print(#t) --17
print(isArray(t)) --false

[Wojak]

Also, it uses too many variables - 'i', 'countT' and 'countA' work almost the same way. Here's an implementation that uses the same principle that you're using (increasing an integer to check each key), with less variables, and with the false values bug fixed:

Code: Select all

function isArray(t)
    local i = 0
    for _ in pairs(t) do
       i = i + 1
       if t[i] == nil then return false end
    end
    return true
end

Great job!
I had a strange feeling that I've missed something...

[Roland_Yonaba]

Code: Select all

function isArray(t)
    local i = 0
    for _ in pairs(t) do
       i = i + 1
       if t[i] == nil then return false end
    end
    return true
end

Wojak and Kikito, this is brilliant.
The t incremental check trick is soooo clean.
God, I love this forum.

One question, though. According to the Lua documentation, pairs would traverse a table in an unpredictable manner. This is true for dict-tables. But is it guaranteed that, no matter what the Lua implementation is, pairs will just behave like ipairs when given a Lua array ?

[Wojak]

One question, though. According to the Lua documentation, pairs would traverse a table in an unpredictable manner. This is true for dict-tables. But is it guaranteed that, no matter what the Lua implementation is, pairs will just behave like ipairs when given a Lua array ?

Even if there is no guarantee, it simply don't matter wit this implementation

edit:

Code: Select all

t={[10]=10,[9]=9,[8]=8,[7]=7,[6]=6,[5]=5,[4]=4,[3]=3,[2]=2,[1]=1}
for i,k in pairs(t) do -- not in order
    print(k)
end
print(t[5])
for i,k in ipairs(t)do --in order
    print(k)
end

[Inny]

Code: Select all

function isArray(t)
    local i = 0
    for _ in pairs(t) do
       i = i + 1
       if t[i] == nil then return false end
    end
    return true
end

This is really clever, I like it, with the exception that something that is array-like wouldn't fit in here. That is to say, if you keep 'n' as the length of the array as a member of the table, then isArray is false. Maybe I'm not understanding our semantics, are we trying to discover nils embedded in the table's integer indexes as a means to disqualify it, or as a way to detect when the underlying struct no longer takes advantage of the array optimization?

[kikito]

This is really clever, I like it, with the exception that something that is array-like wouldn't fit in here. That is to say, if you keep 'n' as the length of the array as a member of the table, then isArray is false.

As far as I know, table.getn and table.setn were deprecated in Lua 5.1 and removed in 5.2, as well as using a key called 'n' to handle the length. The "standard" definition of array does not include any non-array values any more (except for backwards-compatibility with Lua 5.0 libraries), so I don't think this is an issue.

Maybe I'm not understanding our semantics, are we trying to discover nils embedded in the table's integer indexes as a means to disqualify it, or as a way to detect when the underlying struct no longer takes advantage of the array optimization?

Both.

[slime]

The # operator, ipairs, table.insert, and table.remove all will not work as expected on any "array with holes" in Lua (including, for example, {1, 2, nil, 3}). Either don't use "arrays with holes" at all, or don't use the previously mentioned functions/operators with them.

If the array has "holes" (that is, nil values between other non-nil values), then #t can be any of the indices that directly precedes a nil value (that is, it may consider any such nil value as the end of the array).

[master both]

Since I use the # operator a lot, I write this function to remove "holes" from an array. I'll just leave it here if someone wants to use it.

Code: Select all

 
function removeholes(t)
	local n = 0
	local lasti = 0
	for i,v in pairs(t) do
		if i > lasti then
			lasti = i
		end
	end
	for i = 1, lasti do
		if t[i] == nil then
			n = n + 1
		end
	end
	for y = 1, n do
		for i = 1, lasti do
			if t[i] == nil then
				t[i] = t[i + 1]
				t[i + 1] = nil
			end	
		end
	end
end
 

[Nixola]

If I get it correctly, you can just use table.maxn instead of the first loop:

Code: Select all

     
    function removeholes(t)
       local n = 0
       local lasti = table.maxn(t)
       for i = 1, lasti do
          if t[i] == nil then
             n = n + 1
          end
       end
       for y = 1, n do
          for i = 1, lasti do
             if t[i] == nil then
                t[i] = t[i + 1]
                t[i + 1] = nil
             end   
          end
       end
    end