import java.io.*;

public abstract class TableRepresentation implements java.io.Serializable, java.lang.Cloneable
{
	protected int size = 0;
	public Relation[][] cell;
	public String[] label;
	protected boolean consistent = true;
		
	public int getSize()
	{
		return size;
	}
	
	public boolean isConsistent()
	{
		return consistent;
	}
	
    public Object clone() throws CloneNotSupportedException
    {
        // This method is derived from class java.lang.Object
		TableRepresentation t = (TableRepresentation)super.clone();
		t.cell = (Relation[][])cell.clone();
		for (int i = 0; i < size; i++)
		{
			t.cell[i] = (Relation[])cell[i].clone();
			for (int j = 0; j < size; j++)
				t.cell[j][i] = (Relation)cell[j][i].clone();
		}
		t.label = (String[])label.clone();
        return t;
    }
    
    public boolean equals(TableRepresentation t)
    {
        // This method is derived from class java.lang.Object
		for (int i = 0; i < size; i++)
		{
			for (int j = 0; j < size; j++)
			{
				if (t.cell[i][j] != cell[i][j])
					return false;
			}
			if (t.label[i] != label[i])
				return false;
		}
        return true;
    }

    public String toString()
    {
        // This method is derived from class java.lang.Object
        StringBuffer sb = new StringBuffer();
        
        for (int i = 0; i < size; i++)
        {
        	if (i > 0) sb.append(", ");
        	sb.append(label[i]);
        }
        sb.append(": ");
        sb.append('[');
        for (int i = 0; i < size; i++)
        	for (int j = i+1; j < size; j++)
        	{
        		if (j > 1) sb.append(", ");
        		sb.append(cell[i][j].toString());
        	}
        sb.append(']');
        return sb.toString();
    }

	protected String makeLabel(int n)
	{
		StringBuffer sb = new StringBuffer();

		while (true)
		{
			sb.insert(0, (char)('a' + n % 26));
			if (n >= 26) n = (n - 26) / 26;
			else break;
		}
		return sb.toString();
	}

	public void swap(int x, int y)
	{
		// Algorithm 14
		Relation r;
		String s;
		for (int n = 0; n < size; n++) //1, 2, 2.2
		{
			r = cell[x][n];	//2.1
			cell[x][n] = cell[y][n];
			cell[y][n] = r;
		}
		for (int n = 0; n < size; n++) //3, 4, 4.2
		{
			r = cell[n][x];	//4.1
			cell[n][x] = cell[n][y];
			cell[n][y] = r;
		}
		s = label[x];
		label[x] = label[y];
		label[y] = s;
	}
	
	public void move(int x, int y)
	{
		// Algorithm 15
		int n = size; //1
		Relation[] copy = new Relation[n]; //2
		String s;
		
		if (x < y) //3
		{
			for (int i = 0; i < n; i++) //3.1
				copy[i] = cell[x][i];
			s = label[x];
			for (int z = x + 1; z < y; z++) //3.2
			{
				for (int i = 0; i < n; i++) //3.2.1
					cell[z-1][i] = cell[z][i];
				label[z-1] = label[z];
			}
			for (int i = 0; i < n; i++) //3.3
				cell[y-1][i] = copy[i];
			label[y-1] = s;
			for (int i = 0; i < n; i++) //3.4
				copy[i] = cell[i][x];
			for (int z = x + 1; z < y; z++) //3.5
				for (int i = 0; i < n; i++) //3.5.1
					cell[i][z-1] = cell[i][z];
			for (int i = 0; i < n; i++) //3.6
				cell[i][y-1] = copy[i];
		}
		if (y < x) //4
		{
			for (int i = 0; i < n; i++) //4.1
				copy[i] = cell[x][i];
			s = label[x];
			for (int z = x - 1; z >= y; z--) //4.2
			{
				for (int i = 0; i < n; i++) //4.2.1
					cell[z+1][i] = cell[z][i];
				label[z+1] = label[z];
			}
			for (int i = 0; i < n; i++) //4.3
				cell[y][i] = copy[i];
			label[y] = s;
			for (int i = 0; i < n; i++) //4.4
				copy[i] = cell[i][x];
			for (int z = x - 1; z >= y; z--) //4.5
				for (int i = 0; i < n; i++) //4.5.1
					cell[i][z+1] = cell[i][z];
			for (int i = 0; i < n; i++) //4.6
				cell[i][y] = copy[i];
		}
	}
	
