/*
 *This file is part of AdmissibleFPG.
 *
 * Copyright (C) 2014 William Pettersson <william@ewpettersson.se>
 *
 *    AdmissibleFPG is free software: you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation, either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    AdmissibleFPG is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with AdmissibleFPG.  If not, see <http://www.gnu.org/licenses/>.
 */
package se.ewpettersson.admissiblefpg.fpg;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;

import se.ewpettersson.admissiblefpg.Config;
import se.ewpettersson.admissiblefpg.Gluing;

import nl.uu.cs.treewidth.algorithm.GreedyFillIn;
import nl.uu.cs.treewidth.algorithm.MaximumMinimumDegreePlusLeastC;
import nl.uu.cs.treewidth.algorithm.PermutationToTreeDecomposition;
import nl.uu.cs.treewidth.algorithm.QuickBB;
//import nl.uu.cs.treewidth.algorithm.TreewidthDP;
import nl.uu.cs.treewidth.input.GraphInput.InputData;
import nl.uu.cs.treewidth.input.InputException;
import nl.uu.cs.treewidth.ngraph.NGraph;
import nl.uu.cs.treewidth.ngraph.NTDBag;
import nl.uu.cs.treewidth.ngraph.NVertex;
import nl.uu.cs.treewidth.ngraph.NVertexOrder;

public class TreeDecomp {
	List<Edge> edges;

	List<Vertex> vertices;
	public List<Integer> seen;
	Vertex root;

	int nTets;
	int tw;
	
	FacePairingGraph fpg;

	private Config oneConfig;

	
	public FacePairingGraph getFpg() {
		return fpg;
	}

	public TreeDecomp(FacePairingGraph f) throws InputException {
		edges = new ArrayList<Edge>();
		vertices = new ArrayList<Vertex>();
		seen = new ArrayList<Integer>();
		fpg = f;
		getTreeDecomp();
		createRootedTree();
	}
	
	private void createRootedTree() {
//		root = null;
//		for(Vertex v : vertices) {
//			if (v.degree(edges) == 1) {
//				root = v;
//				break;
//			}
//		}
//		if(vertices.size() ==1) {
//			root = vertices.get(0);
//		}
		root = vertices.get(0);
		root.setRoot();
		if (root == null) {
			return;
		}
		// "ToAdd" is a list of which tetrahedra to add at this step
		// For the root bag, any tetrahedra in this bag are added in the final
		// step
		
		root.setToAdd(root.getContents());
		// Keep a track of which tetrahedra we have seen, that is which
		// tetrahedra will be added at a "higher" stage of the tree.
		seen.addAll(root.getContents());
		
		// Find the children of root, and add them.
		addChildren(root);
		
		root.assignEdges();

	}
	
