thi-ng/umbrella

View on GitHub
packages/intervals/src/index.ts

Summary

Maintainability
C
1 day
Test Coverage
import type { Fn, Fn2, ICompare, IContains, ICopy, IEquiv } from "@thi.ng/api";
import { DEFAULT_EPS } from "@thi.ng/api/api";
import { isString } from "@thi.ng/checks/is-string";
import { and, or } from "@thi.ng/dlogic";
import { illegalArgs } from "@thi.ng/errors/illegal-arguments";

export enum Classifier {
    DISJOINT_LEFT,
    DISJOINT_RIGHT,
    EQUIV,
    SUBSET,
    SUPERSET,
    OVERLAP_LEFT,
    OVERLAP_RIGHT,
}

export class Interval
    implements ICompare<Interval>, IContains<number>, ICopy<Interval>, IEquiv
{
    l: number;
    r: number;

    lopen: boolean;
    ropen: boolean;

    constructor(l: number, r: number, lopen = false, ropen = false) {
        (l > r || (l === r && lopen !== ropen)) &&
            illegalArgs(`invalid interval: ${$toString(l, r, lopen, ropen)}`);
        this.l = l;
        this.r = r;
        this.lopen = lopen;
        this.ropen = ropen;
    }

    get size(): number {
        return isEmpty(this) ? 0 : this.r - this.l;
    }

    copy() {
        return new Interval(this.l, this.r, this.lopen, this.ropen);
    }

    /**
     * Compares this interval with `i` and returns a comparator value
     * (-1, 0 or 1). Comparison order is: LHS, RHS, openness.
     *
     * @param i -
     */
    compare(i: Readonly<Interval>) {
        return compare(this, i);
    }

    equiv(i: any) {
        return (
            this === i ||
            (i instanceof Interval &&
                this.l === i.l &&
                this.r === i.r &&
                this.lopen === i.lopen &&
                this.ropen === i.ropen)
        );
    }

    /**
     * Returns true if `x` is lies within this interval.
     *
     * @param x -
     */
    contains(x: number) {
        return contains(this, x);
    }

    toString() {
        return $toString(this.l, this.r, this.lopen, this.ropen);
    }

    toJSON() {
        return this.toString();
    }
}

const BRACES = "()[]";
const RE_INF = /^([-+])?(inf(inity)?|\u221e)$/i;

export function interval(spec: string): Interval;
export function interval(
    l: number,
    r: number,
    lopen?: boolean,
    ropen?: boolean
): Interval;
export function interval(
    l: number | string,
    r?: number,
    lopen?: boolean,
    ropen?: boolean
) {
    return isString(l) ? parse(l) : new Interval(l, r!, lopen, ropen);
}

/**
 * Parses given ISO 80000-2 interval notation into a new `Interval`
 * instance. In addition to the comma separator, `..` can be used
 * alternatively. The following symbols (with optional sign) can be
 * used for infinity (case insensitive):
 *
 * - inf
 * - infinity
 * - ∞ (\u221e)
 *
 * An empty LHS defaults to `-Infinity`. The RHS defaults to
 * `+Infinity`.
 *
 * Openness / closedness symbols:
 *
 * - LHS: open: `]` / `(`, closed: `[`
 * - RHS: open: `[` / `)`, closed: `]`
 *
 * ```js
 * import { parse } from "@thi.ng/interval";
 *
 * // semi-open interval between -∞ and +1
 * parse("[,1)")
 *
 * // closed interval between -1 and +1
 * parse("[-1 .. 1]")
 * ```
 *
 * @param src -
 */
export const parse = (src: string) => {
    let l, r, c1, c2;
    const n = src.length - 1;
    const comma = src.indexOf(",") > 0;
    const dot = src.indexOf("..") > 0;
    if (n < (dot ? 3 : 2)) illegalArgs(src);
    c1 = src.charAt(0);
    c2 = src.charAt(n);
    if (BRACES.indexOf(c1) < 0 || BRACES.indexOf(c2) < 0 || !(comma || dot)) {
        illegalArgs(src);
    }
    [l, r] = src
        .substring(1, n)
        .split(dot ? ".." : ",")
        .map((x, i) => {
            x = x.trim();
            const inf = RE_INF.exec(x);
            const n =
                (x === "" && i === 0) || (inf && inf[1] === "-")
                    ? -Infinity
                    : (x === "" && i > 0) || (inf && inf[1] !== "-")
                    ? Infinity
                    : parseFloat(x);
            isNaN(n) && illegalArgs(`expected number: '${x}'`);
            return n;
        });
    r === undefined && (r = Infinity);
    return new Interval(
        l,
        r,
        c1 === "(" || c1 === "]",
        c2 === ")" || c2 === "["
    );
};

