Simple sort of table array

[vortizee]

I can’t wrap my head around sorting a table constructed like so: pcs.A = {}
pcs.A[1] = { x, y, id } pcs.A[2] = { x, y, id } — values inside those brackets used to place a piece on a map at coordinates pcs.A[1], pcs.A[2].

The sorting function should order pcs.A by comparing distance to some origin x0, y0, derived from an external function that calculates kwikDist(pcs.A[1], pcs.A[2], x0, y0). I just don’t know the syntax to construct the sort, and of course, there’d be other tables that would need sorting too: pcs.B, pcs.C. The tables are pretty small (max 60 units) so speed is not a critical issue, but they are recreated every few minutes as the origin moves.

Sorting function: return kwikDist( pcs.A[1], pcs.A[2], xo, yo ) < kwikDist( pcs.A[i+1][1], pcs.A[i+1][2], xo, yo )

[airstruck]

Is this what you're trying to do?

Code: Select all

table.sort(pcs.A, function (a, b)
    return kwikDist(a[1], a[2], xo, yo) < kwikDist(b[1], b[2], xo, yo)
end)

[vortizee]

Something like that, yes. But how does the function know what a[1] a[2] are? That’s what doesn’t penetrate my sclerotic brain.

[vortizee]

Bingo! And bingo! Worked like a charm first time. I wrote a dozen other functions intuitively that error’ed out because I couldn’t (and can’t) figure out how the interpreter links a and b to the array. Thanks.

[zorg]

Because tables are passed by reference; a and b are passed in as parameters, those are tables themselves, so you can index them, which is what the function airstruck posted does.

[Positive07]

First you need to understand that tables are passed as reference, that is:

Code: Select all

a = { var = "something" }
print(a.var) -- something
b = a
print(b.var) -- something
b.var = "anything"
print(b.var) -- anything
print(a.var) -- anything

This of course applies to functions too so:

Code: Select all

a = {var = "something"}
print(a.var) -- something
b = function (tab)
   tab.var = "anything"
end
b(a)
print(a.var) -- anything

Now if you look at the definition of [manual]table.sort[/manual]

table.sort (table, comp)

Sorts table elements in a given order, in-place, from table[1] to table[n], where n is the length of the table. If comp is given, then it must be a function that receives two table elements, and returns true when the first is less than the second (so that not comp(a[i+1],a) will be true after the sort)...

So this tells us that table sort, sorts an array like table, and if a comp function is specified it uses that to perform the comparison.

This comp function is called with two arguments, those two arguments are elements from the original table, if the function returns true then the second element is "bigger" than the other (I use quotes because bigger is ambiguouse, you may be sorting backwards)

Well so now we know how to sort an array, your array is an array of tables, so when you sort that array, the comp function is called with two arguments as I said before, and those two arguments are elements of the array, so basically they are one of those tables you stored in the array! and as I said before, this are references so we can index them the same as we would do with the original table.

That leads to the code posted by airstruck

Code: Select all

table.sort(pcs.A, function (a, b)
    return kwikDist(a[1], a[2], xo, yo) < kwikDist(b[1], b[2], xo, yo)
end)

Hope that helps, any doubts just ask!

[ivan]

Caching kwikDist is faster and makes it more obvious how table.sort works:

Code: Select all

local kwik = {}
for k, v in ipairs(pcs.A) do
  kwik[v] = kwikDist(v[1], v[2], xo, yo)
end

table.sort(pcs.A, function (a, b)
    return kwik[a] < kwik[b]
end)

[vortizee]

Okay, thanks for the explanations. I’ve read them twice. I’ll need to read them a number of times more (lol — really!). Because I still don’t understand why the sort knows that ‘a' refers to { pcs.A[1][1], pcs.A[1][2] } and ‘b' to { pcs.A[2][1], pcs.A[2][2] }, and not, say, pcs.A[1][3], pcs.A[2][3]. I’m starting to get the picture after the third read. To help me understand, if I wanted to sort them only by the latter (strings), would it be like below? (Hit me on the head if not.)

