function insertLeaf()

in packages/core/micro/src/adjust-tree/node.ts [314:397]

• 62 lines of code
• 7 McCabe index (conditional complexity)

function insertLeaf<T>(ctx: TreeContext<T>, node: LeafNode<T>, position: number, length: number, payload: T): Insertion<T> {
    let pos = position;
    let insertionPoint = 0;
    const { size, lengths, segments } = node;
    while (insertionPoint < size) {
        const len = lengths[insertionPoint];
        if (pos < len) {
            break;
        }
        pos -= len;
        insertionPoint += 1;
    }
    let newSize: number;
    const offset = pos > 0;
    if (insertionPoint === size) {
        assert("Appending should have no offset", !offset);
        /**
         * The segment is being appended to the end and we should have
         * no offset.
         */
        lengths[insertionPoint] = length
        segments[insertionPoint] = payload
        newSize = size + 1;
    }
    else {
        /** 
         * The segment is being inserted into the existing
         * segments. The are two cases.
         *
         * 1. We are inserting at a point that cuts a segment. We
         * split the existing segment and place it either side of our
         * new segment.
         *
         * 2. We are inserting directly between two segments. We shift
         * everything across.
         *
         */
        if (offset) {
            const oldLen = lengths[insertionPoint];
            assert('oldLen - pos > 0', oldLen - pos > 0);
            /**
             * We are splitting an existing segment so we need to
             * create two extra spaces: one for the newly inserted
             * segment, and one for the remaining part of the split
             * segment.
             */
            shiftR(lengths, insertionPoint + 1, size - 1, 2)
            shiftR(segments, insertionPoint + 1, size - 1, 2)
            const { retained, removed } = ctx.extractSegmentRange(segments[insertionPoint], pos, oldLen - pos);
            lengths[insertionPoint] = pos;
            lengths[insertionPoint + 1] = length;
            lengths[insertionPoint + 2] = oldLen - pos;
            segments[insertionPoint] = retained;
            segments[insertionPoint + 1] = payload;
            segments[insertionPoint + 2] = removed;
            newSize = size + 2;
        }
        else {
            shiftR(lengths, insertionPoint, size - 1, 1)
            shiftR(segments, insertionPoint, size - 1, 1)
            lengths[insertionPoint] = length;
            segments[insertionPoint] = payload
            newSize = size + 1;
        }
    }
    if (newSize <= ctx.maxKeys) {
        node.size = newSize;
        return undefined;
    }
    const lhSize = ctx.order + 1;
    const leaf = createLeaf(
        /* size */ 0,
        initArray(ctx.leafLengthSize, EMPTY),
        initArray(ctx.leafSegmentSize, ctx.emptySegment),
        /* prev */ node,
        /* next */ node.next
    );
    const newPartition = split(node, newSize, leaf, newSize - lhSize, ctx.emptySegment);
    if (node.next) {
        node.next.prev = leaf;
    }
    node.next = leaf;
    return [newPartition, leaf];
}