package TheoryLabs;
import java.util.*;
/**
 * Finite set of integers, used to represent sets of states in finite 
 * automata.  The elements of each IntSet are maintained in ascending order.
 * 
 * <BR><BR>Data Fields: The set of integers is stored in a sorted Vector 
 * of Integers.  
 * 
 * <BR><BR>
 * IntSet has two special methods to support conversion from NFA to DFA,  
 * based on binary arithmetic.<BR>
 * 1.  intValue() returns a uniquely-determined integer corresponding 
 *     to this IntSet (assuming all elements are >= 0).<BR>
 *     Example: intValue of [1,3,4] = 2^1 + 2^3 + 2^4 = 33.<BR>
 * 2.  setValue(int n) takes a non-negative integer n and 
 *     returns a uniquely-determined Intset corresponding
 *     to n.<BR>
 *     Example: setValue of 17 is [0,4] because 17 = 2^0 + 2^4.
 *     
 * @author Barbara Wahl
 * @version Fall 2007
 */
public class IntSet {
	
	// ** DATA FIELDS **	
	/**
	 * stores the int values as Integers
	 */
	protected Vector data;  
	
	// ** CONSTRUCTORS **
	/**
	 * 0-parameter constructor.
	 * @post constructs an empty IntSet
	 */
	public IntSet()
	{
		data = new Vector();		
	}
	
	/**
	 * 1-parameter constructor.  Creates a set with one element.
	 * @param n the element to be included in this IntSet
	 * @post constructs a new IntSet with one element, n
	 */
	public IntSet(int n)
	{
		this();
		data.add(new Integer(n));
	}
	
	/**
	 * Copy constructor.
	 * @param current the Intset to be copied
	 * @pre current is not null
	 * @post constructs a new intSet via deep copy of current
	 */
	public IntSet(IntSet current)
	{
		// deep copy of Vector current.data
		data = new Vector();
		for(int i=0; i<current.data.size(); i++)
		{
			Integer theInteger = (Integer)current.data.elementAt(i);
			int theValue = theInteger.intValue();
			data.add(new Integer(theValue));
		}
	}
	
	/**
	 * Returns the int value of the ith element of this IntSet.
	 * @param i index
	 * @return int value of the ith element
	 * @pre 0 <= i < data.size()
	 */
	public int elementAt(int i)
	{
		Assert.pre(0 <= i && i < data.size(),"0 <= i < data.size()");
		return ((Integer) data.elementAt(i)).intValue();
	}
	
	/**
	 * Returns number of elements in this IntSet.
	 * @return data.size()
	 */
	public int size()
	{
		return data.size();
	}	
	
	/**
	 * Returns true if this IntSet is empty.
	 * @return data.isEmpty()
	 */
	public boolean isEmpty()
	{
		return data.isEmpty();
	}
	
	/**
	 * Returns the minimum element.
	 * @return smallest element in this IntSet
	 * @pre this IntSet is not empty
	 */public int min()
	{
		Assert.pre(!this.isEmpty(),"this IntSet is not empty");
		return elementAt(0);
	}
	 
	/**
	* Returns the maximum element.
	 * @return largest element in this IntSet
	 * @pre this IntSet is not empty
	 */public int max()
	{
		 Assert.pre(!this.isEmpty(),"this IntSet is not empty");
		return elementAt(size() - 1);
	}
	 
	/**
	 * Returns a String representation of this IntSet using 
	 * square brackets and commas.
	 * @return data.toString()
	 */
	public String toString()
	{
		return data.toString();
	}
	
	/**
	 * Returns true if a given integer is in this IntSet.
	 * @param n integer to be searched for
	 * @return true iff n is in this IntSet
	 */
	public boolean contains(int n)
	{
		return data.contains(new Integer(n));
	}
	
	/**
	 * Returns index (position) of a given integer in this IntSet.
	 * @param n integer to be searched for
	 * @return index of n in data, or -1 if not found
	 */
	public int indexOf(int n)
	{
		return data.indexOf(new Integer(n));
	}
		
