//! Looks for pairs of caterpillars that are uniquely defined by the induced betweenness (pi_5) triples

class TwoCaterpillars
	{
	int c1 = 0;
	int c2 = 0;
	
	public TwoCaterpillars(int a, int b)
		{
		c1 = a;
		c2 = b;
		}

	//! ...
	static public boolean match( int x, int y )
		{
		//!System.out.println("Calling match for:");
		//! FindbetweenGadget.dumpCaterpillar(x);
		//! FindbetweenGadget.dumpCaterpillar(y);
		

		boolean same = true;

		for(int s = 0; s< FindbetweenGadget.p[x].length; s++)
			{
			if( FindbetweenGadget.p[x][s] != FindbetweenGadget.p[y][s] )
				{
				same = false;
				break;
				}
			}

		int last = FindbetweenGadget.p[x].length - 1;

		
		
		if( !same )
		{
		same = true;
		for(int s = 0; s< FindbetweenGadget.p[x].length; s++)
			{
			//! System.out.println(FindbetweenGadget.p[x][s] + " vs "+ FindbetweenGadget.p[y][ last - s ]);
			if( FindbetweenGadget.p[x][s] != FindbetweenGadget.p[y][ last - s ] )
				{
				same = false;
				break;
				}
			}
		
		}
		
		//! System.out.println("Result of match: "+same);
		return( same );			
			
		}
		
	public boolean sameAs( TwoCaterpillars two )
		{
		if( match( c1, two.c1) && match( c2, two.c2) ) return true;

		if( match( c1, two.c2) && match( c2, two.c1) ) return true;
				
		return false;
		}
			
		
	public boolean containsTriplet( int a, int b, int c )
		{
		if( FindbetweenGadget.catContainsTrip( c1, a, b, c ) ) return true;
		if( FindbetweenGadget.catContainsTrip( c2, a, b, c ) ) return true;
		return false;	
		}

	public void dumpTriplets()
		{
		int t = FindbetweenGadget.taxa;
		for(int a=0; a<t; a++)
		for(int b=0; b<t; b++)
		for(int c=0; c<t; c++)
			{
			if( (a==b) || (b==c) || (a==c) ) continue;
			if( a > c ) continue;	//! Because a and c can be interchanged
			if( containsTriplet(a,b,c) )
				{
				System.out.println(a+" "+b+" "+c);
				}
			}
		
		}

	public void dumpTripletsMiniZinc()
		{
		int t = FindbetweenGadget.taxa;
		int count = 0;
		for(int a=0; a<t; a++)
		for(int b=0; b<t; b++)
		for(int c=0; c<t; c++)
			{
			if( (a==b) || (b==c) || (a==c) ) continue;
			if( a > c ) continue;
			if( containsTriplet(a,b,c) )
				{
				System.out.println(a+","+b+","+c+",");
				count++;
				}
			}

		System.out.println("int: numtrips = "+count);
		}

		
	public boolean satisfiedBy( TwoCaterpillars two )
		{
		int t = FindbetweenGadget.taxa;
		for(int a=0; a<t; a++)
		for(int b=0; b<t; b++)
		for(int c=0; c<t; c++)
			{
			if( (a==b) || (b==c) || (a==c) ) continue;
			if( a > c ) continue;
			if( containsTriplet(a,b,c) )
					{
					if(FindbetweenGadget.DEBUG) System.out.println("Comparing: "+a+" "+b+" "+c);
					if( two.containsTriplet(a,b,c) == false)
						{
						if(FindbetweenGadget.DEBUG) System.out.println("Not in!");
						return false;
						}
					}
			}
		return true;			
		}

	}
		