/**
 * Returns new infinite interval `[-∞..∞]`
 */
export const infinity = () => new Interval(-Infinity, Infinity);

/**
 * Returns new interval of `[min..∞]` or `(min..∞]` depending on if `open` is
 * true (default: false).
 *
 * @param min -
 * @param open -
 */
export const withMin = (min: number, open = false) =>
    new Interval(min, Infinity, open, false);

/**
 * Returns new interval of `[∞..max]` or `[∞..max)` depending on if `open` is
 * true (default: false).
 *
 * @param max -
 * @param open -
 */
export const withMax = (max: number, open = false) =>
    new Interval(-Infinity, max, false, open);

/**
 * Returns an open interval `(min..max)`
 *
 * @param min -
 * @param max -
 */
export const open = (min: number, max: number) =>
    new Interval(min, max, true, true);

/**
 * Returns a semi-open interval `(min..max]`, open on the LHS.
 *
 * @param min -
 * @param max -
 */
export const openClosed = (min: number, max: number) =>
    new Interval(min, max, true, false);

/**
 * Returns a semi-open interval `[min..max)`, open on the RHS.
 *
 * @param min -
 * @param max -
 */
export const closedOpen = (min: number, max: number) =>
    new Interval(min, max, false, true);

/**
 * Returns a closed interval `(min..max)`.
 *
 * @param min -
 * @param max -
 */
export const closed = (min: number, max: number) =>
    new Interval(min, max, false, false);

/**
 * Returns iterator of values in given interval at given `step` size. If the
 * interval is open on either side, the first and/or last sample will be
 * omitted.
 *
 * @param i -
 * @param step -
 */
export const values = (i: Readonly<Interval>, step: number) =>
    samples(i, Math.floor(i.size / step + 1));

/**
 * Returns an iterator yielding up to `n` uniformly spaced samples in given
 * interval. If the interval is open on either side, the first and/or last
 * sample will be omitted.
 *
 * @example
 * ```js
 * import { samples, closed } from "@thi.ng/intervals";
 *
 * [...samples(closed(10, 12), 5)]
 * // [10, 10.5, 11, 11.5, 12]
 *
 * [...samples(open(10, 12), 5)]
 * // [10.5, 11, 11.5]
 * ```
 *
 * @param i -
 * @param n -
 */
export function* samples(i: Readonly<Interval>, n: number) {
    const delta = n > 1 ? (i.r - i.l) / (n - 1) : 0;
    for (let x = 0; x < n; x++) {
        const y = i.l + delta * x;
        if (contains(i, y)) yield y;
    }
}

/**
 * Returns true, if interval has zero range, i.e. if LHS >= RHS.
 *
 * @param i -
 */
export const isEmpty = (i: Readonly<Interval>) => i.l >= i.r;

/**
 * Returns true iff interval `i` RHS < `x`, taking into account openness. If `x`
 * is an interval, then checks `i` RHS is less than LHS of `x` (again with
 * openness).
 *
 * @param i -
 * @param x -
 */
export const isBefore = (
    i: Readonly<Interval>,
    x: number | Readonly<Interval>
) =>
    x instanceof Interval
        ? i.ropen || x.lopen
            ? i.r <= x.l
            : i.r < x.l
        : i.ropen
        ? i.r <= <number>x
        : i.r < <number>x;

/**
 * Returns true iff interval `i` LHS > `x`, taking into account openness. If `x`
 * is an interval, then checks `i` LHS is greater than RHS of `x` (again with
 * openness).
 *
 * @param i -
 * @param x -
 */
export const isAfter = (
    i: Readonly<Interval>,
    x: number | Readonly<Interval>
) =>
    x instanceof Interval
        ? i.lopen || x.ropen
            ? i.l >= x.r
            : i.l > x.r
        : i.ropen
        ? i.l >= <number>x
        : i.l > <number>x;

