import type { ComputeNode, IndirectStorageBufferAttribute, Renderer } from 'three/webgpu';
import type { ComputeBatch } from '../Utils/ComputeBatch.cjs';
import type { TSLStorageNode, TSLUintNode } from '../types/tsl.cjs';
/** Supported number of key bits consumed by each radix pass. */
export type RadixBits = 1 | 2 | 4;
/** Primary/temporary buffer selector tracked between incremental passes. */
export type RadixBufferName = 'Keys' | 'Temp';
/** Scalar and vector storage element types supported by Three r185 `instancedArray()`. */
export type RadixValueNodeType = 'float' | 'int' | 'uint' | 'vec2' | 'ivec2' | 'uvec2' | 'vec3' | 'ivec3' | 'uvec3' | 'vec4' | 'ivec4' | 'uvec4';
/** Uint key storage consumed and produced by the sorter. */
export type RadixKeyStorageNode = TSLStorageNode<'uint'>;
/** Atomic uint storage holding the active element count in indirect mode. */
export type RadixCountStorageNode = TSLStorageNode<'uint'>;
/** Optional payload storage reordered in lockstep with keys. */
export type RadixValueStorageNode<TNodeType extends RadixValueNodeType = RadixValueNodeType> = TSLStorageNode<TNodeType>;
/** Narrow backend capability used to reject the unsupported WebGL path. */
export interface RadixRendererCapabilities {
    isWebGLBackend: boolean;
}
/** Shared options for direct and indirect radix dispatch. */
export interface ComputeRadixSortBaseOptions<TNodeType extends RadixValueNodeType = RadixValueNodeType> {
    values?: RadixValueStorageNode<TNodeType> | undefined;
    workgroupSize?: number | undefined;
    radixBits?: RadixBits | undefined;
    keyBits?: number | undefined;
}
/** Direct dispatch may still clamp its active count without changing dispatch dimensions. */
export interface ComputeRadixSortDirectOptions<TNodeType extends RadixValueNodeType = RadixValueNodeType> extends ComputeRadixSortBaseOptions<TNodeType> {
    indirect?: false | undefined;
    countBuffer?: RadixCountStorageNode | undefined;
}
/** Indirect dispatch requires an atomic active-count buffer. */
export interface ComputeRadixSortIndirectOptions<TNodeType extends RadixValueNodeType = RadixValueNodeType> extends ComputeRadixSortBaseOptions<TNodeType> {
    indirect: true;
    countBuffer: RadixCountStorageNode;
}
/** Configuration for a stable GPU radix-sort graph. */
export type ComputeRadixSortOptions<TNodeType extends RadixValueNodeType = RadixValueNodeType> = ComputeRadixSortDirectOptions<TNodeType> | ComputeRadixSortIndirectOptions<TNodeType>;
/** Ordered histogram → scan chunks → scan totals → scan apply → scatter pass. */
export type RadixPassNodes = [
    histogram: ComputeNode,
    scanChunks: ComputeNode,
    scanTotals: ComputeNode,
    scanApply: ComputeNode,
    scatter: ComputeNode
];
/** Flattened single-submit compute batch for all radix passes and optional alignment. */
export type RadixComputeBatch = ComputeBatch;
/** Three.js indirect dispatch attribute owned by an indirect sorter. */
export type RadixIndirectDispatchBuffer = IndirectStorageBufferAttribute;
/** Runtime workgroup-local uint array used by Blelloch scan kernels. */
export interface RadixUintWorkgroupArrayNode {
    readonly isNode: true;
    readonly isWorkgroupInfoNode?: true;
    element(index: TSLUintNode | number): TSLUintNode;
}
/**
 * GPU-accelerated stable radix sort using workgroup-local Blelloch scans and a
 * fully parallel reduce-then-scan global phase.
 *
 * ComputeRadixSort provides an O(n) stable sorting algorithm that runs entirely on the GPU.
 * It uses a configurable radix (1, 2, or 4 bits per pass) with workgroup-local prefix sums,
 * and submits ALL passes in a single `renderer.compute()` batch (one queue submit) by baking
 * each pass's bit offset into a specialized kernel instead of mutating a uniform between
 * submissions.
 *
 * ## Algorithm (per N-bit pass)
 *
 * 1. **Local histogram + prefix sum**: each workgroup counts digit occurrences and computes
 *    per-element local prefix sums in shared memory (Blelloch scan).
 * 2. **Global scan (parallel)**: an exclusive scan over the flattened digit-major
 *    (digit × workgroup) count matrix. Because the layout is digit-major, one flat exclusive
 *    scan yields `digitBase + cumulativeWithinDigit` for every (digit, workgroup) slot in a
 *    single pass — no single-thread loops anywhere (reference-goal WS2: the previous
 *    implementation serialized ~2·buckets·workgroups global-memory operations on one thread).
 *    Implemented as reduce-then-scan: per-chunk Blelloch scans → single-workgroup scan of
 *    chunk totals → parallel offset apply. Portable by construction — no decoupled-lookback /
 *    OneSweep spin-waiting, which is pathological on Apple/Mali/Adreno.
 * 3. **Scatter**: destination = scannedCounts[digit][workgroup] + localPrefix. Deterministic
 *    positions, no atomics — the sort is stable.
 *
 * ## Radix Bits Configuration
 *
 * | Bits | Buckets | Passes (16-bit keys) | Best For |
 * |------|---------|----------------------|----------|
 * | 1    | 2       | 16                   | Small datasets, low memory |
 * | 2    | 4       | 8                    | General use (default) |
 * | 4    | 16      | 4                    | Large datasets, fewer passes |
 *
 * ## Usage
 *
 * ```javascript
 * import { instancedArray } from 'three/tsl';
 * import { ComputeRadixSort } from 'three-blocks/experimental/compute-foundations';
 *
 * const keysBuffer = instancedArray(new Uint32Array([5, 2, 8, 1, 9, 3]), 'uint');
 * const valuesBuffer = instancedArray(new Uint32Array([50, 20, 80, 10, 90, 30]), 'uint');
 * const sorter = new ComputeRadixSort(keysBuffer, { values: valuesBuffer });
 *
 * // In your render loop (one queue submit for the whole sort):
 * sorter.compute(renderer);
 * // Result: keys = [1, 2, 3, 5, 8, 9], values = [10, 20, 30, 50, 80, 90]
 * ```
 *
 * @class ComputeRadixSort
 * @short Stable GPU radix sort; O(n), parallel global scan, single-submit passes
 * @category Compute
 * @tags WebGPU
 */
