A Set with checkpoints and restore functionality

restore-set.ts

/**
 * Opaque type used by `RestoreSet<T>` to handle restoration.
 */
class Checkpoint {
    constructor(public _value: number) { }
}

/**
 * A set-like object that stores arbitrary `T` elements. At any point in time,
 * the user can create a `Checkpoint` which then can be used to restore the state of the structure.
 * Checkpoints "into the future" are invalid, since the structure is space-efficient
 * by removing elements.
 * 
 * This class **not** thread-safe.
 * 
 * @example
 * let rs = new RestoreSet<number>();
 * rs.add(1);
 * let c1 = rs.createCheckpoint();
 * rs.add(2);
 * let c2 = rs.createCheckpoint();
 * assert(rs.has(1)); assert(rs.has(2));
 * rs.restoreCheckpoint(c1);
 * assert(rs.has(1)); assert(!rs.has(2));
 */
class RestoreSet<T> {
    public _backingMap: Map<T, number> = new Map();
    public _currentCheckpoint: number = 0;

    /**
     * @returns the number of elements in the Set.
     */
    get size(): number {
        return this._backingMap.size;
    }

    /**
     * Add an item `T` into the Set.
     * @param item The item to be added.
     */
    add(item: T): void {
        if (this._backingMap.has(item)) { return; }
        this._backingMap.set(item, this._currentCheckpoint);
    }

    /**
     * Checks if an item `T` is contained in the Set or not
     * 
     * @param item The item to be checked.
     * @returns boolean indicating whether the item is contained in the Set or not.
     */
    has(item: T): boolean {
        return this._backingMap.has(item);
    }

    /**
     * Create a `Checkpoint` to be used with `restoreCheckpoint`.
     * @returns 
     */
    createCheckpoint(): Checkpoint {
        this._currentCheckpoint += 1;
        return new Checkpoint(this._currentCheckpoint)
    }

    /**
     * Restores the Set to a previous `Checkpoint`.
     * All elements inserted before the creation of the checkpoint will still be on the Set.
     * 
     * Checkpoints are only valid if they are constructed before the current checkpoint.
     * @param checkpoint 
     */
    restoreCheckpoint(checkpoint: Checkpoint): void {
        // This implementation involves copying, which is not necessary.
        // Ideally, we would just remove the elements in-place from `this._backingMap`.
        let cp = checkpoint._value;
        if (cp > this._currentCheckpoint || cp < 0) { throw new Error("Invalid checkpoint") }
        let newBackingMap = new Map<T, number>();
        for (const [key, kc] of this._backingMap.entries()) {
            if (kc < cp) {
                newBackingMap.set(key, kc);
            }
        }
        this._backingMap = newBackingMap;
        this._currentCheckpoint = cp;
    }
}

function assert(condition: boolean, message: string = "Expected truthy, got falsy") {
    if (!condition) { throw new Error(message) }
}

function assertThrows(expr: () => any, message: string = "Expected throwable, got none") {
    let didThrow = false;
    try {
        expr();
    } catch (error) {
        didThrow = true;
    }
    if (!didThrow) {
        throw new Error(message);
    }
}

function test_initialSetIsEmpty() {
    let rs = new RestoreSet<number>();
    assert(rs.size == 0)
}

function test_addItem() {
    let rs = new RestoreSet<number>();
    rs.add(1); rs.add(2);
    assert(rs.has(1));
    assert(rs.has(2));
}

function test_restoreCheckpoint() {
    let rs = new RestoreSet<number>();
    rs.add(1);
    let cp = rs.createCheckpoint();
    rs.add(2);

    assert(rs.size == 2);
    assert(rs.has(1));
    assert(rs.has(2));

    rs.restoreCheckpoint(cp);

    assert(rs.size == 1);
    assert(rs.has(1));
    assert(!rs.has(2));
}

function test_invalidRestore() {
    let rs = new RestoreSet<number>();
    rs.add(1);
    let c1 = rs.createCheckpoint();
    rs.add(2);
    let c2 = rs.createCheckpoint();
    rs.restoreCheckpoint(c1);

    assertThrows(() => rs.restoreCheckpoint(c2));
    assert(rs.has(1));
    assert(rs.size == 1);
}

function test_repeatedRestore() {
    let rs = new RestoreSet<number>();
    rs.add(1);
    let cp = rs.createCheckpoint();
    rs.restoreCheckpoint(cp);
    rs.restoreCheckpoint(cp);

    assert(rs.size == 1);
    assert(rs.has(1));
}

function test_restoreToEmpty() {
    let rs = new RestoreSet<number>();
    let cp = rs.createCheckpoint();
    rs.add(1); rs.add(2);
    rs.restoreCheckpoint(cp);

    assert(rs.size == 0);
}

test_initialSetIsEmpty();
test_addItem();
test_restoreCheckpoint();
test_repeatedRestore();
test_invalidRestore();
test_restoreToEmpty();