	protected class TableList
	{
		public TableRepresentation table;
		public TableList next;
		
		TableList()
		{
		}
		
		TableList(TableRepresentation t)
		{
			table = t;
		}
		
		public void add(TableRepresentation t)
		{
			if (table == null)
				table = t;
			else if (next == null)
				next = new TableList(t);
			else
				next.add(t);
		}
	}
	
	public void normalise()
	{
		//Algorithm 16
		TableList candidates = new TableList(); //1
		short min = Short.MAX_VALUE; //2 
			// arbitrary large value in place of number of relations + 1
		Relation c;
		TableRepresentation t;
		for (int i = 0; i < size; i++) //3
			for (int j = 0; j < size; j++)
				if (i != j)
				{
					c = cell[i][j];
					if (c.getData() < min) //3.1
					{
						TableRepresentation copy;
						try
						{
							copy = 
								(TableRepresentation)this.clone();
						}
						catch (CloneNotSupportedException e)
						{
							throw new RuntimeException(
								"Unexpected CloneNotSupportedException: " +
								this);
						}
						copy.swap(i, 0);
						copy.swap(j, 1);
						candidates = new TableList(copy);
						min = c.getData();
					}
					else if (c.getData() == min) //3.2
					{
						TableRepresentation copy;
						try
						{
							copy = 
								(TableRepresentation)this.clone();
						}
						catch (CloneNotSupportedException e)
						{
							throw new RuntimeException(
								"Unexpected CloneNotSupportedException: " +
								this);
						}
						copy.swap(i, 0);
						copy.swap(j, 1);
						candidates.add(copy);
					}
				}
		TableList candidates2; //4
		for (int j = 2; j < size; j++) //5
		{
			min = Short.MAX_VALUE; //5.1
			candidates2 = new TableList(); //5.2
			TableList tl = candidates;
			while (tl != null) //5.3
			{
				t = tl.table;
				for (int j2 = j; j2 < size; j2++) //5.3.1
				{
					Relation c2 = t.cell[0][j2];
					if (c2.getData() < min) //5.3.1.1
					{
						TableRepresentation copy;
						try
						{
							copy = 
								(TableRepresentation)t.clone();
						}
						catch (CloneNotSupportedException e)
						{
							throw new RuntimeException(
								"Unexpected CloneNotSupportedException: " +
								t);
						}
						copy.swap(j2, j);
						candidates2 = new TableList(copy);
						min = c2.getData();
					}
					else if (c2.getData() == min) //5.3.1.2
					{
						TableRepresentation copy;
						try
						{
							copy = 
								(TableRepresentation)t.clone();
						}
						catch (CloneNotSupportedException e)
						{
							throw new RuntimeException(
								"Unexpected CloneNotSupportedException: " +
								t);
						}
						copy.swap(j2, j);
						candidates2.add(copy);
					}
				}
				tl = tl.next;
			}
			candidates = candidates2; //5.4
		}
		for (int i = 1; candidates.next != null && i < size; i++) //6
			for (int j = i + 1; candidates.next != null && j < size; j++)
			{
				min = Short.MAX_VALUE; //6.1
				TableList tl = candidates;
				while (tl != null) //6.2
				{
					t = tl.table;
					c = t.cell[i][j];
					if (c.getData() < min) //6.3
					{
						candidates = tl;
						min = c.getData();
					}
					if (c.getData() > min) //6.4
					{
						TableList tl2 = candidates;
						while (tl2.next != tl)
							tl2 = tl2.next;
						tl2.next = tl.next;
					}
					tl = tl.next;
				}
			}
		t = candidates.table; //7
		for (int i = 0; i < size; i++)
		{
			label[i] = t.label[i];
			for (int j = 0; j < size; j++)
				cell[i][j] = t.cell[i][j];
		}
	}
	