Code: Select all

table.sort(pcs.A, function (a,b)
  return a[3] < b[3]
end)

All the functions are in a local array of functions: local f = { } f.funcName = function() end f.kwikDist = function() end. I thought that meant they were already cached somehow. But I think I see what ivan is suggesting. Where the table is keyed by a sequential number, would “for i=1,#pcs.A do” be slower than a "for j, v in ipairs(pcs.A) do” loop?

On to the fourth read. . .

[zorg]

Okay, so this is how i could think to explain it a bit further:

I can’t wrap my head around sorting a table constructed like so:
pcs.A = {}
pcs.A[1] = { x, y, id }; pcs.A[2] = { x, y, id }

Code: Select all

local pcs = {} -- Nothing weird here, it's a table; the fact it's local or not doesn't mean anything in this example.
pcs.A = {} -- Another table, key is the string 'A', so pcs['A'] would have worked as well
pcs.A[1] = { x, y, id } -- So, the first numeric index of pcs.A has three numeric fields, an x and y coordinate, probably a number, and an id.

— values inside those brackets used to place a piece on a map at coordinates pcs.A[1], pcs.A[2].

I'm guessing you mean that the coordinates are inside them, as you defined it before:

Code: Select all

local i = 1 -- for example
-- this is how the coords could be accessed.
local xcoord, ycoord = pcs.A[i][1], pcs.A[i][2] -- since, you know, you defined numeric indices inside pcs.A[i], not string ones ('x', 'y')

So far probably no issues at all, i just felt i needed to clear up everything.

So, airstruck's sort function would work nicely at sorting the tables indexed by i in pcs.A (pcs.A where i = 1 to #pcs.A).

table.sort takes for its parameters the table it needs to sort, which is pcs.A at the moment, and a sorting function that is consistent at ordering elements, and works on two at a time; a and b in the given code example.

When called, table.sort internally calls that sorting function with elements from pcs.A; whether it's consecutive in order or not, i don't know and frankly don't care, the point is it should sort the table.

A visual aid of sorts:

Code: Select all

local sorting_function = function (a, b) return kwikDist(a[1], a[2], xo, yo) < kwikDist(b[1], b[2], xo, yo) end
table.sort(pcs.A, sorting_function)
-- let's say we have 3 elements in the table: (7,9), (4,2), (1,3); and our xo and yo are (0,0).
-- first iteration of table.sort: (4,2), (7,9), (1,3) -- compared 1st and 2nd
-- second iteration: (1,3), (7,9), (4,2) -- compared 1st and 3rd
-- third iteration: (1,3), (4,2), (7,9) -- compared 2nd and 3rd

Now my math may be wrong with the euclidean distances of such points, but to my eyes, they look sorted.

Edit:

Because I still don’t understand why the sort knows that ‘a' refers to { pcs.A[1][1], pcs.A[1][2] } and ‘b' to { pcs.A[2][1], pcs.A[2][2] }, and not, say, pcs.A[1][3], pcs.A[2][3].

No. The sort goes over the table you give it, a and b will be filled with the elements the sort puts in those variables so that it can sort all the elements. It's not your job to know how the two parameters of -any given- sorting function, or even the builtin one, works. And it's not the job of the sorting function supplied either, it just gets two elements at a time, and it orders only those two. From its perspective, he has a simple job.

[ivan]

On to the fourth read. . .

One thing that should be noted is that:
table.sort works with numerically-indexed tables (aka lists).

If you have a list of numbers (or strings) then you can just write:

Code: Select all

mylist = { 1,5,34,3,54,676,3 }
table.sort(mylist)

And all the magic is done for you.

When your list consists of tables, like in your case
Then you have to tell Lua:
this table should be ranked below that other table in the list, hence:

Code: Select all

table.sort(mylist, function(a, b)
  -- write the code that decides if a should rank below b (where a and b are tables)
  -- return true if a < b
end)