	public void addChildren(Vertex v) {
		// Go through edges and find children of v. Note that the
		// e.isUsed()/e.use() test ensures that each edge is only added once.

		for(Edge e:edges) {
			if (!e.isUsed() && e.touches(v)) {
				e.use();
				// Find the actual child node
				Vertex child = e.getOther(v);
				// Get the tetrahedra at this node, and work out which are new.
				// The ones that are new are to be added at this stage.
				List<Integer> childToAdd = new ArrayList<Integer>(child.getContents());
				childToAdd.removeAll(seen);
				child.setToAdd(childToAdd);
				v.addChild(child);
				// Mark the extra tetrahedra as being seen.
				seen.addAll(childToAdd);
				// Add the children of this child.
				// Note that this is depth-first, but we need a full traversal
				// so that doesn't matter. We also know this will be correct as
				// if two children share a common tetrahedra then the parent
				// must also share that tetrahedra (and thus it must already
				// been in seen)
				addChildren(child);
			}
		}	
	}
	
	
	private void getTreeDecomp() throws InputException {
		FPGReader f = new FPGReader(fpg);
		NGraph<InputData> g = f.get();
		
		MaximumMinimumDegreePlusLeastC<InputData> lbAlgo = new MaximumMinimumDegreePlusLeastC<InputData>();
		lbAlgo.setInput( g );
		lbAlgo.run();
		int lowerbound = lbAlgo.getLowerBound();

		GreedyFillIn<InputData> ubAlgo = new GreedyFillIn<InputData>();
		ubAlgo.setInput( g );
		ubAlgo.run();
		int upperbound = ubAlgo.getUpperBound();
		
		NVertexOrder<InputData> permutation = null;

		if( lowerbound == upperbound ) {
			permutation = ubAlgo.getPermutation();
		} else {
//			TreewidthDP<InputData> dpAlgo = new TreewidthDP<InputData>();
//			dpAlgo.setInput( g );
//			dpAlgo.run();
//			permutation = dpAlgo.
			QuickBB<InputData> qbbAlgo = new QuickBB<InputData>();
			qbbAlgo.setInput( g );
			qbbAlgo.run();
			permutation = qbbAlgo.getPermutation();
			upperbound = qbbAlgo.getUpperBound();
		}
		
		tw = upperbound+1;
		
		PermutationToTreeDecomposition<InputData> convertor = new PermutationToTreeDecomposition<InputData>( permutation );
		convertor.setInput( g );
		convertor.run();
		NGraph<NTDBag<InputData>> decomposition = convertor.getDecomposition();
		Iterator<NVertex<NTDBag<InputData>>> it = decomposition.getVertices();
		HashMap<NVertex<NTDBag<InputData>>,Integer> map = new HashMap<NVertex<NTDBag<InputData>>,Integer>();
		HashMap<Integer,Vertex> vMap = new HashMap<Integer,Vertex>();
		int ind=0;
		while( it.hasNext() ) {
			NVertex<NTDBag<InputData>> bag = it.next();
			map.put(bag, ind);

			List<Integer> contents = new ArrayList<Integer>();
			for( NVertex<InputData> v : bag.data.vertices ) {
				contents.add(v.data.id);
				
			}
			Iterator<NVertex<NTDBag<InputData>>> i = bag.getNeighbors();
			Vertex v = new Vertex(contents, ind, this);
			vMap.put(ind, v);
			while( i.hasNext() ) {
				NVertex<NTDBag<InputData>> n = i.next();
				if (map.containsKey(n)) {
					Edge e = new Edge( v, vMap.get(map.get(n)));
					edges.add(e);
				}
			}
			vertices.add(v);

			ind++;
		}

	}
	
	
	
	public boolean isAdmissible() {
		return root.hasConfig();
		//return (root.getConfigs().size() > 0);
	}
	
	public List<Edge> getEdges() {
		return edges;
	}

	public void makeConfig(int numTet) {
		this.oneConfig = new Config();
		for(int i=0;i<numTet;i++)
			oneConfig.addTetrahedra(i);
	}
	
	public boolean glue(int t1, int f1, int t2, int f2, int s) {
		Gluing g = new Gluing(s, t1, f1, t2, f2);
		System.out.println("Gluing "+g);
		return oneConfig.addGluing(g);
		
//		System.out.println(oneConfig.getVC().getLinks().get(3).get(1).get(6));
//		System.out.println(oneConfig.getVC().getLinks().get(0).get(1).get(6));
//		
//		System.out.println(oneConfig.getVC().getLinks().get(2).get(0).get(5));
//		System.out.println(oneConfig.getVC().getLinks().get(2).get(1).get(6));
		
	}

	public int getTW() {
		if (tw<0) 
			tw=1;
		return tw;
	}
	
	public String toString() {
		String s="[";
		for(Vertex v : vertices) {
			s+= v.toString() + ", ";
		}
		if(s.endsWith(", "))
			s = s.substring(0,s.length()-2);
		s+="]\n[";
		for(Edge e: edges) {
			s+= e.toString() + ", ";
		}
		if(s.endsWith(", "))
			s = s.substring(0,s.length()-2);
		s+="]\n";
		return s;
	}

	public String toPython() {
		String s="[[";
		for(Vertex v : vertices) {
			s+= "[" + v.id + "," + v.contents + "], ";
		}
		if(s.endsWith(", "))
			s = s.substring(0,s.length()-2);
		s+="],[";
		for(Edge e: edges) {
			s+= "[" + e.get(0).id + "," + e.get(1).id + "], ";
		}
		if(s.endsWith(", "))
			s = s.substring(0,s.length()-2);
		s+="]]";
		return s;
	}

	public String toRegina() {
		String s=vertices.size() + " " + getTW() + "\n";
		for(Vertex v : vertices) {
			s+= (v.isRoot ? v.id : v.parent.id);
			s+= " " + v.contents.size();

			// We will be polite and output the bag in sorted order.
			// Make a new list, so that this routine remains read-only.
			ArrayList<Integer> bag = new ArrayList<Integer>(v.contents);
			Collections.sort(bag);
			for (Integer i : bag)
				s += " " + i;
			s += "\n";
		}
		return s;
	}

	public int getMaxConfigs() {
		return root.getMaxConfigs();
	}

	public String vertexOrder() {
		String s = new String();
		s+= root.vertexOrder();
		return s;
	}


}
