class="kw">package com.hypixel.hytale.component.spatial;

class="kw">import it.unimi.dsi.fastutil.objects.ObjectArrayList;
class="kw">import it.unimi.dsi.fastutil.objects.ObjectListIterator;
class="kw">import java.util.Comparator;
class="kw">import java.util.List;
class="kw">import java.util.function.Predicate;
class="kw">import javax.annotation.Nonnull;
class="kw">import javax.annotation.Nullable;
class="kw">import org.joml.Vector3d;
class="kw">import org.joml.Vector3dc;

class="kw">public class KDTree<T> class="kw">implements SpatialStructure<T> {
   @Nonnull
   class="kw">private class="kw">final List<KDTree.Node<T>> nodePool = new ObjectArrayList();
   class="kw">private int nodePoolIndex = 0;
   @Nonnull
   class="kw">private class="kw">final List<List<T>> dataListPool = new ObjectArrayList();
   class="kw">private int dataListPoolIndex = 0;
   class="kw">private int size;
   @Nonnull
   class="kw">private class="kw">final Predicate<T> collectionFilter;
   @Nullable
   class="kw">private KDTree.Node<T> root;

   class="kw">public KDTree(@Nonnull Predicate<T> var1) {
      this.collectionFilter = var1;
   }

   @Override
   class="kw">public int size() {
      class="kw">return this.size;
   }

   @Override
   class="kw">public void rebuild(@Nonnull SpatialData<T> var1) {
      this.root = null;
      this.size = 0;
      int var2 = var1.size();
      if (var2 != 0) {
         for (int var3 = 0; var3 < this.dataListPoolIndex; var3++) {
            this.dataListPool.get(var3).clear();
         }

         this.nodePoolIndex = 0;
         this.dataListPoolIndex = 0;
         var1.sortMorton();
         int var13 = var2 / 2;
         int var4 = var1.getSortedIndex(var13);
         Vector3d var5 = var1.getVector(var4);
         Object var6 = var1.getData(var4);
         List var7 = this.getPooledDataList();
         var7.add(var6);

         int var8;
         for (var8 = var13 - 1; var8 >= 0; var8--) {
            int var9 = var1.getSortedIndex(var8);
            Vector3d var10 = var1.getVector(var9);
            if (!var10.equals(var5)) {
               break;
            }

            Object var11 = var1.getData(var9);
            var7.add(var11);
         }

         int var14;
         for (var14 = var13 + 1; var14 < var2; var14++) {
            int var15 = var1.getSortedIndex(var14);
            Vector3d var16 = var1.getVector(var15);
            if (!var16.equals(var5)) {
               break;
            }

            Object var12 = var1.getData(var15);
            var7.add(var12);
         }

         this.root = this.getPooledNode(var5, var7);
         if (0 < var8 + 1) {
            this.build0(var1, 0, var8 + 1);
         }

         if (var14 < var2) {
            this.build0(var1, var14, var2);
         }

         this.size = var2;
      }
   }

   @Nullable
   @Override
   class="kw">public T closest(@Nonnull Vector3dc var1) {
      KDTree.ClosestState var2 = new KDTree.ClosestState<>(null, Double.MAX_VALUE);
      this.closest0(var2, this.root, var1, 0);
      class="kw">return var2.node == null ? null : var2.node.data.getFirst();
   }

   @Override
   class="kw">public void collect(@Nonnull Vector3dc var1, double var2, @Nonnull List<T> var4) {
      double var5 = var2 * var2;
      this.collect0(var4, this.root, var1, var5, 0);
   }

   @Override
   class="kw">public void collectCylinder(@Nonnull Vector3dc var1, double var2, double var4, @Nonnull List<T> var6) {
      double var7 = var2 * var2;
      double var9 = var4 / 2.0;
      this.collectCylinder0(var6, this.root, var1, var7, var9, var2, 0);
   }

   @Override
   class="kw">public void collectBox(@Nonnull Vector3dc var1, @Nonnull Vector3dc var2, @Nonnull List<T> var3) {
      this.collectBox0(var3, this.root, var1, var2, 0);
   }

   @Override
   class="kw">public void ordered(@Nonnull Vector3dc var1, double var2, @Nonnull List<T> var4) {
      double var5 = var2 * var2;
      ObjectArrayList var7 = new ObjectArrayList();
      this.ordered0(var7, this.root, var1, var5, 0);
      var7.sort(Comparator.comparingDouble(var0 -> var0.distanceSq));
      ObjectListIterator var8 = var7.iterator();

      while (var8.hasNext()) {
         KDTree.OrderedEntry var9 = (KDTree.OrderedEntry<T>)var8.next();
         int var10 = 0;

         for (int var11 = var9.values.size(); var10 < var11; var10++) {
            Object var12 = var9.values.get(var10);
            if (this.collectionFilter.test(var12)) {
               var4.add(var12);
            }
         }
      }
   }

