Source: model/Matching.js

/**
 * @file Class Matching
 * @version March 26, 2017
 *
 * @author Olivier Pirson --- http://www.opimedia.be/
 * @license GPLv3 --- Copyright (C) 2017 Olivier Pirson
 */
/**
 * A geometric matching:
 * - a "set" of points
 * - a "set" of segments on these points
 *
 * The set of points may be shared with other linked matching.
 */
class Matching {
    /**
     * Construct a Matching.
     *
     * If linkedMatching !== null
     * then shared points with it.
     *
     * @param {null|Matching} linkedMatching
     */
    constructor(linkedMatching=null) {
        assert((linkedMatching === null) || (linkedMatching instanceof Matching), linkedMatching);
        if (linkedMatching === null) {
            this._points = [];  // ordonned sequence of Point
            this._linkedMatchings = [this];  // ordonned sequence of Matching
        }
        else {
            this._points = linkedMatching.points;
            linkedMatching.linkedMatchings.push(this);
            this._linkedMatchings = linkedMatching.linkedMatchings;
        }
        this._segments = [];  // ordonned sequence of Segment (for each segment, the two points are ordonned)
        this._numberPerfectMatchingsIfCalculated = null;  // null or (if already calculated) the exact number of perfect matchings for theses points
    }
    /**
     * Returns the ordonned sequence of linked matchings.
     *
     * @returns {Array} Array of Matching
     */
    get linkedMatchings() { return this._linkedMatchings; }
    /**
     * If is already calculated or if it easy to calculate
     * then returns the exact number of perfect matchings for theses points,
     * else returns null.
     *
     * @returns {null|Number}
     */
    get numberPerfectMatchingsIfCalculated() {
        if (this.points.length % 2 !== 0) {
            this._numberPerfectMatchingsIfCalculated = 0;
        }
        else if (this.points.length <= 2) {
            this._numberPerfectMatchingsIfCalculated = this.points.length/2;
        }
        return this._numberPerfectMatchingsIfCalculated;
    }
    /**
     * Returns the ordonned sequence of points.
     *
     * @returns {Array} Array of Point
     */
    get points() { return this._points; }
    /**
     * Returns the sequence of segments.
     *
     * @returns {Array} Array of Segment (for each segment, the two points are ordonned)
     */
    get segments() { return this._segments; }
    /**
     * Returns all possible perfect matchings
     * with the points of this matching.
     *
     * If disjointMatching
     * then keep only perfect matching disjoint with this matching.
     *
     * If compatibleMatching
     * then keep only perfect matching disjoint with this matching.
     *
     * FIXME! Naive algorithm. Implement iterative building?
     *
     * @param {Boolean} disjointMatching
     * @param {Boolean} compatibleMatching
     *
     * @returns {Array} Array of Matching
     */
    allPerfectMatchings(disjointMatching, compatibleMatching) {
        assert(typeof disjointMatching === "boolean", disjointMatching);
        assert(typeof compatibleMatching === "boolean", compatibleMatching);
        const matchings = [];
        if (this.points.length % 2 !== 0) {
            return matchings;
        }
        const thisMatching = this;
        const points = this.points;
        const nbPoints = points.length;
        const assigns = [];
        // Value in assigns:
        //   false: not assigned
        //   number: index of the first point of a segment
        //   true: index of the second point of a segment
        // Fill with first assignation
        for (let i = 0; i < nbPoints; ++i) {
            assigns.push(i % 2 === 0
                         ? i + 1
                         : true);
        }
        var available = new Set();  // available indices
        const backtrackPos = function () {  // return previous position with assignation
            for (let i = nbPoints - 1; i >= 0; --i) {
                if (typeof assigns[i] === "number") {
                    return i;
                }
            }
            return null;
        };
        const nextPointIndex = function (pos, first=0) {  // return next point index
            for (let i = Math.max(first, pos + 1); i < nbPoints; ++i) {
                if (available.has(i)) {
                    return i;
                }
            }
            return null;
        };
        const assign = function (pos, pointIndex) {  // assign two related indices
            available.delete(pos);
            available.delete(pointIndex);
            assigns[pos] = pointIndex;
            assigns[pointIndex] = true;
        };
        const unassign = function (pos) {  // unassign two related indices
            available.add(pos);
            available.add(assigns[pos]);
            assigns[assigns[pos]] = false;
            assigns[pos] = false;
        };
        const toMatching = function () {  // return a new perfect matching corresponding to assignations, or null
            const matching = new Matching();
            matching._points = thisMatching._points;
            for (let i = 0; i < nbPoints; ++i) {
                if (typeof assigns[i] === "number") {
                    const segment = new Segment(points[i], points[assigns[i]]);
                    if (matching.segmentIsIntersect(segment)) {
                        return null;
                    }
                    matching.segmentAdd(segment);
                }
            }
            return matching;
        };
        while (true) {
            // One possible matching
            const matching = toMatching();
            if (matching !== null) {
                matchings.push(matching);
            }
            // Search first position to modify
            var pos;
            var next;
            do {
                pos = backtrackPos();
                if (pos === null) {
                    this._numberPerfectMatchingsIfCalculated = matchings.length;
                    if (disjointMatching || compatibleMatching) {  // keep only "good" matchings
                        for (let i = 0; i < matchings.length; ++i) {
                            if ((disjointMatching && !this.isDisjoint(matchings[i]))
                                || (compatibleMatching && !this.isCompatible(matchings[i]))) {
                                matchings.splice(i, 1);
                                --i;
                            }
                        }
                    }
                    return matchings;
                }
                next = nextPointIndex(pos, assigns[pos] + 1);
                unassign(pos);
            } while (next === null);
            // Set values from pos
            assign(pos, next);
            for (let i = pos + 1; i < nbPoints; ++i) {
                if ((next !== null) && (assigns[i] === false)) {
                    next = nextPointIndex(i);
                    assign(i, next);
                }
            }
        }
    }
    /**
     * Returns an upper bound of number
     * of all possible perfect matchings with the points of this matching.
     *
     * @returns {Number}
     */
    allPerfectMatchingsUppedBound() {
        if ((this.points.length === 0) || (this.points.length % 2 !== 0)) {
            return 0;
        }
        var number = 1;
        for (let i = 3; i < this._points.length; i += 2) {
            number *= i;
        }
        return number;
    }
    /**
     * Returns the canonical perfect matching
     * corresponding to these points.
     *
     * @returns {Matching}
     */
    canonical() {
        assert(this._points.length % 2 === 0, this._points.length);
        const matching = new Matching();
        matching._points = this._points;
        for (let i = 0; i < this._points.length; i += 2) {
            const segment = new Segment(matching._points[i], matching._points[i + 1]);
            matching.segmentAdd(segment);
        }
        return matching;
    }
    /**
     * Empty sets of points and segments,
     * and intermediary linked matchings.
     */
    clear() {
        this.clearIntermediaryLinkedMatchings();
        this._points.splice(0, this._points.length);
        this._segments.splice(0, this._segments.length);
        this.clearIfModifyPoints();
    }
    /**
     * Reset some data when add or remove point.
     */
    clearIfModifyPoints() {
        this._numberPerfectMatchingsIfCalculated = null;
        for (let matching of this._linkedMatchings) {
            matching._numberPerfectMatchingsIfCalculated = null;
        }
    }
    /**
     * Remove all intermediary linked matchings.
     */
    clearIntermediaryLinkedMatchings() {
        assert(this._linkedMatchings.length >= 2, this._linkedMatchings);
        for (let i = 1; i < this._linkedMatchings.length - 1; ++i) {
            this._linkedMatchings[i]._linkedMatchings = null;
        }
        this._linkedMatchings.splice(1, this._linkedMatchings.length - 2);
        this._linkedMatchings[1]._linkedMatchings = this._linkedMatchings;
    }
    /**
     * Returns a set of segments in common between this matching and other.
     *
     * @param {Matching} other
     *
     * @returns {Set} Set of Segment
     */
    commonSegments(other) {
        assert(other instanceof Matching, other);
        const segments = new Set();
        for (let segment of this._segments) {
            for (let otherSegment of other._segments) {
                if (segment.isEquals(otherSegment)) {
                    segments.add(segment);
                }
            }
        }
        return segments;
    }
    /**
     * Returns a set of segments in common between this matching
     * and previous or next one.
     *
     * @returns {Set} Set of Segment
     */
    commonSegmentsWithConsecutiveMatchings() {
        const i = this.linkedMatchingsIndex();
        const left = (i > 0
                      ? this.commonSegments(this._linkedMatchings[i - 1])
                      : new Set());
        const right = (i < this._linkedMatchings.length - 1
                       ? this.commonSegments(this._linkedMatchings[i + 1])
                       : new Set());
        return setUnion(left, right);
    }
    /**
     * Returns true iff the matching is the canonical perfect matching.
     *
     * @returns {boolean}
     */
    isCanonical() {
        if ((this._points.length % 2 !== 0) || (2*this._segments.length < this._points.length)) {
            // Odd number of points or not enough segments, impossible to be perfect
            return false;
        }
        const canonical = this.canonical();
        return this.isEquals(canonical);
    }
    /**
     * Returns true iff matching and other are compatible
     * (union have no intersection segments, without their endpoints).
     *
     * @param {Matching} other
     *
     * @returns {boolean}
     */
    isCompatible(other) {
        assert(other instanceof Matching, other);
        const segments = new Set();
        for (let segment of this._segments) {
            for (let otherSegment of other._segments) {
                if (!segment.isEquals(otherSegment) && segment.isProperIntersect(otherSegment)) {
                    return false;
                }
            }
        }
        return true;
    }
    /**
     * Returns true iff matching and other are disjoint (no common segments).
     *
     * @param {Matching} other
     *
     * @returns {boolean}
     */
    isDisjoint(other) {
        assert(other instanceof Matching, other);
        if (this._segments === other._segments) {
            return false;
        }
        for (let segment of this._segments) {
            for (let otherSegment of other._segments) {
                if (segment.isEquals(otherSegment)) {
                    return false;
                }
            }
        }
        return true;
    }
    /**
     * Returns true iff are equals matchings (same points and same segments).
     *
     * @param {Matching} other
     *
     * @returns {boolean}
     */
    isEquals(other) {
        assert(other instanceof Matching, other);
        if ((this._points === other._points)
            && (this._segments === other._segments)) {
            return true;
        }
        if ((this._points.length !== other._points.length)
            || (this._segments.length !== other._segments.length)
            || !arrayIsEquals(this._points, other._points,
                              function (p, q) { return p.compare(q); })) {
            return false;
        }
        for (let i = 0; i < this._segments.length; ++i) {
            if (!this._segments[i].isEquals(other._segments[i])) {
                return false;
            }
        }
        return true;
    }
    /**
     * Returns a set of all points without segment.
     *
     * @returns {Set} Set of points
     */
    isolatedPoints() {
        const points = new Set(this._points);
        for (let segment of this._segments) {
            points.delete(segment.a);
            points.delete(segment.b);
        }
        return points;
    }
    /**
     * Returns true iff the matching is perfect (each point is degree 1)
     *
     * @returns {boolean}
     */
    isPerfect() {
        if ((this._points.length % 2 !== 0) || (2*this._segments.length < this._points.length)) {
            // Odd number of points or not enough segments, impossible to be perfect
            return false;
        }
        const points = new Set();
        for (let segment of this._segments) {
            if (points.has(segment.a) || points.has(segment.b)) {
                // Point in at least two segments
                return false;
            }
            points.add(segment.a);
            points.add(segment.b);
        }
        if (points.size !== this._points.length) {
            // There is at least one isolated point
            return false;
        }
        return true;
    }
    /**
     * Returns true iff all segment are vertical or horizontal.
     *
     * @returns {boolean}
     */
    isVerticalHorizontal() {
        for (let segment of this._segments) {
            if (!(segment.isVertical() || segment.isHorizontal())) {
                return false;
            }
        }
        return true;
    }
    /**
     * Returns the index of this matching in the sequence of linked matchings.
     *
     * @returns {integer} >= 0
     */
    linkedMatchingsIndex() {
        for (let i = 0; i < this._linkedMatchings.length; ++i) {
            if (this._linkedMatchings[i] === this) {
                return i;
            }
        }
        assert(false);
    }
    /**
     * Returns all informations of all linked matchings in a string :
     *   # points
     *   x_0, y_0
     *   ...
     *   x_{n-1}, y_{n-1}
     *
     *   # matching
     *
     *   # segment for first matching
     *   index point a - index point b
     *   ...
     *
     *   ...
     *
     *   # segment for last matching
     *   index point a - index point b
     *   ...
     *
     * Warning! All point coordinates are rounded to integers.
     *
     * @returns {String}
     */
    matchingsToString() {
        const lines = [this._points.length + " points"];
        for (let point of this._points) {
            lines.push(Math.round(point.x) + ", " + Math.round(point.y));
        }
        lines.push("");
        lines.push(this._linkedMatchings.length + " matchings");
        const indices = this.pointsIndices();
        for (let matching of this._linkedMatchings) {
            lines.push("");
            lines.push(matching._segments.length + " segments");
            for (let segment of matching._segments) {
                lines.push(indices[segment.a] + " - " + indices[segment.b]);
            }
        }
        return lines.join("\n");
    }
    /**
     * Returns the nearest point of the matching
     * or null if no nearest point.
     *
     * @param {Point} point
     *
     * @returns {Point|null}
     */
    nearestPoint(point) {
        assert(point instanceof Point, point);
        var minDistSqr = Number.POSITIVE_INFINITY;
        var minP = null;
        for (let p of this._points) {
            const distSqr = point.distanceSqr(p);
            if (minDistSqr > distSqr) {
                minDistSqr = distSqr;
                minP = p;
            }
        }
        return (minDistSqr < 10*10
                ? minP
                : null);
    }
    /**
     * Add a point.
     *
     * @param {Point} point (not already in the matching)
     */
    pointAdd(point) {
        assert(point instanceof Point, point);
        assert(!this.pointIsInMatching(point), point);
        sortedArrayInsert(this._points, point, function (p, q) { return p.compare(q); } );
        this.clearIfModifyPoints();
    }
    /**
     * Returns an associative table Point: (it index in the sequence of points).
     *
     * @returns {Map} Point:(integer >= 0)
     */
    pointsIndices() {
        const indices = {};
        for (let i = 0; i < this._points.length; ++i) {
            indices[this._points[i]] = i;
        }
        return indices;
    }
    /**
     * Returns true iff point is a point of the matching.
     *
     * @param {Point} point
     *
     * @returns {boolean}
     */
    pointIsInMatching(point) {
        assert(point instanceof Point, point);
        for (let p of this._points) {
            if (point.isEquals(p)) {
                return true;
            }
        }
        return false;
    }
    /**
     * Remove the existing point.
     *
     * If there is a segment with this point
     * then remove this segment.
     *
     * If removeInLinkedMatchings
     * then remove also segments in all linked matchings.
     *
     * @param {Point} point (must be in the matching)
     * @param {boolean} removeInLinkedMatchings
     */
    pointRemove(point, removeInLinkedMatchings=true) {
        assert(point instanceof Point, point);
        assert(this.pointIsInMatching(point), point);
        assert(typeof removeInLinkedMatchings === "boolean", removeInLinkedMatchings);
        // Remove all segment on this point
        for (let i = 0; i < this._segments.length; ++i) {
            if (this._segments[i].isExtremityPoint(point)) {
                this._segments.splice(i, 1);
                --i;
            }
        }
        if (removeInLinkedMatchings) {
            // For each other linked matchings, remove all segment on this point
            for (let linkedMatching of this._linkedMatchings) {
                if (linkedMatching !== this) {
                    linkedMatching.pointRemove(point, false);
                }
            }
        }
        // Remove point
        arrayRemoveFirst(this._points, point,
                         function (a, b) { return a.compare(b); });
        this.clearIfModifyPoints();
    }
    /**
     * Returns a set of segments that intersect (without their endpoints) one of other.
     *
     * @param {Matching} other
     *
     * @returns {Set} Set of Segment
     */
    properIntersectSegments(other) {
        assert(other instanceof Matching, other);
        const segments = new Set();
        for (let segment of this._segments) {
            for (let otherSegment of other._segments) {
                if (!segment.isEquals(otherSegment) && segment.isProperIntersect(otherSegment)) {
                    segments.add(segment);
                }
            }
        }
        return segments;
    }
    /**
     * Returns a set of segments that intersect (without their endpoints)
     * one of previous or next matching.
     *
     * @returns {Set} Set of Segment
     */
    properIntersectSegmentsWithConsecutiveMatchings() {
        const i = this.linkedMatchingsIndex();
        const left = (i > 0
                      ? this.properIntersectSegments(this._linkedMatchings[i - 1])
                      : new Set());
        const right = (i < this._linkedMatchings.length - 1
                       ? this.properIntersectSegments(this._linkedMatchings[i + 1])
                       : new Set());
        return setUnion(left, right);
    }
    /**
     * Add a segment.
     *
     * @param {Segment} segment (not already in the matching)
     */
    segmentAdd(segment) {
        assert(segment instanceof Segment, segment);
        assert(!this.segmentIsInMatching(segment), segment);
        segment = segment.ordonned();  // segment with point a <= point b
        sortedArrayInsert(this._segments, segment, function (a, b) { return a.compare(b); } );
    }
    /**
     * Returns true iff segment is a segment of the matching.
     *
     * @param {Segment} segment
     *
     * @returns {boolean}
     */
    segmentIsInMatching(segment) {
        assert(segment instanceof Segment, segment);
        for (let s of this._segments) {
            if (segment.isEquals(s)) {
                return true;
            }
        }
        return false;
    }
    /**
     * Returns true iff segment intersect (*with* their endpoints) a segment of the matching.
     *
     * @param {Segment} segment
     *
     * @returns {boolean}
     */
    segmentIsIntersect(segment) {
        assert(segment instanceof Segment, segment);
        for (let s of this._segments) {
            if (segment.isIntersect(s)) {
                return true;
            }
        }
        return false;
    }
    /**
     * Remove the existing segment.
     *
     * @param {Segment} segment (must be in the matching)
     */
    segmentRemove(segment) {
        assert(segment instanceof Segment, segment);
        assert(this.segmentIsInMatching(segment), segment);
        arrayRemoveFirst(this._segments, segment,
                         function (a, b) { return a.compare(b); });
    }
    /**
     * Set segments to be the canonical perfect matching
     * corresponding to these points.
     *
     * @returns {Matching}
     */
    setCanonical() {
        this._segments = this.canonical().segments;
    }
    /**
     * Calculate all possible perfect matchings
     * with the points of this matching
     * and set this list as the linked matchings.
     *
     * If disjointMatching
     * then keep only perfect matching disjoint with this matching.
     *
     * If compatibleMatching
     * then keep only perfect matching disjoint with this matching.
     *
     * @param {Boolean} disjointMatching
     * @param {Boolean} compatibleMatching
     */
    setPerfectMatchings(disjointMatching, compatibleMatching) {
        assert(typeof disjointMatching === "boolean", disjointMatching);
        assert(typeof compatibleMatching === "boolean", compatibleMatching);
        assert(this._linkedMatchings.length >= 2, this._linkedMatchings[0].length);
        this.clearIntermediaryLinkedMatchings();
        const matchings = this.allPerfectMatchings(disjointMatching, compatibleMatching);
        if (matchings.length === 0) {
            return;
        }
        const left = this._linkedMatchings[0];
        if (!left.isPerfect()) {
            // Set left matching with first perfect matching
            left._segments = matchings[0]._segments;
        }
        const right = this._linkedMatchings[this._linkedMatchings.length - 1];
        if (right.isEquals(left) || !right.isPerfect()) {
            // Set right matching with last perfect matching
            right._segments = matchings[matchings.length - 1]._segments;
        }
        if ((matchings.length > 1) && right.isEquals(left)) {
            // Set right matching with previous perfect matching
            right._segments = matchings[matchings.length - 2]._segments;
        }
        if (right.isEquals(left)) {
            // In the case where there is only one perfect matching,
            // then set right with a copy of segments.
            right._segments = right._segments.slice(0);
        }
        this._linkedMatchings.splice(1, 1);  // remove right from the list of linked matchings
        // Add all perfect matchings different to left and right
        for (let matching of matchings) {
            if (!matching.isEquals(left) && !matching.isEquals(right)) {
                this._linkedMatchings.push(matching);
            }
        }
        // Add right perfect matching
        this._linkedMatchings.push(right);
        // Set all list of linked matchings
        for (let matching of this._linkedMatchings) {
            matching._linkedMatchings = this._linkedMatchings;
        }
    }
    /**
     * Set the list of linked matchings
     * to be a transformation (a list of perfect matchings two to two compatible)
     * from this matching to the last linked matching.
     *
     * If disjointTransformation
     * then search a disjoint transformation.
     *
     * Returns true if a transformation was found,
     * else return false.
     *
     * The two utmost matchings must be perfect and different.
     *
     * Warning! Only transformations of length 2 and 3 are implemented.
     *
     * FIXME! Naive algorithm that build before all perfect matchings and try possibilities.
     *
     *
     * @param {Boolean} disjointTransformation
     *
     * @returns {boolean}
     */
    setTransformation(disjointTransformation) {
        assert(typeof disjointTransformation === "boolean", disjointTransformation);
        assert(this._linkedMatchings.length >= 2, this._linkedMatchings[0].length);
        assert(this.points.length % 2 === 0, this.points.length);
        const matchings = this.allPerfectMatchings(false, false);
        assert(matchings.length >= 2, matchings.length);
        const left = this._linkedMatchings[0];
        const right = this._linkedMatchings[this._linkedMatchings.length - 1];
        assert(left.isPerfect(), left);
        assert(right.isPerfect(), right);
        assert(!left.isEquals(right));
        this.clearIntermediaryLinkedMatchings();
        this._linkedMatchings.splice(1, 1);
        // Remove left and right matchings from the matchings list
        for (let i = 0; i < matchings.length; ++i) {
            const matching = matchings[0];
            if (matching.isEquals(left) || matching.isEquals(right)) {
                matchings.splice(i, 1);
            }
        }
        // Try with only 1 intermediary matching
        for (let matching of matchings) {
            if ((!disjointTransformation
                 || (matching.isDisjoint(left) && matching.isDisjoint(right)))
                && matching.isCompatible(left) && matching.isCompatible(right)) {
                this._linkedMatchings.push(matching);
                break;
            }
        }
        if (this._linkedMatchings.length === 1) {
            // Try with with 2 intermediary matchings
            var found = false;
            for (let matching1 of matchings) {
                if ((!disjointTransformation || matching1.isDisjoint(left))
                    && matching1.isCompatible(left)) {
                    for (let matching2 of matchings) {
                        if ((!disjointTransformation
                             || (matching2.isDisjoint(matching1) && matching2.isDisjoint(right)))
                            && matching2.isCompatible(matching1) && matching2.isCompatible(right)) {
                            this._linkedMatchings.push(matching1);
                            this._linkedMatchings.push(matching2);
                            found = true;
                            break;
                        }
                    }
                    if (found) {
                        break;
                    }
                }
            }
        }
        // Add the right matching
        this._linkedMatchings.push(right);
        // Set all list of linked matchings
        for (let matching of this._linkedMatchings) {
            matching._linkedMatchings = this._linkedMatchings;
        }
        return (this._linkedMatchings.length > 2);
    }
    /**
     * Set segments at random to be a perfect matching
     * corresponding to these points.
     *
     * @returns {Matching}
     */
    shuffleSegments() {
        if (this._segments.length <= 1) {
            return;
        }
        const maxNb = getRandomInteger(3, 5);
        for (let nb = 0; nb < maxNb; ++nb) {
            for (let i = 0; i < this._segments.length; ++i) {
                const j = getRandomInteger(0, this._segments.length);
                if (i === j) {
                    continue;
                }
                const segmentI = this._segments[i];
                const segmentJ = this._segments[j];
                this.segmentRemove(segmentI);
                this.segmentRemove(segmentJ);
                const segmentA = new Segment(segmentI.a, segmentJ.a);
                const segmentB = new Segment(segmentI.b, segmentJ.b);
                var keep = false;
                if (!this.segmentIsIntersect(segmentA)) {
                    this.segmentAdd(segmentA);
                    if (!this.segmentIsIntersect(segmentB)) {
                        this.segmentAdd(segmentB);
                        keep = true;
                    }
                    else {
                        this.segmentRemove(segmentA);
                    }
                }
                if (!keep) {
                    this.segmentAdd(segmentI);
                    this.segmentAdd(segmentJ);
                }
            }
        }
    }
}