import { OpType } from './utils.cjs';

type Index = readonly [number, number];
/**
 * Node in the backtrace graph corresponding to the index (i, j) in the backtrace matrix.
 */
declare class Node {
    hypIndex: number;
    refIndex: number;
    children: Map<OpType, Node>;
    parents: Map<OpType, Node>;
    constructor(hypIndex: number, refIndex: number);
    get index(): Index;
    /**
     * Get the offset index of th enode so indices match the hypothesis and reference strings.
     *
     * Root will be at (-1, -1).
     */
    get offsetIndex(): Index;
    /**
     * Check if the node is a terminal node (i.e., it has no children).
     */
    get isTerminal(): boolean;
    /**
     * Check if the node is a root node (i.e., it has no parents).
     */
    get isRoot(): boolean;
}
declare class NodeMap {
    private map;
    constructor(entries?: readonly (readonly [Index, Node])[] | null);
    get([hypIndex, refIndex]: Index): Node | undefined;
    set([hypIndex, refIndex]: Index, node: Node): void;
    has([hypIndex, refIndex]: Index): boolean;
    entries(): Generator<readonly [Index, Node], void, unknown>;
    values(): Generator<Node, void, unknown>;
}
/**
 * Backtrace alignment graph
 */
declare class BacktraceGraph {
    backtrackMatrix: number[][];
    hypDim: number;
    refDim: number;
    hypMaxIndex: number;
    refMaxIndex: number;
    private _nodes;
    constructor(backtrackMatrix: number[][]);
    /**
     * Get the nodes in the graph.
     */
    get nodes(): NodeMap;
    /**
     * Get the node at the given index.
     *
     * @param hypIndex Hyp/row index.
     * @param refIndex Ref/column index.
     */
    getNode(hypIndex: number, refIndex: number): Node | undefined;
    /**
     * Get the set of all node indices in the graph.
     */
    getNodeSet(): Set<Index>;
    /**
     * Get a path through the graph.
     *
     * @param sample If true, sample a path randomly based on transition probabilities.
     *               Otherwise, return the first path deterministically.
     * @returns A list of nodes representing the path.
     */
    getPath({ sample }?: {
        sample: boolean;
    }): void;
    /**
     * Get nodes that can only be accounted for by a match.
     *
     * @returns A list of index tuples representing the unambiguous node matches.
     */
    getUnambiguousNodeMatches(): Index[];
    /**
     * Get word spans (i.e., <...>) that are unambiguously matched.
     *
     * That is, there is only one subpath that can account for the span using MATCH operations.
     * Other subpaths that include INSERT, DELETE, SUBSTITUTE operations are not considered.
     *
     * @returns A list of index tuples representing the end node of unambiguous span matches.
     */
    getUnambiguousTokenSpanMatches(ref: string): Set<Index>;
    /**
     * Create a parent node based on the index of the current node and the operation type.
     */
    private parentNodeFromOpType;
    /**
     * Iterate through the nodes in topological order.
     */
    private iterTopologicalOrder;
    /**
     * Add parents to the node at the given index based on the backtrace matrix.
     */
    private addParentsFromBacktrace;
}

export { BacktraceGraph, type Index, Node };