Inserting, deleting and updating elements on an array of infinite length

README.md

index.js

const assert = require("node:assert");

class InfiniteArray {
  refs = new Map();

  get(index) {
    const [ref, offset] = this.findRefPath(index);
    return this.refs.has(ref)
      ? this.refs.get(ref).at(offset)
      : this.getOriginElement(ref);
  }

  set(index, value) {
    const [ref, offset] = this.findRefPath(index);
    this.getFragment(ref).splice(offset, 1, value);
  }

  insert(index, value) {
    const [ref, offset] = this.findRefPath(index);
    this.getFragment(ref).splice(offset, 0, value);
  }

  remove(index) {
    const [ref, offset] = this.findRefPath(index);
    this.getFragment(ref).splice(offset, 1);
  }

  getFragment(ref) {
    if (!this.refs.has(ref)) {
      this.refs.set(ref, [this.getOriginElement(ref)]);
    }
    return this.refs.get(ref);
  }

  findRefPath(index) {
    const [oi, [start, _end], isFragment] = this.buildSearchChain().find(
      ([, [start, end]]) => index >= start && index <= end,
    );
    const offset = index - start;
    return isFragment ? [oi, offset] : [oi + offset, 0];
  }

  /**
   * @description
   * chain node:
   * Array {
   *   originElementIndex,
   *   Array {
   *     actualElementStart,
   *     actualElementEnd
   *   },
   *   isFragment
   * }
   */
  buildSearchChain() {
    const chain = Array.from(this.refs.entries())
      .sort(([a], [b]) => a - b)
      .map(([oi, refedValues]) => [oi, refedValues.length])
      .reduce(
        (res, [oi, len]) => {
          const [poi] = res.at(res.length - 1);
          res.push([poi + 1, oi - poi - 1]);
          res.push([oi, len, true]);
          return res;
        },
        [[-1, -1]],
      );

    const last = chain.at(chain.length - 1);
    chain.push([last ? last.at(0) + 1 : 0, Infinity]);

    return chain
      .filter(([, len]) => len > 0)
      .reduce((res, [oi, len, isFragment = false]) => {
        const prev = res.at(res.length - 1);
        if (!prev) {
          res.push([oi, [0, len - 1], isFragment]);
        } else {
          const [_, [_ps, pe]] = prev;
          res.push([oi, [pe + 1, pe + len], isFragment]);
        }
        return res;
      }, []);
  }

  getOriginElement(index) {
    // free to implement this part
    return index + 1;
  }
}

function headx(len) {
  return Array.from({ length: len }, (_, i) => a.get(i));
}

const a = new InfiniteArray();

assert.deepStrictEqual(headx(10), [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);

a.insert(2, 99);
assert.deepStrictEqual(headx(10), [1, 2, 99, 3, 4, 5, 6, 7, 8, 9]);

a.insert(2, 98);
assert.deepStrictEqual(headx(10), [1, 2, 98, 99, 3, 4, 5, 6, 7, 8]);

a.insert(3, 97);
assert.deepStrictEqual(headx(10), [1, 2, 98, 97, 99, 3, 4, 5, 6, 7]);

a.insert(1, 96);
assert.deepStrictEqual(headx(10), [1, 96, 2, 98, 97, 99, 3, 4, 5, 6]);

a.set(2, 20);
assert.deepStrictEqual(headx(10), [1, 96, 20, 98, 97, 99, 3, 4, 5, 6]);

a.set(6, 30);
assert.deepStrictEqual(headx(10), [1, 96, 20, 98, 97, 99, 30, 4, 5, 6]);

a.set(6, 300);
assert.deepStrictEqual(headx(10), [1, 96, 20, 98, 97, 99, 300, 4, 5, 6]);

a.remove(1);
assert.deepStrictEqual(headx(10), [1, 20, 98, 97, 99, 300, 4, 5, 6, 7]);

a.remove(2);
assert.deepStrictEqual(headx(10), [1, 20, 97, 99, 300, 4, 5, 6, 7, 8]);

a.remove(2);
assert.deepStrictEqual(headx(10), [1, 20, 99, 300, 4, 5, 6, 7, 8, 9]);

a.remove(2);
assert.deepStrictEqual(headx(10), [1, 20, 300, 4, 5, 6, 7, 8, 9, 10]);

a.set(1, 2);
assert.deepStrictEqual(headx(10), [1, 2, 300, 4, 5, 6, 7, 8, 9, 10]);

a.set(2, 3);
assert.deepStrictEqual(headx(10), [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);

console.log("all passed.");