// License: GPL. For details, see LICENSE file.
package org.openstreetmap.josm.plugins.fastdraw;

import java.awt.Point;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Set;

import org.openstreetmap.josm.data.coor.ILatLon;
import org.openstreetmap.josm.data.coor.LatLon;
import org.openstreetmap.josm.gui.MapView;
import org.openstreetmap.josm.tools.Logging;

/**
 * A holder for how the polyline has been drawn
 */
public class DrawnPolyLine {
    MapView mv;
    private final LinkedList<LatLon> points = new LinkedList<>();
    private LinkedList<LatLon> simplePoints = new LinkedList<>();
    private Set<LatLon> used;
    private final Set<LatLon> fixed = new HashSet<>();

    private int lastIdx;
    private boolean closedFlag;

    /**
     * Create a new object
     */
    public DrawnPolyLine() {
        clear();
    }

    public void setMv(MapView mv) {
        this.mv = mv;
    }

    boolean isFixed(LatLon pp2) {
        return fixed.contains(pp2);
    }

    double getLength() {
        List<LatLon> pts = getPoints();
        Iterator<LatLon> it1, it2;
        ILatLon pp1, pp2;
        if (pts.size() < 2) return 0;
        it1 = pts.listIterator(0);
        it2 = pts.listIterator(1);
        double len = 0;
        for (int i = 0; i < pts.size() - 1; i++) {
            pp1 = it1.next();
            pp2 = it2.next();
            len += pp1.greatCircleDistance(pp2);
        }
        return len;
    }

    LinkedList<LatLon> getPoints() {
        if (simplePoints != null) return simplePoints; else return points;
    }

    boolean wasSimplified() {
        return (simplePoints != null && !simplePoints.isEmpty());
    }

    int findClosestPoint(Point p, double d) {
        double x = p.x, y = p.y;
        int n = points.size();
        int idx = -1;
        double dist, minD = 1e10;
        for (int i = 0; i < n; i++) {
            dist = Math.sqrt(getPoint(points.get(i)).distanceSq(x, y));
            if (dist < d && dist < minD) {
                idx = i;
                minD = dist;
            }
        }
        return idx;
    }

    void clear() {
        points.clear();
        used = null;
        lastIdx = 0;
        closedFlag = false;
        fixed.clear();
        simplePoints = null;
    }

    void undo() {
        if (lastIdx > 0 && lastIdx < points.size()) {
            points.remove(lastIdx);
            lastIdx--;
        }
    }

    void fixPoint(LatLon p) {
        fixed.add(p);
    }

    void addFixed(LatLon coor) {
        addLast(coor);
        fixed.add(coor);
    }

    public Set<LatLon> getFixedPoints() {
        return fixed;
    }

    void addLast(LatLon coor) {
        if (closedFlag && lastIdx > points.size()-1) return;
        if (lastIdx >= points.size()-1) {
            //
            if (points.isEmpty() || !coor.equals(points.getLast())) {
                points.addLast(coor);
                if (points.size() > 1) lastIdx++;
            }
        } else {
            // insert point into middle of the line
            if (points.isEmpty() || !coor.equals(points.get(lastIdx))) {
                points.add(lastIdx + 1, coor);
                lastIdx++;
            }
        }
    }

    Point getLastPoint() {
        if (lastIdx < points.size()) return getPoint(points.get(lastIdx));
        else return null;
    }

    Point getPoint(LatLon p) {
        return mv.getPoint(p);
    }

    int getSimplePointsCount() {
        if (simplePoints != null) return simplePoints.size(); else return -1;
    }

    /**
     * Increase epsilon to fit points count in maxPKM point per 1 km
     * @param initEpsilon min point-to line distance in pixels (tolerance, initial)
     * @param ekf The multiplier against the epsilon for the next round, until the max points per km is reached
     * @param k see {@link #getNodesPerKm(int)}
     * @param maxPKM The maximum nodes per km
     * @return The final epsilon value used
     */
    double autoSimplify(double initEpsilon, double ekf, int k, double maxPKM) {
        double e = initEpsilon;
        if (e < 1e-3) e = 1e-3;
        if (ekf < 1 + 1e-2) ekf = 1.01;
        simplify(e);
        while (getNodesPerKm(k) > maxPKM && e < 1e3) {
            e = e * ekf;
            simplify(e);
            if (simplePoints != null) {
                Logging.trace("DrawnPolyLine: eps={0} n={1}", e, simplePoints.size());
            }
        }
        return e;
    }

