public class  EventTableRepresentation extends TableRepresentation
{
	EventTableRepresentation(int n)
	{
		size = n;
		cell = new EventRelation[size][size];
		label = new String[size];
		try
		{
			for (int i = 0; i < size; i++)
			{
				for (int j = 0; j < size; j++)
					cell[i][j] = new EventRelation(
						(i == j ? 0 : EventRelation.ANY));
				label[i] = makeLabel(i);
			}
		}
		catch (FormatException e)
		{
			throw new RuntimeException("Unexpected FormatException: " +
				EventRelation.ANY);
		}
	}
	
	public void partialNormalise()
	{
		//Algorithm 17
		EventTableRepresentation t1;
		int n = size; //1
		int count1[] = new int[n]; //2
		int order[] = new int[n];
			//It would be more efficient to have an inner class which was
			//a pair of integers for count1 and order, and to use and sort a
			//single array of these pairs, but this has not been followed so
			//so as to keep closer to the algorithm as described in the book.
		for (int i = 0; i < n; i++) //3
		{
			count1[i] = 0;
			for (int j = 0; j < n; j++) //3.1
				if (cell[i][j].data == EventRelation.L) count1[i]++;
			order[i] = i; //3.2
		}
		pSort(count1, order); //4
		try
		{
			t1 = (EventTableRepresentation)this.clone(); //5
		}
		catch (CloneNotSupportedException e)
		{
			throw new RuntimeException(
				"Unexpected CloneNotSupportedException: " + e);
		}
		for (int x = 0; x < size; x++) //6, 6.1
		{
			t1.label[x] = label[order[x]];
			for (int y = 0; y < size; y++) //6.2
			{
				t1.cell[x][y] = cell[order[x]][order[y]]; //6.3
			}
		}
		for (int i = 0; i < size; i++)
		{
			label[i] = t1.label[i];
			for (int j = 0; j < size; j++)
				cell[i][j] = t1.cell[i][j];
		}
	}
	
	public void fullNormalise()
	{
		//Algorithm 18
		EventTableRepresentation t1;
		int n = size; //1
		int count1[] = new int[n];
		int order[] = new int[n];
			//It would be more efficient to have an inner class which was
			//a pair of integers for count1 and order, and to use and sort a
			//single array of these pairs, but this has not been followed so
			//so as to keep closer to the algorithm as described in the book.
		for (int i = 0; i < n; i++)
		{
			count1[i] = 0;
			for (int j = 0; j < n; j++)
				if (cell[i][j].data == EventRelation.L) count1[i]++;
			order[i] = i;
		}
		pSort(count1, order);
		
		int[][] count2 = new int[n][n]; //2
		for (int i = 0; i < n; i++) //3
		{
			for (int j = 0; j < n; j++)
				count2[j][i] = 0;
			int m = count1[0]; //3.1
			int k = 0; //3.2
			for (int j = 0; j < n; j++) //3.3
			{
				if (count1[j] < m) //3.3.1
				{
					m = count1[j]; //3.3.1.1
					k++; //3.3.1.2
				}
				if (i == j || cell[order[i]][order[j]].data == EventRelation.ANY) //3.3.2
					count2[i][k]++; //3.3.2.1
			}
		}
		fSort(count2, order); //4
		
		try
		{
			t1 = (EventTableRepresentation)this.clone(); //5
		}
		catch (CloneNotSupportedException e)
		{
			throw new RuntimeException(
				"Unexpected CloneNotSupportedException: " + e);
		}
		for (int x = 0; x < size; x++) //6, 6.1
		{
			t1.label[x] = label[order[x]];
			for (int y = 0; y < size; y++) //6.2
			{
				t1.cell[x][y] = cell[order[x]][order[y]]; //6.3
			}
		}
		for (int i = 0; i < size; i++)
		{
			label[i] = t1.label[i];
			for (int j = 0; j < size; j++)
				cell[i][j] = t1.cell[i][j];
		}
	}
	
