5 Replies Latest reply on Dec 6, 2011 3:02 AM by areohbee

    table.sort - is it broken, or am I doing something wrong?

    areohbee Level 5

      sometimes, what should be the last element is not being put in the correct position (last) (all others are in the correct order) - no matter what I do, and I have to resort to this function, which works flawlessly:

       

      function Table:sort( t, func )

          local tc = self:copy( t ) -- make shallow copy

          tc[#tc + 1] = "___dUmMy___" -- 3 underscores on each side.

          table.sort( tc, func )

          local index = 1

          for i = 1, #tc do

              if tc[i] ~= "___dUmMy___" then

                  t[index] = tc[i]

                  index = index + 1

              else

                  -- skip it.       

              end

          end

          t[#tc] = nil -- shouldn't be necessary, but cheap insurance...

      end

       

      i.e. add an extra dummy element to the table, then sort it using the same sort function, then remove the dummy element.

      Its like table.sort makes one iteration too few, unless the dummy is there to force it, or something...

       

      This is driving me crazy!

       

      Any ideas?

        • 1. Re: table.sort - is it broken, or am I doing something wrong?
          johnrellis Most Valuable Participant

          I wonder if the actual comparison function isn't always returning consistent results, i.e. both func(a, b) and func(b, a) return true for some a and b.

           

          Otherwise, you'd have to get a reproducible test case you could run standalone to really understand what's going on.

          • 2. Re: table.sort - is it broken, or am I doing something wrong?
            DawMatt Level 3

            Hi Rob,

             

            I've never seen this. As John says, if you can come up with a reproducible

            test case it would really help with diagnosing this.

             

            Thanks, Matt

            (Apologies for the brevity - sent from my Android)

            • 3. Re: table.sort - is it broken, or am I doing something wrong?
              areohbee Level 5

              So, I figured it out.

               

              Sometimes I want the exact opposite order than is (reliably) possible given the table sort algorithm.

               

              If, in a table sort function, one replaces:

               

              return order

               

              with

               

              return not order

               

              (in a perfectly working sort function), it reverses the order of the sort but may not handle the last element properly.

               

              The reason is this:

               

              The table sort return value is determining whether to swap two values or not to swap them, it is *not* determining absolute ordering - if it were, then returning true would mean order one way, and returning false would mean order the opposite way.

               

              Enough talk - test plugin: http://www.robcole.com/_temp/TestLrPlugins/Scratch_LrPlugin_0.0.zip

              (Instructions: In plugin manager, click 'Local Test' button. Source code is in ExtendedManager.lua (tableSortTest function) and Framework/Data/Table.lua (reverseSortCopy method).

               

              Rob

              • 4. Re: table.sort - is it broken, or am I doing something wrong?
                johnrellis Most Valuable Participant

                Rob,

                 

                That's a subtle bug, indeed.  Here's another way of looking at it.  The Lua Reference requires that table.sort's comparision function comp(a, b) return true if and only if a < b;  if a = b then the function must return false.  But if you pass a new comparison function

                 

                not comp(a, b)

                 

                that's equivalent to returning "not a < b", which is equivalent to a >= b.  But in this case, when a = b, the function returns true, violating the contract with table.sort.   It's not surprising that table.sort would then operate strangely.

                 

                I can't prove to myself that your workaround is correct.  But here's a simpler suggestion for implementing a reverse sort -- call table.sort with the comparison function, and then make a single pass through the array to reverse it in place.  This is easy to prove correct, is just as fast, and it doesn't involve the use of dummy elements.

                • 5. Re: table.sort - is it broken, or am I doing something wrong?
                  areohbee Level 5

                  Thanks John.

                   

                  I took your advice - now that I know what the deal is, it definitely makes more sense to use a proper sort function and then reverse the result, than to use a bass-ackwards sort function and stuff it with a dummy.

                   

                  (I confess - I had to think for a while to figure out how to reverse in place ;-}

                   

                  A thank you to Matt D. too :-0

                   

                  Cheers,

                  Rob