Question

Complete the following case study:

Case study: Three implementations of contains - comparing approaches to adding functionality

Set A contains Set B if every element in Set B is also in Set A. We will compare three ways to determine whether Set A contains Set B.

Approach 1: Write code in the main method in a test class

Add code to the main of ArraySetTester to create SetA and SetB, fill them with data and write a contains operation that tests if SetA contains SetB.

Question: What is wrong with this approach?
Answer: While the code does the operation for the specific collections SetA and SetB, it only applies to these two collections. The code can't be used for other Sets without repeating it.

Approach 2: Write a static method in a test class

Comment out the code from approach 1.

Add a static method to ArraySetTester with prototype:

   public static boolean contains(SetADT<Integer> Set1, SetADT<Integer> Set2)

Question: Why does contains need to be static?
Answer: We aren't instantiating an object to call the contains. Therefore contains has to be associated with the ArraySetTester class itself, rather than a particular instance.

Question: Why were Set1 and Set2 declared as SetADT rather than as ArraySet?
Answer: This way the contains method can be called for any implementation of SetADT.

Approach 3: Add a prototype to the interface

Add the following prototype to the SetADT interface and add an implementation of contains to ArraySet.

   public boolean contains(SetADT<T> Set)

Question: Why is Approach 3 generally better than Approach 2?
Answer: We have associated the code for contains with the classes that need it most, i.e., if you call contains, you will need SetADT and an implementation of it. This is the object-oriented approach. We can ask the object itself whether it contains another.

ArraySet.java

package arraysetpackage;

import java.util.Iterator;

public class ArraySetTester {

