snuvi-engine/src/me/hammerle/snuviengine/game/BoxList.java

package me.hammerle.snuviengine.game;

import java.util.ConcurrentModificationException;
import java.util.LinkedList;
import java.util.List;
import java.util.function.Consumer;

public class BoxList<T extends IBoxListEntry>
{
    private double maxWidth = 0;
    private double maxHeight = 0;
    
    private final T[] entities;
    private int lastFreeEntity;
    public boolean isIterating = false;
    
    public static class Node
    {
        private Node next = null;
        private Node previous = null;
        private int index = -1;
        private int x = -1;
        private int y = -1;
    }
    
    private final double boxMinX;
    private final double boxMinY;
    private final double boxMaxX;
    private final double boxMaxY;
    
    private final double size;
    
    private final Node[][] nodes;
    
    private final int partionX;
    private final int partionY;
    
    public int amount = 0;
        
    public BoxList(int maxObjects, double x1, double y1, double x2, double y2, double size)
    {
        this.size = size;
        
        boxMinX = Math.min(x1, x2);
        boxMinY = Math.min(y1, y2);
        
        partionX = (int) Math.ceil((Math.max(x1, x2) - boxMinX) / size);
        partionY = (int) Math.ceil((Math.max(y1, y2) - boxMinX) / size);
        
        boxMaxX = partionX * size;
        boxMaxY = partionY * size;
        
        nodes = new Node[partionX][partionY];
        
        entities = (T[]) new IBoxListEntry[maxObjects];
        lastFreeEntity = entities.length - 1;
    }
    
    public Node add(T ent)
    {
        if(isIterating)
        {
            throw new ConcurrentModificationException();
        }
        
        if(maxHeight < ent.getHeight() / 2)
        {
            maxHeight = ent.getHeight() / 2;
        }
        
        if(maxWidth < ent.getWidth() / 2)
        {
            maxWidth = ent.getWidth() / 2;
        }
        
        amount++;
        
        int x = Math.max(Math.min((int) ((ent.getCenterX() + boxMinX) / size), partionX - 1), 0);
        int y = Math.max(Math.min((int) ((ent.getCenterY() + boxMinY) / size), partionY - 1), 0);
        
        Node n = new Node();
        n.index = lastFreeEntity;
        n.x = x;
        n.y = y;
        
        if(nodes[x][y] == null)
        {
            nodes[x][y] = n;
        }
        else
        {
            n.next = nodes[x][y];
            nodes[x][y].previous = n;
            nodes[x][y] = n;
        }
        
        entities[lastFreeEntity--] = ent;
        
        return n;
    }
    
    public void remove(Node n)
    {
        if(isIterating)
        {
            throw new ConcurrentModificationException();
        }
        
        if(n.previous != null)
        {
            n.previous.next = n.next;
        }
        else
        {
            nodes[n.x][n.y] = n.next;
        }
        
        if(n.next != null)
        {
            n.next.previous = n.previous;
        }
        
        if(lastFreeEntity + 1 == entities.length)
        {
            entities[n.index] = null;
        }
        else
        {
            lastFreeEntity++;
            T ent = entities[lastFreeEntity];
            entities[n.index] = ent;
            ent.getNode().index = n.index;
            entities[lastFreeEntity] = null;
        }
        
        n.next = null;
        n.previous = null;
        
        amount--;
    }
    
    public void update(Entity ent)
    {
        int x = Math.max(Math.min((int) (((ent.xPos + ent.width / 2) + boxMinX) / size), partionX - 1), 0);
        int y = Math.max(Math.min((int) (((ent.yPos + ent.height / 2) + boxMinY) / size), partionY - 1), 0);
        
        Node n = ent.node;
        if(n.x == x && n.y == y)
        {
            return;
        }
        
        if(n.previous != null)
        {
            n.previous.next = n.next;
        }
        else
        {
            nodes[n.x][n.y] = n.next;
        }
        
        if(n.next != null)
        {
            n.next.previous = n.previous;
        }
        
        n.x = x;
        n.y = y;
        n.previous = null;
        
        if(nodes[x][y] == null)
        {
            nodes[x][y] = n;
            n.next = null;
        }
        else
        {
            n.next = nodes[x][y];
            nodes[x][y].previous = n;
            nodes[x][y] = n;
        }
    }
    
    public List<T> getAllEntitiesAt(T not, double minX, double minY, double maxX, double maxY)
    {
        int sx = Math.max(Math.min((int) ((minX + boxMinX - maxWidth) / size), partionX - 1), 0);
        int sy = Math.max(Math.min((int) ((minY + boxMinY - maxHeight) / size), partionY - 1), 0);
        int ex = Math.max(Math.min((int) ((maxX + boxMinX + maxWidth) / size), partionX - 1), 0);
        int ey = Math.max(Math.min((int) ((maxY + boxMinY + maxHeight) / size), partionY - 1), 0);
        
        List<T> list = new LinkedList<>();
        
        for(int x = sx; x <= ex; x++)
        {
            for(int y = sy; y <= ey; y++)
            {
                Node n = nodes[x][y];
                while(n != null)
                {
                    if(not != entities[n.index] && entities[n.index].isColliding(minX, minY, maxX, maxY))
                    {
                        list.add(entities[n.index]);
                    }
                    n = n.next;
                }
            }
        }
        
        return list;
    } 
    
    public void forEach(Consumer<T> c)
    {
        isIterating = true;
        for(int i = lastFreeEntity + 1; i < entities.length; i++)
        {
            c.accept(entities[i]);
        }
        isIterating = false;
    }

    @Override
    public String toString()
    {
        StringBuilder sb = new StringBuilder();
        for(T ent : entities)
        {
            sb.append(ent);
            sb.append(", ");
        }
        return sb.toString();
    }
}