   @Override
   class="kw">public void ordered3DAxis(@Nonnull Vector3dc var1, double var2, double var4, double var6, @Nonnull List<T> var8) {
      ObjectArrayList var9 = new ObjectArrayList();
      this._internal_ordered3DAxis(var9, this.root, var1, var2, var4, var6, 0);
      var9.sort(Comparator.comparingDouble(var0 -> var0.distanceSq));
      ObjectListIterator var10 = var9.iterator();

      while (var10.hasNext()) {
         KDTree.OrderedEntry var11 = (KDTree.OrderedEntry<T>)var10.next();
         int var12 = 0;

         for (int var13 = var11.values.size(); var12 < var13; var12++) {
            Object var14 = var11.values.get(var12);
            if (this.collectionFilter.test(var14)) {
               var8.add(var14);
            }
         }
      }
   }

   @Nonnull
   @Override
   class="kw">public String dump() {
      class="kw">return "KDTree(size=" + this.size + ")\n" + (this.root == null ? null : this.root.dump(0));
   }

   @Nonnull
   class="kw">private KDTree.Node<T> getPooledNode(Vector3dc var1, List<T> var2) {
      if (this.nodePoolIndex < this.nodePool.size()) {
         KDTree.Node var4 = this.nodePool.get(this.nodePoolIndex++);
         var4.reset(var1, var2);
         class="kw">return var4;
      } else {
         KDTree.Node var3 = new KDTree.Node<>(var1, var2);
         this.nodePool.add(var3);
         this.nodePoolIndex++;
         class="kw">return var3;
      }
   }

   class="kw">private List<T> getPooledDataList() {
      if (this.dataListPoolIndex < this.dataListPool.size()) {
         class="kw">return this.dataListPool.get(this.dataListPoolIndex++);
      }

      ObjectArrayList var1 = new ObjectArrayList(1);
      this.dataListPool.add(var1);
      this.dataListPoolIndex++;
      class="kw">return var1;
   }

   class="kw">private void build0(@Nonnull SpatialData<T> var1, int var2, int var3) {
      int var4 = (var2 + var3) / 2;
      int var5 = var1.getSortedIndex(var4);
      Vector3d var6 = var1.getVector(var5);
      Object var7 = var1.getData(var5);
      List var8 = this.getPooledDataList();
      var8.add(var7);

      int var9;
      for (var9 = var4 - 1; var9 >= var2; var9--) {
         int var10 = var1.getSortedIndex(var9);
         Vector3d var11 = var1.getVector(var10);
         if (!var11.equals(var6)) {
            break;
         }

         Object var12 = var1.getData(var10);
         var8.add(var12);
      }

      int var14;
      for (var14 = var4 + 1; var14 < var3; var14++) {
         int var15 = var1.getSortedIndex(var14);
         Vector3d var16 = var1.getVector(var15);
         if (!var16.equals(var6)) {
            break;
         }

         Object var13 = var1.getData(var15);
         var8.add(var13);
      }

      this.put0(this.root, var6, var8, 0);
      if (var2 < var9 + 1) {
         this.build0(var1, var2, var9 + 1);
      }

      if (var14 < var3) {
         this.build0(var1, var14, var3);
      }
   }

   class="kw">private void put0(@Nonnull KDTree.Node<T> var1, @Nonnull Vector3dc var2, @Nonnull List<T> var3, int var4) {
      if (compare(var1.vector, var2, var4) < 0) {
         if (var1.one == null) {
            var1.one = this.getPooledNode(var2, var3);
         } else {
            this.put0(var1.one, var2, var3, (var4 + 1) % 3);
         }
      } else if (var1.two == null) {
         var1.two = this.getPooledNode(var2, var3);
      } else {
         this.put0(var1.two, var2, var3, (var4 + 1) % 3);
      }
   }

   class="kw">private void closest0(@Nonnull KDTree.ClosestState<T> var1, @Nullable KDTree.Node<T> var2, @Nonnull Vector3dc var3, int var4) {
      if (var2 != null) {
         if (var3.equals(var2.vector)) {
            var1.distanceSq = 0.0;
            var1.node = var2;
         } else {
            int var5 = var4 % 3;
            int var6 = compare(var2.vector, var3, var5);
            double var7 = var2.vector.distanceSquared(var3);
            if (var7 < var1.distanceSq) {
               var1.node = var2;
               var1.distanceSq = var7;
            }

            int var9 = var4 + 1;
            if (var6 < 0) {
               this.closest0(var1, var2.one, var3, var9);
            } else {
               this.closest0(var1, var2.two, var3, var9);
            }

            double var10 = get(var2.vector, var5);
            double var12 = get(var3, var5);
            double var14 = Math.abs(var12 - var10);
            if (var14 * var14 < var1.distanceSq) {
               if (var6 < 0) {
                  this.closest0(var1, var2.two, var3, var9);
               } else {
                  this.closest0(var1, var2.one, var3, var9);
               }
            }
         }
      }
   }

