Question Sorting City Waypoints by Name Not Working?

[Thunder Chicken]

More Lua adventures.

So I have a waypoint autopilot that takes lat/long data from the Orbiter Cities.mkr file and converts it to a table of tables that is searchable by index, so the user can scroll through the cities and select the desired waypoint.

The resulting table has a number of tables in it that is the same as the number of cities (n_cities) listed in the Cities.mkr file. As an example, it looks something like this (not exact numbers, just making up an example):

city_waypoints = {
{lat = 0.4854, lng = -2.5859, city = La Paz},
{lat = 0.9834, lng = +1.5859, city = Boston},
{lat = 0.7754, lng = -3.5859, city = Reno},
.
.
.
}

This works fine, but there are hundreds of cities, and they are unfortunately not in alphabetical order, so if you want to fly to a certain city, you may need to scroll through and examine a large number of waypoint tables before finding the city you desire. So I am trying to sort the tables by their city name using the following code at the start of the simulation. It basically looks at the city names in index j and index j+1 and sorts them. If the index of the sorted name table and the original don't match, a swap occurred, so the the waypoint tables are also swapped. This is run n_cities times to ensure that the table is fully sorted.

    temp_pair = {}
    temp_sort = {}
    for i=1,n_cities do
        for j=1,n_cities-1 do
                    
            temp_pair = {city_waypoints[j].city, city_waypoints[j+1].city} --make a sub-table with the city names from waypoint tables j and j+1
            temp_sort = temp_pair --store the original  
            table.sort(temp_pair) --this directly modifies temp_pair
            
            if temp_pair[1] ~= temp_sort[1] then --compare the first index entries of both tables, if different, swap the city table entries
                city_waypoints[j], city_waypoints[j+1] = city_waypoints[j+1], city_waypoints[j]
            end
        end
    end

This code runs, but it doesn't seem to do anything. The city_waypoints table is unmodified. I have verified that the temp_pair table is pulling the names correctly. Table.sort requires integer keys for the table to be sorted, and they seem to be. As far as I can tell this code is correct and valid, but it doesn't do anything.

This seems to be a strictly Lua question, but I wonder if I am using too modern Lua syntax for the Orbiter interpreter. But that usually causes a crash. I'm also wondering a little bit about the indices/keys for these tables. I've tried to explicitly set integer keys and it doesn't change anything.

Any thoughts?

 

[kuddel]

Shouldn't Lua's table.sort do the trick on the whole table?
I would imagine something like:

table.sort(city_waypoints, function (left, right)
    return left.city < right.city
end)

...note this is completely untested code

 

[Thunder Chicken]

Shouldn't Lua's table.sort do the trick on the whole table?
I would imagine something like:

table.sort(city_waypoints, function (left, right)
    return left.city < right.city
end)

...note this is completely untested code

Maybe? I didn't think to apply the function like that. I'll give it a shot.

EDIT: I may not be understanding what you mean by the left and right tables. Your function seems to be comparing the names of only two city tables within the city_waypoints table, so it can't possibly sort the entire city_waypoints table.

EDIT2: I did a little more Googling and found this, which is the pattern that you suggested above. I see it now and it does work perfectly. Thanks!

 

[Thunder Chicken]

Actually, there still is a bit of a problem. Some of the cities in Cities.mkr have umlauts and other special characters and the table.sort in Lua seems to fail because of them:


I am unsure what to do about this. I would prefer to not edit the Cities.mkr file as that comes default with Orbiter 2016, and I have vague aspirations of releasing this autopilot suite as an add-on. Hmmm....

 

[kuddel]

So here's my reply(s):

I may not be understanding what you mean by the left and right tables. Your function seems to be comparing the names of only two city tables within the city_waypoints table, so it can't possibly sort the entire city_waypoints table.

The function is called for (almost) all combinations of the array (most probbably using the quicksort algorithm).
The table.sort function calls your function with two arguments that it needs to be compared. The function you've provided (called the 'comparator') just has to return whether the first element or the second element is "bigger". The method how to compare two elements is unknown to the algorithm and could be anything. You could also sort by latitude, longitude or lenght of the city-name.

Actually, there still is a bit of a problem. Some of the cities in Cities.mkr have umlauts and other special characters and the table.sort in Lua seems to fail because of them:

As I tried to explain earlier, how you compare two elements is up to you.
The less-than operator is just a quick way of comparing to strings - it does not account for Umlauts or how they are compared (is 'ä' biggeer than 'a'?).
I don't know if Lua has something like string.compare() or string.strnatcmp() to hande this.
In doubd you might need to implement it special like handling each character separately.
You might replace Umlauts with their replacements (ä => ae, ö => oe, ü => ue, ß => ss ...) temporarily in the comparison function and compare those. That however is not generic enough, as there are many other special characters (like é, è, ê, ...etc. pp.).

Reading up the documentation on Luas string handling might also help.

 

[Thunder Chicken]

So here's my reply(s):

The function is called for (almost) all combinations of the array (most probbably using the quicksort algorithm).
The table.sort function calls your function with two arguments that it needs to be compared. The function you've provided (called the 'comparator') just has to return whether the first element or the second element is "bigger". The method how to compare two elements is unknown to the algorithm and could be anything. You could also sort by latitude, longitude or lenght of the city-name.

Yes, I understand this now. I was trying to use table.sort to implement a quicksort when it could actually handle it internally. Very useful method.

As I tried to explain earlier, how you compare two elements is up to you.
The less-than operator is just a quick way of comparing to strings - it does not account for Umlauts or how they are compared (is 'ä' biggeer than 'a'?).
I don't know if Lua has something like string.compare() or string.strnatcmp() to hande this.
In doubd you might need to implement it special like handling each character separately.
You might replace Umlauts with their replacements (ä => ae, ö => oe, ü => ue, ß => ss ...) temporarily in the comparison function and compare those. That however is not generic enough, as there are many other special characters (like é, è, ê, ...etc. pp.).

Reading up the documentation on Luas string handling might also help.

It turns out that the umlauts were not the problem, but some bug in my code that I have since fixed. There are no names with a leading special character so it seems it can sort them all fine now.