ShuffleDecomp.java

package nfa;

import java.util.*;
import java.lang.Math;

import DFA.DFAState;
import automata.FiniteAutomaton;



public class ShuffleDecomp {
	
	FiniteAutomaton aut;
	private String uString = null;
	private String vString = null;
	
	public String u()
	{
		return uString;
	}
	
	public String v()
	{
		return vString;
	}
	
	public ShuffleDecomp(FiniteAutomaton inAut)
	{
		aut = inAut;
		DFAState q0 = DFAState.initialDFAState(aut);
		
		StepInfo x = new StepInfo("", "", q0, "", "");
		if (deltaSet(x.q).size() == 1)
		{
			x = firstDiff(x);
		}
		else
		{
			x.f = (String)deltaSet(x.q).get(0);
		}
		while (deltaSet(x.q).size() == 2 && (x.f+x.g) != "")
		{
			x = firstDiff(x);
		}
		if (deltaSet(x.q).isEmpty())
		{
			uString = x.u;
			vString = x.v;
		}
		else{
			throw new RuntimeException("Not a shuffle aut, ctor");
		}
	}
	
	
	private DFAState delta(DFAState q, String s)
	{
		return DFAState.delta(q,s);
	}
	
	private List deltaSet(DFAState q){
		return DFAState.deltaSet(q);
	}
	
	private boolean deltaDefined(DFAState q, String s)
	{
		return  DFAState.deltaDefined(q,s);
	}
	
	private int dmax(DFAState q, String a){
		if (a.isEmpty())
		{
			return 0;
		}
		int ret = 0;
		while (!deltaSet( q).isEmpty())
		{
			ret += 1;
		}
		return ret;
	}
	
	private String spow(String s, int n)
	{
		String ret = "";
		for (int i = 0; i < n; i++)
		{
			ret += s;
		}
		return ret;
	}
	
	private List<String> setDifference(List<String> s1, List<String> s2)
	{
		List<String> ret = new LinkedList(s1);
		ret.removeAll(s2);
		return ret;
	}
	
	private String first(List<String> s)
	{
		for (String el : s)
		{
			return el;
		}
		throw new RuntimeException("Empty list doesn't have first");
	}
	
	private int dmin(DFAState q, String a)
	{
		int ret = 0;
		List<String> dset = deltaSet(q);
		dset.remove(a);
		String b = first(dset);
		while(true){
			if ((deltaDefined(q, spow(a, ret) + b) )  ) //TODO or case?
			{
				return ret;
			}
			ret += 1;
		}
	}
	
	private String wq(String w, DFAState q)
	{
		if (w.isEmpty() || ! deltaSet(q).contains(w.charAt(w.length()-1)) )
		{
			return w;
		}
		//remove last block of a's in w and return
		List<String> blockList = blocks(w);
		String last = blockList.get(blockList.size() - 1);
		return w.substring(0, w.length() - (1 + last.length()));
		//TODO what if undefined?
	}
		
	private List<String> blocks(String s)
	{
		    if (s.isEmpty())
		    {
		        return new LinkedList<String>();
		    }
		    
		    int i = 0;
		    LinkedList<String> ret = new LinkedList<String>();
		    while (i < s.length())
		    {
		        String accum = ""; //TODO make faster?
		        char current = s.charAt(i);
		        while (i < s.length() && s.charAt(i) == current)
		        {
		            accum += s.charAt(i);
		            i += 1;
		        }
		        ret.addLast(accum);
		    }
		    return ret;
		
	}
	
	private String skeleton(String s){
	    if (s.isEmpty())
	    {
	        return "";
	    }
	    
	    int i = 0;
	    String ret = "";
	    while (i < s.length())
	    {
	        String accum = "";
	        char current = s.charAt(i);
	        while (i < s.length() && s.charAt(i) == current)
	        {
	            accum += s.charAt(i);
	            i += 1;
	        }
	        ret += current;
	    }
	    return ret;
	}
	
	//When we're at the end of shuffle, combine blocks into the "maximum" word
	private String maxShuf(String s, String t)
	{
		List<String> sblocks, tblocks;
		sblocks = blocks(s);
		tblocks = blocks(t);
		String ret = "";
		int k = 0, l=0;
		int n = sblocks.size(), m=tblocks.size();
		while (k < n || l < m)
		{
			if (k < n && l < m && sblocks.get(k).charAt(0) == tblocks.get(l).charAt(0))
			{
				ret +=  sblocks.get(k) + tblocks.get(l);
				k++;
				l++;
			}
			else if(k <= n)
			{
				ret +=  sblocks.get(k);
				k++;
			}
			else
			{
				ret +=  tblocks.get(l);
				l++;
			}
		}
		return ret;
	}
	
	String findUnique(DFAState q)
	{
		DFAState qq = q;
		String z = "";
		
		while (!aut.F.contains(qq))
		{
			if (deltaSet(qq).size() == 2 || deltaSet(qq).isEmpty())
			{
				throw new RuntimeException("Not shuffle decomposable");
			}
			String a = first(deltaSet(qq));
			z += a;
			qq = delta(q,a);
		}
		return z;
	}
	
	class StepInfo
	{
		public String f;
		public String g;
		public DFAState q;
		public String u;
		public String v;
		
		public StepInfo(String f, String g, DFAState q, String u, String v)
		{
			this.f = f;
			this.g = g;
			this.q = q;
			this.u = u;
			this.v = v;
		}
		
	}
	
	class MaxInfo
	{
		public String s;
		public String t;
		public String z;
		public DFAState qprev;
		public DFAState qq;
		String c;
		public int eps;
		public int b;
		