   class="kw">private void collect0(@Nonnull List<T> var1, @Nullable KDTree.Node<T> var2, @Nonnull Vector3dc var3, double var4, int var6) {
      if (var2 != null) {
         int var7 = var6 % 3;
         int var8 = compare(var2.vector, var3, var7);
         double var9 = var2.vector.distanceSquared(var3);
         if (var9 < var4) {
            int var11 = 0;

            for (int var12 = var2.data.size(); var11 < var12; var11++) {
               Object var13 = var2.data.get(var11);
               if (this.collectionFilter.test(var13)) {
                  var1.add(var13);
               }
            }
         }

         int var18 = var6 + 1;
         if (var8 < 0) {
            this.collect0(var1, var2.one, var3, var4, var18);
         } else {
            this.collect0(var1, var2.two, var3, var4, var18);
         }

         double var19 = get(var2.vector, var7);
         double var14 = get(var3, var7);
         double var16 = Math.abs(var14 - var19);
         if (var16 * var16 < var4) {
            if (var8 < 0) {
               this.collect0(var1, var2.two, var3, var4, var18);
            } else {
               this.collect0(var1, var2.one, var3, var4, var18);
            }
         }
      }
   }

   class="kw">private void collectCylinder0(
      @Nonnull List<T> var1, @Nullable KDTree.Node<T> var2, @Nonnull Vector3dc var3, double var4, double var6, double var8, int var10
   ) {
      if (var2 != null) {
         int var11 = var10 % 3;
         int var12 = compare(var2.vector, var3, var11);
         double var13 = var2.vector.y() - var3.y();
         if (Math.abs(var13) <= var6) {
            double var15 = var2.vector.x() - var3.x();
            double var17 = var2.vector.z() - var3.z();
            double var19 = var15 * var15 + var17 * var17;
            if (var19 <= var4) {
               int var21 = 0;

               for (int var22 = var2.data.size(); var21 < var22; var21++) {
                  Object var23 = var2.data.get(var21);
                  if (this.collectionFilter.test(var23)) {
                     var1.add(var23);
                  }
               }
            }
         }

         int var24 = var10 + 1;
         if (var12 < 0) {
            this.collectCylinder0(var1, var2.one, var3, var4, var6, var8, var24);
         } else {
            this.collectCylinder0(var1, var2.two, var3, var4, var6, var8, var24);
         }

         double var16 = get(var2.vector, var11);
         double var18 = get(var3, var11);
         double var20 = var11 == 2 ? var6 : var8;
         if (Math.abs(var18 - var16) <= var20) {
            if (var12 < 0) {
               this.collectCylinder0(var1, var2.two, var3, var4, var6, var8, var24);
            } else {
               this.collectCylinder0(var1, var2.one, var3, var4, var6, var8, var24);
            }
         }
      }
   }

   class="kw">private void collectBox0(@Nonnull List<T> var1, @Nullable KDTree.Node<T> var2, @Nonnull Vector3dc var3, @Nonnull Vector3dc var4, int var5) {
      if (var2 != null) {
         int var6 = var5 % 3;
         if (var2.vector.x() >= var3.x()
            && var2.vector.x() <= var4.x()
            && var2.vector.y() >= var3.y()
            && var2.vector.y() <= var4.y()
            && var2.vector.z() >= var3.z()
            && var2.vector.z() <= var4.z()) {
            int var7 = 0;

            for (int var8 = var2.data.size(); var7 < var8; var7++) {
               Object var9 = var2.data.get(var7);
               if (this.collectionFilter.test(var9)) {
                  var1.add(var9);
               }
            }
         }

         int var14 = var5 + 1;
         double var15 = get(var2.vector, var6);
         double var10 = get(var3, var6);
         double var12 = get(var4, var6);
         if (var12 >= var15) {
            this.collectBox0(var1, var2.one, var3, var4, var14);
         }

         if (var10 <= var15) {
            this.collectBox0(var1, var2.two, var3, var4, var14);
         }
      }
   }