	/**
	 * Adds a given integer to this IntSet.
	 * @param n integer to be added
	 * @post n is added to this IntSet (unless it is already present)
	 * @post the underlying vector (data) is maintained in ascending order
	 */	
	public void add(int n)
	{
		if(this.contains(n)) // do nothing in this case
			return; 	
		
		int pos;           // position in data Vector
		Integer current;   // element in data Vector
		
		// find location for inserting n
		for(pos=0; pos<data.size(); pos++)		
		{   // keep looking until element at pos is > n
			current = (Integer)data.elementAt(pos);
			if(current.intValue() > n) break;
		}
		this.data.insertElementAt(new Integer(n),pos);
	}
	
	/**
	 * Removes a given integer from this IntSet.
	 * @param n integer to be removed
	 * @post if found, n is removed from this IntSet
	 */
	public void remove(int n)
	{
		data.remove(new Integer(n));
	}
	
	/**
	 * Adds all the elements of "other" to this IntSet, forming
	 * the union.
	 * @param other set to be unioned with this IntSet
	 * @return set union of "this" and "other" (no repetitions, 
	 * ascending order)
	 * @pre other is not null
	 * @post this IntSet is changed (unless other is a subset of this)
	 */
	public IntSet union(IntSet other)
	{
		// add elements of "other" to "this" & return
		for(int i=0; i<other.size(); i++)
			this.add(other.elementAt(i));
		return this;
	}
	
	/**
	 * Returns true if "this" is a subset of "other".
	 * @param other the potential superset
	 * @pre other is not null
	 * @return true iff every element of this IntSet is also in other
	 */
	public boolean subsetOf(IntSet other)
	{
		// for efficiency, return false if this is larger than other
		if(this.size() > other.size()) 
			return false;
		
		// return false if find element of this not in other
		for(int i=0; i<this.size(); i++)
			if(!other.contains(this.elementAt(i)))
				return false;	

		return true;
	}
	
	/**
	 * Returns true if other has exactly the same elements as this IntSet.
	 * @param other the IntSet with which this will be compared
	 * @return true iff containment holds each way
	 * @pre other is a non-null IntSet
	 */
	public boolean equals(Object other)
	{
		// cast other as an explicit IntSet object
		IntSet that = (IntSet) other;
		
		// return false if unequal size
		if(this.size() != that.size())
			return false;
		
		// do pairwise comparison to look for mismatch 
		for(int i=0; i<this.size(); i++)
			if(this.elementAt(i) != that.elementAt(i))
				return false;
		
		return true;
	}
	
	/**
	 * Returns a unique non-negative integer (bijection from finite subsets 
	 * of W to W) determined by this set of non-negative integers.
	 * @return sum of 2^i where i varies over the elements of this IntSet
	 * @pre this IntSet is non-null and has no negative values
	 */
	public int intValue()
	// For example, the "intValue" of [0,2,3] is 2^0 + 2^2 + 2^3 = 13.
	{
		int val = 0;
		if(this.isEmpty())
			return val;
		
		Assert.pre(this.min() >= 0,"this IntSet has no negative values");		
		for(int i = 0; i<this.size(); i++) 		
		{
			int j = this.elementAt(i);    // for each int j in this.data...
			val = val + Util.twoPower(j); // increase val by 2^j
		}
		return val;
	}
	
	/**
	 * Calculates a unique IntSet of non-negative integers corresponding
	 * a given integer i >= 0 (bijection from W to finite subsets of W).
	 * @param i the integer to be converted to an IntSet
	 * @return IntSet determined by expressing i in binary notation; 
	 * if the bit in the 2^j place is non-zero then j is placed in the 
	 * IntSet
	 */
	public static IntSet setValue(int i)
	// For example, if i = 13 then i = 1101 = 2^0 + 2^2 + 2^3, so
	// the corresponding IntSet is [0,2,3].
	{
		// FIRST, find the binary digits to represent i in base 2;		
		// 1+(log-base-two of i+2) is used to determine 
		// a sufficient number of digits for i in base 2
		int numDigits = 1+ Util.intLogTwo(i+2);		
		int rem = i;                  // remainder to be processed
		int[] a = new int[numDigits]; // array for the digits, initially all zero
		
		for(int j=0; j<numDigits; j++)
		{
			a[j] = rem % 2;	// jth digit from right is remainder on 
			                // division by 2			
			rem = rem/2;    // reduce remainder by a factor of 2 & continue
		}	
		
		// SECOND, convert the bits to a subset of the non-negative integers;
		// each non-zero bit corresponds to an element of the IntSet
		IntSet set = new IntSet();  
		for(int j=0; j<numDigits; j++)
			if(a[j]==1)	set.add(j);
		return set;
	}
	