		public MaxInfo(String s, String t, String z, DFAState qprev, DFAState qq, String c, int eps, int b)
		{
			this.s = s;
			this.t = t;
			this.z = z;
			this.qprev = qprev;
			this.qq = qq;
			this.c = c;
			this.eps = eps;
			this.b = b;
		}
		
	}
	
	
	private MaxInfo maxEqual(DFAState qprev, DFAState qq)
	{
		String s = "";
		String t = "";
		String z= "";
		String c = "";
		int b = -99;
		int eps = -101;
		while (deltaSet(qq).size() == 1)
		{
			c = first(deltaSet(qq));
			b = dmax(qq, c);
			eps = dmin(qq, c);
			if (2*eps == b)
			{
				s += spow(c,eps);
				t += spow(c,eps);
				z += spow(c,b);
				qprev = delta(qq, spow(c, b-1));
				
				
			}
			else{
				return new MaxInfo(s,t,z,qprev, qq, c, eps, b);
			}
		}
		
		return new MaxInfo(s,t,z,qprev, qq, c, eps, b);
	}
	
	private StepInfo firstDiff(StepInfo step)
	{
		String f = step.f;
		String g = step.g;
		DFAState q = step.q;
		String u = step.u;
		String v = step.v;
		
		if (g.isEmpty())
		{
			int gamma = dmax(q,f);
			DFAState qprev = delta(q, spow(f, gamma-1));
			DFAState qq = delta(q, spow(f,gamma));
			String s = "";
			String t = "";
			String z = "";
			//Case 1
			if (deltaSet(qq).size() == 2)
			{
				List<String> diff = new LinkedList(deltaSet(qq));
				diff.removeAll(deltaSet(q));
				String d;
				if (diff.isEmpty())
				{
					List<String> candidates = deltaSet(qq);
					candidates.remove(u.substring(u.length() - 1));
					d = diff.get(0);
				}
				else
				{
					d = diff.get(0);
				}
				u += spow(f,gamma);
				q = delta(q, spow(f,gamma));
				return new StepInfo(d,"", q, u, v);
			}
			else if (deltaSet(qq).size() == 1)
			{
				MaxInfo m = maxEqual(qprev, qq);
				s = m.s;
				t = m.t;
				z = m.z;
				qprev = m.qprev;
				qq = m.qq;
				String c = m.c;
				int eps = m.eps;
				int b = m.b;
				//Case 2
				if (deltaSet(qq).size() == 2)
				{
					String d,e;
					d = (String)deltaSet(qq).get(0);
					e = (String)deltaSet(qq).get(1);
					
					if (deltaDefined(q,maxShuf(s+e, spow(f,gamma) + t)))
					{
						u = u + spow(f,gamma) + s;
						v = v + t;
						q = delta(q, spow(f,gamma) + z);
						return new StepInfo(d, "", q, u, v);
					}
					else
					{
						u = u + spow(f, gamma) + t;
						v = v + s;
						q = delta(q, spow(f,gamma) + z);
						return new StepInfo("", d, q, u, v);
					}
				}
				else if (eps == b) //Case 3
				{
					int a = dmax(qprev, c);
					if (a == b)
					{
						s = s + findUnique(qq);
						z = z + findUnique(qq);
					}
					else
					{
						s = s + spow(c, Math.max(a, b-a));
						t = t + spow(c, Math.min(a, b-a));
						z = z + spow(c,b);
					}
					if (deltaDefined(q, maxShuf(s, spow(f,gamma) + t)))
					{
						u = u + spow(f,gamma) + t;
						v = v + s;
						q = delta(q, maxShuf(s, spow(f,gamma) + z));
						return new StepInfo("", "", q, u, v);
					}
					else
					{
						u = u + spow(f, gamma) + s;
						v = v + t;
						q = delta(q, maxShuf(s, spow(f,gamma) + z));
						return new StepInfo("", "", q, u, v);
					}
				}
				else if (eps != b)//Case 4
				{
					if (2*eps > b) //Case 4a
					{
						qq = delta(qq, spow(c,b));
						String r = findUnique(qq);
						if (deltaDefined(q, maxShuf(s + spow(c,eps+1), spow(f,gamma)+t)))
						{
							u = u + spow(f,gamma) + s + spow(c,b-eps);
							v = v + t + spow(c,eps) + r;
							
						}
						else
						{
							 u = u + spow(f,gamma) + spow(c,eps) + r;
							 v = v + t + s + spow(c, b-eps);
							 
						}
						q = delta(q, spow(f,gamma) + z + spow(c,b) + r);
						return new StepInfo("", "", q, u, v);
					}
					else
					{
						List<String> candidates = deltaSet(delta(qq, spow(c,eps)));
						candidates.remove(c);
						String d = candidates.get(0);
						if (deltaDefined(q, maxShuf(s + spow(c, eps + 1), spow(f,gamma) + t )))
						{
							u = u + spow(f,gamma) + s + spow(c,eps);
							v = v + s + spow(c,eps);
							q = delta(q, spow(f,gamma) + z + spow(c,eps));
							return new StepInfo(d, "", q, u, v);
						}
						else
						{
							u = u + spow(f,gamma) + t;
							v = v + s + spow(c,eps);
							q = delta(q, spow(f,gamma) + z + spow(c,eps));
							return new StepInfo("", d, q, u, v);
						}
						
					}
				}
			}
			else
			{
				throw new RuntimeException("Not decomposable firstDiff0");
			}
		}
		else if (f.isEmpty())
		{
			StepInfo flipStep = new StepInfo(g,f,q,v,u);
			StepInfo next = firstDiff(flipStep);
			return new StepInfo(next.g, next.f, next.q, next.v, next.u);
		}
		
		throw new RuntimeException("Not decomposable firstDiff1");
	}
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	

}