/*******************************************************************************
 * Copyright (c) 2013 Association for Decentralized Information Management in
 * Industry THTH ry.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *     VTT Technical Research Centre of Finland - initial API and implementation
 *******************************************************************************/
package org.simantics.diagram.connection.segments;

import gnu.trove.map.TObjectIntMap;
import gnu.trove.map.hash.THashMap;
import gnu.trove.map.hash.TObjectIntHashMap;
import gnu.trove.procedure.TObjectIntProcedure;
import gnu.trove.set.hash.THashSet;

import java.awt.geom.Point2D;
import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.simantics.diagram.connection.RoutePoint;

/**
 * @author Hannu Niemistö
 * @author Tuukka Lehtonen <tuukka.lehtonen@semantum.fi>
 */
public class GeometricSegment {
    public final double x1;
    public final double y1;
    public final boolean isBranching1;

    public final double x2;
    public final double y2;
    public final boolean isBranching2;

    public GeometricSegment(double x1, double y1, boolean isBranching1,
            double x2, double y2, boolean isBranching2) {
        this.x1 = x1;
        this.y1 = y1;
        this.isBranching1 = isBranching1;
        this.x2 = x2;
        this.y2 = y2;
        this.isBranching2 = isBranching2;
    }

    public boolean isOnSegment(double x, double y) {
        double dist = distanceFrom(x1, y1, x2, y2, x, y);
        //System.out.println("distance(" + this + ", " + x + ", " + y + "): " + dist);
        return dist == 0;
    }

    public static List<GeometricSegment> convert(Collection<Segment> segments) {
        // Compute point counts
        TObjectIntHashMap<RoutePoint> pointCounts = new TObjectIntHashMap<RoutePoint>(); 
        for(Segment segment : segments) {
            pointCounts.adjustOrPutValue(segment.p1, 1, 1);
            pointCounts.adjustOrPutValue(segment.p2, 1, 1);
        }

        // Propagate point counts thru degenerated points
        // This code is not perfect: it may fail if there are multiple
        // degenerated segments connected to the same point.
        for(Segment segment : segments) {
            if(segment.isDegenerated()) {
                int count = pointCounts.get(segment.p1) +  
                        pointCounts.get(segment.p2) - 2;
                pointCounts.put(segment.p1, count);
                pointCounts.put(segment.p2, count);
            }
        }

        // Generate geometric segments
        ArrayList<GeometricSegment> result = new ArrayList<GeometricSegment>();
        for(Segment segment : segments) {
            if(!segment.isDegenerated()) {
                result.add(new GeometricSegment(
                        segment.p1.getX(), segment.p1.getY(), 
                        pointCounts.get(segment.p1) > 2, 
                        segment.p2.getX(), segment.p2.getY(), 
                        pointCounts.get(segment.p2) > 2
                        ));
            }
        }
        return result;
    }

    /**
     * Removes unnecessary points from the specified set of segments. Returns a
     * set of segments that no longer specify these unnecessary points.
     * 
     * Definition: point P is unnecessary iff
     * 1. P connects only two other points P1 and P2 together (P1 != P && P2 != P)
     * 2. P lies on the line segment formed by points (P1, P2)
     * 
     * @param segments unoptimized set of line segments
     * @return optimized set of line segments
     */
    public static List<GeometricSegment> optimize(List<GeometricSegment> segments) {
        if (segments.size() == 1)
            return segments;

        TObjectIntMap<Point2D> degree = new TObjectIntHashMap<Point2D>();
        final TObjectIntMap<Point2D> branched = new TObjectIntHashMap<Point2D>();
        final Map<Point2D, List<GeometricSegment>> segmentsOfPoint = new THashMap<Point2D, List<GeometricSegment>>();

        for (GeometricSegment seg : segments) {
            Point2D p1 = new Point2D.Double(seg.x1, seg.y1);
            Point2D p2 = new Point2D.Double(seg.x2, seg.y2);
            degree.adjustOrPutValue(p1, 1, 1);
            degree.adjustOrPutValue(p2, 1, 1);
            int bi1 = seg.isBranching1 ? 1 : 0;
            int bi2 = seg.isBranching2 ? 1 : 0;
            branched.adjustOrPutValue(p1, bi1, bi1);
            branched.adjustOrPutValue(p2, bi2, bi2);
            addSegmentToPoint(p1, seg, segmentsOfPoint);
            addSegmentToPoint(p2, seg, segmentsOfPoint);
        }

        final List<Point2D> unnecessaryPoints = new ArrayList<Point2D>(segments.size());
        degree.forEachEntry(new TObjectIntProcedure<Point2D>() {
            @Override
            public boolean execute(Point2D a, int branchCount) {
                if (branchCount == 2 && branched.get(a) == 0) {
                    // Is the point on the same line formed by the
                    // join of the two segments if a is removed from
                    // between them?
                    List<GeometricSegment> segs = segmentsOfPoint.get(a);
                    assert segs.size() == 2;
                    GeometricSegment seg = join(a, segs.get(0), segs.get(1));
                    if (seg.isOnSegment(a.getX(), a.getY())) {
                        // a is a degenerate route point that can be removed
                        unnecessaryPoints.add(a);
                    }
                }
                return true;
            }
        });

        if (unnecessaryPoints.isEmpty())
            return segments;

        // Remove all unnecessary points from 
        Point2D p = new Point2D.Double();
        for (Point2D dp : unnecessaryPoints) {
            //System.out.println("Removing unnecessary point: " + dp);
            List<GeometricSegment> segs = segmentsOfPoint.remove(dp);
            assert segs.size() == 2;

            GeometricSegment joined = join(dp, segs.get(0), segs.get(1));

            GeometricSegment a = segs.get(0);
            a.otherEnd(dp, p);
            removeSegmentFromPoint(p, a, segmentsOfPoint);
            addSegmentToPoint(p, joined, segmentsOfPoint);

            GeometricSegment b = segs.get(1);
            b.otherEnd(dp, p);
            removeSegmentFromPoint(p, b, segmentsOfPoint);
            addSegmentToPoint(p, joined, segmentsOfPoint);
        }

        ArrayList<GeometricSegment> result = new ArrayList<GeometricSegment>(segments.size());
        Set<GeometricSegment> processed = new THashSet<GeometricSegment>();
        for (List<GeometricSegment> segs : segmentsOfPoint.values()) {
            for (GeometricSegment seg : segs) {
                if (processed.add(seg)) {
                    result.add(seg);
                }
            }
        }

        return result;
    }

