import { Bool, Field, type InferProvable, Option, UInt32, type InferValue, type ProvableHashable, type From, type ProvablePure, type IsPure, MerkleList } from 'o1js';
import { type ProvableHashablePure, type ProvableHashableType, type ProvableHashableWide } from '../o1js-missing.ts';
import { TypeBuilder, TypeBuilderPure } from '../provable-type-builder.ts';
import { StaticArray } from './static-array.ts';
import { type NestedProvableFor } from '../nested.ts';
export { DynamicArray };
export { DynamicArrayBase, provable as provableDynamicArray, type DynamicArrayClass, };
type DynamicArray<T = any, V = any> = DynamicArrayBase<T, V>;
type DynamicArrayClass<T, V> = typeof DynamicArrayBase<T, V> & {
    provable: ProvableHashableWide<DynamicArrayBase<T, V>, V[], (T | V)[]>;
    /**
     * Create a new DynamicArray from an array of values.
     *
     * Note: Both the actual length and the values beyond the original ones will be constant.
     */
    from(v: (T | V)[] | DynamicArrayBase<T, V>): DynamicArrayBase<T, V>;
};
type DynamicArrayClassPure<T, V> = typeof DynamicArrayBase<T, V> & Omit<DynamicArrayClass<T, V>, 'provable'> & {
    provable: ProvableHashableWide<DynamicArrayBase<T, V>, V[], (T | V)[]> & Omit<ProvablePure<DynamicArrayBase<T, V>, V[]>, 'fromValue'>;
};
/**
 * Dynamic-length array type that has a
 * - constant max length, but
 * - dynamic actual length
 *
 * ```ts
 * const Bytes = DynamicArray(UInt8, { maxLength: 32 });
 * ```
 *
 * `maxLength` can be any number from 0 to 2^16-1.
 *
 * **Details**: Internally, this is represented as a static-sized array, plus a Field element
 * that represents the length.
 * The _only_ requirement on these is that the length is less or equal maxLength.
 * In particular, there are no provable guarantees maintained on the content of the static-sized array beyond the actual length.
 * Instead, our methods ensure integrity of array operations _within_ the actual length.
 */
