import * as THREE from 'three/webgpu';
import type { ComputeNode, Renderer } from 'three/webgpu';
import { ComputeRadixSort } from '../../Compute/ComputeRadixSort.cjs';
import { ComputeBitonicSort } from '../../Compute/ComputeBitonicSort.cjs';
import { ComputePrefixSum } from '../../Compute/ComputePrefixSum.cjs';
import type { SpatialLookupCellNode, SpatialLookupHelpers, SpatialLookupVectorNode } from './compute/helpers.cjs';
import type { TSLStorageNode, TSLUniformNode } from '../../types/tsl.cjs';
export type SpatialGridSortAlgorithm = 'auto' | 'bitonic' | 'radix';
export type SpatialGridEffectiveSortAlgorithm = Exclude<SpatialGridSortAlgorithm, 'auto'>;
export type SpatialGridBuildAlgorithm = 'auto' | 'sort' | 'atomic';
export type SpatialGridEffectiveBuildAlgorithm = Exclude<SpatialGridBuildAlgorithm, 'auto'>;
export type SpatialGridLookupAlgorithm = 'global' | 'workgroup';
export interface SpatialGridOptions {
    is3D?: boolean | undefined;
    kernelRadius?: number | undefined;
    domainDimensions?: THREE.Vector3 | undefined;
    debug?: boolean | undefined;
    sortAlgorithm?: SpatialGridSortAlgorithm | undefined;
    buildAlgorithm?: SpatialGridBuildAlgorithm | undefined;
    cellSizeScale?: number | undefined;
    maxCellsPerParticle?: number | undefined;
    lookupAlgorithm?: SpatialGridLookupAlgorithm | undefined;
    lookupWorkgroupSize?: number | undefined;
    profile?: boolean | undefined;
}
export interface SpatialGridUpdateOptions {
    allocate?: boolean | undefined;
}
export interface SpatialGridUniforms {
    grid_cell_size: TSLUniformNode<'vec3', THREE.Vector3>;
    grid_resolution: TSLUniformNode<'vec3', THREE.Vector3>;
    count_cells: TSLUniformNode<'uint', number>;
    domainDimensions: TSLUniformNode<'vec3', THREE.Vector3>;
    domainMatrix: TSLUniformNode<'mat4', THREE.Matrix4>;
    kernel_radius: TSLUniformNode<'float', number>;
    particleCount: TSLUniformNode<'uint', number>;
    max_particles: TSLUniformNode<'uint', number>;
}
export interface SpatialGridBuffers {
    cellHashes: TSLStorageNode<'uint'> | null;
    particleIds: TSLStorageNode<'uint'> | null;
    cell_offsets: TSLStorageNode<'uint'> | null;
    cellOffsetsAtomic: TSLStorageNode<'uint'> | null;
    sortData: TSLStorageNode<'uvec2'> | null;
    cellCursors: TSLStorageNode<'uint'> | null;
    cellCursorsAtomic: TSLStorageNode<'uint'> | null;
    candidateVisits: TSLStorageNode<'uint'> | null;
}
export interface SpatialGridProfile {
    builds: number;
    lastBuildCpuMs: number;
    candidateVisits?: number | undefined;
}
export type SpatialGridVectorNode = SpatialLookupVectorNode;
export type SpatialGridCellNode = SpatialLookupCellNode;
export type SpatialGridPositionToCellCoordsFunction = SpatialLookupHelpers['positionToCellCoords'];
export type SpatialGridCellKeyToHashFunction = SpatialLookupHelpers['cellKeyToHash'];
interface SpatialGridBackendOptions {
    buildAlgorithm: SpatialGridEffectiveBuildAlgorithm;
    sortAlgorithm: SpatialGridEffectiveSortAlgorithm;
    lookupAlgorithm: SpatialGridLookupAlgorithm;
}
type SpatialGridSorter = ComputeBitonicSort | ComputeRadixSort<'uint'>;
/**
 * Spatial hashing grid to accelerate neighbor queries for particle simulations.
 *
 * Responsibilities:
 * - Build cell offsets and particle IDs with an automatic backend-appropriate algorithm.
 * - Provide helper functions to map positions to cell coordinates and hash keys.
 *
 * Builder Algorithms:
 * - 'auto' (default): Uses atomic count → prefix scan → scatter on WebGPU and bitonic sorting on WebGL.
 * - 'sort': Uses radix sorting on WebGPU by default and bitonic sorting on WebGL.
 * - 'atomic': Forces the WebGPU atomic builder while retaining the WebGL sorted fallback.
 *
 * Usage:
 * - Call `setInput(positions, particleCount)` to set the input buffer and allocate internal buffers.
 * - Call `computeGrid(renderer)` every frame before neighbor-dependent compute passes.
 *
 * @class SpatialGrid
 * @category Simulation
 * @tags WebGPU
 * @private
 * This implementation-level API is intentionally internal and has no public package import.
 */