    /**
     * Internal utility for {@link #optimize(List)}.
     * @param seg
     * @param oneEnd
     * @param otherEnd
     * @return
     */
    private Point2D otherEnd(Point2D oneEnd, Point2D otherEnd) {
        double x = oneEnd.getX();
        double y = oneEnd.getY();
        double rx = x1;
        double ry = y1;
        if (x == x1 && y == y1) {
            rx = x2;
            ry = y2;
        }
        otherEnd.setLocation(rx, ry);
        return otherEnd;
    }

    /**
     * Internal utility for {@link #optimize(List)}.
     * 
     * @param at
     * @param s1
     * @param s2
     * @return
     */
    private static GeometricSegment join(Point2D at, GeometricSegment s1, GeometricSegment s2) {
        double x = at.getX();
        double y = at.getY();

        double x1 = s1.x1;
        double y1 = s1.y1;
        boolean b1 = s1.isBranching1;
        if (x == s1.x1 && y == s1.y1) {
            x1 = s1.x2;
            y1 = s1.y2;
            b1 = s1.isBranching2;
        }

        double x2 = s2.x1;
        double y2 = s2.y1;
        boolean b2 = s2.isBranching1;
        if (x == s2.x1 && y == s2.y1) {
            x2 = s2.x2;
            y2 = s2.y2;
            b1 = s2.isBranching2;
        }

        return new GeometricSegment(x1, y1, b1, x2, y2, b2);
    }

    /**
     * Internal utility for {@link #optimize(List)}.
     * 
     * @param p
     * @param seg
     * @param segmentsOfPoint
     */
    private static void addSegmentToPoint(Point2D p, GeometricSegment seg, Map<Point2D, List<GeometricSegment>> segmentsOfPoint) {
        List<GeometricSegment> l = segmentsOfPoint.get(p);
        if (l == null)
            segmentsOfPoint.put(p, l = new ArrayList<GeometricSegment>(4));
        l.add(seg);
    }

    /**
     * Internal utility for {@link #optimize(List)}.
     * 
     * @param p
     * @param seg
     * @param segmentsOfPoint
     * @return
     */
    private static boolean removeSegmentFromPoint(Point2D p, GeometricSegment seg, Map<Point2D, List<GeometricSegment>> segmentsOfPoint) {
        List<GeometricSegment> l = segmentsOfPoint.get(p);
        return l != null ? l.remove(seg) : false;
    }

    /**
     * @param x1 line segment end 1 x
     * @param y1 line segment end 1 y
     * @param x2 line segment end 2 x
     * @param y2 line segment end 2 y
     * @param px point x
     * @param py point y
     * @return distance of (px,py) from line ((x1,y1), (x2,y2))
     */
    private static double distanceFrom(double x1, double y1, double x2, double y2, double px, double py) {
        // Adjust vectors relative to x1,y1
        // x2,y2 becomes relative vector from x1,y1 to end of segment
        x2 -= x1;
        y2 -= y1;
        // px,py becomes relative vector from x1,y1 to test point
        px -= x1;
        py -= y1;
        double dotprod = px * x2 + py * y2;
        // dotprod is the length of the px,py vector
        // projected on the x1,y1=>x2,y2 vector times the
        // length of the x1,y1=>x2,y2 vector
        double lineLenSq = x2 * x2 + y2 * y2;
        double lineLen = Math.sqrt(lineLenSq);
        double projLen = dotprod / lineLen;

        // Check whether the projection of (px,py) is outside the specified line.
        if (projLen < 0) {
            return Math.sqrt(px * px + py * py);
        } else if (projLen > lineLen) {
            double dx = px - x2;
            double dy = py - y2;
            return Math.sqrt(dx * dx + dy * dy);
        }
        return Math.sqrt(px * px + py * py - projLen * projLen);
    }

    @Override
    public String toString() {
        return getClass().getSimpleName() + "[(" + x1 + ", " + y1 + ", " + isBranching1
                + ") <-> (" + x2 + ", " + y2 + ", " + isBranching2 + ")]";
    }
}