    /**
     * Simplified drawn line, not touching the nodes includes in "fixed" set.
     * @param epsilon min point-to line distance in pixels (tolerance)
     */
    void simplify(double epsilon) {
        Logging.trace("DrawnPolyLine: Simplify polyline...");
        int n = points.size();
        if (n < 3) return;
        used = new HashSet<>(n);
        int start = 0;
        for (int i = 0; i < n; i++) {
            LatLon p = points.get(i);
            if (fixed.contains(p) || i == n - 1) {
                if (start < 0) {
                    start = i;
                } else {
                    douglasPeucker(start, i, epsilon, 0);
                }
            }
        }
        simplePoints = new LinkedList<>();
        simplePoints.addAll(points);
        simplePoints.retainAll(used);
        used = null;
    }

    /**
     * Simplification of the line specified by "points" field.
     * Remaining points are included to "used" set.
     * @param start - starting index
     * @param end - ending index
     * @param epsilon - min point-to line distance in pixels (tolerance)
     * @param depth - recursion level
     */
    private void douglasPeucker(int start, int end, double epsilon, int depth) {
        if (depth > 500) return;
        if (end - start < 1) return; // incorrect invocation
        LatLon first = points.get(start);
        LatLon last = points.get(end);
        Point firstP = getPoint(first);
        Point lastP = getPoint(last);
        used.add(first);
        used.add(last);

        if (end - start < 2) return;

        int farthestNode = -1;
        double farthestDist = 0;

        for (int i = start + 1; i < end; i++) {
            double d = pointLineDistance(getPoint(points.get(i)), firstP, lastP);
            if (d > farthestDist) {
                farthestDist = d;
                farthestNode = i;
            }
        }

        if (farthestDist > epsilon) {
            douglasPeucker(start, farthestNode, epsilon, depth + 1);
            douglasPeucker(farthestNode, end, epsilon, depth + 1);
        }
    }

    /**
     * Modified function from LakeWalker
     * Gets distance from point p1 to line p2-p3
     * @param p1 The originating point
     * @param p2 An end of the line
     * @param p3 The other end of the line
     * @return The distance from point p1 to the line p2-p3
     */
    public double pointLineDistance(Point p1, Point p2, Point p3) {
        double x0 = p1.x; double y0 = p1.y;
        double x1 = p2.x; double y1 = p2.y;
        double x2 = p3.x; double y2 = p3.y;
        if (x2 == x1 && y2 == y1) {
            return Math.hypot(x1 - x0, y1 - y0);
        } else {
            return Math.abs((x2-x1)*(y1-y0)-(x1-x0)*(y2-y1))/Math.hypot(x2 - x1, y2 - y1);
        }
    }

    void closeLine() {
        points.add(points.getFirst());
        closedFlag = true;
    }

    boolean isClosed() {
        return closedFlag;
    }

    void deleteNode(int idx) {
        final boolean isClosed = isClosed();
        final LatLon point = points.get(idx);
        if (isClosed) {
            if (idx == 0) idx = getPointCount() - 1;
            if (idx == getPointCount() - 1) closedFlag = false;
        }
        if (idx <= lastIdx && lastIdx != 0) lastIdx--;
        fixed.remove(points.get(idx));
        points.remove(idx);
        if (isClosed && points.size() == 1 && points.get(0) == point) {
            this.deleteNode(0);
        }
    }

    void tryToDeleteSegment(Point p) {
        if (points.size() < 3) return;

        LatLon start;
        start = findBigSegment(p);
        ListIterator<LatLon> it = points.listIterator();
        LatLon pp;
        boolean f = false;
        int i = 0, idx = -1;
        while (it.hasNext()) {
            pp = it.next();
            if (f && fixed.contains(pp)) {
                // if end of line fragment reached
                lastIdx = idx;
                return;
            }
            if (f && !it.hasNext()) {
                // if end of whole line reached
                closedFlag = false;
                it.remove();
                lastIdx = points.size()-1;
                return;
            }

            // if we are deleting this segment
            if (f) it.remove();
            if (pp == start) {
                f = true;
                idx = i;
            } // next node should be removed
            i++;
        }
        lastIdx = points.size()-1;
    }