	//Sorting algorithms are C.A.R. Hoare's quick sort with median-of-three
	//and insertion sort. Adapted from code at 
	//http://www.cs.ubc.ca/spider/harrison/Java/FastQSortAlgorithm.java
	//by James Gosling, Kevin A. Smith and Denis Ahrens.
	private void pSort(int[] a, int[]b)
	{
		pQuickSort(a, b, 0, a.length - 1);
		pInsertionSort(a, b, 0, a.length-1);
	}

	private void pQuickSort(int a[], int b[], int l, int r)
	{
		int M = 4;
		int i;
		int j;
		int v;

		if ((r-l)>M)
		{
			i = (r+l)/2;
			if (a[l]<a[i]) pSwap(a,b,l,i);	// Tri-Median Methode!
			if (a[l]<a[r]) pSwap(a,b,l,r);
			if (a[i]<a[r]) pSwap(a,b,i,r);

			j = r-1;
			pSwap(a,b,i,j);
			i = l;
			v = a[j];
			for(;;)
			{
				while(a[++i]>v);
				while(a[--j]<v);
				if (j<i) break;
				pSwap(a,b,i,j);
			}
			pSwap(a,b,i,r-1);
			pQuickSort(a,b,l,j);
			pQuickSort(a,b,i+1,r);
		}
	}

	private void pInsertionSort(int a[], int b[], int lo0, int hi0)
	{
		int i;
		int j;
		int v;
		int w;

		for (i=lo0+1;i<=hi0;i++)
		{
			v = a[i];
			w = b[i];
			j=i;
			while ((j>lo0) && (a[j-1]<v))
			{
				a[j] = a[j-1];
				b[j] = b[j-1];
				j--;
			}
			a[j] = v;
			b[j] = w;
	 	}
	}

	private void pSwap(int a[], int b[], int i, int j)
	{
		int T;
		T = a[i]; 
		a[i] = a[j];
		a[j] = T;
		T = b[i]; 
		b[i] = b[j];
		b[j] = T;
	}
	
	private void fSort(int[][] a, int[]b)
	{
		fQuickSort(a, b, 0, b.length - 1);
		fInsertionSort(a, b, 0, b.length-1);
	}

	private void fQuickSort(int a[][], int b[], int l, int r)
	{
		int M = 4;
		int i;
		int j;
		int[] v;

		if ((r-l)>M)
		{
			i = (r+l)/2;
			if (!fPrec(a[l], a[i])) fSwap(a,b,l,i);	// Tri-Median Methode!
			if (!fPrec(a[l], a[r])) fSwap(a,b,l,r);
			if (!fPrec(a[i], a[r])) fSwap(a,b,i,r);

			j = r-1;
			fSwap(a,b,i,j);
			i = l;
			v = a[j];
			for(;;)
			{
				while(fPrec(a[++i], v));
				while(!fPrec(a[--j], v));
				if (j<i) break;
				fSwap(a,b,i,j);
			}
			fSwap(a,b,i,r-1);
			fQuickSort(a,b,l,j);
			fQuickSort(a,b,i+1,r);
		}
	}

	private void fInsertionSort(int a[][], int b[], int lo0, int hi0)
	{
		int i;
		int j;
		int[] v;
		int w;

		for (i=lo0+1;i<=hi0;i++)
		{
			v = a[i];
			w = b[i];
			j=i;
			while ((j>lo0) && (!fPrec(a[j-1], v)))
			{
				a[j] = a[j-1];
				b[j] = b[j-1];
				j--;
			}
			a[j] = v;
			b[j] = w;
	 	}
	}

	private boolean fPrec(int[] a, int[] b)
	{
		for (int i = 0; i < a.length; i++)
		{
			if (a[i] > b[i]) return true;
			else if (a[i] < b[i]) return false;
		}
		return true;
	}

	private void fSwap(int a[][], int b[], int i, int j)
	{
		int[] T;
		T = a[i]; 
		a[i] = a[j];
		a[j] = T;
		int U;
		U = b[i]; 
		b[i] = b[j];
		b[j] = U;
	}
}