Source: model/Matching.js

/**
 * @file Class Matching
 * @version March 22, 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.
     *
     * FIXME! Naive algorithm. Implement iterative building?
     *
     * @returns {Array} Array of Matching
     */
    allPerfectMatchings() {
        const matchings = [];

        if (this.points.length % 2 !== 0) {
            return matchings;
        }

        const thisMatching = this;
        const points = this.points;
        const nbPoints = points.length;
        const assigns = new Array();

        // 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;

                    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.
     */
    setPerfectMatchings() {
        assert(this._linkedMatchings.length >= 2, this._linkedMatchings[0].length);

        this.clearIntermediaryLinkedMatchings();

        const matchings = this.allPerfectMatchings();

        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.
     *
     * Returns true if a transformation was found,
     * else return false.
     *
     * The two utmost matchings must be perfect.
     *
     * Warning! Only transformations of length 2, 3 and 4 are implemented.
     *
     * FIXME! Naive algorithm that build before all perfect matchings and try possibilities.
     *
     * @returns {boolean}
     */
    setTransformation() {
        assert(this._linkedMatchings.length >= 2, this._linkedMatchings[0].length);

        assert(this.points.length % 2 === 0, this.points.length);

        const matchings = this.allPerfectMatchings();

        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);

        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 (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 (matching1.isDisjoint(left)
                    && matching1.isCompatible(left)) {
                    for (let matching2 of matchings) {
                        if (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);
                }
            }
        }
    }
}