declare function DynamicArray<A extends ProvableHashableType, T extends InferProvable<A> = InferProvable<A>, V extends InferValue<A> = InferValue<A>>(type: A, options: {
    maxLength: number;
}): IsPure<A, Field> extends true ? DynamicArrayClassPure<T, V> : DynamicArrayClass<T, V>;
declare namespace DynamicArray {
    var Base: typeof DynamicArrayBase;
}
declare class DynamicArrayBase<T = any, V = any> {
    /**
     * The internal array, which includes the actual values, padded up to `maxLength` with unconstrained values.
     */
    array: T[];
    /**
     * Length of the array. Guaranteed to be in [0, maxLength].
     */
    length: Field;
    get innerType(): ProvableHashableType<T, V>;
    static get maxLength(): number;
    get maxLength(): number;
    constructor(array: T[], length: Field);
    /**
     * Asserts that 0 <= i < this.length, using a cached check that's not duplicated when doing it on the same variable multiple times.
     *
     * Cost: 1.5
     */
    assertIndexInRange(i: UInt32): void;
    /**
     * Gets value at index i, and proves that the index is in the array.
     *
     * Cost: TN + 1.5
     */
    get(i: UInt32): T;
    /**
     * Gets a value at index i, as an option that is None if the index is not in the array.
     *
     * Note: The correct type for `i` is actually UInt16 which doesn't exist. The method is not complete (but sound) for i >= 2^16.
     *
     * Cost: TN + 2.5
     */
    getOption(i: UInt32): Option<T>;
    /**
     * Gets a value at index i, ASSUMING that the index is in the array.
     *
     * If the index is in fact not in the array, the return value is completely unconstrained.
     *
     * **Warning**: Only use this if you already know/proved by other means that the index is within bounds.
     *
     * Cost: T*N where T = size of the type
     */
    getOrUnconstrained(i: Field): T;
    /**
     * Sets a value at index i and proves that the index is in the array.
     *
     * Cost: 1.5(T + 1)N + 1.5
     */
    set(i: UInt32, value: T): void;
    /**
     * Sets a value at index i, or does nothing if the index is not in the array
     *
     * Cost: 1.5(T + 1)N
     */
    setOrDoNothing(i: Field, value: T): void;
    /**
     * Map every element of the array to a new value.
     *
     * **Warning**: The callback will be passed unconstrained dummy values.
     */
    map<S extends ProvableHashableType>(type: S, f: (t: T, i: number) => From<S>): DynamicArray<InferProvable<S>, InferValue<S>>;
    /**
     * Iterate over all elements of the array.
     *
     * The callback will be passed an element and a boolean `isDummy` indicating whether the value is part of the actual array.
     */
    forEach(f: (t: T, isDummy: Bool, i: number) => void): void;
    /**
     * Iterate over all elements of the array, in reverse order.
     *
     * The callback will be passed an element and a boolean `isDummy` indicating whether the value is part of the actual array.
     *
     * Note: the indices are also passed in reverse order, i.e. we always have `t = this.array[i]`.
     */
    forEachReverse(f: (t: T, isDummy: Bool, i: number) => void): void;
    /**
     * Reduce the array to a single value.
     *
     * The callback will be passed the current state, an element, and a boolean `isDummy` indicating whether the value is part of the actual array.
     */
    reduce<S>(stateType: NestedProvableFor<S>, state: S, f: (state: S, t: T, isDummy: Bool) => S): S;
    /**
     * Split the array at index i, i.e. returns `[slice(0, i), slice(i)]`.
     *
     * If i is 0, the first array will be empty.
     * If i it >= the length, the second array will be empty.
     *
     * Note: this method uses very few constraints, it's only rearranging the array contents
     * and recomputing the two lengths.
     */
    splitAt(i: number): [DynamicArray<T, V>, DynamicArray<T, V>];
    /**
     * Equivalent to `Array.slice(start)`. Supports variable start index.
     */
    slice(start: number | UInt32): DynamicArray<T, V>;
    /**
     * Returns a new array with the elements reversed.
     */
    reverse(): DynamicArray<T, V>;
    /**
     * Dynamic array hash that only depends on the actual values (not the padding).
     *
     * Avoids hash collisions by encoding the number of actual elements at the beginning of the hash input.
     */
    hash(): import("node_modules/o1js/dist/node/lib/provable/field.js").Field;
    /**
     * Convert the array to a MerkleList.
     */
    merkelize(listHash?: (hash: Field, t: T) => Field): MerkleList<T>;
    /**
     * Returns a dynamic number of full chunks and a final, smaller chunk.
     *
     * If the array is evenly divided into chunks, the final chunk has length 0.
     *
     * Note: This method uses very few constraints, it's mostly rearranging the array contents
     * doing a small amount of math on the lengths, and a single `get()` operation on the chunked array.
     */
    chunk(chunkSize: number): [DynamicArray<StaticArray<T, V>, V[]>, DynamicArray<T, V>];
    /**
     * Assert that the array is exactly equal, in its representation in field elements, to another array.
     *
     * Warning: Also checks equality of the padding and maxLength, which don't contribute to the "meaningful" part of the array.
     * Therefore, this method is mainly intended for testing.
     */
    assertEqualsStrict(other: DynamicArray<T, V>): void;
    /**
     * Assert that this array is equal to another.
     *
     * Note: This only requires the length and the actual elements to be equal, not the padding or the maxLength.
     * To check for exact equality, use `assertEqualsStrict()`.
     */
    assertEquals(other: DynamicArray<T, V> | StaticArray<T, V> | (T | V)[]): void;
    /**
     * Concatenate two arrays.
     *
     * The resulting (max)length is the sum of the two individual (max)lengths.
     *
     * **Warning**: This method takes effort proportional to (M + N)*N where M, N are the two maxlengths.
     * It's only recommended to use if at least one of the arrays is small.
     */
    concat(other: DynamicArray<T, V>): DynamicArray<T, V>;
    /**
     * Concatenate two arrays.
     *
     * Alternative to `concat()` that takes effort proportional to (M + N)*M where M, N are the two maxlengths,
     * and also has a better constant.
     *
     * Note: This is better than `concat()` if the arrays are about equal or the first array is smaller.
     * It's worse is the first array is much larger than the second.
     */
    concatTransposed(other: DynamicArray<T, V> | StaticArray<T, V>): DynamicArray<T, V>;
    /**
     * Concatenate two arrays.
     *
     * Alternative to `concat()` that proves correctness of the concatenated array
     * by Poseidon-hashing it element by element. In contrast to `concat()`, the effort is linear in N + M,
     * but with a larger constant.
     *
     * The resulting (max)length is the sum of the two individual (max)lengths.
     */
    concatByHashing(other: DynamicArray<T, V>): DynamicArray<T, V>;
    /**
     * Push a value, without changing the maxLength.
     *
     * Proves that the new length is still within the maxLength, fails otherwise.
     *
     * To grow the maxLength along with the actual length, you can use:
     *
     * ```ts
     * array = array.growMaxLengthBy(1);
     * array.push(value);
     * ```
     *
     * Cost: 1.5(T + 1)N + 2
     */
    push(value: T): void;
    /**
     * Return a version of the same array with a larger maxLength.
     *
     * **Warning**: Does not modify the array, but returns a new one.
     *
     * **Note**: this doesn't cost constraints, but currently doesn't preserve any cached constraints.
     */
    growMaxLengthTo(maxLength: number): DynamicArray<T, V>;
    /**
     * Return a version of the same array with a larger maxLength.
     *
     * **Warning**: Does not modify the array, but returns a new one.
     *
     * **Note**: this doesn't cost constraints, but currently doesn't preserve any cached constraints.
     */
    growMaxLengthBy(maxLength: number): DynamicArray<T, V>;
    /**
     * Mutate this array such that all elements beyond the actual length are set to an empty value.
     */
    normalize(): void;
    /**
     * Assert that the array is normalized, i.e. all padding elements are empty.
     *
     * Note: For completeness, it is probably better to use `normalize()` which uses the same amount
     * of constraints and comes with the same guarantee.
     */
    assertNormalized(): void;
    _indexMasks: Map<Field, Bool[]>;
    _indicesInRange: Set<Field>;
    __dummyMask?: Bool[];
    /**
     * Compute i.equals(j) for all indices j in the static-size array.
     *
     * Costs: 1.5N
     *
     * TODO: equals() could be optimized to just 1 double generic because j is constant, o1js doesn't do that
     */
    _indexMask(i: Field): import("node_modules/o1js/dist/node/lib/provable/bool.js").Bool[];
    /**
     * Tells us which elements are dummies = not actually in the array.
     *
     * 0 0 0 1 1 1 1
     *       ^
     *       length
     */
    _dummyMask(): import("node_modules/o1js/dist/node/lib/provable/bool.js").Bool[];
    /**
     * Returns true if the index is a dummy index,
     * i.e. not actually in the array.
     */
    isDummyIndex(i: number): import("node_modules/o1js/dist/node/lib/provable/bool.js").Bool | undefined;
    toValue(): V[];
    /**
     * Assert that this array contains the given subarray, and returns the index where it starts.
     */
    assertContains(subarray: DynamicArray<T, V> | StaticArray<T, V>, message?: string): import("node_modules/o1js/dist/node/lib/provable/field.js").Field;
}
declare function provable<T, V, Class extends typeof DynamicArrayBase<T, V>>(type: ProvableHashablePure<T, V>, Class: Class): TypeBuilderPure<InstanceType<Class>, V[]>;
declare function provable<T, V, Class extends typeof DynamicArrayBase<T, V>>(type: ProvableHashable<T, V>, Class: Class): TypeBuilder<InstanceType<Class>, V[]>;