import type { ComputeNode, Renderer } from 'three/webgpu';
import type { TSLBoolNode, TSLFunction, TSLStorageNode, TSLUintNode, TSLUVec2Node, TSLUniformNode } from '../types/tsl.js';
/** Configuration for a GPU bitonic-sort graph. */
export interface ComputeBitonicSortOptions {
    workgroupSize?: number | undefined;
    ascending?: boolean | undefined;
    globalOnly?: boolean | undefined;
}
/** Storage-buffer selector used by the WebGL ping-pong path. */
export type BitonicBufferName = 'Data' | 'Temp';
/** Uvec2 key/id storage consumed and produced by the sort graph. */
export type BitonicStorageNode = TSLStorageNode<'uvec2'>;
/** Global compare stages carry their current compare span. */
export interface BitonicGlobalStage {
    type: 'flipGlobal' | 'disperseGlobal';
    swapSpan: number;
}
/** Workgroup-local stages operate on the already configured local span. */
export type BitonicLocalStage = {
    type: 'swapLocal';
} | {
    type: 'disperseLocal';
};
/** One ordered dispatch in the CPU-side bitonic-sort schedule. */
export type BitonicSortStage = BitonicGlobalStage | BitonicLocalStage;
/** Source-buffer keyed compute nodes; WebGPU only needs the Data entry. */
export type BitonicComputeNodeMap = Partial<Record<BitonicBufferName, ComputeNode | null>>;
/** Workgroup limits read from the active WebGPU device when present. */
export interface BitonicWorkgroupLimits {
    maxComputeWorkgroupSizeX?: number | undefined;
    maxComputeInvocationsPerWorkgroup?: number | undefined;
}
/** Narrow backend capabilities required to choose and size the sort graph. */
export interface BitonicRendererCapabilities {
    isWebGLBackend: boolean;
    limits: BitonicWorkgroupLimits | null;
}
/** Runtime workgroup storage used for local uvec2 compare-and-swap passes. */
export interface BitonicWorkgroupStorageNode {
    readonly isNode: true;
    readonly isWorkgroupInfoNode?: true;
    element(index: TSLUintNode | number): TSLUVec2Node;
}
export type BitonicFlipIndexArguments = [index: TSLUintNode, blockHeight: TSLUintNode];
export type BitonicDisperseIndexArguments = [index: TSLUintNode, swapSpan: TSLUintNode];
export type BitonicCompareArguments = [first: TSLUVec2Node, second: TSLUVec2Node];
export type BitonicIndexFunction<TArguments extends BitonicFlipIndexArguments | BitonicDisperseIndexArguments> = TSLFunction<TArguments, TSLUVec2Node>;
export type BitonicFlipIndexFunction = BitonicIndexFunction<BitonicFlipIndexArguments>;
export type BitonicDisperseIndexFunction = BitonicIndexFunction<BitonicDisperseIndexArguments>;
export type BitonicCompareFunction = TSLFunction<BitonicCompareArguments, TSLBoolNode>;
/**
 * @fileoverview GPU-accelerated Bitonic Sort implementation using Three.js TSL (Three.js Shading Language).
 * @module ComputeBitonicSort
 */
/**
 * Computes the pair of indices to compare during a bitonic flip operation.
 *
 * In a flip operation, elements are compared at mirrored positions within each block.
 * For a block of height `h`, element at position `i` is compared with element at
 * position `h - 1 - i` within the same block.
 *
 * @function
 * @private
 * @param {import('../types/tsl.js').TSLUintNode} index - The compute thread's invocation index.
 * @param {import('../types/tsl.js').TSLUintNode} blockHeight - The height of the block within which elements are being swapped.
 * @returns {import('../types/tsl.js').TSLUVec2Node} A pair of indices (x, y) where x < y, representing the two elements to compare.
 */
