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

public class LabeledSkewGraph {
	
	/*Note: The zero element in the adjacency list MUST be the minimal one!*/
	Graph graph;
	Integer [] labels; //the labeling of our poset
	
	HashSet<Integer> innerCorners;
	HashSet<Integer> emptyCorners;
	ArrayList<List<Integer>> dotPath;
	
	LabeledSkewGraph (Graph graph,  Integer [] labels){
		this.graph = graph;
		this.labels = labels;
		
		innerCorners = new HashSet<Integer>();
		emptyCorners = new HashSet<Integer>();
		dotPath = new ArrayList<List<Integer>>();
		
		//sets up inner corners and empty corners
		setInnerCorners();
	}
	
	LabeledSkewGraph (Graph graph, Integer [] labels, HashSet<Integer> innerCorners, HashSet<Integer> emptyCorners, ArrayList<List<Integer>> dotPath){
		this.graph = graph;
		this.labels = labels;
		this.innerCorners = innerCorners;
		this.emptyCorners = emptyCorners;
		this.dotPath = dotPath;
	}
	
	//finds and sets inner corners and empty corners
	void setInnerCorners(){
		
		//do this in DFS manner
		Stack<Integer> stk = new Stack<Integer>();
		stk.push(0);
		
		while(!stk.isEmpty()){
			Integer v = stk.pop();
			
			//add to empty corners if empty
			if (labels[v] == null){
				emptyCorners.add(v);
			}
			
			//if empty and has children, see if all filled
			if (labels[v] == null){
				//check to see if all children are filled
				Boolean filledChildren = true;
				for (Integer c: graph.adjacencyList[v]){
					if (labels[c] == null){
						filledChildren = false;
						stk.push(c);
					}
				}
				//add if all children are filled
				if (filledChildren){
					innerCorners.add(v);
				}
			}
		}
		
	}
	
	//gets a list of the minimum children of the node (use in dot swapping)
	ArrayList<Integer> getMinimumChildren (Integer vertex, Integer[] labels){
		Integer min = null;
		ArrayList<Integer> minimumChildren = new ArrayList<Integer>();
		
		for (Integer c: graph.adjacencyList[vertex]){
			Integer value = labels[c];
			if (value != null){
				if (min == null || value < min){
					min = value;
					minimumChildren = new ArrayList<Integer>();
					minimumChildren.add(c);
				} else if (value == min){
					minimumChildren.add(c);
				}
			}
		}
		return minimumChildren;
	}
	
	
	//outputs all possible rectifications of this Skewed Graph
	ArrayList<LabeledSkewGraph> rectify(){
		
		//Set up stack to hold graphs we create
		Stack <LabeledSkewGraph> stk = new Stack<LabeledSkewGraph>();
		//hash the graphs we have inserted to the stack, so we don't repeat work
		HashSet<String> insertedGraphs = new HashSet<String>();
		//keep the list of the final rectifications of the graph
		ArrayList<LabeledSkewGraph> rectifiedGraphs = new ArrayList<LabeledSkewGraph>();
		
		//add our original graph to the stack and hashSet
		ArrayList<List<Integer>> emptyDotPath = new ArrayList<List<Integer>> ();
		stk.add(new LabeledSkewGraph(graph, labels, innerCorners, emptyCorners, emptyDotPath));
		insertedGraphs.add(Arrays.toString(labels) + innerCorners.toString());
		
		//graphs are removed from stack when they have no  more inner corners
		while (!stk.isEmpty()){
			LabeledSkewGraph rg = stk.pop();
			
			//if no more inner corners, then add it to our finished list
			//no need to have continue statement, because next for loop doesn't run
			if (rg.innerCorners.size() == 0){
				rectifiedGraphs.add(rg);
			}
			
//			System.out.println("pre-swaps");
//			rg.display();
			
			//loop through all the inner corners of this graph and create the rectifications from choosing each one
			List<Integer> innerCornerList = new ArrayList<Integer> (rg.innerCorners);
			SubsetIterator<Integer> it = new SubsetIterator<Integer>(innerCornerList);
			while (it.hasNext()){
				
				List<Integer> selectedIcs = it.next();
				
				//create new InnerCorners, emptyCorners, dotpath, and labels (cloned so we can change them)
				HashSet<Integer> innerCorners = (HashSet<Integer>)rg.innerCorners.clone();
				HashSet<Integer> emptyCorners = (HashSet<Integer>)rg.emptyCorners.clone();
				ArrayList<List<Integer>> dotPath = (ArrayList<List<Integer>>) rg.dotPath.clone();
				Integer[] labels = rg.labels.clone();
				
				//add selectedIcs to dot path
				dotPath.add(selectedIcs);
				
				//remove all selected inner corners
				for (Integer ic: selectedIcs){
					innerCorners.remove(ic);
					emptyCorners.remove(ic);
				}
				
				
				//add dots and keep swapping
				HashSet<Integer> dots = new HashSet<Integer>();
				for (Integer ic: selectedIcs){
					dots.add(ic);
				}

				while (dots.size() != 0){
					ArrayList<Integer> dotsToRemove = new ArrayList<Integer>();
					ArrayList<Integer> dotsToAdd = new ArrayList<Integer>();
					Integer min = null;
					for (Integer dot : dots){
						for (Integer c: graph.adjacencyList[dot]){
							Integer value = labels[c];
							if (value != null){
								if (min == null || value < min){
									min = value;
									dotsToAdd = new ArrayList<Integer>();
									dotsToRemove = new ArrayList<Integer>();
									dotsToAdd.add(c);
									dotsToRemove.add(dot);
								} else if (value == min){
									dotsToAdd.add(c);
									dotsToRemove.add(dot);
								}
							}
							
						}
					}
					if (min == null){
						break;
					}
					for (Integer dot: dotsToRemove){
						labels[dot] = min;
						dots.remove(dot);
					}
					
					for (Integer dot: dotsToAdd){
						labels[dot] = null;
						dots.add(dot);
					}
					
				}
				
				//add parents of selected inner corners if need be
				for (Integer ic: selectedIcs){
					for(Integer icParent: graph.parentList.get(ic)){
						boolean childrenFilled = true;
						for(Integer icParentChild : graph.adjacencyList[icParent]){
							if (emptyCorners.contains(icParentChild)){
								childrenFilled = false;
								break;
							}
						}
						if (childrenFilled){
							innerCorners.add(icParent);
						}
					}
				}
				
//				RectifiedGraph newRgp = new RectifiedGraph(labels, innerCorners, emptyCorners);
//				newRgp.display();
				
				//add new graph to stack and hashset if need be
				if (!insertedGraphs.contains(Arrays.toString(labels) + innerCorners.toString())){
					//System.out.println("selectedIcs: " + selectedIcs.toString());
					//rg.display();
					LabeledSkewGraph newRg = new LabeledSkewGraph(graph, labels, innerCorners, emptyCorners, dotPath);
					//newRg.display();
					//System.out.println();
					insertedGraphs.add(Arrays.toString(labels) + innerCorners.toString());
					stk.add(newRg);
				}
				
			}
		}
//		System.out.println("hashes");
//		
//		for (String labels : insertedGraphs){
//			System.out.println(labels);
//		}
//		System.out.println("rectifications");
//		for (LabeledSkewGraph rg : rectifiedGraphs){
//			rg.display();
//		}
		
		return rectifiedGraphs;

	}
	
	void display(){
		System.out.println("Final labeling:  " + Arrays.toString(labels));
		System.out.println("dot Path: " + dotPath.stream().map(Object::toString)
                .collect(Collectors.joining(", ")));
		System.out.println(emptyCorners);
	}
}