	// ** TESTING METHOD **
	public static void main(String args[])
	{
		// exercise both constructors & add
		IntSet A = new IntSet();
		A.add(5); A.add(2); A.add(1); A.add(25);A.add(25);A.add(25);A.add(25);
		IntSet B = new IntSet();
		B.add(25); B.add(1); B.add(2); B.add(5);
		IntSet C = new IntSet(3);
		C.add(1); C.add(20);
		IntSet D = new IntSet(1);
		D.add(3); D.add(4);
		IntSet E = new IntSet(2);
		E.add(25); E.add(1); E.add(2); E.add(2); E.add(5);
		IntSet F = new IntSet(); // empty set
				
		// use toString, verify add working correctly
		System.out.println("A contains: " + A.toString());
		System.out.println("B contains: " + B.toString());
		System.out.println("C contains: " + C.toString());
		System.out.println("D contains: " + D.toString());
		System.out.println("E contains: " + E.toString());
		System.out.println("F contains: " + F.toString());
		
		// size
		System.out.println("A.size() = " + A.size());
		System.out.println("B.size() = " + B.size());
		System.out.println("C.size() = " + C.size());
		System.out.println("D.size() = " + D.size());
		System.out.println("E.size() = " + E.size());
		System.out.println("F.size() = " + F.size());
		
		// contains
		System.out.println("Does A contain 1? " + A.contains(1));
		System.out.println("Does B contain 7? " + B.contains(7));
		System.out.println("Does C contain 20? " + C.contains(20));
		System.out.println("Does D contain 5? " + D.contains(5));
		System.out.println("Does F contain 2? " + F.contains(2));
		
		// elementAt
		System.out.println("A.elementAt(1) = " + A.elementAt(1));
		System.out.println("C.elementAt(0) = " + C.elementAt(0));
		System.out.println("E.elementAt(2) = " + E.elementAt(2));	
		
		// equals
		System.out.println("Does A equal B? " + A.equals(B));
		System.out.println("Does A equal C? " + A.equals(C));
		System.out.println("Does C equal D? " + C.equals(D));
		System.out.println("Does A equal E? " + A.equals(E));
		System.out.println("Does A equal A? " + A.equals(E));
		System.out.println("Does F equal E? " + F.equals(E));
		System.out.println("Does F equal F? " + F.equals(F));
		
		// union
		System.out.println("A union B = " + A.union(B));
		System.out.println("C union D = " + C.union(D));
		System.out.println("F union E = " + F.union(E));
		
		// show how union changes the original sets
		System.out.println("A contains: " + A.toString());
		System.out.println("B contains: " + B.toString());
		System.out.println("C contains: " + C.toString());
		System.out.println("D contains: " + D.toString());
		System.out.println("E contains: " + E.toString());
		System.out.println("F contains: " + F.toString());
		
		// create an array of IntSets for testing
		IntSet[] array = new IntSet[6];
		array[0] = new IntSet(0); // {0}
		array[1] = new IntSet(1);
		array[1].union(new IntSet(3)); // {1,3}
		array[2] = new IntSet(2); // {2}
		array[3] = new IntSet(2);
		array[3].union(array[1]); // {1,2,3}
		array[4] = new IntSet(0);
		array[4].union(array[1]); // {0,1,3}
		array[5] = new IntSet(5);
		array[5].union(array[1]); // {1,3,5}
		
		// test intValue
		for(int i = 0; i<6; i++) // for each IntSet in array		
			System.out.println("The int value of " + array[i] + 
				" is " + array[i].intValue());
	
		// test setValue
		for(int i=0; i<30; i=i+5)
			System.out.println("The IntSet corresponding to i = " +
				i + " is " + setValue(i));
	
	}
}