BigArray.ts

const enum CONST {
  MAX_LENGTH = 128,
}

class BigArrayRef<T> {
  constructor (public readonly arr: BigArray<T>, public readonly pos: number) {}
}

export class BigArray<T> {
  public length = 0;
  public parent: undefined | BigArray<T> = undefined;
  public data: Array<T | BigArray<T>>;

  constructor(data: Array<T | BigArray<T>>) {
    this.data = data;
  }

  public ins(after: number, ...items: T[]): void {
    const ref = this.ref(after);
    ref.arr.insRef(ref.pos, ...items);
  }

  public insRef(offset: number, ...items: T[]): void {
    const insertLength = items.length;
    const data = this.data;
    const dataLength = data.length;
    if (dataLength < CONST.MAX_LENGTH) {
      if (data.length === offset) data.push(...items);
      else this.data.splice(offset, 0, ...items);
    } else {
      const item = data[offset];
      const arr = new BigArray<T>([item, ...items]);
      data[offset] = arr;
      arr.parent = this;
    }
    let curr: undefined | BigArray<T> = this;
    while (curr) {
      curr.length += insertLength;
      curr = curr.parent;
    }
  }

  public get(index: number): T {
    const ref = this.ref(index);
    return ref.arr.data[ref.pos] as T;
  }

  public del(index: number): void {
    const ref = this.ref(index);
    const arr = ref.arr;
    const data = arr.data;
    data.splice(index, 1);
    let curr: undefined | BigArray<T> = arr;
    while (curr) {
      curr.length--;
      curr = curr.parent;
    }
  }

  public ref(offset: number): BigArrayRef<T> {
    const data = this.data;
    let length = data.length;
    for (let i = 0; i < length; i++) {
      const item = data[i];
      if (item instanceof BigArray) {
        const itemLength = item.length;
        if (itemLength >= offset) return new BigArrayRef(item, offset);
        else offset -= itemLength;
      } else if (!offset) return new BigArrayRef(this, i);
      else offset--;
    }
    throw new Error('OUT_OF_BOUNDS');
  }

  public * items(): IterableIterator<T> {
    const data = this.data;
    let length = data.length;
    for (let i = 0; i < length; i++) {
      const item = data[i];
      if (item instanceof BigArray) yield * item.items();
      else yield item;
    }
  }
}

WIP. Performant big array implementation.