/*
 * Copyright (c) 2017, Hisao Tamaki and Hiromu Ohtsuka, Keitaro Makii
*/

package tw.heuristic;

import java.util.ArrayList;
import java.util.Arrays;

public class Separator implements Cloneable{
	Bag parent;
	Graph graph;
	VertexSet vertexSet;
	int size;
	ArrayList<Bag> incidentBags;
	boolean safe;
	boolean unsafe;
	boolean wall;

	int[] parentVertex;
	int safeSteps;

	public Separator(Bag parent) {
		this.parent = parent;
		graph = parent.graph;
		incidentBags = new ArrayList<>();
	}

	public Separator(Bag parent, VertexSet vertexSet) {
		this(parent);
		this.vertexSet = vertexSet;
		size = vertexSet.cardinality();
	}

	public void addIncidentBag(Bag bag) {
		incidentBags.add(bag);
	}

	public void removeVertex(int v) {
		if (vertexSet.get(v)) {
			size--;
		}
		vertexSet.clear(v);
	}

	public void invert() {
		vertexSet = convert(vertexSet, parent.inv);
		parent = parent.parent;
	}

	public void convert() {
		vertexSet = convert(vertexSet, parent.conv);
	}

	private VertexSet convert(VertexSet s, int[] conv) {
		VertexSet result = new VertexSet();
		for (int v = s.nextSetBit(0); v >= 0;
				v = s.nextSetBit(v + 1)) {
			result.set(conv[v]);
		}
		return result;
	}

	void collectBagsToPack(ArrayList<Bag> list, Bag from) {
		for (Bag bag: incidentBags) {
			if (bag !=from) {
				bag.collectBagsToPack(list,  this);
			}
		}
	}

	public void figureOutSafetyBySPT() {
		if (!safe && !unsafe) {
			safe = isSafe();
			unsafe = !safe;
		}
	}

	public boolean isSafe() {
		SafeSeparator ss = new SafeSeparator(parent.graph);
		//return isSafeBySPT();
		safeSteps = ss.decideSafeness(vertexSet);
		return safeSteps > 0;
		//return ss.isSafeSeparator(vertexSet);
	}

	public int getSteps(){
	  return Math.abs(safeSteps);
	}

	public boolean isSafeBySPT() {
		parentVertex = new int[graph.n];
		ArrayList<VertexSet> components = 
			graph.getComponents(vertexSet);
		for (VertexSet compo: components) {
			if (!isSafeComponentBySPT(compo)) {
				return false;
			}
		}
		return true;
	}

	private boolean isSafeComponentBySPT(VertexSet component) {
		VertexSet neighborSet = graph.neighborSet(component);
		VertexSet rest = graph.all.subtract(neighborSet).subtract(component);

		for (int v = neighborSet.nextSetBit(0); v >= 0;
				v = neighborSet.nextSetBit(v + 1)) {
			VertexSet missing = neighborSet.subtract(graph.neighborSet[v]);

			for (int w = missing.nextSetBit(0); w >= 0 && w <= v;
					w = missing.nextSetBit(w + 1)) {
				missing.clear(w);
			}

			if (!missing.isEmpty()) {
				VertexSet spt = shortestPathTree(v, missing, rest);
				if (spt == null) {
					return false;
				}
				rest.andNot(spt);
			}
		}
		return true;
	}

	private VertexSet shortestPathTree(int v, VertexSet targets,
			VertexSet available) {
		VertexSet union = available.unionWith(targets);

		VertexSet reached = new VertexSet(graph.n);
		reached.set(v);
		VertexSet leaves = (VertexSet) reached.clone();
		while (!targets.isSubset(reached) && !leaves.isEmpty()) {
			VertexSet newLeaves = new VertexSet(graph.n);
			for (int u = leaves.nextSetBit(0); u >= 0;
					u = leaves.nextSetBit(u + 1)) {
				VertexSet children = 
					graph.neighborSet[u].intersectWith(union).subtract(reached);
				for (int w = children.nextSetBit(0); w >= 0;
						w = children.nextSetBit(w + 1)) {
					reached.set(w);
					parentVertex[w] = u;
					if (available.get(w)) {
						newLeaves.set(w);
					}
				}
			}
			leaves = newLeaves;
		}

		if (!targets.isSubset(reached)) {
			return null;
		}

		VertexSet spt = new VertexSet(graph.n);
		for (int u = targets.nextSetBit(0); u >= 0;
				u = targets.nextSetBit(u + 1)) {
			int w = parentVertex[u];
			while (w != v) {
				spt.set(w);
				w = parentVertex[w];
			}
		}
		return spt;
	}


	public void dump(String indent) {
		System.out.println(indent + "sep:" + toString());
	}

	public String toString() {
		StringBuilder sb = new StringBuilder();
		sb.append(vertexSet);
		sb.append("(");
		for (Bag bag: incidentBags){
			if (bag == null) {
				sb.append("null bag ");
			}
			else {
				sb.append(parent.nestedBags.indexOf(bag) + ":" + bag.vertexSet);
				sb.append(" ");
			}
		}
		sb.append(")");

		return sb.toString();
	}

	@Override
		public Separator clone(){
			try{
				Separator result = (Separator)super.clone();

				if(vertexSet != null){
					result.vertexSet = (VertexSet)vertexSet.clone();
				}
				if(parentVertex != null){
					result.parentVertex = Arrays.copyOf(parentVertex, parentVertex.length);
				}
				if(incidentBags != null){
					result.incidentBags = new ArrayList< >(incidentBags);
				}

				return result;
			}
			catch(CloneNotSupportedException cnse){
				throw new AssertionError();
			}
		}
}
