AK-21/Graphite-Industrial-Intelligence

1/**2 * Some of the internal operations of micromark do lots of editing3 * operations on very large arrays. This runs into problems with two4 * properties of most circa-2020 JavaScript interpreters:5 *6 *  - Array-length modifications at the high end of an array (push/pop) are7 *    expected to be common and are implemented in (amortized) time8 *    proportional to the number of elements added or removed, whereas9 *    other operations (shift/unshift and splice) are much less efficient.10 *  - Function arguments are passed on the stack, so adding tens of thousands11 *    of elements to an array with `arr.push(...newElements)` will frequently12 *    cause stack overflows. (see <https://stackoverflow.com/questions/22123769/rangeerror-maximum-call-stack-size-exceeded-why>)13 *14 * SpliceBuffers are an implementation of gap buffers, which are a15 * generalization of the "queue made of two stacks" idea. The splice buffer16 * maintains a cursor, and moving the cursor has cost proportional to the17 * distance the cursor moves, but inserting, deleting, or splicing in18 * new information at the cursor is as efficient as the push/pop operation.19 * This allows for an efficient sequence of splices (or pushes, pops, shifts,20 * or unshifts) as long such edits happen at the same part of the array or21 * generally sweep through the array from the beginning to the end.22 *23 * The interface for splice buffers also supports large numbers of inputs by24 * passing a single array argument rather passing multiple arguments on the25 * function call stack.26 *27 * @template T28 *   Item type.29 */30export class SpliceBuffer<T> {31    /**32     * @param {ReadonlyArray<T> | null | undefined} [initial]33     *   Initial items (optional).34     * @returns35     *   Splice buffer.36     */37    constructor(initial?: ReadonlyArray<T> | null | undefined);38    /** @type {Array<T>} */39    left: Array<T>;40    /** @type {Array<T>} */41    right: Array<T>;42    /**43     * Array access;44     * does not move the cursor.45     *46     * @param {number} index47     *   Index.48     * @return {T}49     *   Item.50     */51    get(index: number): T;52    /**53     * The length of the splice buffer, one greater than the largest index in the54     * array.55     */56    get length(): number;57    /**58     * Remove and return `list[0]`;59     * moves the cursor to `0`.60     *61     * @returns {T | undefined}62     *   Item, optional.63     */64    shift(): T | undefined;65    /**66     * Slice the buffer to get an array;67     * does not move the cursor.68     *69     * @param {number} start70     *   Start.71     * @param {number | null | undefined} [end]72     *   End (optional).73     * @returns {Array<T>}74     *   Array of items.75     */76    slice(start: number, end?: number | null | undefined): Array<T>;77    /**78     * Mimics the behavior of Array.prototype.splice() except for the change of79     * interface necessary to avoid segfaults when patching in very large arrays.80     *81     * This operation moves cursor is moved to `start` and results in the cursor82     * placed after any inserted items.83     *84     * @param {number} start85     *   Start;86     *   zero-based index at which to start changing the array;87     *   negative numbers count backwards from the end of the array and values88     *   that are out-of bounds are clamped to the appropriate end of the array.89     * @param {number | null | undefined} [deleteCount=0]90     *   Delete count (default: `0`);91     *   maximum number of elements to delete, starting from start.92     * @param {Array<T> | null | undefined} [items=[]]93     *   Items to include in place of the deleted items (default: `[]`).94     * @return {Array<T>}95     *   Any removed items.96     */97    splice(start: number, deleteCount?: number | null | undefined, items?: Array<T> | null | undefined): Array<T>;98    /**99     * Remove and return the highest-numbered item in the array, so100     * `list[list.length - 1]`;101     * Moves the cursor to `length`.102     *103     * @returns {T | undefined}104     *   Item, optional.105     */106    pop(): T | undefined;107    /**108     * Inserts a single item to the high-numbered side of the array;109     * moves the cursor to `length`.110     *111     * @param {T} item112     *   Item.113     * @returns {undefined}114     *   Nothing.115     */116    push(item: T): undefined;117    /**118     * Inserts many items to the high-numbered side of the array.119     * Moves the cursor to `length`.120     *121     * @param {Array<T>} items122     *   Items.123     * @returns {undefined}124     *   Nothing.125     */126    pushMany(items: Array<T>): undefined;127    /**128     * Inserts a single item to the low-numbered side of the array;129     * Moves the cursor to `0`.130     *131     * @param {T} item132     *   Item.133     * @returns {undefined}134     *   Nothing.135     */136    unshift(item: T): undefined;137    /**138     * Inserts many items to the low-numbered side of the array;139     * moves the cursor to `0`.140     *141     * @param {Array<T>} items142     *   Items.143     * @returns {undefined}144     *   Nothing.145     */146    unshiftMany(items: Array<T>): undefined;147    /**148     * Move the cursor to a specific position in the array. Requires149     * time proportional to the distance moved.150     *151     * If `n < 0`, the cursor will end up at the beginning.152     * If `n > length`, the cursor will end up at the end.153     *154     * @param {number} n155     *   Position.156     * @return {undefined}157     *   Nothing.158     */159    setCursor(n: number): undefined;160}161//# sourceMappingURL=splice-buffer.d.ts.map