// Construct a GeomGraph and a GeomGraphQuad, from the same
// command line arguments, and save snapshots (GG.png, GQ.png).
// Report any edge differences. Repeated edges in either graph
// are silently ignored before making this comparison.

import java.util.Iterator;
import java.util.ListIterator;
import java.util.ArrayList;

public class CompareGraphs
{
    // Size our our window and snapshot images.
    static int SIZE = 900;

    // Draw G to StdDraw, and save snapshot to name.png
    static void snapshot(GeomGraph G, String name)
    {
        StdOut.printf("Drawing %s ... ", name);
        StdDraw.setCanvasSize(SIZE,SIZE);
        Rectangle bb = G.bbox().bSquare();
        StdDraw.setXscale(bb.min.x, bb.max.x);
        StdDraw.setYscale(bb.min.y, bb.max.y);
        StdDraw.setPenColor(StdDraw.BLACK);
        StdDraw.show(0);        // start deferred drawing
        // Draw all vertices (fat pen):
        StdDraw.setPenRadius(0.008);
        int V = G.V();
        for (int v=0; v<V; ++v)
            G.point(v).draw();
        // Draw all edges (thin pen):
        StdDraw.setPenRadius(0.002);
        for (int v=0; v<V; ++v) {
            Point p = G.point(v);
            for (Edge e: G.adj(v))
                p.drawTo(G.point(e.other(v)));
        }
        // Label with name, show, and save snapshot.
        StdDraw.setPenColor(StdDraw.BLUE);
        StdDraw.textLeft(bb.min.x, bb.max.y, name);
        StdDraw.show(0);
        StdDraw.save(name + ".png");
        StdOut.printf("wrote %s.png%n%n", name);
    }

    public static void main(String[] args)
    {
        Point[] none = new Point[0];

        StdOut.printf("Creating GeomGraph GG:%n%n");
        GeomGraph GG = new GeomGraph(none).create(args, null);
        snapshot(GG, "GG");

        StdOut.printf("Creating GeomGraphQuad GQ:%n%n");
        GeomGraph GQ = new GeomGraphQuad(none).create(args, null);
        snapshot(GQ, "GQ");

        StdOut.println("Comparing edges (ignoring dups):");
        assert GG.V() == GQ.V();
        int diffs = 0, V = GG.V();
        for (int v=0; v<V; ++v) {
            // Get sorted edge lists, with duplicates removed:
            EdgeList el1 = new EdgeList(GG, v);
            EdgeList el2 = new EdgeList(GQ, v);
            // Look for edges e in one list but not in the other.
            // Since we are confident that our graphs are symmetric,
            // we only report edge e when found in list of e.either().
            ListIterator<Edge> it1 = el1.listIterator();
            ListIterator<Edge> it2 = el2.listIterator();
            while (it1.hasNext() && it2.hasNext()) {
                Edge e1 = it1.next(), e2 = it2.next();
                int cmp = e1.compareTo(e2);
                if (cmp == 0) continue; // equal, good
                if (cmp < 0 && e1.either()==v) {
                    StdOut.printf("Edge in GG-GQ: %s%n", e1);
                    ++diffs;
                    it2.previous();
                }
                if (cmp > 0 && e2.either()==v) {
                    StdOut.printf("Edge in GQ-GG: %s%n", e2);
                    ++diffs;
                    it1.previous();
                }
            }
            while (it1.hasNext()) {
                Edge e = it1.next();
                if (e.either()!=v) continue;
                StdOut.printf("tail Edge in GG-GQ: %s%n", e);
                ++diffs;
            }
            while (it2.hasNext()) {
                Edge e = it2.next();
                if (e.either()!=v) continue;
                StdOut.printf("tail Edge in GQ-GG: %s%n", e);
                ++diffs;
            }
        }
        StdOut.printf("Found %d edge differences (ignoring dups)%n", diffs);
        // Exit and close the StdDraw window.
        System.exit(0);
    }
}

class EdgeList extends ArrayList<Edge>
{
    EdgeList(GeomGraph G, int v) {
        // Get point corresponding to v.
        Point p = G.point(v);
        // Copy all edges from the adjacency list (a bag, any order)
        for (Edge e: G.adj(v)) add(e);
        // Sort the edges by weight
        java.util.Collections.sort(this);
        Iterator<Edge> it = iterator();
        Edge last = null;
        while (it.hasNext()) {
            Edge e = it.next();
            int w = e.other(v);
            Point q = G.point(w);
            // check edge length
            double dist = p.distanceTo(q);
            if (dist != e.weight())
                StdOut.printf("Warning: edge (%d,%d) weight is %f, not %f%n",
                              v, w, e.weight(), dist);
            // Is this a duplicate edge (same w)? quietly remove it
            if (last != null && w == last.other(v))
                it.remove();
            else
                last = e;
        }
    }
}