declare class SpatialGrid {
    is3D: boolean;
    _requestedBuildAlgorithm: SpatialGridBuildAlgorithm;
    _requestedSortAlgorithm: SpatialGridSortAlgorithm;
    _requestedLookupAlgorithm: SpatialGridLookupAlgorithm;
    buildAlgorithm: SpatialGridEffectiveBuildAlgorithm;
    sortAlgorithm: SpatialGridEffectiveSortAlgorithm;
    cellSizeScale: number;
    maxCellsPerParticle: number;
    lookupAlgorithm: SpatialGridLookupAlgorithm;
    lookupWorkgroupSize: number;
    profile: boolean;
    debug: boolean;
    gridCellSize: THREE.Vector3;
    gridResolution: THREE.Vector3;
    gridCellCount: number;
    _domainMatrix: THREE.Matrix4;
    ubos: SpatialGridUniforms;
    inputPositions: TSLStorageNode<'vec3'> | null;
    particleMaxCount: number;
    workgroupSize: number;
    workgroupSizeVec: [number];
    workGroupsCount: [number];
    buffers: SpatialGridBuffers;
    cellOffsetsCapacity: number;
    prefixSum: ComputePrefixSum | null;
    _backendSignature: string | null;
    stats: Pick<SpatialGridProfile, 'builds' | 'lastBuildCpuMs'>;
    sorter: SpatialGridSorter | null;
    splitCompute: ComputeNode | null;
    computeScatter: ComputeNode | null;
    clearOffsets: ComputeNode | null | undefined;
    clearCandidateVisits: ComputeNode | null | undefined;
    computeIndices: ComputeNode | null | undefined;
    computeOffsets: ComputeNode | null | undefined;
    positionToCellCoords: SpatialGridPositionToCellCoordsFunction;
    cellKeyToHash: SpatialGridCellKeyToHashFunction;
    /**
   * Grid-only structure to accelerate neighbor queries.
   * - Call setInput(positions, particleMaxCount) once (or when particle count changes)
   * - Call computeGrid(renderer) every frame *before* your neighbor-dependent compute passes.
   * @param {Object} options - Configuration options.
   * @param {boolean} [options.is3D=false] - Whether to use 3D spatial grid.
   * @param {number} [options.kernelRadius=1.0] - Kernel radius for neighbor queries.
   * @param {THREE.Vector3} [options.domainDimensions] - Domain dimensions.
     * @param {boolean} [options.debug=false] - Enable debug mode.
     * @param {'auto'|'bitonic'|'radix'} [options.sortAlgorithm='auto'] - Sorting algorithm to use.
     *   'auto' selects radix on WebGPU and bitonic on WebGL.
     *   'bitonic' uses ComputeBitonicSort (WebGPU + WebGL compatible).
     *   'radix' uses ComputeRadixSort (WebGPU only, O(n) complexity).
     * @param {'auto'|'sort'|'atomic'} [options.buildAlgorithm='auto'] - Grid builder implementation.
     *   'auto' selects atomic on WebGPU and sorted grids on WebGL.
     *   'atomic' uses count → prefix scan → scatter and requires WebGPU.
         * @param {number} [options.cellSizeScale=1.0] - Cell size multiplier applied to the neighbor radius. Values below 1 are clamped.
         * @param {number} [options.maxCellsPerParticle=4] - Hard cap used to prevent oversized sparse offset tables.
         * @param {'global'|'workgroup'} [options.lookupAlgorithm='global'] - Neighbor lookup implementation. Workgroup lookup requires the atomic builder.
         * @param {number} [options.lookupWorkgroupSize=64] - Shared-memory lookup tile size, rounded down to a power of two.
     * @param {boolean} [options.profile=false] - Allocate an optional GPU candidate-visit counter.
   */
    constructor({ is3D, kernelRadius, domainDimensions, debug, sortAlgorithm, buildAlgorithm, cellSizeScale, maxCellsPerParticle, lookupAlgorithm, lookupWorkgroupSize, profile, }?: SpatialGridOptions);
    _resolveBackendOptions(renderer: Renderer): SpatialGridBackendOptions;
    _syncBackend(renderer: Renderer): boolean;
    _disposeNode(node: unknown): void;
    _disposeBuilder(): void;
    _allocateOffsets(neededSize: number, growthFactor?: number): void;
    _syncRadixKeyBits(): void;
    /**
   * Update kernel radius and/or domain dimensions, recomputing grid cell size,
   * resolution, and internal buffers. Rebuilds compute passes to update dispatch sizes.
   * @param {number} newKernelRadius
   * @param {THREE.Vector3} [newDomainDimensions]
     * @returns {boolean} true if dependent passes require rebuilding.
   */
    updateKernelRadius(newKernelRadius: number | null | undefined, newDomainDimensions?: THREE.Vector3 | undefined, { allocate }?: SpatialGridUpdateOptions): boolean;
    /**
     * Set the input positions buffer and particle count. Allocates grid buffers and initializes sorter.
     * @param {import('../../types/tsl.js').TSLStorageNode<'vec3'>} positions - Position storage (vec3 per particle).
     * @param {number} particleCount - Active particle count.
     */
    setInput(positions: TSLStorageNode<'vec3'>, particleCount: number): void;
    _buildHelpers(): void;
    _buildCompute(): void;
    /**
   * Build/update the grid for current positions: compute indices, sort by cell key, and compute cell offsets.
   * Should be called before any neighbor-dependent compute pass each frame.
   * @param {THREE.WebGPURenderer} renderer
   */
    computeGrid(renderer: Renderer): boolean;
    resetProfileCounters(renderer: Renderer): void;
    getProfile(): SpatialGridProfile;
    /**
     * Read CPU submission stats and the optional GPU candidate counter.
     * Reading the GPU counter synchronizes with the renderer and should only be used for profiling.
     *
     * @param {THREE.WebGPURenderer} renderer
     * @returns {Promise<Object>}
     */
    readProfile(renderer: Renderer): Promise<SpatialGridProfile>;
    dispose(): void;
}
export { SpatialGrid };