From 3dd005eaa18a24e80f04c67bd23b8e80788ee02f Mon Sep 17 00:00:00 2001
From: Michael Carleton <micycle1@hotmail.co.uk>
Date: Sat, 31 May 2025 01:36:24 +0100
Subject: [PATCH] add HilbertEncoder.sort().

---
 .../jts/index/hprtree/HilbertEncoder.java     | 75 +++++++++++++++++++
 1 file changed, 75 insertions(+)

diff --git a/modules/core/src/main/java/org/locationtech/jts/index/hprtree/HilbertEncoder.java b/modules/core/src/main/java/org/locationtech/jts/index/hprtree/HilbertEncoder.java
index 33729c9399..5d709e045b 100644
--- a/modules/core/src/main/java/org/locationtech/jts/index/hprtree/HilbertEncoder.java
+++ b/modules/core/src/main/java/org/locationtech/jts/index/hprtree/HilbertEncoder.java
@@ -11,7 +11,13 @@
  */
 package org.locationtech.jts.index.hprtree;
 
+import java.util.Arrays;
+import java.util.Comparator;
+import java.util.List;
+import java.util.stream.IntStream;
+
 import org.locationtech.jts.geom.Envelope;
+import org.locationtech.jts.geom.Geometry;
 import org.locationtech.jts.shape.fractal.HilbertCode;
 
 public class HilbertEncoder {
@@ -42,4 +48,73 @@ public int encode(Envelope env) {
     return HilbertCode.encode(level, x, y);
   }
 
+  /**
+   * Sorts a list of {@link Geometry} objects in-place by their spatial order
+   * using Hilbert curve encoding of their envelopes.
+   *
+   * @param geoms the list of geometries to sort
+   */
+  public static void sort(List<Geometry> geoms) {
+	  sort(geoms, 12);
+  }
+  
+  /**
+   * Sorts a list of {@link Geometry} objects in-place by their spatial order
+   * using Hilbert curve encoding of their envelopes.
+   *
+   * @param geoms the list of geometries to sort
+   * @param level the resolution level for Hilbert curve encoding
+   */
+  public static void sort(List<Geometry> geoms, int level) {
+    int n = geoms.size();
+    if (n < 2)
+      return;
+
+    Envelope globalExtent = new Envelope();
+    for (Geometry g : geoms) {
+      globalExtent.expandToInclude(g.getEnvelopeInternal());
+    }
+
+    HilbertEncoder encoder = new HilbertEncoder(level, globalExtent);
+    int[] keys = new int[n];
+    for (int i = 0; i < n; i++) {
+      Envelope e = geoms.get(i).getEnvelopeInternal();
+      keys[i] = encoder.encode(e);
+    }
+    sortInPlaceByKeys(keys, geoms);
+  }
+
+  private static <T> void sortInPlaceByKeys(int[] keys, List<T> values) {
+    final int n = keys.length;
+
+    Integer[] idx = IntStream.range(0, n).boxed().toArray(Integer[]::new);
+    Arrays.sort(idx, Comparator.comparingInt(i -> keys[i]));
+
+    // rearrange keys and values in-place by following permutation cycles,
+    // so that both arrays are sorted according to hilbert order key.
+    boolean[] seen = new boolean[n];
+    for (int i = 0; i < n; i++) {
+      if (seen[i] || idx[i] == i)
+        continue;
+
+      int cycleStart = i;
+      int j = i;
+      int savedKey = keys[j];
+      T savedVal = values.get(j);
+
+      do {
+        seen[j] = true;
+        int next = idx[j];
+        keys[j] = keys[next];
+        values.set(j, values.get(next));
+
+        j = next;
+      } while (j != cycleStart);
+
+      keys[j] = savedKey;
+      values.set(j, savedVal);
+      seen[j] = true;
+    }
+  }
+
 }