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

public class URTsTuple {
	HashSet<ArrayList<Integer>> possibles;
	HashSet<ArrayList<Integer>> impossibles;
	
	URTsTuple (){
		this.possibles = new HashSet<ArrayList<Integer>>();
		this.impossibles = new HashSet<ArrayList<Integer>>();
	}
	
	public static Comparator<ArrayList<Integer>> ShapeComparator
    = new Comparator<ArrayList<Integer>>() {
		public int compare(ArrayList<Integer> a, ArrayList<Integer> b){
			for (int i = 0; i < a.size() && i < b.size(); i++){
				boolean aNull = a.get(i) == null;
				boolean bNull = b.get(i) == null;
				if (aNull && ! bNull) { return -1;}
				if (!aNull && bNull) { return 1;}
			}
			for (int i = 0; i < a.size() && i < b.size(); i++){
				Integer ai = a.get(i);
				Integer bi = b.get(i);
				if (ai != null && bi != null){
					if (ai != bi){
						return ai > bi ? 1 : -1;
					}
				}
			}
			if (a.size() < b.size()) { return 1;}
			return 0;
		}
	};
	
	public static boolean sameShape (ArrayList<Integer> a, ArrayList<Integer> b){
		if (a == null | b == null) { return true;}
		if (a.size() != b.size()){return false;}
		for (int i = 0; i < a.size(); i++){
			boolean aNull = a.get(i) == null;
			boolean bNull = b.get(i) == null;
			if (aNull && ! bNull || !aNull && bNull) { return false;}
		}
		return true;
	}
	
	void display(){
		ArrayList<ArrayList<Integer>> urts = new ArrayList<ArrayList<Integer>>(this.possibles);
		Collections.sort(urts, URTsTuple.ShapeComparator);
		ArrayList<Integer> prev = null;
		for (ArrayList<Integer> s: urts){
			if (!URTsTuple.sameShape(s, prev)){
				System.out.println();
			}
			System.out.println(s);
			prev = s;
		}
		int rects = urts.size();
		System.out.println(urts.size());
		System.out.println("NONRECTS");
		
		urts = new ArrayList<ArrayList<Integer>>(this.impossibles);
		Collections.sort(urts, URTsTuple.ShapeComparator);
		prev = null;
		for (ArrayList<Integer> s: urts){
			if (!URTsTuple.sameShape(s, prev)){
				System.out.println();
			}
			System.out.println(s);
			prev = s;
		}
		System.out.println(rects);
		System.out.println(urts.size());
	}
	
	void countDisplay(){
		System.out.println("URTS: " + possibles.size() + ", Non-URTs: " + impossibles.size());
	}
	
	boolean hasAllShapes(Graph g){
		IdealIterator idealIterator = new IdealIterator(g);
		ArrayList<ArrayList<Integer>> urts = new ArrayList<ArrayList<Integer>>(this.possibles);
		Collections.sort(urts, URTsTuple.ShapeComparator);
		while(true){
			Ideal ideal = idealIterator.next();
			if (ideal == null) break;
			ArrayList<Integer> labels = new ArrayList<Integer>();
			for (Integer n : ideal.labels){
				labels.add(n == null ? 0 : null);
			}
//			System.out.println("labels: " + labels.toString());
			int insertionPoint = (-1)*(Collections.binarySearch(urts, labels, URTsTuple.ShapeComparator) + 1);
//			System.out.println(insertionPoint);
//			if (insertionPoint > 0){	
//				System.out.println("prev: " + urts.get(insertionPoint -1).toString());
//			} else {
//				System.out.println("prev: ");
//			}
//			if (insertionPoint < urts.size()){
//				System.out.println("next: " + urts.get(insertionPoint).toString());
//			} else {
//				System.out.println("next: ");
//			}
			if (insertionPoint < urts.size() && !sameShape(labels, urts.get(insertionPoint))){
				return false;
			}
		}
		return true;
	}
	
	boolean hasMinimalFillings (Graph g){
		IdealIterator idealIterator = new IdealIterator(g);
		while(true){
			Ideal ideal = idealIterator.next();
			if (ideal == null) break;
			if (ideal.emptyNodes.size() != ideal.graph.adjacencyList.length && !this.possibles.contains(ideal.minimalFilling())){
				System.out.println(Arrays.toString(ideal.labels));
				System.out.println(ideal.minimalFilling());
				return false;
			}
		}
		return true;
	}
}