//
// Percolation Applet
//   by Kevin Chase
//
// This Java applet generates and displays bond 
// percolation lattices, identifying the first few large clusters
// with distinct colors.
//
// It's a work in progress, so don't be too critical.
//

import java.applet.*;
import java.awt.*;
import java.util.*;

//
// BondLattice class
//    contains the lattice data and its cluster maps.
//
class BondLattice extends Object {
  static final int colored_clusters = 8;

  double p;                 // Bond filling probability
  int x_sites, y_sites;     // Dimensions of lattice (width, height)
  double bondx[], bondy[];  // Bond data: <p then filled.
  int cluster_id[];         // Site data: =n -=> site belongs to cluster n
  int large_cluster[];      // Cluster data: 0th entry is largest, etc.

  // Constructor for the lattice
  BondLattice(double p, int x, int y) {
    this.p = p;
    x_sites = x;
    y_sites = y;
    bondx = new double[x_sites*y_sites];
    bondy = new double[x_sites*y_sites];
    cluster_id = new int[x_sites*y_sites];
    large_cluster = new int[colored_clusters+1];
  }

  // 
  // randomize(p)
  //   Generates a random bond percolation lattice with bond 
  //   occupation probability p.  Avoids edge bonds.
  //
  void randomize() {
    int i, j, idx;
    Random r = new Random();

    // Randomize Central bonds
    for (i = 0; i<x_sites-1; i++)
      for (j = 0; j<y_sites-1; j++) {
	idx = i + j*x_sites;
        bondx[idx] = r.nextDouble();
        bondy[idx] = r.nextDouble();
      }
    // Randomize Bottom x-bonds 
    for (i = 0, j = y_sites-1; i<x_sites-1; i++) {
      idx = i + j*x_sites;
      bondx[idx] = r.nextDouble();
      bondy[idx] = 2.0;  // Bond is cut
    }
    // Randomize Right y-bonds
    for (j = 0, i = x_sites-1; j<y_sites-1; j++) {
      idx = i + j*x_sites;
      bondy[idx] = r.nextDouble();
      bondx[idx] = 2.0;  // Bond is cut
    }
    // Last site has no bonds
    idx = x_sites-1 + (y_sites-1)*x_sites;
    bondx[idx] = 2.0;  // Bond is cut
    bondy[idx] = 2.0;  // Bond is cut

    label();  // Label clusters after finish
  }

  //
  // label()
  //   labels sites by which cluster they reside in.
  //   0 = largest cluster, 1 = next largest, etc.
  //   First time through, labeling is arbitrary.
  //   Later results get ordered.
  //
  void label() {
    int lattice_size = x_sites*y_sites;
    int j, k, temp, hold, label, new_label;
    int remap[], size[];
    int new_size, clusters;

    remap = new int[lattice_size];  // cluster label remap permutation
    size  = new int[lattice_size];  // cluster sizes (by label)

    for (k=lattice_size-1; k>=0; k--)
      cluster_id[k] = -1;  // Initially all sites unlabeled

    new_label = 0;
    for (k=0; k<lattice_size; k++) {
      // If not labeled yet, start a new cluster
      if (cluster_id[k] < 0) {
	remap[new_label] = new_label;
	cluster_id[k] = new_label++;
      }
      label = cluster_id[k];  // Extract label for this site
      size[label] += 1;       // Increment cluster's size

      // Label adjacent sites if connected
      if (bondx[k] < p)
	label_site(label, k+1, remap);
      if (bondy[k] < p)
	label_site(label, k+x_sites, remap);
    }

    // Convert remap from a permutation to a direct map
    for (k=0, clusters = 0; k<new_label; k++) {
      // If remap[k] points to a cluster label k or greater,
      // it is the anchor (smallest index) of a yet to be visited
      // remap cycle.  Have all elements of this cycle point instead to k.
      if (remap[k] >= k) {
	clusters += 1;    // Update number of clusters
	temp = k;         // Start with kth cluster
	new_size = 0;
	do {
	  new_size += size[temp]; // Add this cluster to k'th cluster size
	  size[temp] = 0;         // Zero size of this cluster to remove it
	  hold = remap[temp];     // Grab next cluster in remap
	  remap[temp] = k;        // Convert from cycle to direct map to k
	  temp = hold;            // Go to next cluster
	} while (temp != k);
	size[k] = new_size;
      }
    }

    // Relabel sites according to remap
    for (k=0; k<lattice_size; k++)
      cluster_id[k] = remap[cluster_id[k]];

    // Find the first few large clusters
    for (k=1; k<colored_clusters; k++)
      large_cluster[k] = -1;
    int number_of_big_clusters = 1;
    large_cluster[0] = 0;
    int smallest_big_cluster_size = 0;

    for (k=1; k<new_label; k++)
      if (size[k] > smallest_big_cluster_size) {
	// Add this cluster to list (in correct order)
	for (j=number_of_big_clusters-1; j>=0; j--)
	  if (size[k] > size[large_cluster[j]]) {
	    large_cluster[j+1] = large_cluster[j];
	    if (j==0) large_cluster[0] = k;
	  } else {
	    large_cluster[j+1] = k;
	    j = -1;
	  }
	if (number_of_big_clusters < colored_clusters)
	  number_of_big_clusters++;
	else
	  smallest_big_cluster_size = 
	    size[large_cluster[number_of_big_clusters-1]];
      }
  }
      
