package models.deltaAlgebra;

import java.util.*;

/**
 * A dependency-chained closed delta
 * 
 * @author Nitta
 * 
 */
public class DeltaComplex extends DeltaExpression {
	private DeltaExpression frontierDelta;
	private DeltaComplex subComplex = null;

	public DeltaComplex(Delta delta) {
		this.frontierDelta = new DeltaSimplex(delta);
	}

	public DeltaComplex(DeltaExpression delta) {
		this.frontierDelta = delta;
	}

	public DeltaComplex(Delta frontierDelta, DeltaComplex subComplex) {
		this.frontierDelta = new DeltaSimplex(frontierDelta);
		this.subComplex = subComplex;
	}

	public DeltaComplex(DeltaExpression frontierDelta, DeltaComplex subComplex) {
		this.frontierDelta = frontierDelta;
		this.subComplex = subComplex;
	}

	/**
	 * dependency chaining
	 * (this = delta | this)
	 * 
	 * @param delta
	 */
	public void attach(Delta delta) {
		this.subComplex = this.copy();
		this.frontierDelta = new DeltaSimplex(delta);
	}

	/**
	 * split
	 * if this = d1 | d2 | ... | dn
	 *
	 * @return [d1, d2, ..., dn]
	 */
	public List<DeltaExpression> split() {
		if (subComplex == null) {
			List<DeltaExpression> deltaSequence = new ArrayList<>();
			deltaSequence.add(frontierDelta);
			return deltaSequence;
		}
		List<DeltaExpression> deltaSequence = subComplex.split();
		deltaSequence.add(0, frontierDelta);
		return deltaSequence;
	}

	/**
	 * decompose
	 * if this = (d1 x d2) | (d3 + d4 | d5) | (d6 + d7)
	 * 
	 * @return [d1, d2, d3, d4, d5, d6, d7]
	 */
	@Override
	public List<Delta> decompose() {
		if (subComplex == null) {
			List<Delta> deltaSequence = new ArrayList<>();
			deltaSequence.addAll(frontierDelta.decompose());
			return deltaSequence;
		}
		List<Delta> deltaSequence = subComplex.decompose();
		deltaSequence.addAll(0, frontierDelta.decompose());
		return deltaSequence;
	}

	/**
	 * merge operation (not add)
	 *
	 * if this = d1 | d2 | d3 | d5 and another = d1 | d4 | d5
	 * then return d1 | ((d2 | d3) + d4) | d5
	 *
	 * @param another
	 */
	public DeltaComplex merge(DeltaComplex another) {
		// Compute LCS (Longest Common Subsequence) as anchors.
		int i = 0;
		HashMap<DeltaExpression, Integer> anotherPosMap = new HashMap<>();
		List<DeltaExpression> anotherSequence = another.split();
		Collections.reverse(anotherSequence);
		for (DeltaExpression delta: anotherSequence) {
			anotherPosMap.put(delta, i);
			i++;
		}
		// Compute LIS (Longest Increasing Subsequence) in positions.
		List<Integer> anotherPositions = new ArrayList<>();
		int j = 0;
		HashMap<DeltaExpression, Integer> thisPosMap = new HashMap<>();
		List<DeltaExpression> thisSequence = this.split();
		Collections.reverse(thisSequence);
		for (DeltaExpression delta: thisSequence) {
			thisPosMap.put(delta, j);
			j++;
			Integer pos = anotherPosMap.get(delta);
			if (pos != null) {
				anotherPositions.add(pos);
			}
		}
		int tails[] = new int[anotherPositions.size()];
		int tailValues[] = new int[anotherPositions.size()];
		int prev[] = new int[anotherPositions.size()];
		Arrays.fill(prev, -1);
		int len = 0;
		for (i = 0; i < anotherPositions.size(); i++) {
			int pos = anotherPositions.get(i);
			int index = Arrays.binarySearch(tailValues, 0, len, pos);
			if (index < 0) {
				index = -index - 1;
			}
			if (index > 0) {
				prev[i] = tails[index - 1];
			}
			tails[index] = i;
			tailValues[index] = pos;

			if (index == len) {
				len++;
			}
		}
		List<Integer> lis = new ArrayList<>();
		for (i = tails[len - 1]; i >= 0; i = prev[i]) {
			lis.add(anotherPositions.get(i));
		}
		Collections.reverse(lis);

		DeltaComplex deltaComplex = null;
		int anotherPrevPos = -1;
		int thisPrevPos = -1;
		for (int anotherPos: lis) {
			DeltaExpression delta = anotherSequence.get(anotherPos);
			int thisPos = thisPosMap.get(delta);
			DeltaComplex leftComplex = null;
			if (thisPos - thisPrevPos > 1) {
				for (int ii = thisPrevPos + 1; ii < thisPos; ii++) {
					DeltaExpression thisDelta = thisSequence.get(ii);
					leftComplex = new DeltaComplex(thisDelta, leftComplex);
				}
			}
			DeltaComplex rightComplex = null;
			if (anotherPos - anotherPrevPos > 1) {
				for (int jj = anotherPrevPos + 1; jj < anotherPos; jj++) {
					DeltaExpression anotherDelta = anotherSequence.get(jj);
					rightComplex = new DeltaComplex(anotherDelta, rightComplex);
				}
			}
			if (leftComplex != null && rightComplex != null) {
				deltaComplex = new DeltaComplex(new DeltaSum(leftComplex, rightComplex), deltaComplex);
			} else if (leftComplex != null) {
				deltaComplex = new DeltaComplex(leftComplex, deltaComplex);
			} else if (rightComplex != null) {
				deltaComplex = new DeltaComplex(rightComplex, deltaComplex);
			}
			deltaComplex = new DeltaComplex(delta, deltaComplex);
			anotherPrevPos = anotherPos;
			thisPrevPos = thisPos;
		}
		DeltaComplex leftComplex = null;
		if (thisSequence.size() - thisPrevPos > 1) {
			for (int ii = thisPrevPos + 1; ii < thisSequence.size(); ii++) {
				DeltaExpression thisDelta = thisSequence.get(ii);
				leftComplex = new DeltaComplex(thisDelta, leftComplex);
			}
		}
		DeltaComplex rightComplex = null;
		if (anotherSequence.size() - anotherPrevPos > 1) {
			for (int jj = anotherPrevPos + 1; jj < anotherSequence.size(); jj++) {
				DeltaExpression anotherDelta = anotherSequence.get(jj);
				rightComplex = new DeltaComplex(anotherDelta, rightComplex);
			}
		}
		if (leftComplex != null && rightComplex != null) {
			deltaComplex = new DeltaComplex(new DeltaSum(leftComplex, rightComplex), deltaComplex);
		} else if (leftComplex != null) {
			deltaComplex = new DeltaComplex(leftComplex, deltaComplex);
		} else if (rightComplex != null) {
			deltaComplex = new DeltaComplex(rightComplex, deltaComplex);
		}
		this.frontierDelta = deltaComplex.frontierDelta;
		this.subComplex = deltaComplex.subComplex;
		return this;
	}

	@Override
	public DeltaComplex copy() {
		if (subComplex == null) {
			return new DeltaComplex(frontierDelta.copy());
		}
		return new DeltaComplex(frontierDelta.copy(), subComplex.copy());
	}

	public String toString() {
		return frontierDelta.toString() + (subComplex == null ? "" : " | " + subComplex.toString());
	}
}