[core] sort symbols using symbol-sort-key before placement (#16023)

fix #15964
partially port mapbox/mapbox-gl-js#9054

2 files changed, 25 insertions, 1 deletions

diff --git a/test/gl/bucket.test.cpp b/test/gl/bucket.test.cpp
index 2a7455e17c..c7636dabcf 100644
--- a/test/gl/bucket.test.cpp
+++ b/test/gl/bucket.test.cpp
@@ -123,6 +123,7 @@ TEST(Buckets, SymbolBucket) {
     bool sortFeaturesByY = false;
     std::string bucketLeaderID = "test";
     std::vector<SymbolInstance> symbolInstances;
+    std::vector<SortKeyRange> symbolRanges;
 
     gl::Context context{ backend };
     SymbolBucket bucket{std::move(layout),
@@ -134,6 +135,7 @@ TEST(Buckets, SymbolBucket) {
                         sortFeaturesByY,
                         bucketLeaderID,
                         std::move(symbolInstances),
+                        std::move(symbolRanges),
                         1.0f,
                         false,
                         {},
diff --git a/test/text/cross_tile_symbol_index.test.cpp b/test/text/cross_tile_symbol_index.test.cpp
index 6119392fd2..bedf96b430 100644
--- a/test/text/cross_tile_symbol_index.test.cpp
+++ b/test/text/cross_tile_symbol_index.test.cpp
@@ -47,6 +47,7 @@ TEST(CrossTileSymbolLayerIndex, addBucket) {
 
     OverscaledTileID mainID(6, 0, 6, 8, 8);
     std::vector<SymbolInstance> mainInstances;
+    std::vector<SortKeyRange> mainRanges;
     mainInstances.push_back(makeSymbolInstance(1000, 1000, u"Detroit"));
     mainInstances.push_back(makeSymbolInstance(2000, 2000, u"Toronto"));
     SymbolBucket mainBucket{layout,
@@ -58,6 +59,7 @@ TEST(CrossTileSymbolLayerIndex, addBucket) {
                             sortFeaturesByY,
                             bucketLeaderID,
                             std::move(mainInstances),
+                            std::move(mainRanges),
                             1.0f,
                             false,
                             {},
@@ -72,6 +74,7 @@ TEST(CrossTileSymbolLayerIndex, addBucket) {
 
     OverscaledTileID childID(7, 0, 7, 16, 16);
     std::vector<SymbolInstance> childInstances;
+    std::vector<SortKeyRange> childRanges;
     childInstances.push_back(makeSymbolInstance(2000, 2000, u"Detroit"));
     childInstances.push_back(makeSymbolInstance(2000, 2000, u"Windsor"));
     childInstances.push_back(makeSymbolInstance(3000, 3000, u"Toronto"));
@@ -85,6 +88,7 @@ TEST(CrossTileSymbolLayerIndex, addBucket) {
                              sortFeaturesByY,
                              bucketLeaderID,
                              std::move(childInstances),
+                             std::move(childRanges),
                              1.0f,
                              false,
                              {},
@@ -103,6 +107,7 @@ TEST(CrossTileSymbolLayerIndex, addBucket) {
 
     OverscaledTileID parentID(5, 0, 5, 4, 4);
     std::vector<SymbolInstance> parentInstances;
+    std::vector<SortKeyRange> parentRanges;
     parentInstances.push_back(makeSymbolInstance(500, 500, u"Detroit"));
     SymbolBucket parentBucket{layout,
                               {},
@@ -113,6 +118,7 @@ TEST(CrossTileSymbolLayerIndex, addBucket) {
                               sortFeaturesByY,
                               bucketLeaderID,
                               std::move(parentInstances),
+                              std::move(parentRanges),
                               1.0f,
                               false,
                               {},
@@ -130,6 +136,7 @@ TEST(CrossTileSymbolLayerIndex, addBucket) {
     // grandchild
     OverscaledTileID grandchildID(8, 0, 8, 32, 32);
     std::vector<SymbolInstance> grandchildInstances;
+    std::vector<SortKeyRange> grandchildRanges;
     grandchildInstances.push_back(makeSymbolInstance(4000, 4000, u"Detroit"));
     grandchildInstances.push_back(makeSymbolInstance(4000, 4000, u"Windsor"));
     SymbolBucket grandchildBucket{layout,
@@ -141,6 +148,7 @@ TEST(CrossTileSymbolLayerIndex, addBucket) {
                                   sortFeaturesByY,
                                   bucketLeaderID,
                                   std::move(grandchildInstances),
+                                  std::move(grandchildRanges),
                                   1.0f,
                                   false,
                                   {},
@@ -169,6 +177,7 @@ TEST(CrossTileSymbolLayerIndex, resetIDs) {
 
     OverscaledTileID mainID(6, 0, 6, 8, 8);
     std::vector<SymbolInstance> mainInstances;
+    std::vector<SortKeyRange> mainRanges;
     mainInstances.push_back(makeSymbolInstance(1000, 1000, u"Detroit"));
     SymbolBucket mainBucket{layout,
                             {},
@@ -179,6 +188,7 @@ TEST(CrossTileSymbolLayerIndex, resetIDs) {
                             sortFeaturesByY,
                             bucketLeaderID,
                             std::move(mainInstances),
+                            std::move(mainRanges),
                             1.0f,
                             false,
                             {},
@@ -187,6 +197,7 @@ TEST(CrossTileSymbolLayerIndex, resetIDs) {
 
     OverscaledTileID childID(7, 0, 7, 16, 16);
     std::vector<SymbolInstance> childInstances;
+    std::vector<SortKeyRange> childRanges;
     childInstances.push_back(makeSymbolInstance(2000, 2000, u"Detroit"));
     SymbolBucket childBucket{layout,
                              {},
@@ -197,6 +208,7 @@ TEST(CrossTileSymbolLayerIndex, resetIDs) {
                              sortFeaturesByY,
                              bucketLeaderID,
                              std::move(childInstances),
+                             std::move(childRanges),
                              1.0f,
                              false,
                              {},
@@ -233,6 +245,7 @@ TEST(CrossTileSymbolLayerIndex, noDuplicatesWithinZoomLevel) {
 
     OverscaledTileID mainID(6, 0, 6, 8, 8);
     std::vector<SymbolInstance> mainInstances;
+    std::vector<SortKeyRange> mainRanges;
     mainInstances.push_back(makeSymbolInstance(1000, 1000, u"")); // A
     mainInstances.push_back(makeSymbolInstance(1000, 1000, u"")); // B
     SymbolBucket mainBucket{layout,
@@ -244,6 +257,7 @@ TEST(CrossTileSymbolLayerIndex, noDuplicatesWithinZoomLevel) {
                             sortFeaturesByY,
                             bucketLeaderID,
                             std::move(mainInstances),
+                            std::move(mainRanges),
                             1.0f,
                             false,
                             {},
@@ -252,6 +266,7 @@ TEST(CrossTileSymbolLayerIndex, noDuplicatesWithinZoomLevel) {
 
     OverscaledTileID childID(7, 0, 7, 16, 16);
     std::vector<SymbolInstance> childInstances;
+    std::vector<SortKeyRange> childRanges;
     childInstances.push_back(makeSymbolInstance(2000, 2000, u"")); // A'
     childInstances.push_back(makeSymbolInstance(2000, 2000, u"")); // B'
     childInstances.push_back(makeSymbolInstance(2000, 2000, u"")); // C'
@@ -264,6 +279,7 @@ TEST(CrossTileSymbolLayerIndex, noDuplicatesWithinZoomLevel) {
                              sortFeaturesByY,
                              bucketLeaderID,
                              std::move(childInstances),
+                             std::move(childRanges),
                              1.0f,
                              false,
                              {},
@@ -295,6 +311,7 @@ TEST(CrossTileSymbolLayerIndex, bucketReplacement) {
 
     OverscaledTileID tileID(6, 0, 6, 8, 8);
     std::vector<SymbolInstance> firstInstances;
+    std::vector<SortKeyRange> firstRanges;
     firstInstances.push_back(makeSymbolInstance(1000, 1000, u"")); // A
     firstInstances.push_back(makeSymbolInstance(1000, 1000, u"")); // B
     SymbolBucket firstBucket{layout,
@@ -306,6 +323,7 @@ TEST(CrossTileSymbolLayerIndex, bucketReplacement) {
                              sortFeaturesByY,
                              bucketLeaderID,
                              std::move(firstInstances),
+                             std::move(firstRanges),
                              1.0f,
                              false,
                              {},
@@ -313,6 +331,7 @@ TEST(CrossTileSymbolLayerIndex, bucketReplacement) {
     firstBucket.bucketInstanceId = ++maxBucketInstanceId;
 
     std::vector<SymbolInstance> secondInstances;
+    std::vector<SortKeyRange> secondRanges;
     secondInstances.push_back(makeSymbolInstance(1000, 1000, u"")); // A'
     secondInstances.push_back(makeSymbolInstance(1000, 1000, u"")); // B'
     secondInstances.push_back(makeSymbolInstance(1000, 1000, u"")); // C'
@@ -325,6 +344,7 @@ TEST(CrossTileSymbolLayerIndex, bucketReplacement) {
                               sortFeaturesByY,
                               bucketLeaderID,
                               std::move(secondInstances),
+                              std::move(secondRanges),
                               1.0f,
                               false,
                               {},
@@ -369,6 +389,7 @@ TEST(CrossTileSymbolLayerIndex, offscreenSymbols) {
     std::vector<SymbolInstance> mainInstances;
     mainInstances.push_back(makeSymbolInstance(1000, 1000, u"Washington"));
     mainInstances.push_back(makeSymbolInstance(2000, 2000, u"Richmond"));
+    std::vector<SortKeyRange> mainRanges;
     SymbolBucket symbolBucket{layout,
                               {},
                               16.0f,
@@ -378,6 +399,7 @@ TEST(CrossTileSymbolLayerIndex, offscreenSymbols) {
                               sortFeaturesByY,
                               bucketLeaderID,
                               std::move(mainInstances),
+                              std::move(mainRanges),
                               1.0f,
                               false,
                               {},
@@ -394,4 +416,4 @@ TEST(CrossTileSymbolLayerIndex, offscreenSymbols) {
 
     EXPECT_EQ(symbolBucket.symbolInstances.at(0).crossTileID, 1u);
     EXPECT_EQ(symbolBucket.symbolInstances.at(1).crossTileID, 2u);
-}
\ No newline at end of file
+}