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

public class LabeledSkewGraphIterator {
	
	class SemiLabeledIdeal{
		Ideal ideal;
		HashSet<Integer> interiorUnlabeledNodes;
		HashSet<Integer> labeledNodes;
		Integer maxNumber;
		Integer[] labels;
		
		SemiLabeledIdeal (Ideal ideal){
			this.ideal = ideal;
			this.labels = ideal.labels.clone();
			this.maxNumber = 0;
			this.labeledNodes = new HashSet<Integer>();
			this.interiorUnlabeledNodes = new HashSet<Integer>();
			//go through each exterior child to find the interior unlabeled ones (ones whose parents are all skewed out)
			for (Integer n: ideal.exteriorChildren()){
				boolean parentsSkewed = true;
				for (Integer p: ideal.graph.parentList.get(n)){
					if (ideal.labels[p] != null){
						parentsSkewed = false;
						break;
					}
				}
				if (parentsSkewed){ this.interiorUnlabeledNodes.add(n); }
			}
		}
		
		SemiLabeledIdeal (Ideal ideal, HashSet<Integer> interiorUnlabeledNodes, HashSet<Integer> labeledNodes, Integer maxNumber, Integer[] labels){
			this.ideal = ideal;
			this.interiorUnlabeledNodes = interiorUnlabeledNodes;
			this.labeledNodes = labeledNodes;
			this.maxNumber = maxNumber;
			this.labels = labels;
		}
		
		SemiLabeledIdeal labelNodes (List<Integer> nodes){
			
			//clone necessary elements
			HashSet<Integer> interiorUnlabeledNodes = (HashSet<Integer>)this.interiorUnlabeledNodes.clone();
			HashSet<Integer> labeledNodes = (HashSet<Integer>)this.labeledNodes.clone();
			Integer[] labels = this.labels.clone();
			
			Integer label = this.maxNumber + 1;
			
			for (Integer n: nodes){
				labels[n] = label;
				labeledNodes.add(n);
				interiorUnlabeledNodes.remove(n);
			}
			
			//add children whose parents are all labeled or skewed out 
			for (Integer n: nodes){
				for (Integer c: ideal.graph.adjacencyList[n]){
					if (!labeledNodes.contains(c)){
						boolean parentsFinished = true;
						for (Integer p: ideal.graph.parentList.get(c)){
							if  (!labeledNodes.contains(p) && !ideal.emptyNodes.contains(p)){
								parentsFinished = false;
								break;
							}
						}
						if (parentsFinished){
							interiorUnlabeledNodes.add(c);
						}
					}
				}
			}
			
			return new SemiLabeledIdeal ( ideal, interiorUnlabeledNodes, labeledNodes, this.maxNumber + 1, labels);
		}
		
		SubsetIterator<Integer> interiorUnlabeledSubsetIterator (){
			List<Integer> children = new ArrayList(interiorUnlabeledNodes);
			return new SubsetIterator<Integer> (children);
		}
		
		void display(){
			System.out.println("SemiLabeledIdeal");
			System.out.println("interior: " + interiorUnlabeledNodes.toString());
			System.out.println("labels: " + Arrays.toString(labels));
			
		}
	}
	
	class SemiLabeledIdealIteratorTuple{
		SemiLabeledIdeal ideal;
		SubsetIterator<Integer> iterator;
		
		 SemiLabeledIdealIteratorTuple(SemiLabeledIdeal ideal){
			 this.ideal = ideal;
			 this.iterator = ideal.interiorUnlabeledSubsetIterator();
		 }
		 
		 SemiLabeledIdealIteratorTuple(SemiLabeledIdeal ideal, SubsetIterator<Integer> iterator){
			 this.ideal = ideal;
			 this.iterator = iterator;
		 }
		 
	}
	
	Ideal ideal;
	Stack<SemiLabeledIdealIteratorTuple> stk;
	
	LabeledSkewGraphIterator (Ideal ideal){
		this.ideal = ideal;
		this.stk = new Stack<SemiLabeledIdealIteratorTuple>();
		
		SemiLabeledIdeal emptyIdeal = new SemiLabeledIdeal(ideal);
		SemiLabeledIdealIteratorTuple t = new SemiLabeledIdealIteratorTuple(emptyIdeal);
		
		stk.push(t);
	}
	
	LabeledSkewGraph next(){
		while (!stk.isEmpty()){
			SemiLabeledIdealIteratorTuple t = stk.pop();
			SemiLabeledIdeal ideal =  t.ideal;
			SubsetIterator<Integer> iterator = t.iterator;
			
			
			if (iterator.hasNext()){  
				List<Integer> nodesToAdd = iterator.next();
				//ideal.display();
				//System.out.println("nodesToAdd: " + nodesToAdd.toString());
				SemiLabeledIdeal newIdeal = ideal.labelNodes(nodesToAdd);
				//newIdeal.display();
				//System.out.println();
				
				if (newIdeal.interiorUnlabeledNodes.isEmpty()){
					stk.push(t);
					LabeledSkewGraph labeledGraph = new LabeledSkewGraph(this.ideal.graph, newIdeal.labels);
					return labeledGraph;
				} else {
					stk.push(t);
					stk.push(new SemiLabeledIdealIteratorTuple(newIdeal));
				}
			}

		}
		return null;
	}
}