/** @type {import('../types/tsl.js').TSLFunction<[import('../types/tsl.js').TSLUintNode, import('../types/tsl.js').TSLUintNode], import('../types/tsl.js').TSLUVec2Node>} */
export declare const getBitonicFlipIndices: BitonicFlipIndexFunction;
/**
 * Computes the pair of indices to compare during a bitonic disperse operation.
 *
 * In a disperse operation, elements are compared at a fixed distance (half the swap span)
 * apart. This operation merges bitonic sequences into sorted sequences.
 *
 * @function
 * @private
 * @param {import('../types/tsl.js').TSLUintNode} index - The compute thread's invocation index.
 * @param {import('../types/tsl.js').TSLUintNode} swapSpan - The span over which elements are being compared (distance * 2).
 * @returns {import('../types/tsl.js').TSLUVec2Node} A pair of indices (x, y) where x < y, representing the two elements to compare.
 */
/** @type {import('../types/tsl.js').TSLFunction<[import('../types/tsl.js').TSLUintNode, import('../types/tsl.js').TSLUintNode], import('../types/tsl.js').TSLUVec2Node>} */
export declare const getBitonicDisperseIndices: BitonicDisperseIndexFunction;
/**
 * @class
 * @short Stable GPU bitonic sort for uvec2 key/id pairs with WebGPU and WebGL paths; used by culling and sims.
 * @category Compute
 * @tags WebGPU
 */
