// ----
// Sets
// ----

import java.util.*;

public final class Sets
{
    // ------
    // equals
    // ------

    /**
     * O(1) in space<br>
     * O(n^2) in time<br>
     * Check to see if two sets are equal.
     * <br>pre conditions: a != null && b != null.
     * @param a A set to check for equality against 'b'
     * @param b Another set
     * @see Sets.member()
     * @return true if set 'a' equals set 'b', false otherwise.
     */
    public static boolean equals(long[] a, long[] b)
    {
    	assert (a != null && b != null): "Violation of precondition: Sets.equals()";
    	
    	// if the sets point to the same array, then they are the same.
    	if(a == b)
    		return true;
    	
    	// if the lengths arent the same, then the sets cannot be the same.
    	if(a.length != b.length)
    		return false;
    	
    	// loop through both sets
    	// note that a.length == b.length
    	for(int i = 0; i < a.length; i++)
    		if( !member(a, b[i]) || !member(b, a[i]) ) // if we find a element that in one set, but is not in
    			return false;						  // the other, then the sets are not equal
    	
    	// all elements are found in both sets, so return true
    	return true;
    }

    // ------
    // member
    // ------

    /**
     * O(1) in space<br>
     * O(n) in time<br>
     * Check to see if an element 'v' is a member of the set 'a' (Linear Search).
     * <br>pre conditions: a != null.
     * @param a A set to look for 'v'
     * @param v A long that we are looking for in 'a'
     * @return true If 'v' is a member of 'a', false otherwise.
     */
    public static boolean member(long[] a, long v)
    {
    	assert (a != null): "Violation of precondition: Sets.member()";
    	
    	if(a.length == 0)
    		return false;
    	
    	// loop through set 'a' searching for 'v' (linear search)
        for(int i = 0; i < a.length; i++)
        	if( a[i] == v )		// check to see if we have found 'v'
        		return true;
        
        // we did not find 'v' in 'a', so return false
        return false;
    }

    // ------
    // subset
    // ------

    /**
     * O(1) in space<br>
     * O(n^2) in time<br>
     * Check to see if set 'a' is a subset of set 'b'
     * <br>pre conditions: a != null && b != nul
     * @param a A set
     * @param b Another set
     * @return true if 'a' is a subset of 'b', false otherwise
     */
    public static boolean subset(long[] a, long[] b) 
    {
    	assert (a != null && b != null): "Violation of precondition: Sets.subset()";
    	
    	//(1)if set 'a' and set 'b' reference the same array, then it is the same set and is its own subset :)
    	//(2)if 'a' is empty, then by definition it is in 'b'
    	if( a == b || a.length == 0 )
    		return true;

    	// if 'a' is larger than 'b', then 'a' is not a subset of 'b'
    	if(a.length > b.length)
    		return false;
    	
    	// loop through set 'a' and check to make sure each element in this set is in set 'b'
    	for(int i = 0; i < a.length; i++)
    		if( !member(b, a[i]) )		// if a[i] is not in set 'b', then 'a' is NOT a subset of 'b'
    			return false;
    	
    	// all elements in 'a' are in 'b', so 'a' is a subset of 'b'
    	return true;
    }

    // ------------
    // properSubset
    // ------------

    /**
     * O(1) in space<br>
     * O(n^2) in time<br>
     * Check to see if 'a' is a proper subset of 'b'<br>
     * <br>pre conditions: a != null && b != null
     * @param a A set
     * @param b Another set
     * @return true if 'a' is a proper subset of 'b', false otherwise.
     */
    public static boolean properSubset(long[] a, long[] b)
    {
    	assert (a != null && b != null): "Violation of preconditions: Sets.properSubsets()";
    	
        return subset(a, b) && !equals(a, b);
    }

    // ----------
    // difference
    // ----------

    /**
     * O(1) in space<br>
     * O(n^2) in time<br>
     * Stores the difference of 'a' and 'b' ('a' - 'b') in x.<br>
     * <br>pre conditions: a != null && b != null && x != null<br>
     * @param a The set A in the expression: X = A - B
     * @param b The set B in the expression: X = A - B
     * @param x The set X in the expression: X = A - B
     */
    public static void difference(long[] a, long[] b, long[] x)
    {
    	assert (a != null && b != null && x != null): "Violation of preconditions: Sets.difference()";
    	
    	int c = 0;	// this tell us where in x[] we are
    	
    	// loop through a[] and checking to see if a[i] is NOT in b[]
    	for(int i = 0; i < a.length; i++)
    		if( !member(b, a[i]) )	// if a[i] is not in b, then we add it to x[]
    			x[c++] = a[i];
    }

    // ------------
    // intersection
    // ------------

    /**
     * O(1) in space<br>
     * O(n^2) in time<br>
     * Stores the intersection of 'a' and 'b' in x.<br>
     * <br>pre conditions: a != null && b != null && x != null<br>
     * @param a The set 'A' in the expression X = A and B
     * @param b The set 'B' in the expression X = A and B
     * @param x The set 'X' in the expression X = A and B
     */
    public static void intersection(long[] a, long[] b, long[] x)
    {
    	assert (a != null && b != null && x != null): "Violation of preconditions: Sets.intersection()";
    	
        int c = 0; // this tell us where in x[] we are
        
        // loop through a[]
        for(int i = 0; i < a.length; i++)
        	if( member(b, a[i]) )	// is a[i] also in b[] ?
        		x[c++] = a[i];	// if so, then add it to x[]
    }