    /**
     * find starting point of the polyline line fragment close to p
     *  line fragment = segments between two fixed (green) nodes
     * @param p The point to find the segment for
     * @return the LatLon of the start of the segment
     */
    LatLon findBigSegment(Point p) {
        if (points.size() < 2) return null;
        Iterator<LatLon> it1 = points.listIterator(0);
        Iterator<LatLon> it2 = points.listIterator(1);
        Point p1, p2;
        LatLon pp1, pp2, start;
        start = points.getFirst();
        do {
            pp1 = it1.next();
            pp2 = it2.next();
            p1 = getPoint(pp1);
            p2 = getPoint(pp2);
            // maintain segment start end end
            if (fixed.contains(pp1)) {
                start = pp1;
            }
            if (pointSegmentDistance(p, p1, p2) < 5) {
                return start;
            }
        } while (it2.hasNext());
        return null;
    }

    private static double pointSegmentDistance(Point p, Point p1, Point p2) {
        final int x = p.x - p1.x;
        final int y = p.y - p1.y;
        final int a = p2.x - p1.x;
        final int b = p2.y - p1.y;
        final double l = Math.hypot(a, b);
        if (l == 0) {
            return Math.hypot(x, y); // p1 = p2
        }
        final double kt = (x * a + y * b)/l;
        final double kn = Math.abs((-x * b + y * a)/l);
        double dist;
        if (kt >= 0 && kt < l) dist = kn; else {
            dist = Math.min(Math.hypot(x, y), Math.hypot((double) x - a, (double) y - b));
        }
        return dist;
    }

    void clearSimplifiedVersion() {
        simplePoints = null;
    }

    boolean isLastPoint(int i) {
        return (lastIdx == i);
    }

    void moveToTheEnd() {
        lastIdx = points.size()-1;
    }

    void toggleFixed(int idx) {
        LatLon p = points.get(idx);
        if (fixed.contains(p)) fixed.remove(p);
        else fixed.add(p);
    }

    void moveNode(int dragNode, LatLon coor) {
        LatLon dragged = points.get(dragNode);
        // points.getLast().equals(points.getFirst()
        if (closedFlag && points.getFirst().equals(dragged)) {
            // move both ends
            points.set(0, coor);
            points.set(points.size()-1, coor);
        } else {
            points.set(dragNode, coor);
        }
        if (fixed.contains(dragged)) {
            fixed.remove(dragged);
            fixed.add(coor);
        }
    }

    /**
     * Returns maximum number of simplified line points divided by line segment length
     * max((k-1) / (L(i,i+1)+L(i+1,i+2)+...+L(i+k-1,i+k))) [ i=1..n-k ]
     * @param k - window size (number of points to average points per km
     * @return The maximum number of <i>simplified</i> line points divided by the segment length
     */
    public double getNodesPerKm(int k) {
        List<LatLon> pts = simplePoints;
        if (!wasSimplified()) pts = points;
        int n = pts.size();
        if (n < 2) return 0;
        if (k < 2) k = 2;
        if (k > n) k = n;

        ILatLon pp1, pp2;
        Iterator<LatLon> it1, it2;
        it1 = pts.listIterator(0);
        it2 = pts.listIterator(1);
        double[] lens = new double[n];
        for (int i = 0; i < n-1; i++) {
            pp1 = it1.next();
            pp2 = it2.next();
            lens[i] = pp1.greatCircleDistance(pp2);
        }
        double pkm = 0, maxpkm = 0;
        double len = 0;
        int seg; // averaged segments counts
        for (int i = 1; i < n; i++) {
            len += lens[i-1]; // add next next point
            // remove old segment
            if (i > k) {
                seg = k;
                len -= lens[i-k-1];
            } else
                seg = i;
            if (i >= k || i == n-1) {
                // len is length of points[i-windowSize] .. points[i]
                if (len > 0) pkm = seg / len * 1000;
                Logging.trace("DrawnPolyLine: i={0} len={1} pkm={2}", i, len, pkm);
                if (pkm > maxpkm) maxpkm = pkm;
            }
        }
        return Math.round(maxpkm);
    }

    int getPointCount() {
        return points.size();
    }
}