/**
 * Compares interval `a` with `b` and returns a comparator value
 * (-1, 0 or 1). Comparison order is: LHS, RHS, openness.
 *
 * @param a -
 * @param b -
 */
export const compare = (a: Readonly<Interval>, b: Readonly<Interval>) => {
    if (a === b) return 0;
    let c: number;
    return a.l < b.l
        ? -1
        : a.l > b.l
        ? 1
        : a.r < b.r
        ? -1
        : a.r > b.r
        ? 1
        : (c = ~~a.lopen - ~~b.lopen) === 0
        ? ~~b.ropen - ~~a.ropen
        : c;
};

/**
 * Returns true if `x` is lies within interval `i`.
 *
 * @param i -
 * @param x -
 */
export const contains = (i: Readonly<Interval>, x: number) =>
    (i.lopen ? x > i.l : x >= i.l) && (i.ropen ? x < i.r : x <= i.r);

export const centroid = (i: Readonly<Interval>) => (i.l + i.r) / 2;

/**
 * Returns a new version of interval `i` such that `x` is included. If `x` lies
 * outside the current interval, the new one will be extended correspondingly.
 *
 * @param i -
 * @param x -
 */
export const include = (i: Readonly<Interval>, x: number) =>
    isAfter(i, x)
        ? new Interval(x, i.r, false, i.ropen)
        : isBefore(i, x)
        ? new Interval(i.l, x, i.lopen, false)
        : i.copy();

/**
 * Returns the distance between intervals, or zero if they touch or
 * overlap.
 *
 * @param a -
 * @param b -
 */
export const distance = (a: Readonly<Interval>, b: Readonly<Interval>) =>
    overlaps(a, b) ? 0 : a.l < b.l ? b.l - a.r : a.l - b.r;

/**
 * Applies given `fn` to both sides of interval `i` and returns a new
 * {@link Interval} of transformed end points.
 *
 * @param i -
 * @param fn -
 */
export const transform = (i: Readonly<Interval>, fn: Fn<number, number>) =>
    new Interval(fn(i.l), fn(i.r), i.lopen, i.ropen);

/**
 * Returns classifier for interval `a` WRT given interval `b`. E.g.
 * if the result is `Classifier.SUPERSET`, then interval `a` fully
 * contains `b`.
 *
 * ```text
 * EQUIV
 * [   a     ]
 * [   b     ]
 *
 * DISJOINT_LEFT
 * [ b ]
 *       [ a ]
 *
 * DISJOINT_RIGHT
 * [ a ]
 *       [ b ]
 *
 * SUPERSET
 * [ a         ]
 *    [ b   ]
 *
 * SUBSET
 * [ b         ]
 *    [ a ]
 *
 * OVERLAP_RIGHT
 * [ a     ]
 *       [ b ]
 *
 * OVERLAP_LEFT
 * [ b     ]
 *       [ a ]
 * ```
 *
 * @param a -
 * @param b -
 */
export const classify = (a: Readonly<Interval>, b: Readonly<Interval>) =>
    a.equiv(b)
        ? Classifier.EQUIV
        : isBefore(a, b)
        ? Classifier.DISJOINT_LEFT
        : isAfter(a, b)
        ? Classifier.DISJOINT_RIGHT
        : contains(a, b.l)
        ? contains(a, b.r)
            ? Classifier.SUPERSET
            : Classifier.OVERLAP_RIGHT
        : contains(a, b.r)
        ? Classifier.OVERLAP_LEFT
        : Classifier.SUBSET;

/**
 * Returns true if interval `a` intersects `b` in any way (incl.
 * subset / superset).
 *
 * @param a -
 * @param b -
 */
export const overlaps = (a: Readonly<Interval>, b: Readonly<Interval>) =>
    classify(a, b) >= Classifier.EQUIV;

/**
 * Returns the union of the two given intervals, taken their openness into
 * account.
 *
 * @param a -
 * @param b -
 */
export const union = (a: Readonly<Interval>, b: Readonly<Interval>) => {
    if (isEmpty(a)) return b;
    if (isEmpty(b)) return a;
    const [l, lo] = $min(a.l, b.l, a.lopen, b.lopen, and);
    const [r, ro] = $max(a.r, b.r, a.ropen, b.ropen, and);
    return new Interval(l, r, lo, ro);
};