   public static void main(String[] args) {
       SetADT <String> mySet = new ArraySet<String>();

       for (int i = 0; i < 12; i++)
           mySet.add(new String("apple"+i));

       System.out.println(mySet);
      
       System.out.println("mysize = "+mySet.size()+ " [expect 12]");
       mySet.add(new String ("apple0"));
       System.out.println("mysize = "+mySet.size()+ " [expect 12]");
       System.out.println("contains 11? = "+mySet.contains(new String("11")));
       System.out.println("contains apple11? = "+mySet.contains(new String("apple11")));      
      
       try {
           String removedItem = mySet.remove("apple7");
           System.out.println(mySet);
           System.out.println(removedItem+ " was removed");
       } catch (Exception e) {
           System.out.println("item not found, can't remove");
       }
      
       try {
           String removedItem = mySet.remove("apple17");
           System.out.println(mySet);
           System.out.println(removedItem+ " was removed");
       } catch (Exception e) {
           System.out.println("item not found, can't remove");
       }
      
       Iterator<String> iter = mySet.iterator();
       while (iter.hasNext()){
           System.out.println(iter.next());
       }

ArraySetIterator.java

package arraysetpackage;

import java.util.Iterator;
import java.util.NoSuchElementException;

public class ArraySetIterator <T> implements Iterator <T> {
   private int position; //Always points to the next value
   private T [] values;
   private int count;
  
  
   public ArraySetIterator (T [] theValues, int aCount) {
       position = 0;
       values = theValues;
       count = aCount;
   }
  
   public boolean hasNext() {
       return position < count;
   }
  
   public T next() {
       if (position >= count)
           throw new NoSuchElementException("Past " + count + " elements");
       position++;
       return values[position - 1];
    }
  
   public void remove() {
       throw new
       UnsupportedOperationException("No remove for ArraySet");
   }

}

ArraySetTester.java

package arraysetpackage;

import java.util.Iterator;

public class ArraySetTester {

   public static void main(String[] args) {
       SetADT <String> mySet = new ArraySet<String>();

       for (int i = 0; i < 12; i++)
           mySet.add(new String("apple"+i));

       System.out.println(mySet);
      
       System.out.println("mysize = "+mySet.size()+ " [expect 12]");
       mySet.add(new String ("apple0"));
       System.out.println("mysize = "+mySet.size()+ " [expect 12]");
       System.out.println("contains 11? = "+mySet.contains(new String("11")));
       System.out.println("contains apple11? = "+mySet.contains(new String("apple11")));      
      
       try {
           String removedItem = mySet.remove("apple7");
           System.out.println(mySet);
           System.out.println(removedItem+ " was removed");
       } catch (Exception e) {
           System.out.println("item not found, can't remove");
       }
      
       try {
           String removedItem = mySet.remove("apple17");
           System.out.println(mySet);
           System.out.println(removedItem+ " was removed");
       } catch (Exception e) {
           System.out.println("item not found, can't remove");
       }
      
       Iterator<String> iter = mySet.iterator();
       while (iter.hasNext()){
           System.out.println(iter.next());
       }

       SetADT <String> mySet2 = new ArraySet<String>();

       for (int i = 0; i < 12; i++)
           mySet2.add(new String("orange"+i));  
       System.out.println(mySet2);
      
       // add code here to test methods you finish in ArraySet
      
      
      
       // after you complete the existing methods, do the Case Study
       // Approach 1 will be here in the main
      
      
      
       // Approach 2 will be here in ArraySetTester, but you will
       // create a local static method that you will call from the main
      
       // Approach 3 will start with uncommenting the prototype in SetADT
       // and then creating the method in ArraySet. Finally you will write
       // code here to test the new method
      
   }

}

SetADT.java

package arraysetpackage;

import java.util.Iterator;

public interface SetADT<T> {
       public void add (T element); //Adds one element to this set, ignoring duplicates
       public void addAll (SetADT<T> set); //Adds all elements in the parameter to this set,
                                           // ignoring duplicates
       public T removeRandom (); //Removes and returns a random element from this set
       public T remove (T element); //Removes and returns the specified element from this set
       public SetADT<T> union (SetADT<T> set); //Returns the union of this set and the
                                               // parameter
       public boolean contains (T target); //Returns true if this set contains the parameter
       //public boolean contains(SetADT<T> Set); // Returns true if this set contains the parameter
       public boolean equals (SetADT<T> set); //Returns true if this set and the parameter
                                              //contain exactly same elements
       public boolean isEmpty(); //Returns true if this set contains no elements
       public int size(); //Returns the number of elements in this set
       public Iterator<T> iterator(); //Returns an iterator for the elements in this set
       public String toString(); //Returns a string representation of this set
}

Answer 1

import java.util.Iterator;

public class ArraySetTester {

    public static void main(String[] args) {
        SetADT <String> mySet = new ArraySet<String>();
        SetADT <String> oSet = new ArraySet<String>();
        SetADT <Integer> intSet1 = new ArraySet<Integer>();
        SetADT <Integer> intSet2 = new ArraySet<Integer>();

        for (int i = 0; i < 12; i++)
        {
            mySet.add(new String("apple"+i));
            oSet.add(new String("apple"+i + 1));
            intSet1.add(new Integer(i));
            intSet2.add(new Integer(i));
        }

        System.out.println(mySet.equals(oSet));
        System.out.println(intSet1.equals(intSet2));
        System.out.println(mySet.removeRandom());
        System.out.println(mySet.equals(oSet));
        System.out.println(mySet.union(oSet));

//   Start of provided code---------------------------------------------
//       System.out.println(mySet);
//
//       System.out.println("mysize = "+mySet.size()+ " [expect 12]");
//       mySet.add(new String ("apple0"));
//       System.out.println("mysize = "+mySet.size()+ " [expect 12]");
//       System.out.println("contains 11? = "+mySet.contains(new String("11")));
//       System.out.println("contains apple11? = "+mySet.contains(new String("apple11")));
//
//       try {
//           String removedItem = mySet.remove("apple7");
//           System.out.println(mySet);
//           System.out.println(removedItem+ " was removed");
//       } catch (Exception e) {
//           System.out.println("item not found, can't remove");
//       }
//
//       try {
//           String removedItem = mySet.remove("apple17");
//           System.out.println(mySet);
//           System.out.println(removedItem+ " was removed");
//       } catch (Exception e) {
//           System.out.println("item not found, can't remove");
//       }
//
//       Iterator<String> iter = mySet.iterator();
//       while (iter.hasNext()){
//           System.out.println(iter.next());
//       }
//
//
//
//       SetADT <String> mySet2 = new ArraySet<String>();
//
//       for (int i = 0; i < 12; i++)
//           mySet2.add(new String("orange"+i));
//       System.out.println(mySet2);
//
        // add code here to test methods you finish in ArraySet
//   End of provided code---------------------------------------------------

        // after you complete the existing methods, do the Case Study
        //Case 1
//       SetADT <String> setA = new ArraySet<String>();
//       SetADT <String> setB = new ArraySet<String>();
//       boolean found = true;
//       boolean next = false;
//
//       for (int i = 0; i < 12; i++)
//       {
//           setA.add(new String("apple"+i));
//           if (i % 2 == 0)
//           {
//               setB.add(new String("apple"+i));
//           }
//       }
//
//       Iterator<String> iterB = setB.iterator();
//
//       while(iterB.hasNext())
//       {
//           String temp = iterB.next();
//           Iterator<String> iterA = setA.iterator();
//           while(iterA.hasNext())
//           {
//               if (temp.equals(iterA.next()))
//               {
//                   next = true;
//                   break;
//               }
//           }
//           if (!next)
//           {
//               found = false;
//               break;
//           }
//       }
//       if (!found)
//       {
//           System.out.println("Set A does not contain Set B.");
//       }
//       else
//       {
//           System.out.println("Set A contains Set B.");
//       }

        // Approach 2 will be here in ArraySetTester, but you will
//       SetADT <Integer> setA = new ArraySet<Integer>();
//       SetADT <Integer> setB = new ArraySet<Integer>();
//
//       for (int i = 0; i < 12; i++)
//       {
//           setA.add(i);
//           if (i % 2 == 0)
//           {
//               setB.add(i);
//           }
//       }
//
//       System.out.println(contains(setA, setB));

        // Approach 3 will start with uncommenting the prototype in SetADT
        // and then creating the method in ArraySet. Finally you will write
        // code here to test the new method
        SetADT <String> setA = new ArraySet<String>();
        SetADT <String> setB = new ArraySet<String>();
        boolean found = true;
        boolean next = false;

        for (int i = 0; i < 12; i++)
        {
            setA.add(new String("apple"+i));
            if (i % 2 == 0)
            {
                setB.add(new String("apple"+i));
            }
        }
        System.out.println(setA.contains(setB));
    }

//public static boolean contains(SetADT<Integer> set1, SetADT<Integer> set2)
//{
//   Iterator<Integer> iter = set2.iterator();
//
//   while (iter.hasNext())
//   {
//       if (!set1.contains(iter.next()))
//       {
//           return false;
//       }
//   }
//
//   return true;
//}

}
-------------------------------------------------------------------------------------------------------------
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Random;

public class ArraySet<T> implements SetADT<T> {
    private static final int DEFAULT_SIZE = 20;
    private int count;
    private T[] setValues;
    private Random rand;

    public ArraySet (){
        this(DEFAULT_SIZE);
    } // end of constructor

    public ArraySet (int size){
        count = 0;
        setValues = (T[]) new Object[size];
        rand = new Random();
    } // end of constructor

    public void add(T element) {
        if (contains(element))
            return;
        if (count == setValues.length) {
            T[] temp = (T[]) new Object[setValues.length*2];
            for (int i = 0; i < setValues.length; i++) {
                temp[i] = setValues[i];
            }
            setValues = temp;
        }
        setValues[count] = element;
        count++;
    }

    public void addAll(SetADT<T> set)
    {
        Iterator<T> iter = set.iterator();
        while (iter.hasNext())
        {
            add(iter.next());
        }

    }

    public boolean contains(T target) {
        for (int i = 0; i < count; i++ )
            if (setValues[i].equals(target))
                return true;
        return false;
    }

    public boolean contains(SetADT<T> set)
    {
        Iterator<T> iter = set.iterator();
        boolean found = false;
        T temp;

        while (iter.hasNext())
        {
            temp = iter.next();
            for (int i = 0; i < count; i++)
            {
                if (setValues[i].equals(temp))
                {
                    found = true;
                    break;
                }
            }
            if (!found)
            {
                return false;
            }
        }

        return true;
    }

    public String toString () {
        String toReturn = "[";
        for (int i = 0; i < count; i++) {
            toReturn += setValues[i] + " ";
        }
        toReturn +="]";
        return toReturn;
    }

    public boolean equals(SetADT<T> set)
    {
        Iterator<T> iter = set.iterator();
        T temp;
        for (int i = 0; i < count; i++)
        {
            if (!iter.hasNext())
            {
                return false;
            }
            temp = iter.next();
            if (!setValues[i].equals(temp))
            {
                return false;
            }
        }
        if (iter.hasNext())
        {
            return false;
        }
        return true;
    }

    public boolean isEmpty() {
        return count==0;
    }

    public Iterator<T> iterator() {
        return new ArraySetIterator<T>(setValues,count);
    }

    public T remove(T element) {
        for (int i = 0; i < count; i++ ) {
            if (setValues[i].equals(element)) {
                T toReturn = setValues[i];
                setValues[i] = setValues[count-1];
                count--;
                return toReturn;
            }
        }
        throw new NoSuchElementException("not present");
    }

    public T removeRandom()
    {
        rand = new Random();
        int index = rand.nextInt(count);
        T tempVal = setValues[index];
        T[] tempArr = (T[]) new Object[count - 1];
        for (int i = 0; i < index; i++)
        {
            if (i != index)
            {
                tempArr[i] = setValues[i];
            }
        }
        for (int i = index; i < (count - 1); i++)
        {
            tempArr[i] = setValues[i + 1];
        }
        setValues = tempArr;
        count--;
        return tempVal;
    }

    public int size() {
        return count;
    }

    public SetADT<T> union(SetADT<T> set)
    {
        SetADT<T> toReturn = new ArraySet<T>(this.count);
        Iterator<T> iter = set.iterator();
        Iterator<T> thisIter = this.iterator();
        while (thisIter.hasNext())
        {
            toReturn.add(thisIter.next());
        }
        while (iter.hasNext())
        {
            toReturn.add(iter.next());
        }
        return toReturn;
    }

}
----------------------------------------------------------------------------------------------------------------------
import java.util.Iterator;
import java.util.NoSuchElementException;

public class ArraySetIterator <T> implements Iterator <T> {
    private int position; //Always points to the next value
    private T [] values;
    private int count;

    public ArraySetIterator (T [] theValues, int aCount) {
        position = 0;
        values = theValues;
        count = aCount;
    }

    public boolean hasNext() {
        return position < count;
    }

    public T next() {
        if (position >= count)
            throw new NoSuchElementException("Past " + count + " elements");
        position++;
        return values[position - 1];
    }

    public void remove() {
        throw new
                UnsupportedOperationException("No remove for ArraySet");
    }

}

-----------------------------------------------------------------------------------------------------------
import java.util.Iterator;

public interface SetADT<T> {
    public void add (T element);
    public void addAll (SetADT<T> set);
    public T removeRandom ();
    public T remove (T element);
    public SetADT<T> union (SetADT<T> set);
    public boolean contains (T target);
    public boolean contains(SetADT<T> set);
    //public boolean contains(SetADT<T> Set);
    public boolean equals (SetADT<T> set);
    //contain exactly same elements
    public boolean isEmpty();
    public int size();
    public Iterator<T> iterator();
    public String toString();
}