    // -----
    // union
    // -----

    /**
     * O(1) in space<br>
     * O(n) in time<br>
     * Store the union of 'a' and 'b' in x. In other words, x = a or b<br>
     * <br>pre conditions: a != null && b != null && x != null
     * @param a The set 'A' in the expression X = A or B
     * @param b The set 'B' in the expression X = A or B
     * @param x The set 'X' in the expression X = A or B
     */
    public static void union(long[] a, long[] b, long[] x)
    {
    	assert (a != null && b != null && x != null): "Violation of preconditions: Sets.union()";
    	
    	// go through all the elements in a[] and save them in x[]
    	for(int i = 0; i < a.length; ++i )
    		x[i] = a[i];
    	
    	int t = 0;	// keep track of where we are in x[]
    	
    	// loop through b[] and save those elements that are not already in x[] in x[]
    	for(int i = 0; i < b.length; i++)
    		if( !member(x, b[i]) ) {
    			x[t + a.length] = b[i];
    			t++;	// increment where the next value would be
    		}
    }

    // -------------------
    // symmetricDifference
    // -------------------

    /**
     * O(1) in space<br>
     * O(n) in time<br>
     * Store the symmetric difference of 'a' and 'b' in 'x'
     * <br>pre conditions: a != null && b != null && x != null<br>
     * @param a The set 'A' in the expression X = A sym_diff B
     * @param b The set 'B' in the expression X = A sym_diff B
     * @param x The set 'X' in the expression X = A sym_diff B
     */
    public static void symmetricDifference(long[] a, long[] b, long[] x)
    {
    	assert (a != null && b != null && x != null): "Violation of preconditions: Sets.symmetricDifference()";
       
    	int t = 0;	// tell us where we are in x[]
    	
    	// loop through the elements of a[]
    	for(int i = 0; i < a.length; ++i)
    		if( !member(b, a[i]) )	// store only those elements from a[] that are not in b[]
    			x[t++] = a[i];
    	
    	// loop through the elements of b[]
    	for(int i = 0; i < b.length; ++i)
    		if( !member(a, b[i]) )	// do the same; store only those element in b[] that are not in b[]
    			x[t++] = b[i];
    }

    // ----------------
    // cartesianProduct
    // ----------------

    /**
     * O(1) in space<br>
     * O(n) in time<br>
     * Store the cartesian product of 'a' and 'b' in 'x'
     * <br>pre conditions: a != null && b != null && x != null
     * @param a The set 'A' in the expression X = AxB
     * @param b The set 'B' in the expression X = AxB
     * @param x The set 'X' in the expression X = AxB
     */
    public static void cartesianProduct(long[] a, long[] b, long[][] x)
    {
    	assert (a != null && b != null && x != null): "Violation of preconditions: Sets.cartesianProduct()";
    	
        for(int i = 0; i < a.length * b.length; i++) // we must allocate enough memory based on set 'a' abd 'b'
            x[i] = new long[2];
        
        int t = 0;	// keep track of where in 'x' we are
    	 
        for(int i = 0; i < a.length; i++)	// loop through every element of 'a'
        	for(int j = 0; j < b.length; j++) {	// loop through every element of 'b'
        		x[t][0] = a[i];	// form a pair 
                x[t++][1] = b[j];
            }
         
    }

    // --------
    // powerSet
    // --------

    /**
     * O(1) in space<br>
     * O(n) in time<br>
     * Store the power set of 'a' in 'x'<br>
     * <br>pre conditions: a != null && x != null
     * @param a A set
     * @param x The power set of 'a'
     */
    public static void powerSet(long[] a, long[][] x)
    {
    	assert (a != null && x != null): "Violation of preconditions: Sets.powerSet()";
    	
    	
    	int limit = (int)Math.pow(2, a.length);	// specify the length for which the size of the power set will be, ie 2^|a|
    	
    	// loop from 0 - limit
    	for(int i = 0; i < limit; ++i) {
    		String bitString = Integer.toBinaryString(i);	// convert i to a bit string
    		//System.out.println(bitString);
    		
    		bitString = new StringBuffer(bitString).reverse().toString();	// reverse that bit string
    		
    		ArrayList<Long> tmp = new ArrayList<Long>();	// its elements symbolizes a subset of the power set of a[]
    		
    		/*
    		 * loop through the reversed bit string
    		 * for each '1' in the reversed bit string, we know what the location for where the '1' is in, we must place the element of 'a' in a subset
    		 */
    		for(int j = 0; j < bitString.length(); j++)
    			if( bitString.charAt(j) == '1')		// is the current position in the reversed bit string a '1' ?
    				tmp.add( (long)a[j] );		// if so, then add the element in locaion j of a[] in our temporary ArrayList
    		
    		x[i] = new long[tmp.size()];	// create a subset in x[] big enough to hold our recently computed subset
    		
    		// loop through the ArrayList storing the values of it in x[i]
    		for(int j = 0; j < tmp.size(); j++)
    			x[i][j] = tmp.get(j);

    	}
    		
    }
}