// 
// Decompiled by Procyon v0.6.0
// 

package com.hypixel.hytale.builtin.portals.utils.spatial;

import it.unimi.dsi.fastutil.objects.ObjectArrayList;
import java.util.List;
import java.util.Iterator;
import it.unimi.dsi.fastutil.objects.Object2ObjectOpenHashMap;
import java.util.Map;
import com.hypixel.hytale.math.vector.Vector3d;
import com.hypixel.hytale.math.shape.Box;

public class OctTree<T>
{
    private static final int SIZE = 8;
    private static final int DEFAULT_NODE_CAPACITY = 4;
    private final Node root;
    private final int nodeCapacity;
    
    public OctTree(final double inradius) {
        this(new Box(-inradius, -inradius, -inradius, inradius, inradius, inradius), 4);
    }
    
    public OctTree(final Box boundary) {
        this(boundary, 4);
    }
    
    public OctTree(final Box boundary, final int nodeCapacity) {
        this.root = new Node(boundary);
        this.nodeCapacity = nodeCapacity;
    }
    
    public void add(final Vector3d pos, final T value) {
        this.add(this.root, pos, value);
    }
    
    private boolean add(final Node node, final Vector3d pos, final T value) {
        if (node == null || !node.boundary.containsPosition(pos)) {
            return false;
        }
        if (node.size() < this.nodeCapacity) {
            node.addPoint(pos, value);
            return true;
        }
        if (node.dirs.isEmpty()) {
            this.subdivide(node);
        }
        for (int i = 0; i < 8; ++i) {
            if (this.add(node.dirs.get(i), pos, value)) {
                return true;
            }
        }
        return false;
    }
    
    private void subdivide(final Node node) {
        final Vector3d min = node.boundary.min;
        final double side = node.boundary.width() / 2.0;
        for (int i = 0; i < 8; ++i) {
            final Vector3d subMin = new Vector3d(min.x + (((i & 0x1) > 0) ? side : 0.0), min.y + (((i & 0x2) > 0) ? side : 0.0), min.z + (((i & 0x4) > 0) ? side : 0.0));
            final Box sub = Box.cube(subMin, side);
            node.dirs.add(new Node(sub));
        }
    }
    
    public Map<T, Vector3d> getAllPoints() {
        return this.queryRange(this.root.boundary);
    }
    
    public Map<T, Vector3d> queryRange(final Vector3d position, final double inradius) {
        final Box range = Box.centeredCube(position, inradius);
        return this.queryRange(range);
    }
    
    public Map<T, Vector3d> queryRange(final Box range) {
        final Map<T, Vector3d> out = new Object2ObjectOpenHashMap<T, Vector3d>();
        this.queryRange(this.root, range, out);
        return out;
    }
    
    private void queryRange(final Node node, final Box range, final Map<T, Vector3d> out) {
        if (node == null || !node.boundary.isIntersecting(range)) {
            return;
        }
        for (int i = 0; i < node.size(); ++i) {
            final Vector3d point = node.points[i];
            if (range.containsPosition(point)) {
                final T value = node.values.get(i);
                out.put(value, point);
            }
        }
        for (final Node dir : node.dirs) {
            this.queryRange(dir, range, out);
        }
    }
    
    private class Node
    {
        private final Box boundary;
        private final List<Node> dirs;
        private final Vector3d[] points;
        private final List<T> values;
        private int count;
        
        public Node(final Box boundary) {
            this.dirs = new ObjectArrayList<Node>(8);
            this.points = new Vector3d[OctTree.this.nodeCapacity];
            this.values = new ObjectArrayList<T>(OctTree.this.nodeCapacity);
            this.boundary = boundary;
        }
        
        public int size() {
            return this.count;
        }
        
        public void addPoint(final Vector3d pos, final T value) {
            this.points[this.count++] = pos;
            this.values.add(value);
        }
    }
}