Re: table / array sort and API annoyance

[Philipp Janda <siffiejoe@...>]

Am 09.06.2016 um 09:46 schröbte Volker Eckert:
> hi,

Hi!

> as a relative new user of lua, only a couple of months ago i stumbled
> upon the fact that non-contiguous arrays/tables can't be used with
> table.sort(). granted, it is not always clear for arbitrary keys,
> what the result would look like, but in this case it was an array
> with integer indices with a gap (or two), so i'd argue it's not too
> far out to want it sorted.

Of course not. But where do you want the gaps to go? You'll have to tell 
`table.sort` by supplying a custom comparator function. And you'll have 
to tell Lua how many elements you want sorted, because the built-in 
heuristic is not unambiguous when gaps are involved. You can do that 
using the `__len` metamethod:


    local t2 = { [1] = 1, [4] = 3, [5] = 4, [8] = 2 }
    setmetatable( t2, { __len = function() return 9 end } )

    local function cmp( a, b )
      if a == nil then
        return false
      elseif b == nil then
        return true
      else
        return a < b
      end
    end

    table.sort( t2, cmp )

    for i = 1, #t2 do
      print( i, t2[ i ] )
    end


> the annoying thing is that under lua it only fails if it is not the
> first entry that's missing (whereas under luajit it always fails):

That's coincidence. E.g. sorting the table `{ [2]=2, [3]=3 }` will 
silently do nothing on Lua *and* LuaJIT.

> i was wondering why table.sort() isn't written so that it always
> fails if the table/array is non-contiguous (because even in the case
> where it  doesn't, it doesn't actually sort).

In the specific case of `table.sort` it's probably consistency. In 
general it's performance reasons. To detect whether a table is a proper 
sequence (contiguous) is O(n) while the current length operator is 
O(log(n)).

> so, instead of the length check, just let it always auxsort() (like
> luajit does), which will then fail.

The difference is not whether `auxsort()` is called or not. The 
difference is that for this specific array LuaJIT thinks the length is 4 
while PUC-Rio Lua thinks it is 0. Both assumptions are reasonable.

> further, i think either all the functions from the table [sic!]
> namespace that only work with arrays

That would be most of them.

> should fail if used on a non-contiguous table/array (probably quite
> straightforward to implement, like ... maybe remove __len from them?)
> or they should do what it says on the tin (probably more tedious to
> implement).

Again, detecting a proper sequence (contiguous array) is costly (and has 
nothing to do with removing `__len`). And `__len` actually allows you to 
work with non-contiguous arrays in newer Lua versions.

> thanks,
> volker

Philipp