import { QuadTreeNode } from "./QuadTreeNode";

export class Quadtree {
    public max_objects: number;
    public max_levels: number;
    public level: number;
    public bounds: {
        x: number;
        y: number;
        width: number;
        height: number;
    };
    public objects: Array<QuadTreeNode>;
    public nodes: Array<Quadtree>;


    // 缓存常用计算结果
    private verticalMidpoint: number;
    private horizontalMidpoint: number;
    private subWidth: number;
    private subHeight: number;


    /**
     * Quadtree Constructor
     * @param {Object} bounds            bounds of the node { x, y, width, height }
     * @param {number} max_objects      (optional) max objects a node can hold before splitting into 4 subnodes (default: 10)
     * @param {number} max_levels       (optional) total max levels inside root Quadtree (default: 4)
     * @param {number} level            (optional) depth level, required for subnodes (default: 0)
     */
    constructor(bounds: { x: number; y: number; width: number; height: number },
        max_objects: number = 10,
        max_levels: number = 4,
        level: number = 0) {
        this.max_objects = max_objects;
        this.max_levels = max_levels;
        this.level = level;
        this.bounds = bounds;
        this.objects = [];
        this.nodes = [];

        // 预计算常用值
        this.verticalMidpoint = bounds.x + (bounds.width * 0.5);
        this.horizontalMidpoint = bounds.y + (bounds.height * 0.5);
        this.subWidth = bounds.width * 0.5;
        this.subHeight = bounds.height * 0.5;
    }


    // 对象池用于复用四叉树节点
    private static nodePool: Quadtree[] = [];

    private static createNode(bounds: any, max_objects: number, max_levels: number, level: number): Quadtree {
        if (this.nodePool.length > 0) {
            const node = this.nodePool.pop();
            node.init(bounds, max_objects, max_levels, level);
            return node;
        }
        return new Quadtree(bounds, max_objects, max_levels, level);
    }

    private init(bounds: any, max_objects: number, max_levels: number, level: number): void {
        this.bounds = bounds;
        this.max_objects = max_objects;
        this.max_levels = max_levels;
        this.level = level;
        this.objects.length = 0;
        this.nodes.length = 0;
        this.verticalMidpoint = bounds.x + (bounds.width * 0.5);
        this.horizontalMidpoint = bounds.y + (bounds.height * 0.5);
        this.subWidth = bounds.width * 0.5;
        this.subHeight = bounds.height * 0.5;
    }

    /**
     * Split the node into 4 subnodes
     */
    split(): void {
        const nextLevel = this.level + 1;
        const x = this.bounds.x;
        const y = this.bounds.y;

        // 使用对象池创建子节点
        this.nodes[0] = Quadtree.createNode({
            x: x + this.subWidth,
            y: y,
            width: this.subWidth,
            height: this.subHeight
        }, this.max_objects, this.max_levels, nextLevel);

        this.nodes[1] = Quadtree.createNode({
            x: x,
            y: y,
            width: this.subWidth,
            height: this.subHeight
        }, this.max_objects, this.max_levels, nextLevel);

        this.nodes[2] = Quadtree.createNode({
            x: x,
            y: y + this.subHeight,
            width: this.subWidth,
            height: this.subHeight
        }, this.max_objects, this.max_levels, nextLevel);

        this.nodes[3] = Quadtree.createNode({
            x: x + this.subWidth,
            y: y + this.subHeight,
            width: this.subWidth,
            height: this.subHeight
        }, this.max_objects, this.max_levels, nextLevel);
    }


    /**
     * Determine which node the object belongs to
     * @return Array            an array of indexes of the intersecting subnodes
     *                          (0-3 = top-right, top-left, bottom-left, bottom-right / ne, nw, sw, se)
     * @param node
     */
    getIndex(node: QuadTreeNode): number[] {
        const indexes: number[] = [];

        // 使用预计算的中点值
        const startIsNorth = node.y < this.horizontalMidpoint;
        const startIsWest = node.x < this.verticalMidpoint;
        const endIsEast = node.x + node.width > this.verticalMidpoint;
        const endIsSouth = node.y + node.height > this.horizontalMidpoint;

        if (startIsNorth && endIsEast) indexes.push(0);
        if (startIsWest && startIsNorth) indexes.push(1);
        if (startIsWest && endIsSouth) indexes.push(2);
        if (endIsEast && endIsSouth) indexes.push(3);

        return indexes;
    }


    /**
     * Insert the object into the node. If the node
     * exceeds the capacity, it will split and add all
     * objects to their corresponding subnodes.
     * @param node
     */
    insert(node: QuadTreeNode): void {
        if (this.nodes.length) {
            const indexes = this.getIndex(node);
            for (let i = 0; i < indexes.length; i++) {
                this.nodes[indexes[i]].insert(node);
            }
            return;
        }

        this.objects.push(node);

        if (this.objects.length > this.max_objects && this.level < this.max_levels) {
            if (!this.nodes.length) {
                this.split();
            }

            // 使用临时数组避免频繁的数组操作
            const tempObjects = this.objects;
            this.objects = [];

            for (let i = 0; i < tempObjects.length; i++) {
                const obj = tempObjects[i];
                const indexes = this.getIndex(obj);
                for (let k = 0; k < indexes.length; k++) {
                    this.nodes[indexes[k]].insert(obj);
                }
            }
        }
    }

    // 使用 Set 来去重，比 filter 更快
    private static uniqueSet = new Set<QuadTreeNode>();

    /**
     * Return all objects that could collide with the given object
     * @return Array            array with all detected objects
     * @param node
     */
    retrieve(node: QuadTreeNode): QuadTreeNode[] {
        const indexes = this.getIndex(node);
        let returnObjects = this.objects;

        if (this.nodes.length) {
            for (let i = 0; i < indexes.length; i++) {
                returnObjects = returnObjects.concat(this.nodes[indexes[i]].retrieve(node));
            }
        }

        // 只在根节点进行去重
        if (this.level === 0 && returnObjects.length > 0) {
            Quadtree.uniqueSet.clear();
            for (let i = 0; i < returnObjects.length; i++) {
                Quadtree.uniqueSet.add(returnObjects[i]);
            }
            returnObjects = Array.from(Quadtree.uniqueSet);
        }

        return returnObjects;
    }


    /**
     * Clear the quadtree
     */
    clear(): void {
        this.objects.length = 0;

        for (let i = 0; i < this.nodes.length; i++) {
            if (this.nodes[i]) {
                this.nodes[i].clear();
                // 将节点放回对象池
                Quadtree.nodePool.push(this.nodes[i]);
            }
        }
        this.nodes.length = 0;
    }
}