import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Stack;

public class Ideal{
		Graph graph;
		HashSet<Integer> emptyNodes;
		HashSet<Integer> exteriorEmptyNodes;
		Integer [] labels;
		ArrayList<Integer> emptyList;
		HashMap<Integer, Integer> emptyListIndices;
		
		Ideal (Graph graph, HashSet<Integer> emptyNodes, HashSet<Integer> exteriorEmptyNodes){
			this.graph = graph;
			this.emptyNodes = emptyNodes;
			this.exteriorEmptyNodes = exteriorEmptyNodes;
			this.labels = new Integer[graph.adjacencyList.length];
			
			//set labeling
			for (int i = 0; i < this.labels.length; i++){
				   this.labels[i] = this.emptyNodes.contains(i) ? null : 0;
			}
		}
		
		Graph subGraph(){
			//this.display();
			emptyList = this.emptyNodeList();
			emptyListIndices = this.emptyNodeListIndices(emptyList);
			
			Integer[][] adjacencyList = new Integer[emptyNodes.size()][];
			for (Integer node: emptyList){
				ArrayList<Integer> neighbors = new ArrayList<Integer>();
				for (Integer n: this.graph.adjacencyList[node]){
					if (labels[n] == null){
						neighbors.add(emptyListIndices.get(n));
					}
				}
				adjacencyList[emptyListIndices.get(node)] = neighbors.toArray(new Integer[neighbors.size()]);
			}
			
			return new Graph(adjacencyList);
		}
		
		ArrayList<Integer> emptyNodeList(){
			ArrayList<Integer> list = new ArrayList<Integer>();
			for (int i = 0; i < labels.length; i++){
				if (labels[i] == null){
					list.add(i);
				}
			}
			return list;
		}
		
		HashMap<Integer, Integer> emptyNodeListIndices(ArrayList<Integer> emptyNodesList){
			HashMap<Integer, Integer> indices = new HashMap<Integer, Integer>();
			for (int i = 0; i < emptyNodesList.size(); i++){
				indices.put(emptyNodesList.get(i), i);
			}
			return indices;
		}
		
		//assumes that subgraph has been run first!
		ArrayList<Integer> graphLabelingFromSubGraph(ArrayList<Integer> subLabeling){
			ArrayList<Integer> labeling = new ArrayList<Integer>();
			for (int i = 0; i < labels.length; i++){
				if (labels[i] == null){
					labeling.add(subLabeling.get(emptyListIndices.get(i)));
				} else {
					labeling.add(null);
				}
			}
			return labeling;
		}
		
		//assume all new nodes are on the exterior
		Ideal addEmptyNodes(List<Integer> nodes){
			//clone properties
			HashSet<Integer> emptyNodes = (HashSet<Integer>)this.emptyNodes.clone();
			HashSet<Integer> exteriorEmptyNodes = (HashSet<Integer>)this.exteriorEmptyNodes.clone();
			
			//close downwards
			Stack<Integer> stk = new Stack<Integer> ();
			for (Integer n: nodes){
				stk.push(n);
			}
			ArrayList<Integer> closedNodes = new ArrayList();
			
			while (!stk.isEmpty()){
				Integer n = stk.pop();
				closedNodes.add(n);
				for (Integer p: this.graph.parentList.get(n)){
					if (!emptyNodes.contains(p)){
						stk.push(p);
					}
				}
			}
			
			
			//add empty nodes
			for (Integer n: closedNodes){
				emptyNodes.add(n);
				labels[n] = null;
				exteriorEmptyNodes.add(n);
				
			}
			
			//update exteriorEmptyNodes if need be
			for (Integer n: closedNodes){
				//go through each parent to check if still exterior
				for (Integer p : graph.parentList.get(n)){
					if (exteriorEmptyNodes.contains(p)){
						boolean stillExterior = false;
						for (Integer c: graph.adjacencyList[p]){
							if (!emptyNodes.contains(c)){
								stillExterior = true;
								break;
							}
						}
						if (!stillExterior){
							exteriorEmptyNodes.remove(p);
						}
					}
				}
			}
			
			return new Ideal(graph, emptyNodes, exteriorEmptyNodes);
		}
		
		List<Integer> exteriorChildren (){
			HashSet<Integer> hashedChildren = new HashSet<Integer>();
			for (Integer e: exteriorEmptyNodes){
				for (Integer c: graph.adjacencyList[e]){
					if (!emptyNodes.contains(c)){
						hashedChildren.add(c);
					}
				}
			}
			
			return new ArrayList<Integer>(hashedChildren);
		}
		
		SubsetIterator<Integer> exteriorChildrenSubsetIterator (){
			List<Integer> children = exteriorChildren();
			return new SubsetIterator<Integer> (children);
		}
		
		void display(){
			System.out.println("ideal");
			System.out.println(Arrays.toString(labels));
		}
		
		ArrayList<Integer> minimalFilling(){
			HashSet<Integer> labeled = new HashSet<Integer>();
			HashSet<Integer> innerUnlabeled = new HashSet<Integer>();
			ArrayList<Integer> labeling = new ArrayList<Integer>(this.labels.length);
			for (int i = 0; i < this.graph.adjacencyList.length; i++){
				labeling.add(null);
			}
			if (emptyNodes.contains(0)){
				innerUnlabeled.add(0);
			}
			
			int label = 1;

			while(!innerUnlabeled.isEmpty()){
				//label this nodes minimally
				HashSet<Integer> newInnerUnlabeled = new HashSet<Integer>();

				for (Integer n: innerUnlabeled){
					labeling.set(n, label);
					labeled.add(n);
				}
				
				//add new innerUnlabeled children
				for (Integer n: innerUnlabeled){
					for (Integer c: this.graph.adjacencyList[n]){
						if (emptyNodes.contains(c)){
							boolean parentsLabeled = true;
							for (Integer p: this.graph.parentList.get(c)){
								if (!labeled.contains(p)){
									parentsLabeled = false;
									break;
								}
							}
							if (parentsLabeled){
								newInnerUnlabeled.add(c);
							}
						}
					}
				}
				
				label += 1;
				innerUnlabeled = newInnerUnlabeled;
			}
			
			return labeling;
		}
	}