package gve.calc.graph;

import java.awt.*;
import java.awt.event.*;
import gve.calc.formula.*;

 Should be called FinitePointGraph or something (finite # of points having 2D plane coords) 
public class Graph extends Part {
	public static final int VERTEXDIAM = 10;
	private int size;	// aantal toppen
	private boolean[][] adjacent;	// adjacent[i][j]=true -> er loopt een pijl van i naar j
	private boolean directed = true;
	private int []xcoord;
	private int []ycoord;

	public Graph() {
		this(0);
	}

	public Graph(int siz) {
		size = siz;
		adjacent = new boolean[siz][siz];
		xcoord = new int[size];
		ycoord = new int[size];
		// generate standard coords
		double twopin = Math.PI * 2.0 / (double)size;
		int width = 100, height = 100;
		for (int i = size-1; i>=0; i--) {
			xcoord[i] = (int)(width/2 + (width/2-Graph.VERTEXDIAM)*Math.cos(i*twopin));
			ycoord[i] = (int)(height/2 + (height/2-Graph.VERTEXDIAM)*Math.sin(i*twopin));
		}
	}

	public Graph(int siz,boolean dir) {
		this(siz);
		directed = dir;
	}

	public int getXcoord(int i) { return xcoord[i]; }
	public int getYcoord(int i) { return ycoord[i]; }

	public void setXcoord(int i,int coord) {
		xcoord[i] = coord;
		MVC.changed(this);
	}

	public void setYcoord(int i,int coord) {
		ycoord[i] = coord;
		MVC.changed(this);
	}

	public Object clone() {
		Graph result = new Graph(size,directed);
		for (int i = 0; i < size; i++)
			for (int j = 0; j < size; j++)
				result.adjacent[i][j] = adjacent[i][j];
		result.xcoord = new int[size];
		result.ycoord = new int[size];
		System.arraycopy(xcoord,0,result.xcoord,0,size);
		System.arraycopy(ycoord,0,result.ycoord,0,size);
		return result;
	}
	
	public int getSize() { return size; }

	
 Returns a reason why these are (not) isomorph
	  in "why". If the graphs are isomorph, the result is
	  an array of ints describing the mapping of this->g,
	  else it can be either null or a String. 
	public boolean isIsomorph(Graph g,ObjectObject why) {
		if (size != g.getSize()) {
			if (why != null)
				why.obj = "Graphs have different number of vertices";
			return false;
		}
		if (directed != g.directed) {
			if (why != null)
				why.obj = "One graph is directed, the other undirected";
			return false;
		}
		// Bepaal valenties
		int [] in1 = new int[size];
		int [] uit1 = null;
		int [] in2 = new int[size];
		int [] uit2 = null;
		if (directed) {
			uit1 = new int[size];
			uit2 = new int[size];
		}
		for (int i = 0; i < size; i++) {
			in1[i] = ingraad(i);
			in2[i] = g.ingraad(i);
			if (directed) {
				uit1[i] = uitgraad(i);
				uit2[i] = g.uitgraad(i);
			}
		}
		// Test of het aantal punten van een bepaalde valentie gelijk is
		{	int val = testvalentie(in1,in2);
			if (val >= 0) {
printarr(in1);
printarr(in2);
				if (why != null)
					why.obj = "Graphs have a different number of vertices with "
						+ (directed ? "in-" : "") + "degree "+val;
				return false;
			}
			if (directed) {
				val = testvalentie(uit1,uit2);
				if (val >= 0) {
printarr(uit1);
printarr(uit2);
					if (why != null)
						why.obj = "Graphs have a different number of vertices with out-degree "+val;
					return false;
				}
			}
		}
		// probeer een isomorfisme te maken
		int [] map = new int[size];
		// top i in deze graaf       <-> top map[i] in graaf g
		// -1 duidt aan dat de top nog niet gemapt is
		for (int i = size-1; i >=0; i--)
			map[i] = -1;
		boolean result;
		result = voegpunttoe(g,map,in1,in2,uit1,uit2,size);
		if (result) {
			if (why != null)
				why.obj = map;	// return found morphism
		} else {
			if (why != null) why.obj = null;
		}
		return result;
	}

	
 debug functie 
	private void printarr(int [] arr) {
		System.out.print("[");
		for (int i = 0; i < arr.length; i++) {
			System.out.print(" ");
			System.out.print(arr[i]);
		}
		System.out.println(" ]");
	}

	
 Probeer ``toetevoegen'' toppen aan de mapping toe te voegen
	  geeft true terug als het gelukt is, anders false 
	private boolean voegpunttoe(Graph g,int []map,int []in1,int []in2,int []uit1,int []uit2,int toetevoegen) {
		// Zoek een nog niet gemapte top i uit de eerste graaf
		for (int i = 0; i < size; i++) {
			if (map[i] >= 0) continue;	// al gemapt
			// Zoek een nog niet gemapte top j uit de tweede graaf
			// met zelfde valentie als top i
			for (int j = 0; j < size; j++) {
				// zelfde valentie?
				if (directed) {
					if (in1[i]!=in2[j] || uit1[i]!=uit2[j]) continue;
				} else {
					if (in1[i]!=in2[j]) continue;
				}
				// top j al gemapt?
				{	int k;
					for (k = 0; k < size; k++)
						if (map[k] == j) break;
					if (k != size) continue;	// al gemapt	
				}
				// Mag ``i <-> j'' bij de mapping?
				int k;
				for (k = 0; k < size; k++) {
					if (map[k] < 0) continue;
					// als adjacent[i][k] dan moet ook
					// g.isAdjacent(map[i],map[k])
					if (adjacent[i][k] != g.isAdjacent(j,map[k]))
						break;	// mag niet bij de mapping!
					if (adjacent[k][i] != g.isAdjacent(map[k],j))
						break;
				}
				if (k == size) {	// breid mapping uit
					map[i] = j;
					if (toetevoegen == 1) return true;	// iso gevonden!
					// Recursief doordoen
					if (voegpunttoe(g,map,in1,in2,uit1,uit2,toetevoegen-1))
						return true;
					else	// kan deze mapping niet vervolledigen
						map[i] = -1;	// backtrack
				}
				// zoek een andere top j
			}
			// zoek een andere top i
		}
		// Geen punten gevonden die in aanmerking kwamen
		return false;
	}

	
 a en b zijn matrices met de valentie van de toppen van beide grafen
	  Er wordt getest of er een bijectie tussen a[] en b[] mogelijk is
	  Resultaat is <0 als er een bijectie mogelijk is
	  Resultaat is >=0 geeft aan dat het aantal elementen met waarde
	 	`resultaat' in beide arrays verschillend is 
	private int testvalentie(int [] a,int [] b) {
		for (int i = 0; i < size; i++) {
			int valentie = a[i];	// de valentie waarop we testen
			// Hebben we al het aantal toppen met valentie a[i] geteld?
			{	int j;
				for (j = 0; j < i; j++)
					if (valentie == a[j]) break;	// al gedaan
				if (i != j) continue;	// al gedaan
			}
			int aantA = 1,aantB = 0;
			for (int j = i+1; j < size; j++)
				if (a[j] == valentie) aantA++;
			for (int j = 0; j < size; j++)
				if (b[j] == valentie) aantB++;
			if (aantA != aantB) return valentie;
		}
		return -1;
	}

	
 Take complement of this graph 
	public void complement() {
		for (int i = size-1; i>=0; i--)
			for (int j = size-1; j>=0; j--)
				adjacent[i][j] = !adjacent[i][j];
		MVC.changed(this);
	}

	
 Aantal pijlen die vanuit idx vertrekken 
	public int ingraad(int idx) {
		int graad = 0;
		for (int i = 0; i < size; i++) {
			if (adjacent[idx][i]) graad++;
		}
		return graad;
	}

	
 Aantal pijlen die in idx toekomen 
	public int uitgraad(int idx) {
		int graad = 0;
		for (int i = 0; i < size; i++) {
			if (adjacent[i][idx]) graad++;
		}
		return graad;
	}

	public boolean isDirected() { return directed; }

	public void setDirected(boolean dir) {
		if (directed && !dir) {	// maak van een gerichte een ongerichte graaf
			// alle richtingsinfo gaat verloren
			for (int i = 0; i < size; i++)
				for (int j = 0; j < size; j++)
					adjacent[i][j] = adjacent[j][i] = adjacent[i][j] || adjacent[j][i];
		}
		directed = dir;
		MVC.changed(this);
	}

	
 Make room for capacity extra vertices. New vertex
	  has the highest index. 
	public void enlarge(int capacity) {
		if (capacity < 0) throw new IllegalArgumentException(capacity+"<0");
		if (capacity == 0) return;
		{	int [] n = new int[size+capacity];
			System.arraycopy(xcoord,0,n,0,xcoord.length);
			xcoord = n;
			n = new int[size+capacity];
			System.arraycopy(ycoord,0,n,0,ycoord.length);
			ycoord = n;
		}
		boolean[][] newadj = new boolean[size+capacity][size+capacity];
		// PENDING: use System.arrayCopy() here
		for (int i = 0; i < size; i++)
			for (int j = 0; j < size; j++)
				newadj[i][j] = adjacent[i][j];
		adjacent = newadj;
		size += capacity;
		MVC.changed(this);
	}

	public void removeVertex(int idx) {
		{	int [] n = new int[size-1];
			System.arraycopy(xcoord,0,n,0,idx);
			System.arraycopy(xcoord,idx+1,n,idx,size-idx-1);
			xcoord = n;
			n = new int[size-1];
			System.arraycopy(ycoord,0,n,0,idx);
			System.arraycopy(ycoord,idx+1,n,idx,size-idx-1);
			ycoord = n;
		}
		size--;
		boolean[][] newadj = new boolean[size-1][size-1];
		for (int i = 0; i < size; i++)
			for (int j = 0; j < size; j++)
				newadj[i][j] = adjacent[i>=idx ? i+1 : i][j>=idx ? j+1 : j];
		adjacent = newadj;
		MVC.changed(this);
	}

	public boolean isAdjacent(int i,int j) {
		return adjacent[i][j];
	}

	public void setAdjacent(int i,int j,boolean adj) {
		adjacent[i][j] = adj;
		if (!directed) adjacent[j][i] = adj;
		MVC.changed(this);
	}

	
 returns -1 if no vertex is close enough 
	public int vertexAt(int x,int y) {
		int dichtst = Integer.MAX_VALUE;
		int result = -1;
		for (int i = size-1; i>=0; i--) {
			int vx = xcoord[i], vy=ycoord[i];
			int afst2 = (x-vx)*(x-vx) + (y-vy)*(y-vy);
			if (afst2 > 5*5) continue;	// te ver
			if (afst2 < dichtst) {
				dichtst = afst2;
				result = i;
			}
		}
		return result;
	}

	public Part evaluate(Evaluator ev) {
		return (Part)clone();
	}

	public Component createView(FormulaView view) {
		return new GraphView(this);
	}
}