export declare class ComputeBitonicSort {
    dataBuffer: BitonicStorageNode | null;
    count: number;
    dispatchSize: number;
    requestedWorkgroupSize: number | null;
    workgroupSize: number;
    ascending: boolean;
    globalOnly: boolean;
    _compare: BitonicCompareFunction;
    localStorage: BitonicWorkgroupStorageNode | null;
    tempBuffer: BitonicStorageNode | null;
    swapSpanUniform: TSLUniformNode<'uint', number>;
    swapOpCount: number;
    stepCount: number;
    readBufferName: BitonicBufferName;
    flipGlobalNodes: BitonicComputeNodeMap;
    disperseGlobalNodes: BitonicComputeNodeMap;
    swapLocalFn: ComputeNode | null;
    disperseLocalNodes: BitonicComputeNodeMap | null;
    alignFn: ComputeNode | null;
    currentDispatch: number;
    schedule: BitonicSortStage[];
    initialized: boolean;
    isWebGL: boolean;
    useGlobalOnly: boolean | undefined;
    useInPlaceGlobal: boolean | undefined;
    _renderer: Renderer | null | undefined;
    /**
     * GPU-accelerated parallel bitonic sort for Three.js TSL compute shaders.
     *
     * ComputeBitonicSort provides an efficient O(n log²n) parallel sorting algorithm that runs
     * entirely on the GPU. It's designed for sorting large arrays of key-value pairs where
     * deterministic, stable ordering is required. It is used in SPH, PBF, Boids, and ComputeInstanceCulling.
     *
     * ## Features
     *
     * - **Fully GPU-accelerated**: All sorting operations execute as compute shaders
     * - **Stable sorting**: Elements with equal keys maintain their relative order via tie-breaker IDs
     * - **Deterministic**: Produces identical results across frames and devices
     * - **Dual-backend support**: Optimized path for WebGPU, fallback for WebGL
     * - **Workgroup optimization**: Uses shared memory for efficient local sorting (WebGPU)
     * - **Bounds-safe**: Uses local sentinels while requiring power-of-two buffer counts
     *
     * ## Usage
     *
     * ```javascript
     * import { instancedArray } from 'three/tsl';
     * import { ComputeBitonicSort } from './ComputeBitonicSort.js';
     *
     * // Create a buffer of uvec2 pairs: (sortKey, stableId)
     * const count = 1024;
     * const dataBuffer = instancedArray( count, 'uvec2' );
     *
     * // Initialize the sorter
     * const sorter = new ComputeBitonicSort( dataBuffer, { workgroupSize: 64 } );
     *
     * // In your render loop:
     * sorter.compute( renderer ); // Full sort in one call
     *
     * // Or for amortized sorting across frames:
     * sorter.computeStep( renderer ); // One step per frame
     * ```
     *
     * ## Data Format
     *
     * The data buffer must contain `uvec2` elements where:
     * - **x**: The primary sort key (e.g., spatial hash, distance, priority)
     * - **y**: A unique stable ID to break ties deterministically
     *
     * Elements are sorted in ascending order by (x, y) lexicographically.
     *
     * ## Performance Considerations
     *
     * - Buffer count must be a power of 2; pad unused entries with sentinel values
     * - Larger workgroup sizes (64-256) typically perform better on modern GPUs
     * - The `compute()` method executes all steps synchronously; use `computeStep()`
     *   for amortized sorting across multiple frames
     *
     *
     * @param {StorageBufferNode} dataBuffer - The storage buffer containing uvec2 elements to sort.
     *   Each element should be a uvec2 where x is the sort key and y is a stable tie-breaker ID.
     * @param {Object} [options={}] - Configuration options.
     * @param {number} [options.workgroupSize] - The workgroup size for compute shaders.
     *   Must be a power of 2. Larger values (64-256) typically perform better but are limited
     *   by GPU capabilities. Defaults to 256 on WebGPU and 64 on WebGL, then clamps to the
     *   active backend limits and data size.
     * @param {boolean} [options.ascending=true] - Sort direction. If true (default), sorts in
     *   ascending order (smallest keys first). If false, sorts in descending order (largest keys first).
     * @param {boolean} [options.globalOnly=false] - Force global-memory stages while retaining
     *   WebGPU in-place writes. WebGL always uses global stages with ping-pong buffers.
     *
     * @example
     * // Ascending sort (default)
     * const sorter = new ComputeBitonicSort( dataBuffer, { workgroupSize: 128 } );
     *
     * @example
     * // Descending sort (for front-to-back rendering)
     * const sorter = new ComputeBitonicSort( dataBuffer, { workgroupSize: 128, ascending: false } );
     */
    constructor(dataBuffer: BitonicStorageNode, options?: ComputeBitonicSortOptions);
    /**
     * Initializes the sorter for the given renderer.
     *
     * This method detects the backend type (WebGL vs WebGPU) and creates the
     * appropriate compute shaders. Must be called before sorting, but is
     * automatically invoked by `compute()` and `computeStep()` if needed.
     *
     * @param {WebGPURenderer} renderer - The Three.js WebGPU renderer.
     */
    init(renderer: Renderer): void;
    /**
     * Calculates the total number of swap operations in a bitonic sort.
     *
     * @private
     * @returns {number} The number of distinct swap operations: (log2(n) * (log2(n) + 1)) / 2
     */
    _getSwapOpCount(): number;
    /**
     * Builds the CPU-side dispatch schedule for a complete sort.
     *
     * For WebGL (global-only), every compare stage is a global dispatch. For WebGPU,
     * local workgroup stages replace the smaller global merge stages.
     *
     * @private
     * @returns {Array<{type: string, swapSpan?: number}>} Sorting stages in dispatch order.
     */
    _buildSchedule(): BitonicSortStage[];
    /**
     * Performs a compare-and-swap operation in global memory.
     *
     * Reads two elements from the source buffer, compares them, and writes
     * them in sorted order to the destination buffer.
     *
     * @private
     * @param {import('../types/tsl.js').TSLUintNode} idxBefore - Index of the first element.
     * @param {import('../types/tsl.js').TSLUintNode} idxAfter - Index of the second element.
     * @param {StorageBufferNode} dataBuffer - Source buffer to read from.
     * @param {StorageBufferNode} tempBuffer - Destination buffer to write to.
     */
    _globalCompareAndSwapTSL(idxBefore: TSLUintNode, idxAfter: TSLUintNode, dataBuffer: BitonicStorageNode, tempBuffer: BitonicStorageNode): void;
    /**
     * Performs a compare-and-swap operation in workgroup shared memory.
     *
     * Reads two elements from local storage, compares them, and writes
     * them back in sorted order.
     *
     * @private
     * @param {import('../types/tsl.js').TSLUintNode} idxBefore - Local index of the first element.
     * @param {import('../types/tsl.js').TSLUintNode} idxAfter - Local index of the second element.
     */
    _localCompareAndSwapTSL(idxBefore: TSLUintNode, idxAfter: TSLUintNode): void;
    /**
     * Creates the out-of-bounds sentinel for local workgroup padding.
     *
     * @private
     * @returns {import('../types/tsl.js').TSLUVec2Node} Sentinel that sorts after valid elements.
     */
    _getSentinel(): TSLUVec2Node;
    /**
     * Creates a compute shader for global disperse operations.
     *
     * @private
     * @param {StorageBufferNode} readBuffer - Buffer to read elements from.
     * @param {StorageBufferNode} writeBuffer - Buffer to write sorted elements to.
     * @returns {ComputeNode} The disperse compute shader.
     */
    _getDisperseGlobal(readBuffer: BitonicStorageNode, writeBuffer: BitonicStorageNode): ComputeNode;
    /**
     * Creates a compute shader for global flip operations.
     *
     * @private
     * @param {StorageBufferNode} readBuffer - Buffer to read elements from.
     * @param {StorageBufferNode} writeBuffer - Buffer to write sorted elements to.
     * @returns {ComputeNode} The flip compute shader.
     */
    _getFlipGlobal(readBuffer: BitonicStorageNode, writeBuffer: BitonicStorageNode): ComputeNode;
    /**
     * Creates the compute shader for complete local sorting.
     *
     * This shader performs a full bitonic sort on elements within a single workgroup
     * using shared memory. Each workgroup independently sorts 2 * workgroupSize elements.
     *
     * The algorithm:
     * 1. Load elements from global memory into shared memory (with OOB sentinel handling)
     * 2. For each block size k = 2, 4, 8, ..., localSize:
     *    - Perform flip operation with block height k
     *    - For each disperse span j = k/2, k/4, ..., 1:
     *      - Perform disperse operation
     * 3. Write sorted elements back to global memory
     *
     * @private
     * @returns {ComputeNode} The local swap compute shader.
     */
    _getSwapLocal(): ComputeNode;
    /**
     * Creates the compute shader for local disperse operations.
     *
     * This shader performs disperse-only stages in shared memory, used after
     * a global flip to complete the merge operation locally.
     *
     * @private
     * @param {StorageBufferNode} readWriteBuffer - Buffer to read from and write to.
     * @returns {ComputeNode} The local disperse compute shader.
     */
    _getDisperseLocal(readWriteBuffer: BitonicStorageNode): ComputeNode;
    /**
     * Creates the compute shader that copies temp buffer back to data buffer.
     *
     * Used to ensure the final sorted result is in the original data buffer
     * after an odd number of global operations.
     *
     * @private
     * @returns {ComputeNode} The alignment compute shader.
     */
    _getAlignFn(): ComputeNode;
    /**
     * Executes a single step of the bitonic sort.
     *
     * Call this method repeatedly (once per frame) to amortize sorting cost
     * over multiple frames. A complete sort requires `stepCount` calls.
     *
     * The method automatically:
     * - Initializes on first call
     * - Advances through flip/disperse stages
     * - Handles buffer ping-ponging
     * - Resets state when sort completes
     *
     * @param {WebGPURenderer} renderer - The Three.js WebGPU renderer.
     *
     * @example
     * // Amortized sorting - one step per frame
     * function animate() {
     *   sorter.computeStep( renderer );
     *   renderer.render( scene, camera );
     * }
     */
    computeStep(renderer: Renderer): void;
    /**
     * Executes a complete bitonic sort in a single call.
     *
     * This method runs all sorting steps synchronously, which may cause
     * frame drops for large arrays. For real-time applications, consider
     * using `computeStep()` to spread the work across multiple frames.
     *
     * @param {WebGPURenderer} renderer - The Three.js WebGPU renderer.
     *
     * @example
     * // Complete sort in one frame
     * sorter.compute( renderer );
     * // Data buffer is now fully sorted
     */
    compute(renderer: Renderer): void;
    /**
     * Disposes of GPU resources held by this sorter.
     *
     * Call this method when the sorter is no longer needed to free GPU memory.
     * After disposal, the sorter should not be used.
     */
    dispose(): void;
}