  void label_site(int label, int k, int remap[]) {
    int temp, old_label = cluster_id[k];
    boolean needs_remap;

    if (old_label < 0) cluster_id[k] = label;
    else {
      // Cycle through remap to see if this labeling error
      // has already been caught?
      temp = label;
      needs_remap = true;
      do {
	if (temp == old_label) needs_remap = false;
	temp = remap[temp];
      } while ((temp != label) && needs_remap);

      // If not caught, add this to the remap cycle.
      if (needs_remap) {
	temp = remap[label];
	remap[label] = remap[old_label];
	remap[old_label] = temp;
      }
    }
  }
}

//
// LatticePanel class
//   contains the LatticeCanvas and the scrollbar
//
class LatticePanel extends Panel {
  Scrollbar pbar;
  LatticeCanvas lc;
  int pbar_value;

  LatticePanel(BondLattice lattice, int x, int y) {
    setLayout(new BorderLayout());

    lc = new LatticeCanvas(lattice, (int)(0.95*x), (int)(0.95*y));
    add("Center", lc);

    pbar_value = (int)(lc.lattice.p*100);
    pbar = new Scrollbar(Scrollbar.HORIZONTAL);
    pbar.setValues(pbar_value, 10, 0, 110);
    add("South", pbar);
  }

  public boolean handleEvent(Event e) {
    if (e.target == pbar) {
      switch(e.id) {
      case Event.SCROLL_LINE_UP:
      case Event.SCROLL_LINE_DOWN:
      case Event.SCROLL_PAGE_UP:
      case Event.SCROLL_PAGE_DOWN:
      case Event.SCROLL_ABSOLUTE:
	pbar_value = ((Integer)e.arg).intValue();
	lc.lattice.p = (double)pbar_value/100.0;
        lc.lattice.label();
	lc.draw(lc.offscreen.getGraphics(),0,lc.x,0,lc.y);
	lc.paint(lc.getGraphics());
	break;
      }
    }
    return super.handleEvent(e);
  }
}

//
// LatticeCanvas class
//   contains the lattice and its offscreen bitmap.
//
class LatticeCanvas extends Canvas {
  BondLattice lattice;   // Bond Lattice for this Canvas
  int x, y;              // x, y dimensions of Canvas
  Image offscreen;       // Offscreen bitmap (makes drawing smoother)
  
  LatticeCanvas(BondLattice lattice, int x, int y) {
    this.lattice = lattice;
    this.x = x;
    this.y = y;
    resize(x,y);
  }
  
