numberSet.ts

/*
 * This is pretty complicated and otherwise uncommented so I feel as though I owe a bit of an explanation here.
 * We want an intrinsically sorted set that can contain ANY valid JS number. So we first convert the number into bytes,
 * by sharing an ArrayBuffer between a Uint8Array and Float64Array. Then we use the first 7 bytes, going from MSB to
 * LSB, to traverse through a tree until we find the "ByteSet" that defines the values within the set for the
 * last 8 bits. An optimization is also implemented where if it is known that all bytes after the one represented by
 * the current node being traversed are 0, the presence of that exact number within the set is stored in that node
 * and NO children are made. This takes advantage of the fact that integers in IEEE754 will typically end in long runs
 * of 0.
 */

class ByteSet {

    private readonly data;
    constructor() {
        this.data = new Uint8Array(32);
    }

    has(index: number): boolean {
        const flag = 1 << (index & 7);
        return (this.data[index >> 3] & flag) !== 0;
    }

    add(index: number): void {
        this.set(index, true);
    }

    remove(index: number): void {
        this.set(index, false);
    }

    private set(index: number, value: boolean): void {
        const flag = 1 << (index & 7);
        index >>= 3;
        if (value) {
            this.data[index] |= flag;
        } else {
            this.data[index] &= (~flag);
        }
    }

    *iterator(buf8: Uint8Array, buf64: Float64Array, offset: number): Generator<number> {
        let head: number = -1;
        let base: number;
        let flag: number;
        while ((++head) < 32) {
            flag = this.data[head];
            if (flag === 0) continue;
            base = head << 3;
            for (let i=0; i < 8; i++) {
                if (flag & (1 << i)) {
                    buf8[offset] = (base | i);
                    yield buf64[0];
                }
            }
        }
    }

}

const IS_BIG_ENDIAN: boolean = (() => {
    const ab = new ArrayBuffer(2);
    const u8 = new Uint8Array(ab);
    const u16 = new Uint16Array(ab);
    u8[0] = 0xAA;
    u8[1] = 0xBB;
    return u16[0] === 0xAABB;
})();

const TRAVERSAL_DIRECTION: 1 | -1 = IS_BIG_ENDIAN ? 1 : -1;
const TRAVERSAL_START: 0 | 7 = IS_BIG_ENDIAN ? 0 : 7;
const TRAVERSAL_END: 0 | 7 = IS_BIG_ENDIAN ? 7 : 0;

class NumberSetNode {

    private value: boolean;
    private readonly children: { [index: number]: NumberSetNode | ByteSet };
    constructor() {
        this.value = false;
        this.children = {};
    }

    protected has0(bytes: Uint8Array, index: number, atWhichAllZero: number): boolean {
        if (index === atWhichAllZero) return this.value;
        const determinant: number = bytes[index];
        const child = this.children[determinant];
        if (typeof child === "undefined") return false;
        index += TRAVERSAL_DIRECTION;
        if (index === TRAVERSAL_END) {
            return (child as ByteSet).has(bytes[index]);
        } else {
            return (child as NumberSetNode).has0(bytes, index, atWhichAllZero);
        }
    }

    protected add0(bytes: Uint8Array, index: number, atWhichAllZero: number): void {
        if (index === atWhichAllZero) {
            this.value = true;
            return;
        }
        const determinant: number = bytes[index];
        let child: NumberSetNode | ByteSet = this.children[determinant];

        index += TRAVERSAL_DIRECTION;
        const isTail: boolean = (index === TRAVERSAL_END);
        if (typeof child === "undefined") {
            child = isTail ? new ByteSet() : new NumberSetNode();
            this.children[determinant] = child;
        }

        if (isTail) {
            (child as ByteSet).add(bytes[index]);
        } else {
            (child as NumberSetNode).add0(bytes, index, atWhichAllZero);
        }
    }

    protected remove0(bytes: Uint8Array, index: number, atWhichAllZero: number): void {
        if (index === atWhichAllZero) {
            this.value = false;
            return;
        }
        const determinant: number = bytes[index];
        const child: NumberSetNode | ByteSet = this.children[determinant];
        if (typeof child === "undefined") return;

        index += TRAVERSAL_DIRECTION;
        if (index === TRAVERSAL_END) {
            (child as ByteSet).remove(bytes[index]);
        } else {
            (child as NumberSetNode).remove0(bytes, index, atWhichAllZero);
        }
    }

    protected *iterator(buf8: Uint8Array, buf64: Float64Array, offset: number): Generator<number> {
        if (this.value) {
            IS_BIG_ENDIAN ? buf8.fill(0, offset, 8) : buf8.fill(0, 0, offset + 1);
            yield buf64[0];
        }

        const next: number = offset + TRAVERSAL_DIRECTION;
        const isTail: boolean = next === TRAVERSAL_END;
        let child: NumberSetNode | ByteSet;
        for (let k of Object.keys(this.children)) {
            buf8[offset] = parseInt(k);
            child = this.children[k as unknown as number];
            if (isTail) {
                for (let n of (child as ByteSet).iterator(buf8, buf64, next)) yield n;
            } else {
                for (let n of (child as NumberSetNode).iterator(buf8, buf64, next)) yield n;
            }
        }
    }

}

export class NumberSet extends NumberSetNode implements Iterable<number> {

    private readonly buf8: Uint8Array;
    private readonly buf64: Float64Array;
    private mayHaveNegativeValues: boolean = false;

    constructor() {
        super();
        const buf = new ArrayBuffer(8);
        this.buf8 = new Uint8Array(buf);
        this.buf64 = new Float64Array(buf);
    }

    private parameterize(n: number): [ Uint8Array, number, number ] {
        this.buf64[0] = n;
        let atWhichAllZero: number = TRAVERSAL_END + TRAVERSAL_DIRECTION;
        let i: number = atWhichAllZero;
        while (i !== TRAVERSAL_START) {
            i -= TRAVERSAL_DIRECTION;
            if (this.buf8[i] !== 0) break;
            atWhichAllZero = i;
        }
        return [ this.buf8, TRAVERSAL_START, atWhichAllZero ];
    }

    has(n: number): boolean {
        return this.has0(...this.parameterize(n));
    }

    add(n: number): void {
        this.mayHaveNegativeValues |= (n < 0);
        return this.add0(...this.parameterize(n));
    }

    remove(n: number): void {
        return this.remove0(...this.parameterize(n));
    }

    [Symbol.iterator](): Iterator<number> {
        return this.iterator(this.buf8, this.buf64, TRAVERSAL_START);
    }

}