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

public class Graph {
	
	/*Note: The zero element in the adjacency list MUST be the minimal one!*/
	Integer [][] adjacencyList;
	ArrayList<ArrayList<Integer>> parentList; //list of all the parents of a node
	
	Graph (Integer[][] adjacencyList){
		this.adjacencyList = adjacencyList;
		setParentList();
	}
	
	//populates parentList with the corresponding parents of each node
	void setParentList(){
		//create empty Arraylist of nodes
		parentList = new ArrayList<ArrayList<Integer>>();
		for (int v = 0; v < adjacencyList.length; v++){
			parentList.add(new ArrayList<Integer>());
		}
		
		//populate with proper parents
		for (int v = 0; v < adjacencyList.length; v++){
			for (Integer c: adjacencyList[v]){
				parentList.get(c).add(v);
			}
		}
				
	}
	
	
	//MAY USE LOTS OF MEMORY, AVOID THIS
	ArrayList<Ideal> allIdeals(){
		IdealIterator it = new IdealIterator(this);
		ArrayList<Ideal> ideals = new ArrayList<Ideal>();
		while (true){
			Ideal i = it.next();
			if (i == null) break;
			ideals.add(i);
		}
		return ideals;
	}
	
	Integer idealCount(){
		int i = 0;
		IdealIterator it = new IdealIterator(this);
		while (it.next() != null){
			i += 1;
		}
		return i;
	}
	
	URTsTuple URTs (){
		IdealIterator idealIterator = new IdealIterator(this);
		URTsTuple urts = new URTsTuple();
		
		int i = 0;
		int idealCount = this.idealCount();
		//go through each ideal
		while (true){
			System.out.println("   " +i + " / " + idealCount);
			Ideal ideal = idealIterator.next();
			if (ideal == null) break;
			LabeledSkewGraphIterator labeledIterator = new LabeledSkewGraphIterator(ideal);
//			ideal.display();
			//go through each labeling
			while (true){
				 LabeledSkewGraph lsg = labeledIterator.next();
				 if (lsg == null) {break;}
//				 System.out.println("skew graph: " + Arrays.toString(lsg.labels));
				 ArrayList<LabeledSkewGraph> rectifications = lsg.rectify();
				 if (rectifications.size() > 1){
					 for (LabeledSkewGraph rec: rectifications){
						 ArrayList<Integer> labeling = new ArrayList<Integer>(Arrays.asList(rec.labels));
						 urts.impossibles.add(labeling);
						 urts.possibles.remove(labeling);
					 }
				 } else if (rectifications.size() == 1) {
					 LabeledSkewGraph rec = rectifications.get(0);
					 ArrayList<Integer> labeling = new ArrayList<Integer>(Arrays.asList(rec.labels));
					 if (!urts.impossibles.contains(labeling)){
						 urts.possibles.add(labeling);
					 }
				 }
			}
			i += 1;
			
		}
		
		return urts;
	}
	
	URTsTuple idealURTs (){
		IdealIterator idealIterator = new IdealIterator(this);
		URTsTuple urts = new URTsTuple();
		
		int i = 0;
		int idealCount = this.idealCount();
		//go through each ideal
		while (true){
			System.out.println(i + " / " +idealCount);
			Ideal ideal = idealIterator.next();
			if (ideal == null) break;
			Graph idealGraph = ideal.subGraph();
			URTsTuple idealURTs = idealGraph.URTs();
			//add and remove bad urts
			for (ArrayList<Integer> impossibleRT : idealURTs.impossibles){
				urts.impossibles.add(ideal.graphLabelingFromSubGraph(impossibleRT));
				boolean removed = urts.possibles.remove(ideal.graphLabelingFromSubGraph(impossibleRT));
//				if (removed){
//					System.out.println("removed!");
//				}
			}
			//add good urts
			for (ArrayList<Integer> possibleRT : idealURTs.possibles){
				ArrayList<Integer> labeling = ideal.graphLabelingFromSubGraph(possibleRT);
				if (!urts.impossibles.contains(labeling)){
					boolean added = urts.possibles.add(labeling);
//					if (added){
//						System.out.println("added!");
//					}
				}
			}
			i += 1;
			
		}
		return urts;
	}
	
	void sqlURTs(URTsDb db, Ideal baseIdeal){
		IdealIterator idealIterator = new IdealIterator(this);
		
		int i = 0;
		int idealCount = this.idealCount();
		//go through each ideal
		while (true){
			System.out.println("   " +i + " / " + idealCount);
			Ideal ideal = idealIterator.next();
			if (ideal == null) break;
			LabeledSkewGraphIterator labeledIterator = new LabeledSkewGraphIterator(ideal);

			//go through each labeling
			while (true){
				 LabeledSkewGraph lsg = labeledIterator.next();
				 if (lsg == null) {break;}

				 ArrayList<LabeledSkewGraph> rectifications = lsg.rectify();
				 String lsgLabels = baseIdeal.graphLabelingFromSubGraph(new ArrayList<Integer>(Arrays.asList(lsg.labels))).toString();
				 for (LabeledSkewGraph rect : rectifications){
					 db.add(
							 baseIdeal.graphLabelingFromSubGraph(new ArrayList<Integer>(Arrays.asList(rect.labels))).toString(),
							 lsgLabels);
					 
				 }
			}
			i += 1;
			
		}
		
	}
	
	URTsDb sqlIdealURTs(String name, Integer size){
		IdealIterator idealIterator = new IdealIterator(this);
		URTsDb db = new URTsDb(name, size);
		
		int i = 0;
		int idealCount = this.idealCount();
		while(true){
			System.out.println(i + " / " +idealCount);
			Ideal ideal = idealIterator.next();
			if (ideal == null) break;
			Graph idealGraph = ideal.subGraph();
			idealGraph.sqlURTs(db, ideal);
			i +=1;
		}
		db.finishAdding();
		db.findURTs();
		System.out.println(db.hasMinimalFillings(this));
		return db;
	}
	
	boolean tailTest(int tail){
		//create the graph without the tail
		HashSet<Integer> emptySet = new HashSet<Integer>();
		for (int i = 0; i < adjacencyList.length; i++){
			if (i != tail){
				emptySet.add(i);
			}
		}
		Ideal ideal = new Ideal(this, emptySet, new HashSet<Integer>());
		Graph noTailGraph = ideal.subGraph();
		
		//get urts with and without tail
		URTsTuple urtsWithTail = idealURTs();
		URTsTuple urtsNoTail = noTailGraph.idealURTs();
		
		for (ArrayList<Integer> noTailURT : urtsNoTail.possibles){
			ArrayList<Integer> conURT = ideal.graphLabelingFromSubGraph(noTailURT);
			if (!urtsWithTail.possibles.contains(conURT)){
				System.out.println("Failure on no tail URT: " + conURT.toString());
				return false;
			}
		}
		return true;
	}

}