  //
  // addNotify()
  //   createImage() can't be called until the component exists!
  //   addNotify creates the component, so this method overloading
  //   neatly solves the problem by postponing createImage() until
  //   super.addNotify() is completed.
  //
  public void addNotify() {
    super.addNotify();
    offscreen = createImage(size().height, size().width);
  }

  //
  // mouseDown event
  //
  public boolean mouseDown(Event e, int xx, int yy) {
    lattice.randomize();
    draw(offscreen.getGraphics(),0,x,0,y);
    paint(getGraphics());
    return true;
  }

  //
  // draw(g)
  //   Draw the percolation lattice onto graphics object g.
  //
  void draw(Graphics g, int x_min, int x_max, int y_min, int y_max) {
    int x, y, i, j;
    int delta_x = (x_max-x_min)/lattice.x_sites;
    int delta_y = (y_max-y_min)/lattice.y_sites;

    // Clear the region before drawing
    g.clearRect(x_min, y_min, x_max, y_max);

    // Draw the bonds which are filled
    for (x = x_min+delta_x/2, i = 0; i<lattice.x_sites; x += delta_x, i++) {
      for (y = y_min+delta_y/2, j = 0; j<lattice.y_sites; y += delta_y, j++) {
	g.setColor(localColor(i+j*lattice.x_sites));
	if (lattice.bondx[i+j*lattice.x_sites] < lattice.p)
	  g.fillRect(x, y-delta_y/8, delta_x, delta_y/4);
	if (lattice.bondy[i+j*lattice.x_sites] < lattice.p)
	  g.fillRect(x-delta_x/8, y, delta_x/4, delta_y);
      }
    }

    // Draw all the sites
    for (x = x_min+delta_x/2, i = 0; i<lattice.x_sites; x += delta_x, i++) {
      for (y = y_min+delta_y/2, j = 0; j<lattice.y_sites; y += delta_y, j++) {
	g.setColor(localColor(i+j*lattice.x_sites));
	g.fillOval(x-delta_x/4, y-delta_y/4, delta_x/2, delta_x/2);
      }
    }
  }

  //
  // Color localColor(int Site)
  //   select Color for cluster based on size
  //
  Color localColor(int site) {
    Color c = new Color(0,0,0);
    int k;

    // Choose color of site based on size of cluster
    for (k=0; k<lattice.colored_clusters; k++)
      if (lattice.cluster_id[site] == lattice.large_cluster[k])
	return c.getHSBColor((0.80f*k)/lattice.colored_clusters, 1.0f, 1.0f);
    // default color for all the small clusters
    return c.getHSBColor(0.80f, 1.0f, 1.0f);
  }

  //
  // update(g)
  //   overide Canvas update.
  //
  public void update(Graphics g) {
    paint(g);
  }

  //
  // paint(g)
  //   overide usual paint method.
  //
  public void paint(Graphics g) {
    g.drawImage(offscreen,0,0,this);
  }
}

//
// Applet PercolationApplet
//   This is the main code.
//
public class PercolationApplet extends Applet {
  int x_sites = 24, y_sites = 24;
  LatticePanel p1, p2, p3, p4;
  BondLattice lattice1, lattice2, lattice3, lattice4;

  //
  // Initialization stage
  //
  public void init() {
    lattice1 = new BondLattice(0.35, x_sites, y_sites);
    lattice2 = new BondLattice(0.45, x_sites, y_sites);
    lattice3 = new BondLattice(0.55, x_sites, y_sites);
    lattice4 = new BondLattice(0.65, x_sites, y_sites);
    
    setLayout(new GridLayout(2,2));
    int width  = Integer.parseInt(getParameter("width"));
    int height = Integer.parseInt(getParameter("height"));
    add(p1 = new LatticePanel(lattice1, width/2, height/2));
    add(p2 = new LatticePanel(lattice2, width/2, height/2));
    add(p3 = new LatticePanel(lattice3, width/2, height/2));
    add(p4 = new LatticePanel(lattice4, width/2, height/2));
  }
}