Sorting nested tables

[zgrssd]

As part of my LibConstantMapper I wanted to add a simple sorting of the result set.
My results are well formed arrays, where each entry is a table containing a "key" and "value" index.
I want those nested tables to be sorted - first by value, then by key (in the odd case a duplicate value exists).
As far as I understand table.sort accepts a function. That function takes 2 parameters (element a and b) and returns true if a < b. So I wrote this function:

local function CompareKeyValuePair(a, b)
  --assert valid input
  assert(type(a) == "table" and a.key ~= nil and a.value ~= nil, "argument a must be a table containing a 'key' and 'value' string-index")
  assert(type(b) == "table" and b.key ~= nil and b.value ~= nil, "argument b must be a table containing a 'key' and 'value' string-index")
 
  --Sort by value first, key second
  return (a.value < b.value) or (a.key < b.key)
end

And call it like this:

if result ~= {} then
  table.sort(result, CompareKeyValuePair)
end

I checked with a d() message, it actually goes into the if block.
But the result does not seems to be ordered.
Anything I overlooked?

[Khaibit]

It seems like you might want to do the following if you want a sort by value primarily, then key as a tie-breaker:

local function CompareKeyValuePair(a, b)
  --assert valid input
  assert(type(a) == "table" and a.key ~= nil and a.value ~= nil, "argument a must be a table containing a 'key' and 'value' string-index")
  assert(type(b) == "table" and b.key ~= nil and b.value ~= nil, "argument b must be a table containing a 'key' and 'value' string-index")
     
  --Sort by value first, key second
  if (a.value == b.value) then
    return (a.key < b.key)
  else
    return (a.value < b.value)
  end
end

As written, if I understand the LUA sorting functions properly, your function will consider element A to be 'before' element B if either the value OR the key is less than B's (if a.value < b.value is false, but a.key < b.key is true, your sort function returns true). If I understand you correctly, you only want the keys to be considered if the values are the same, instead.

[zgrssd]

Originally Posted by Khaibit It seems like you might want to do the following if you want a sort by value primarily, then key as a tie-breaker: local function CompareKeyValuePair(a, b) --assert valid input assert(type(a) == "table" and a.key ~= nil and a.value ~= nil, "argument a must be a table containing a 'key' and 'value' string-index") assert(type(b) == "table" and b.key ~= nil and b.value ~= nil, "argument b must be a table containing a 'key' and 'value' string-index") --Sort by value first, key second if (a.value == b.value) then return (a.key < b.key) else return (a.value < b.value) end end As written, if I understand the LUA sorting functions properly, your function will consider element A to be 'before' element B if either the value OR the key is less than B's (if a.value < b.value is false, but a.key < b.key is true, your sort function returns true). If I understand you correctly, you only want the keys to be considered if the values are the same, instead.

My asumption was this:
When any part of a OR statement is true, the other parts are not even executed.
If the value comparision returns true, the key is irrelevant.
If the value coimparision returns false, then the key might tip it.
In all other cases this one should not be smaller.

But I will try to rework it as you sugested. Could be there is something different in Lua about Bool Operator processing too.

[merlight]

Your understanding of the or operator (short-circuit evaluation) is correct.
I won't quote but slightly adjust your above post in an attempt to make it clearer where's the catch

If a.value < b.value, the key is irrelevant, you return true. (a goes before b)
If not (a.value < b.value), it doesn't mean that (a.value == b.value).
If a.value > b.value, the key is irrelevant, you return false (there's no way the keys could make a < b, a simply has higher value, must go after b)

[zgrssd]

Argh, now I get what I did wrong:
The key was compared when value was bigger. Not only when it was equal. I Ultiamtively choose this version and it seems to work out:

local function CompareKeyValuePair(a, b)
  --assert valid input
  assert(type(a) == "table" and a.key ~= nil and a.value ~= nil, "argument a must be a table containing a 'key' and 'value' string-index")
  assert(type(b) == "table" and b.key ~= nil and b.value ~= nil, "argument b must be a table containing a 'key' and 'value' string-index")
 
  --check if the value is smaller first
  if (a.value < b.value) then
    return true
  end
  
  --if values are the same, try to order by key
  if (a.value == b.value) and (a.key < b.key) then
    return true
  end
 
  return false
end

Thanks for the help.

[Khaibit]

As a side note, the 'and' and 'or' operators in LUA don't necessarily work the way you expect from other languages. They don't always return false or true; consider for example the following:

local function blah(myInput)

  return (myInput < 5) and "apple" or "orange"

end

What does this code actually do? If myInput is less than 5, it returns the string "apple", and otherwise, it returns the string "orange". In essence, so long as Y is guaranteed to not be nil or false (even 0 as a value is OK as LUA doesn't treat 0 as false), X and Y or Z in LUA is equivalent to the C-style ternary operator X ? Y : Z, a condensed form of "if X then Y else Z end".

Why is this? Because AND in LUA is implemented like this: for X AND Y, if X is false or nil, return X. Otherwise, return Y. Similarly, OR is implemented such that if X is false or nil, return Y, and otherwise, return X. So, in the above function, if myInput is less than 5, the AND function returns "apple", and the return reduces to "'apple' or 'orange'". "apple", being a non-nil string, evaluates to true, and thus the OR returns "apple" as well. If myInput is >= 5, AND returns false, and the return reduces to "false or 'orange'", thus the OR call returns "orange".

A bit of a tangent, but it can sometimes help you find some shortcuts in your coding

[CrazyDutchGuy]

so in short he could say, if i am right, and he wants to put it in a sngle return statement.

return (a.value < b.value)  or ((a.value = b.value) and (a.key < b.key))

[Khaibit]

Originally Posted by CrazyDutchGuy so in short he could say, if i am right, and he wants to put it in a sngle return statement. return (a.value < b.value)  or ((a.value == b.value) and (a.key < b.key))

Looks right, after I added an extra equals for you Although it's the sort of thing you might want to add a comment above since it's not that easily readable to those not familiar with LUA

To make it easier for folks less familiar with LUA and logic like this to piece through, let's look at the 3 possibilities:

a.value < b.value, which we want to return 'true' - we get:
(true) or ((false) and (a.key < b.key)) -> (true) or (false) -> (true) OK!
a.value == b.value, we want the return to be true if a.key < b.key - we get:
(false) or ((true) and (a.key < b.key)) -> (false) or (a.key < b.key) -> (a.key < b.key) OK!
a.value > b.value, which we want to return 'false' - we get:
(false) or ((false) and (a.key < b.key)) -> (false) or (false) -> (false) OK!