export declare class ComputeRadixSort<TValueNodeType extends RadixValueNodeType = RadixValueNodeType> {
    keysBuffer: RadixKeyStorageNode;
    valuesBuffer: RadixValueStorageNode<TValueNodeType> | null;
    count: number;
    countBuffer: RadixCountStorageNode | null;
    indirect: boolean;
    keyBits: number;
    radixBits: RadixBits;
    bucketCount: number;
    bitMask: number;
    passCount: number;
    workgroupSize: number;
    elementsPerWorkgroup: number;
    workgroupCount: number;
    flatCountLength: number;
    scanChunkCount: number;
    initialized: boolean;
    readBufferName: RadixBufferName;
    tempKeysBuffer: RadixKeyStorageNode | null;
    tempValuesBuffer: RadixValueStorageNode<TValueNodeType> | null;
    localPrefixBuffer: RadixKeyStorageNode | null;
    digitCountsBuffer: RadixKeyStorageNode | null;
    chunkTotalsBuffer: RadixKeyStorageNode | null;
    _dispatchArgs: RadixIndirectDispatchBuffer | null | undefined;
    _alignDispatchArgs: RadixIndirectDispatchBuffer | null | undefined;
    _renderer: Renderer | null | undefined;
    _prepareDispatchFn: ComputeNode | null | undefined;
    _scanChunksFn: ComputeNode | null | undefined;
    _scanTotalsFn: ComputeNode | null | undefined;
    _scanApplyFn: ComputeNode | null | undefined;
    _passNodes: RadixPassNodes[] | null | undefined;
    _alignFn: ComputeNode | null | undefined;
    _allPassNodes: RadixComputeBatch | null | undefined;
    timestampContexts: Array<ComputeNode | ComputeNode[]>;
    /**
     * Creates a new GPU radix sorter.
     *
     * @param {StorageBufferNode} keysBuffer - The storage buffer containing uint32 keys to sort.
     * @param {Object} [options={}] - Configuration options.
     * @param {StorageBufferNode} [options.values] - Optional buffer of values to sort alongside keys.
     * @param {number} [options.workgroupSize=256] - The workgroup size for compute shaders.
     * @param {number} [options.radixBits=2] - Bits per sorting pass (1, 2, or 4). Higher values mean fewer passes but more memory.
     * @param {number} [options.keyBits=32] - Effective key width in bits (1 to 32). Reduce this when keys use a smaller known range.
     * @param {StorageBufferNode} [options.countBuffer] - Optional atomic uint buffer containing the active element count.
     * @param {boolean} [options.indirect=false] - Dispatch only the active range from countBuffer.
     */
    constructor(keysBuffer: RadixKeyStorageNode, options?: ComputeRadixSortOptions<TValueNodeType>);
    /**
     * Whether the flattened histogram of a configuration fits the single-workgroup totals scan.
     * @private
     */
    static _scanFits(count: number, radixBits: RadixBits, requestedWorkgroupSize: number): boolean;
    /**
     * Allocates GPU buffers for the radix sort algorithm.
     *
     * Buffer count is kept minimal to stay within WebGPU limits (typically 8 storage buffers per bind group).
     * Total buffers: keysBuffer, tempKeysBuffer, [valuesBuffer, tempValuesBuffer], localPrefixBuffer,
     * digitCountsBuffer, chunkTotalsBuffer = 5-7 buffers.
     *
     * @private
     */
    _allocateBuffers(): void;
    /**
     * Initializes the sorter for the given renderer.
     *
     * @param {WebGPURenderer} renderer - The Three.js WebGPU renderer.
     */
    init(renderer: Renderer): void;
    /**
     * Builds all compute shaders for the radix sort algorithm.
     *
     * Every pass gets its own histogram/scatter kernels with the pass's bit offset baked in as a
     * constant, so the full sort submits as ONE `renderer.compute()` batch instead of one queue
     * submission per pass (a uniform mutated between submissions forces a submit per pass).
     * The global-scan kernels carry no per-pass state and are shared across passes.
     *
     * @private
     */
    _buildComputeShaders(): void;
    /**
     * Read the clamped active element count inside a compute shader.
     * @private
     * @returns {Node.<uint>} Active element count.
     */
    _getActiveCount(): TSLUintNode;
    /**
     * Active workgroup count derived from the active element count.
     * @private
     * @returns {Node.<uint>} Number of workgroups holding live histogram data this frame.
     */
    _getActiveWorkgroupCount(): TSLUintNode;
    /**
     * Builds the kernel that derives indirect dispatch arguments from the active count.
     * @private
     */
    _buildPrepareDispatch(): ComputeNode;
    /**
     * Builds Phase 1: Local histogram + prefix sum kernel for one pass.
     *
     * This kernel:
     * 1. Loads elements and categorizes by the pass's N-bit digit (baked constant)
     * 2. Uses bucketCount workgroup arrays to mark which digit each element has
     * 3. Runs Blelloch scan on all arrays to compute local prefix sums
     * 4. Outputs per-element local offsets and per-workgroup bucket totals
     *
     * @private
     */
    _buildPhase1(readKeys: RadixKeyStorageNode, bitOffset: number, name: string): ComputeNode;
    /**
     * Global scan, stage A: parallel per-chunk exclusive Blelloch scans over the flattened
     * digit-major count matrix, emitting per-chunk totals. Indirect frames guard inactive
     * workgroups' (stale) histogram slots to zero at load time.
     *
     * @private
     */
    _buildScanChunks(): ComputeNode;
    /**
     * Global scan, stage B: single-workgroup exclusive Blelloch scan of the chunk totals.
     * scanChunkCount is bounded by MAX_SCAN_CHUNKS (= SCAN_ELEMENTS), so one workgroup suffices.
     *
     * @private
     */
    _buildScanTotals(): ComputeNode;
    /**
     * Global scan, stage C: add each chunk's scanned base offset to its elements, completing the
     * flat exclusive scan of the digit-major count matrix.
     *
     * @private
     */
    _buildScanApply(): ComputeNode;
    /**
     * Builds Phase 3: Scatter/reorder kernel for one pass.
     *
     * Destination = scannedCounts[digit][workgroup] + localPrefix. The flat exclusive scan already
     * folded each digit's global base into the per-(digit, workgroup) offsets, so no separate
     * totals lookup is required. Deterministic positions keep the sort stable.
     *
     * @private
     */
    _buildPhase3(readKeys: RadixKeyStorageNode, writeKeys: RadixKeyStorageNode, readValues: RadixValueStorageNode<TValueNodeType> | null, writeValues: RadixValueStorageNode<TValueNodeType> | null, bitOffset: number, name: string): ComputeNode;
    /**
     * Builds align kernel to copy temp back to keys if needed.
     * @private
     */
    _buildAlign(): ComputeNode;
    /**
     * Executes a complete radix sort (all passes) in a single queue submission
     * (two in indirect mode: dispatch-args preparation, then all passes).
     *
     * @param {WebGPURenderer} renderer - The Three.js WebGPU renderer.
     */
    compute(renderer: Renderer): void;
    /**
     * Executes a single radix pass (histogram → global scan → scatter).
     *
     * Call this method `passCount` times (passIndex 0..passCount-1) to complete a sort.
     * Useful for amortizing sort cost across multiple frames.
     *
     * @param {WebGPURenderer} renderer - The Three.js WebGPU renderer.
     * @param {number} passIndex - Pass index (0 to passCount-1).
     */
    computeStep(renderer: Renderer, passIndex: number): void;
    /**
     * Disposes of GPU resources held by this sorter.
     */
    dispose(): void;
}