public class FindbetweenGadget
{
public static void dumpCaterpillar(int catNum)
	{
	for( int x=0; x<p[catNum].length; x++)
		{
		System.out.print(p[catNum][x]);
		}
	System.out.println();
	}

//! checks whether b is not in the middle...
public static boolean catContainsTrip(int catNum, int a, int b, int c)
	{	
	if( (pos[catNum][a] < pos[catNum][b]) && (pos[catNum][b] < pos[catNum][c]) ) return true;

	if( (pos[catNum][c] < pos[catNum][b]) && (pos[catNum][b] < pos[catNum][a]) ) return true;
	
	return false;
	}

static int p[][];

static int pos[][];

static int taxa = -1;

static boolean uniqueExists = false;

static boolean DEBUG = false;

public static void main(String args[])
	{
	taxa = 5;

	System.out.println("Going to look for unique caterpillars on "+taxa+" taxa for betweenness.");

	
	int perm = 1;
	for(int loop=taxa; loop>=1; loop--)
		{
		perm = perm * loop;
		}
		
	System.out.println("First, generating all possible "+perm+" permutations of "+taxa+" taxa...");

	p = new int[perm][taxa];
	
	pos = new int[perm][taxa];
	
	int at = 0;

	int counter[] = new int[taxa];

	while( at < p.length )
		{
		boolean seen[] = new boolean[taxa];
		for(int x=0; x<seen.length; x++) seen[x] = false;
		
		for(int x=0; x<counter.length; x++) seen[ counter[x] ]=true;
			
		boolean good = true;
		for(int x=0; x<seen.length; x++)
			{
			if(seen[x] == false)
				{
				good = false;
				break;
				}
			}
	
		if( good )
			{
			if(DEBUG) System.out.print(at+": ");
			for(int x=0; x<counter.length; x++)
					{
					p[at][x] = counter[x];
					if(DEBUG) System.out.print(counter[x]);
					pos[at][counter[x]] = x;
					}

			if(DEBUG) System.out.println();
			at++;
			}
			
		int ptr = counter.length-1;
		while( ptr >= 0 )
			{
			if( counter[ptr] < (taxa-1) )
				{
				counter[ptr]++;
				break;
				}
			else
				{
				counter[ptr]=0;
				ptr--;
				}
			}
			
		}

	System.out.println("Found "+at+" permutations.");	
	
	System.out.println("Starting search for uniquely defined caterpillars.");

	int x = 0;	//! Assume that the first caterpillar is 0123...
	for( int y = (x+1); y<perm; y++)
		{
		TwoCaterpillars tc = new TwoCaterpillars(x,y);
		//! System.out.println("Checking: "+x+" "+y);
		
		if(DEBUG)
		{
		System.out.println("Checking the following caterpillars for uniqueness:");
		dumpCaterpillar(x);
		dumpCaterpillar(y);
		//dumpCaterpillar(z);
		}
		
		boolean unique = true;
		
		outer: for(int d=0; d<perm; d++)
		for(int e=0; e<perm; e++)
			{
			TwoCaterpillars two = new TwoCaterpillars(d,e);

			if(DEBUG)
			{
			System.out.println("Comparing with:");
			dumpCaterpillar(d);
			dumpCaterpillar(e);
			}

			if( tc.sameAs(two) )
				{
				if(DEBUG) System.out.println("Same caterpillars up to symmetry. Skipping.");
				continue;
				}
			
			if( tc.satisfiedBy(two) )
				{

				if(DEBUG)
				{
				System.out.println("NOT UNIQUE BECAUSE THESE CATERPILLARS ALSO CONTAIN ALL THE TRIPLETS:");

				dumpCaterpillar(d);
				dumpCaterpillar(e);
				}
				
				unique = false;
				break outer;
				}
			}
		if( unique )
			{
			System.out.println("THE FOLLOWING TWO CATERPILLARS ARE UNIQUELY DEFINED (UP TO INVERSION SYMMETRY)!");
			//! System.out.println("Code ="+x+" - "+y);
			
			uniqueExists = true;
			
		dumpCaterpillar(x);
		dumpCaterpillar(y);
			
		 System.out.println("-- betweenness Triplets --");
		System.out.println("-- Format (a,b,c) which means that b should be between a and c.");
		tc.dumpTriplets();	
		//!System.out.println("--------------");
		//!tc.dumpTripletsMiniZinc();
		
			//! Comment this line out to get more unique caterpillars
			//! System.exit(0);
			}
		}
	
	if( !uniqueExists )
		{
		System.out.println("NO UNIQUE CATERPILLARS FOUND ON "+taxa+" TAXA :-(");
		
		}
	
		
	}






}