Plane.java

package com.sencha.example.emst.client.widget;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;

import com.google.gwt.event.dom.client.ClickEvent;
import com.google.gwt.event.dom.client.ClickHandler;
import com.sencha.example.emst.client.widget.Plane.DisjointSet.Entry;
import com.sencha.gxt.chart.client.draw.DrawComponent;
import com.sencha.gxt.chart.client.draw.RGB;
import com.sencha.gxt.chart.client.draw.path.LineTo;
import com.sencha.gxt.chart.client.draw.path.MoveTo;
import com.sencha.gxt.chart.client.draw.path.PathSprite;
import com.sencha.gxt.widget.core.client.Composite;

public class Plane extends Composite {

  public static class DisjointSet<E> {
    // from http://en.wikipedia.org/wiki/Disjoint-set_data_structure
    public static class Entry<E> {
      E item;
      int rant = 0;
      Entry<E> parent = this;
    }

    private Map<E, Entry<E>> entries = new HashMap<E, Entry<E>>();

    public Entry<E> get(E item) {
      Entry<E> e = entries.get(item);
      if (e == null) {
        e = make(item);
        entries.put(item, e);
      }
      return e;
    }

    public int size() {
      return entries.size();
    }

    private Entry<E> make(E item) {
      Entry<E> e = new Entry<E>();
      e.item = item;
      return e;
    }

    public Entry<E> find(E item) {
      return find(get(item));
    }
    public Entry<E> find(Entry<E> item) {
      if (item.parent == item) {
        return item;
      }
      item.parent = find(item.parent);
      return item.parent;
    }

    public void union(Entry<E> item1, Entry<E> item2) {
      Entry<E> root1 = find(item1);
      Entry<E> root2 = find(item2);

      if (root1 == root2) {
        return;
      }
      if (root1.rant < root2.rant) {
        root1.parent = root2;
      } else if (root2.rant < root1.rant) {
        root2.parent = root1;
      } else {
        root2.parent = root1;
        root1.rant++;
      }
    }
  }

  private Triangulation t = new Triangulation();
  private Map<Edge, PathSprite> sprites = new HashMap<Edge, PathSprite>();

  private boolean isSpanning = true;

  public Set<Edge> span(Set<Edge> edges) {
    // from http://en.wikipedia.org/wiki/Kruskal%27s_algorithm
    DisjointSet<Vertex> edgeClusters = new DisjointSet<Vertex>();
    PriorityQueue<Edge> q = new PriorityQueue<Edge>(edges);
    for (Edge e : edges) {
      edgeClusters.get(e.getV1());
      edgeClusters.get(e.getV2());
    }

    Set<Edge> finished = new HashSet<Edge>();
    while (finished.size() < edgeClusters.size() - 1) {
      assert q.isEmpty() == false;
      Edge min = q.remove();

      Entry<Vertex> cluster1 = edgeClusters.find(min.getV1());
      Entry<Vertex> cluster2 = edgeClusters.find(min.getV2());
      if (cluster1 != cluster2) {
        finished.add(min);
        edgeClusters.union(cluster1, cluster2);
      }
    }

    return finished;
  }

  public Plane() {
    initWidget(new DrawComponent());
    getWidget().addDomHandler(new ClickHandler() {

      public void onClick(ClickEvent event) {
        double x = (double) event.getRelativeX(getElement()) / (double) getWidth();
        double y = (double) event.getRelativeY(getElement()) / (double) getHeight();
        add(new Vertex(x, y));
      }
    }, ClickEvent.getType());


    for (int i = 0; i < 1000; i++) {
      t.addVertex(new Vertex(Math.random(), Math.random()));
    }
  }

  @Override
  protected void onLoad() {
    super.onLoad();
    draw();
  }

  @Override
  protected void onResize(int width, int height) {
    for (PathSprite s : sprites.values()) {
      s.remove();
    }
    sprites.clear();
    super.onResize(width, height);
    draw();
  }

  protected DrawComponent getDrawComponent() {
    return (DrawComponent) getWidget();
  }

  public void add(Vertex v) {
    t.addVertex(v);
    draw();
  }

  protected void draw() {
    if (isSpanning) {
      draw(span(t.getEdges()));
    } else {
      draw(t.getEdges());
    }
  }


  public Set<Edge> addOneVertex(Vertex v) {
    Triangulation copy = t.copy();
    copy.addVertex(v);
    return copy.getEdges();
  }

  private void draw(Set<Edge> edges) {
    Map<Edge, PathSprite> old = sprites;
    sprites = new HashMap<Edge, PathSprite>();

    for (Edge e : edges) {
      PathSprite s = old.remove(e);
      if (s == null) {
        s = new PathSprite();
        s.setStroke(RGB.BLACK);
        s.addCommand(new MoveTo(scaleX(e.getV1().getX()), scaleY(e.getV1().getY())));
        s.addCommand(new LineTo(scaleX(e.getV2().getX()), scaleY(e.getV2().getY())));
        getDrawComponent().add(s);
      }
      sprites.put(e, s);
    }

    for (PathSprite sprite : old.values()) {
      sprite.remove();
    }
    getDrawComponent().redraw();

  }

  private double scaleX(double x) {
    return getWidth() * x;
  }

  private double scaleY(double y) {
    return getHeight() * y;
  }

  public void setSpan(Boolean value) {
    if (value != isSpanning) {
      this.isSpanning = value;
      draw();
    }
  }

  public void clear() {
    t = new Triangulation();
    draw();
  }
}