/**
 * Returns the intersection of the two given intervals, taken their openness
 * into account. Returns undefined if `a` and `b` don't overlap.
 *
 * @param a -
 * @param b -
 */
export const intersection = (a: Readonly<Interval>, b: Readonly<Interval>) => {
    if (overlaps(a, b)) {
        const [l, lo] = $max(a.l, b.l, a.lopen, b.lopen, or);
        const [r, ro] = $min(a.r, b.r, a.ropen, b.ropen, or);
        return new Interval(l, r, lo, ro);
    }
};

export const prefix = (a: Readonly<Interval>, b: Readonly<Interval>) => {
    if (overlaps(a, b)) {
        const [l, lo] = $min(a.l, b.l, a.lopen, b.lopen, or);
        const [r, ro] = $min(a.r, b.l, a.ropen, b.lopen, or);
        return new Interval(l, r, lo, ro);
    }
};

export const suffix = (a: Readonly<Interval>, b: Readonly<Interval>) => {
    if (overlaps(a, b)) {
        const [l, lo] = $max(a.l, b.r, a.lopen, b.ropen, or);
        const [r, ro] = $max(a.r, b.r, a.ropen, b.ropen, or);
        return new Interval(l, r, lo, ro);
    }
};

/**
 * Returns the lesser value of either `x` or interval `i`'s RHS value. If
 * the interval is open on the RHS, and `x >= r`, then `r - eps` will be
 * returned.
 *
 * @param i -
 * @param x -
 * @param eps -
 */
export const min = (i: Readonly<Interval>, x: number, eps = DEFAULT_EPS) =>
    i.ropen ? (x >= i.r ? i.r - eps : x) : x > i.r ? i.r : x;

/**
 * Returns the greater value of either `x` or interval `i`'s LHS value. If
 * the interval is open on the LHS, and `x <= l`, then `l + eps` will be
 * returned.
 *
 * @param i -
 * @param x -
 * @param eps -
 */
export const max = (i: Readonly<Interval>, x: number, eps = DEFAULT_EPS) =>
    i.lopen ? (x <= i.l ? i.l + eps : x) : x < i.l ? i.l : x;

/**
 * Clamps `x` to interval `i`, using {@link min} and {@link max}.
 *
 * @param i -
 * @param x -
 * @param eps -
 */
export const clamp = (i: Readonly<Interval>, x: number, eps = DEFAULT_EPS) =>
    min(i, max(i, x, eps), eps);

/**
 * Folds `x` back into interval `i`, should it lie outside. `x` MUST originally
 * lie in the `(i.l-i.size .. i.r+i.size)` interval.
 *
 * @remarks
 * Current implementation is recursive and O(N) where N =
 * ceil(max(|x-i.l|, \x-i.r|) / i.size).
 *
 * See {@link min} or {@link max} for handling of optional `eps` arg.
 *
 * @param i
 * @param x
 * @param eps
 */
export const fold = (i: Readonly<Interval>, x: number, eps = DEFAULT_EPS) => {
    do {
        if ((i.lopen && x <= i.l) || (!i.lopen && x < i.l)) {
            x = x - i.l + i.r - (i.ropen ? eps : 0);
        } else if ((i.ropen && x >= i.r) || (!i.ropen && x > i.r)) {
            x = x - i.r + i.l + (i.lopen ? eps : 0);
        }
    } while (!contains(i, x));
    return x;
};

/** @internal */
const $min = (
    a: number,
    b: number,
    ao: boolean,
    bo: boolean,
    op: Fn2<boolean, boolean, boolean>
) => $minmax(a < b, a, b, ao, bo, op);

/** @internal */
const $max = (
    a: number,
    b: number,
    ao: boolean,
    bo: boolean,
    op: Fn2<boolean, boolean, boolean>
) => $minmax(a > b, a, b, ao, bo, op);

/** @internal */
const $minmax = (
    test: boolean,
    a: number,
    b: number,
    ao: boolean,
    bo: boolean,
    op: Fn2<boolean, boolean, boolean>
): [number, boolean] => (test ? [a, ao] : a === b ? [a, op(ao, bo)] : [b, bo]);

/** @internal */
const $toString = (l: number, r: number, lopen: boolean, ropen: boolean) =>
    `${lopen ? "(" : "["}${l} .. ${r}${ropen ? ")" : "]"}`;