import type { Bounds } from "../bounds.ts";
import type World from "../world.js";
import type { Broadphase } from "./broadphase.ts";
/**
 * Minimal axis-aligned rectangle shape consumed by `QuadTree` — the
 * full {@link Bounds} class satisfies it structurally, so do the
 * `{ left, top, width, height }` POJOs `split` allocates for
 * subnodes. Kept as an exported interface so any subclass / adapter
 * that constructs its own root bounds doesn't have to import
 * `Bounds`.
 */
export interface QuadRect {
    left: number;
    top: number;
    width: number;
    height: number;
}
/**
 * Structural shape for an item inserted into the `QuadTree`. Every
 * Renderable satisfies it; `getBounds()` is the only required
 * member. `isFloating` triggers the viewport-localToWorld coord
 * remap; `isKinematic` / `name` / `addChild` are consulted only by
 * `insertContainer` / `removeContainer` when walking a subtree.
 */
export interface QuadTreeItem {
    getBounds(): QuadRect;
    isFloating?: boolean;
    isKinematic?: boolean;
    name?: string;
}
/**
 * Optional comparator passed to {@link QuadTree.retrieve} — invoked
 * once on the assembled candidate array, only when `retrieve` was
 * called in root mode (no caller-supplied `result`).
 */
export type QuadTreeSortFn = (a: QuadTreeItem, b: QuadTreeItem) => number;
/**
 * a QuadTree implementation in JavaScript, a 2d spatial subdivision algorithm.
 * @category Physics
 * @see World.broadphase
 */
export default class QuadTree implements Broadphase<QuadTreeItem> {
    world: World;
    bounds: QuadRect | Bounds;
    max_objects: number;
    max_levels: number;
    level: number;
    objects: QuadTreeItem[];
    nodes: QuadTree[];
    /**
     * Total number of objects in this subtree (this node's own
     * `objects` plus every descendant's). Maintained by `insert`
     * and `remove` so `isPrunable` / `hasChildren` are O(1) reads
     * instead of O(tree-size) walks. Reset to 0 in `clear`.
     * @ignore
     */
    _subtreeCount: number;
    /**
     * Root-only scratch array reused across `retrieve` calls to
     * avoid allocating a fresh array per pointer event / per
     * narrow-phase query. Only the root allocates one; recursive
     * subnode calls receive the array via the `result` arg.
     * @ignore
     */
    _retrieveScratch: QuadTreeItem[] | null;
    /**
     * @param world - the physic world this QuadTree belongs to
     * @param bounds - bounds of the node
     * @param [max_objects=4] - max objects a node can hold before splitting into 4 subnodes
     * @param [max_levels=4] - total max levels inside root QuadTree
     * @param [level] - depth level, required for subnodes
     */
    constructor(world: World, bounds: QuadRect | Bounds, max_objects?: number, max_levels?: number, level?: number);
    split(): void;
    getIndex(item: QuadTreeItem): number;
    /**
     * Insert the given object container into the node.
     *
     * Typed against the structural duck shape (`getChildren() →
     * ContainerOrChild[]`) rather than the concrete `Container` class
     * so the recursive call below — where `child` is the structural
     * `ContainerOrChild` shape from `getChildren()`, not a `Container`
     * instance — type-checks without an `as unknown as Container` cast.
     * `Container` itself satisfies the shape (its `getChildren()`
     * returns `Renderable[]`, which matches the looser structural
     * `ContainerOrChild[]`).
     * @param container - group of objects to be added
     */
    insertContainer(container: ContainerLike): void;
    /**
     * Insert the given object into the node. If the node
     * exceeds the capacity, it will split and add all
     * objects to their corresponding subnodes.
     * @param item - object to be added
     */
    insert(item: QuadTreeItem): void;
    /**
     * Recursively remove the given container and its descendants from
     * the quadtree. Mirrors `insertContainer` so the broadphase can be
     * kept in sync when a subtree is detached via
     * `Container.removeChildNow` between two `world.update()` rebuilds
     * (pointer events fire async in that window and would otherwise
     * hit destroyed renderables).
     * @param container - group of objects to be removed
     */
    removeContainer(container: ContainerLikeOptional): void;
    /**
     * Return all objects that could collide with the given object.
     *
     * **Re-entrancy contract:** when called with no explicit `result`
     * argument, this method reuses a single root-level scratch array to
     * avoid per-frame allocations. The returned reference is therefore
     * **not safe to retain** past the next `retrieve()` call, AND it is
     * **not safe to issue another scratch-mode `retrieve()` while iterating
     * the previous result** — the second call clears the scratch and
     * refills it, corrupting the outer iteration. In-engine callers
     * (`pointerevent.ts`, `detector.js`) iterate synchronously and never
     * recurse into `retrieve()`, so they're fine. User-facing portable
     * APIs (`adapter.queryAABB`, `adapter.raycast`) pass their own array
     * via the `result` parameter, which bypasses the scratch entirely
     * and is safe to call from inside collision handlers.
     * @param item - object to be checked against
     * @param [fn] - a sorting function for the returned array
     * @param [result] - optional caller-supplied result array. Pass an
     *   explicit (typically empty) array to sidestep the shared scratch —
     *   required for re-entrancy safety.
     * @returns array with all detected objects
     */
    retrieve(item: QuadTreeItem, fn?: QuadTreeSortFn, result?: QuadTreeItem[]): QuadTreeItem[];
    /**
     * Remove the given item from the quadtree.
     * (this function won't recalculate the impacted node)
     * @param item - object to be removed
     * @returns true if the item was found and removed.
     */
    remove(item: QuadTreeItem): boolean;
    /**
     * return true if the node is prunable
     * @returns true if the node is prunable
     */
    isPrunable(): boolean;
    /**
     * return true if the node has any children
     * @returns true if the node has any children
     */
    hasChildren(): boolean;
    /**
     * clear the quadtree
     * @param [bounds] - the bounds to be cleared
     */
    clear(bounds?: Bounds): void;
}
/**
 * Structural shape consumed by `insertContainer` / `removeContainer`
 * when walking a Container's `getChildren()`. Captures only the
 * fields the walk inspects — keeps the conversion strict-mode clean
 * without leaking `any`.
 *
 * `getChildren` is optional because leaf renderables don't have it;
 * the recursive `insertContainer` narrows via {@link hasGetChildren}.
 * @ignore
 */
interface ContainerOrChild extends QuadTreeItem {
    addChild?: (...args: unknown[]) => unknown;
    getChildren?: () => ContainerOrChild[];
}
/**
 * Structural shape used as the `insertContainer` /
 * `removeContainer` parameter type. Named (rather than inline) so the
 * JSDoc-aware lint doesn't require nested `@param container.getChildren`
 * documentation at every call site. `Container` itself satisfies this
 * shape; the optional variant covers the case where the World's lazy
 * `children` accessor returns `undefined`.
 * @ignore
 */
type ContainerLike = {
    getChildren(): ContainerOrChild[];
};
/** @ignore */
type ContainerLikeOptional = {
    getChildren?(): ContainerOrChild[];
};
export {};
//# sourceMappingURL=quadtree.d.ts.map