	public void propagate(int i, int j) throws ConsistencyException
	{
		//Algorithm 19
		CellSet toBeChecked = new CellSet(); //1
		toBeChecked.add(i, j);
		while (!toBeChecked.empty()) //2
		{
			CellSetMember c1 = toBeChecked.remove(); //2.1
			int x = c1.x; //2.2
			int y = c1.y; //2.3
			Relation r1 = cell[x][y]; //2.4
			for (int z = 0; z < size; z ++) //2.5, 2.5.1
				if (z != x && z != y)
				{
					Relation r2 = cell[x][z]; //2.5.2
					Relation r3 = cell[y][z]; //2.5.3
					Relation r2a = r2.intersection(r1.transition(r3)); //2.5.5
					if (r2a.isNull())
					{
						consistent = false;
						throw new ConsistencyException(
							"Inconsistency found at: " 
							+ x + " " + y + " " + z);
					}
					if (!r2a.equals(r2)) //2.5.6
					{
						try
						{
							cell[x][z] = r2a; //2.5.6.1
							cell[z][x] = r2a.inverse(); //2.5.6.2
						}
						catch (ArrayStoreException e)
							//transitions on symbolic period relations
							//might not be symbolic period relations
						{
							throw new TypeConsistencyException(
								"Relation type inconsistency found at: "
								+ x + " " + y + " " + z);
						}
						toBeChecked.add(x, z); //2.5.6.3
					}
					else //2.5.7
					{
						Relation r3a = r3.intersection((r1.inverse())
							.transition(r2)); //2.5.7.1
						if (r3a.isNull())
						{
							consistent = false;
							throw new ConsistencyException(
								"Inconsistency found at: " 
								+ x + " " + y + " " + z);
						}
						if (!r3a.equals(r3)) //2.5.7.2
						{
							try
							{
								cell[y][z] = r3a; //2.5.7.2.1
								cell[z][y] = r3a.inverse(); //2.5.7.2.2
							}
							catch (ArrayStoreException e)
								//transitions on symbolic period relations
								//might not be symbolic period relations
							{
								throw new TypeConsistencyException(
									"Relation type inconsistency found at: "
									+ x + " " + y + " " + z);
							}
							toBeChecked.add(y, z); //2.5.7.2.3
						}
					}
				}
		}
	}
	
	protected class CellSet
	{
		private CellSetMember first;
				
		public boolean empty()
		{
			return(first == null);
		}
		
		public void add(int x, int y)
		{			
			if (first == null || x <= first.x && y <= first.y)
			{
				first = new CellSetMember(x, y, first);
				return;
			}
			
			CellSetMember c = first;
			while (c.next != null && c.next.x <= x && c.next.y < y)
				c = c.next;
			c.next = new CellSetMember(x, y, c.next);
		}
		
		public CellSetMember remove()
		{
			CellSetMember c = first;
			if (first != null)
				first = first.next;
			return c;
		}
	}
	
	protected class CellSetMember
	{
		public int x;
		public int y;
		public CellSetMember next;
		
		CellSetMember(int i, int j, CellSetMember n)
		{
			x = i;
			y = j;
			next = n;
		}
	}
	
	public void determinatePropagate(int x, int y)
	{
		//Algorithm 20
		Relation r = cell[x][y]; //3
		Relation ri = cell[y][x]; //4
		for (int a = 0; a < size; a ++) //5, 5.1
			for (int b = a + 1; b < size; b++) //5.2
			{
				if (a != b)
				{
					Relation rc;
					Relation r1 = cell[a][b]; //5.3
						//special cases not in book but required here because
						//tables have nulls on the diagonal rather than
						//relations of equality
					if (a == x)
					{ 
						if (b == y) rc = r1;
						else
							rc = r1.intersection(r.transition(cell[y][b]));
					}
					else if (b == x)
					{
						if (a == y) rc = r1;
						else
							rc = r1.intersection(cell[a][y].transition(ri));
					}
					else if (a == y)
						rc = r1.intersection(ri.transition(cell[x][b]));
					else if (b == y)
						rc = r1.intersection(cell[a][x].transition(r));
					else
					{
						Relation rax = cell[a][x]; //5.4
						Relation ryb = cell[y][b]; //5.5
						Relation ray = cell[a][y]; //5.6
						Relation rxb = cell[x][b]; //5.7
						rc = r1.intersection(r.propagate(rax, ryb).
							intersection(ri.propagate(ray, rxb))); //5.8
					}
					cell[a][b] = rc;
					cell[b][a] = rc.inverse();
				}
			}
	}
}