   class="kw">private void ordered0(@Nonnull List<KDTree.OrderedEntry<T>> var1, @Nullable KDTree.Node<T> var2, @Nonnull Vector3dc var3, double var4, int var6) {
      if (var2 != null) {
         int var7 = var6 % 3;
         int var8 = compare(var2.vector, var3, var7);
         double var9 = var2.vector.distanceSquared(var3);
         if (var9 < var4) {
            var1.add(new KDTree.OrderedEntry<>(var9, var2.data));
         }

         int var11 = var6 + 1;
         if (var8 < 0) {
            this.ordered0(var1, var2.one, var3, var4, var11);
         } else {
            this.ordered0(var1, var2.two, var3, var4, var11);
         }

         double var12 = get(var2.vector, var7);
         double var14 = get(var3, var7);
         double var16 = Math.abs(var14 - var12);
         if (var16 * var16 < var4) {
            if (var8 < 0) {
               this.ordered0(var1, var2.two, var3, var4, var11);
            } else {
               this.ordered0(var1, var2.one, var3, var4, var11);
            }
         }
      }
   }

   class="kw">private void _internal_ordered3DAxis(
      @Nonnull List<KDTree.OrderedEntry<T>> var1, @Nullable KDTree.Node<T> var2, @Nonnull Vector3dc var3, double var4, double var6, double var8, int var10
   ) {
      if (var2 != null) {
         int var11 = var10 % 3;
         boolean var12 = var2.vector.x() >= var3.x() - var4
            && var2.vector.x() <= var3.x() + var4
            && var2.vector.y() >= var3.y() - var6
            && var2.vector.y() <= var3.y() + var6
            && var2.vector.z() >= var3.z() - var8
            && var2.vector.z() <= var3.z() + var8;
         if (var12) {
            double var13 = var2.vector.distanceSquared(var3);
            var1.add(new KDTree.OrderedEntry<>(var13, var2.data));
         }

         int var23 = var10 + 1;
         int var14 = compare(var2.vector, var3, var11);
         KDTree.Node var15 = var14 < 0 ? var2.one : var2.two;
         KDTree.Node var16 = var14 < 0 ? var2.two : var2.one;
         this._internal_ordered3DAxis(var1, var15, var3, var4, var6, var8, var23);
         double var17 = get(var2.vector, var11);
         double var19 = get(var3, var11);
         double var21 = var11 == 0 ? var4 : (var11 == 1 ? var8 : var6);
         if (Math.abs(var19 - var17) <= var21) {
            this._internal_ordered3DAxis(var1, var16, var3, var4, var6, var8, var23);
         }
      }
   }

   class="kw">private class="kw">static int compare(@Nonnull Vector3dc var0, @Nonnull Vector3dc var1, int var2) {
      class="kw">return class="kw">switch (var2) {
         case 0 -> Double.compare(var0.x(), var1.x());
         case 1 -> Double.compare(var0.z(), var1.z());
         case 2 -> Double.compare(var0.y(), var1.y());
         class="kw">default -> throw new IllegalArgumentException("Invalid axis: " + var2);
      };
   }

   class="kw">private class="kw">static double get(@Nonnull Vector3dc var0, int var1) {
      class="kw">return class="kw">switch (var1) {
         case 0 -> var0.x();
         case 1 -> var0.z();
         case 2 -> var0.y();
         class="kw">default -> throw new IllegalArgumentException("Invalid axis: " + var1);
      };
   }

   class="kw">private class="kw">static class ClosestState<T> {
      class="kw">private KDTree.Node<T> node;
      class="kw">private double distanceSq;

      class="kw">public ClosestState(KDTree.Node<T> var1, double var2) {
         this.node = var1;
         this.distanceSq = var2;
      }
   }

   class="kw">private class="kw">static class Node<T> {
      class="kw">private Vector3dc vector;
      class="kw">private List<T> data;
      @Nullable
      class="kw">private KDTree.Node<T> one;
      @Nullable
      class="kw">private KDTree.Node<T> two;

      class="kw">public Node(Vector3dc var1, List<T> var2) {
         this.vector = var1;
         this.data = var2;
      }

      class="kw">public void reset(Vector3dc var1, List<T> var2) {
         this.vector = var1;
         this.data = var2;
         this.one = null;
         this.two = null;
      }

      @Nonnull
      class="kw">public String dump(int var1) {
         int var2 = var1 + 1;
         class="kw">return "vector="
            + this.vector
            + ", data="
            + this.data
            + ",\n"
            + " ".repeat(var1)
            + "one="
            + (this.one == null ? null : this.one.dump(var2))
            + ",\n"
            + " ".repeat(var1)
            + "two="
            + (this.two == null ? null : this.two.dump(var2));
      }
   }

   class="kw">private class="kw">static class OrderedEntry<T> {
      class="kw">private class="kw">final double distanceSq;
      class="kw">private class="kw">final List<T> values;

      class="kw">public OrderedEntry(double var1, List<T> var3) {
         this.distanceSq = var1;
         this.values = var3;
      }
   }
}