import type { ComputeNode, Renderer } from 'three/webgpu';
import type { TSLStorageNode, TSLUniformNode, TSLUintNode } from '../types/tsl.js';
export interface ComputePrefixSumOptions {
    workgroupSize?: number | undefined;
    /**
     * Largest element count this prefix-sum graph must support. Keeping this bound
     * stable between shader capture and replay fixes the recursive pass topology,
     * while the live buffer count is supplied to WGSL through uniforms.
     *
     * Defaults to the current buffer count for fixed-size uses.
     */
    maxCount?: number | undefined;
}
export interface ComputePrefixSumBatch extends Array<ComputeNode> {
    id: string;
    name: 'PrefixSum';
    isComputeNode: true;
}
interface UintWorkgroupArrayNode {
    readonly isNode: true;
    element(index: TSLUintNode | number): TSLUintNode;
}
/**
 * GPU-accelerated parallel prefix sum (exclusive scan) for Three.js TSL compute shaders.
 *
 * ComputePrefixSum implements the Blelloch scan algorithm for computing prefix sums
 * entirely on the GPU. It's designed as a building block for more complex parallel
 * algorithms like radix sort.
 *
 * ## Features
 *
 * - **Fully GPU-accelerated**: All operations execute as compute shaders
 * - **Hierarchical**: Handles arrays larger than a single workgroup via recursive block sums
 * - **Work-efficient**: O(n) work complexity using Blelloch algorithm
 * - **WebGPU only**: Requires workgroup shared memory (not available in WebGL)
 *
 * ## Algorithm
 *
 * The Blelloch scan operates in two phases:
 * 1. **Up-sweep (reduce)**: Build a tree of partial sums from leaves to root
 * 2. **Down-sweep**: Propagate prefix sums from root back to leaves
 *
 * For arrays larger than workgroup capacity, the algorithm:
 * 1. Computes local prefix sums per workgroup
 * 2. Extracts block sums (total per workgroup)
 * 3. Recursively computes prefix sum on block sums
 * 4. Adds block prefix sums back to each element
 *
 * ## Usage
 *
 * ```javascript
 * import { instancedArray } from 'three/tsl';
 * import { ComputePrefixSum } from 'three-blocks/experimental/compute-foundations';
 *
 * // Create a buffer of uint values
 * const data = instancedArray(new Uint32Array([3, 1, 4, 1, 5, 9, 2, 6]), 'uint');
 *
 * // Create prefix sum instance
 * const prefixSum = new ComputePrefixSum(data);
 *
 * // Compute prefix sum
 * prefixSum.compute(renderer);
 * // Result: [0, 3, 4, 8, 9, 14, 23, 25]
 * ```
 *
 * @class ComputePrefixSum
 * @short GPU parallel prefix sum using Blelloch scan algorithm
 * @category Compute
 * @tags WebGPU
 */
export declare class ComputePrefixSum {
    id: number;
    dataBuffer: TSLStorageNode<'uint'>;
    count: number;
    countUniform: TSLUniformNode<'uint', number>;
    maxCount: number;
    hierarchyDepth: number;
    workgroupSize: number;
    itemsPerWorkgroup: number;
    workgroupCount: number;
    localStorage: UintWorkgroupArrayNode | null;
    blockSumsBuffer: TSLStorageNode<'uint'> | null;
    blockPrefixSum: ComputePrefixSum | null;
    localScanFn: ComputeNode | null;
    addBlockSumsFn: ComputeNode | null;
    computeBatch: ComputePrefixSumBatch | null;
    initialized: boolean;
    _renderer: Renderer | null | undefined;
    /**
     * Creates a new ComputePrefixSum instance.
     *
     * @param {StorageBufferNode} dataBuffer - The storage buffer containing uint elements.
     * @param {Object} [options={}] - Configuration options.
     * @param {number} [options.workgroupSize=128] - The workgroup size for compute shaders.
     *   Each workgroup processes 2 * workgroupSize elements. Must be a power of 2.
     * @param {number} [options.maxCount=dataBuffer.value.count] - Maximum replay-time
     *   element count used to keep the recursive shader topology stable.
     */
    constructor(dataBuffer: TSLStorageNode<'uint'>, options?: ComputePrefixSumOptions);
    /**
     * Initializes the prefix sum for the given renderer.
     *
     * @param {WebGPURenderer} renderer - The Three.js WebGPU renderer.
     * @throws {Error} If the backend is WebGL (not supported).
     */
    init(renderer: Renderer): void;
    /**
     * Creates the compute shader for local prefix sum within workgroups.
     *
     * Implements the Blelloch scan algorithm:
     * 1. Load elements into shared memory
     * 2. Up-sweep: Build partial sums tree
     * 3. Down-sweep: Propagate prefix sums
     * 4. Write results and extract block sum
     *
     * @private
     * @returns {ComputeNode} The local scan compute shader.
     */
    _getLocalScan(): ComputeNode;
    /**
     * Creates the compute shader that adds block prefix sums to elements.
     *
     * After local scans are complete and block sums have their prefix computed,
     * this shader adds each block's prefix to all elements in that block.
     *
     * @private
     * @returns {ComputeNode} The add block sums compute shader.
     */
    _getAddBlockSums(): ComputeNode;
    /**
     * Return ordered compute nodes for a single batched prefix-sum submission.
     *
     * @param {WebGPURenderer} renderer - Three.js renderer used to initialize the graph.
     * @returns {Array<ComputeNode>} Ordered compute nodes.
     */
    getComputeNodes(renderer: Renderer): ComputePrefixSumBatch;
    /**
     * Computes the prefix sum in a single batched submission.
     *
     * @param {WebGPURenderer} renderer - The Three.js WebGPU renderer.
     */
    compute(renderer: Renderer): void;
    /**
     * Disposes of GPU resources held by this instance.
     */
    dispose(): void;
}
export {};