Question

Using Java

The given class SetInterface.java is :

public interface SetInterface<T> {

   /**

   * Gets the current number of entries in this set.

   *

   * @return The integer number of entries currently in the set.

   */

   public int getSize();

   /**

   * Sees whether this set is empty.

   *

   * @return True if the set is empty, or false if not.

   */

   public boolean isEmpty();

   /**

   * Adds a new entry to this set, avoiding duplicates.

   *

   * @param newEntry The object to be added as a new entry.

   * @return True if the addition is successful, or false if the item already is

   * in the set.

   */

   public boolean add(T newEntry);

   /**

   * Removes a specific entry from this set, if possible.

   *

   * @param anEntry The entry to be removed.

   * @return True if the removal was successful, or false if not.

   */

   public boolean remove(T anEntry);

   /**

   * Removes one unspecified entry from this set, if possible.

   *

   * @return Either the removed entry, if the removal was successful, or null.

   */

   public T remove();

   /** Removes all entries from this set. */

   public void clear();

   /**

   * Tests whether this set contains a given entry.

   *

   * @param anEntry The entry to locate.

   * @return true if the set contains anEntry, or false if not.

   */

   public boolean contains(T anEntry);

   /**

   * Returns true if one set is equivalent to another (contains the same

   * elements), and false otherwise.

   *

   * @param anotherSet another set

   * @return true if this set contains the same elements as the other set, or

   * false if not.

   */

   public boolean isEquivalentTo(SetInterface<T> anotherSet);

   /**

   * Returns true if all of the elements of this set are contained in the other

   * set, and false otherwise.

   *

   * @param anotherSet another set

   * @return true if all of the elements of this set are contained in the other

   * set, and false otherwise.

   */

   public boolean isSubsetOf(SetInterface<T> anotherSet);

   /**

   * Computes the union of this set with a given set

   *

   * @param anotherSet another set

   * @return the union of this set with anotherSet

   */

   public SetInterface<T> union(SetInterface<T> anotherSet);

   /**

   * Computes the intersection of this set with a given set

   *

   * @param anotherSet another set

   * @return the intersection of this set with anotherSet

   */

   public SetInterface<T> intersection(SetInterface<T> anotherSet);

   /**

   * Retrieves all entries that are in this set.

   *

   * @return A newly allocated array of all the entries in the set, where the size

   * of the array is equal to the number of entries in the set.

   */

   public T[] toArray();

} // end SetInterface

1. (63 points) Create a class ResizableArraySet that implements the methods in SetInterface.java file that you have been provided (do not modify the given interface file). There should be just one constructor, with no parameters, that creates a Set containing no elements (but the underlying array should have an initial length of 5). Methods should avoid unnecessary code duplication, using private helper methods to reduce repeated code. ○ Double the size of the array when the array is full. ○ After removing an element, if the array is less than half full, then cut the size of the array in half. However, the size of the array should never be less than 5. ○ Write a toString() method that returns a comma-separated list of the data in the set, surrounded by curly braces (such as "{A, C, B}"). (write early so you can test)

2. (See sample run at the end of this document) In a separate class, Tester, create a void method named setTester() that has no parameters and: ○ (10 points) Creates an array consisting of several strings, including some repeated strings, and then adds them to one of your sets, displaying information about your set as it goes. Then, remove the elements you added, in the same order that you added them. The idea is that this will help you show yourself (and us) that all the methods in your Set class are working. ○ (10 points) Creates another set and adds 20 random integers in the range 0 to 99. Each time a number is added, print the number that was added, along with the contents of the set. Note that if duplicates are added, then the set size after adding 20 numbers would actually be less than 20. After adding the numbers to the set, use a loop to remove all even numbers from the set, showing the number that was removed, and the resulting set. Only show the removal if the number is actually in the set.   

The final testing file:

import java.awt.Point;

public class BaselineTester {

   public static void main(String[] args) {

       testResizableArraySet();

       testNodeClass();

       testTester();

   }

  

   // Verifies that the proper methods and constructor exist in ResizableArraySet

   // If this tester contains compiler errors, it indicates a problem with your code.

   // Do not modify this tester. Instead, modify your ResizableArraySet code.

   public static void testResizableArraySet() {

      

       // Is it possible to create different kinds of sets?

       SetInterface<String> set1 = new ResizableArraySet<>();

       SetInterface<Point> set2 = new ResizableArraySet<>();

       SetInterface<Integer> set3 = new ResizableArraySet<>();

      

       // Test the add and remove methods:

       boolean b = set1.add("cat");

       b = set1.remove("cat");

       String s = set1.remove();

       set1.clear();

       int i = set1.getSize();

      

       String[] arr = set1.toArray();

      

       SetInterface<Point> set4 = new ResizableArraySet<>();

       SetInterface<Point> set5 = new ResizableArraySet<>();

       SetInterface<Point> set6 = set4.union(set5);

       set6 = set4.intersection(set5);

      

       b = set6.contains(new Point());

       b = set6.isEquivalentTo(set5);

       b = set6.isSubsetOf(set5);

       b = set6.isEmpty();      

   }

  

   // This makes sure that your Node class exists and has package-level instance variables

   // named data and next, and a constructor that has an int parameter.

   public static void testNodeClass() {

       Node n = new Node(5);

       int i = n.data;

       Node n2 = n.next;

   }

  

   // This makes sure that you have a class named Tester and that the class has static

   // methods with the proper names.

   public static void testTester() {

       Tester.setTester();

       Tester.nodeTester();      

   }

  

}

Answer 1

SetTester.java

import java.util.Arrays;

public class SetTester {

   public static void main(String[] args) {
      
       System.out.println("Testing implementation of ResizableArraySet: - ");
      
       // Create new default set
       ResizableArraySet<Integer> array = new ResizableArraySet<>();
      
       // Test getSize()
       System.out.println("Created new default ResizableArraySet! ");
       System.out.println("Testing getSize()");
       System.out.println("Expecting to see: 0");
       System.out.print("Result: ");
       System.out.println(array.getSize());
       System.out.println("Array currently holds " + Arrays.toString(array.toArray()));
       System.out.println();
      
       // Test add()
       System.out.println("Adding five items 4 9 2 5 3");
       array.add(4);
       array.add(9);
       array.add(2);
       array.add(5);
       array.add(3);
       System.out.println("Expecting to see: 4 9 2 5 3");
       System.out.print("Result: ");
       System.out.println(Arrays.toString(array.toArray()));
       System.out.println();
      
       // Test adding a duplicate
       System.out.println("Trying to add a duplicate 5");
       System.out.println("Expecting to see: fasle");
       System.out.print("Result: ");
       System.out.println(array.add(5));
       System.out.println("Array currently holds " + Arrays.toString(array.toArray()));
       System.out.println();
      
       // Test remove(T anEntry)
       System.out.println("Removing 4 and expecting to see: 3 9 2 5");
       array.remove(4);
       System.out.print("Result: ");
       System.out.println(Arrays.toString(array.toArray()));
       System.out.println();
      
       // Test remove()
       System.out.println("Removing last element by calling remove()");
       System.out.println("Expecting to see: 3 9 2");
       System.out.println("Element removed: " + array.remove());
       System.out.print("Result: ");
       System.out.println(Arrays.toString(array.toArray()));
       System.out.println();
      
       // Test contains()
       System.out.println("Checking if Set contains element '3'");
       System.out.println("Expecting to see: true");
       System.out.print("Result: ");
       System.out.println(array.contains(3));
       System.out.println("Array currently holds " + Arrays.toString(array.toArray()));
       System.out.println();
      
       // Test clear()
       System.out.println("Clearing the entire set");
       array.clear();
       System.out.println("Expecting to see: empty array");
       System.out.print("Result: ");
       System.out.println(Arrays.toString(array.toArray()));
       System.out.println();
      
       // Test isEmpty()
       System.out.println("Checking to see if array is empty by calling isEmpty()");
       System.out.println("Expecting to see: true");
       System.out.print("Result: ");
       System.out.println(array.isEmpty());
       System.out.println();
      
       System.out.println("Creating new ResizableArraySet with start size 30 ");
      
       // Test parameterized constructor and create new set for union & intersection
       ResizableArraySet<Integer> set1 = new ResizableArraySet<>(30);
      
       System.out.println("Adding five items 7 1 8 0 4");
       set1.add(7);
       set1.add(1);
       set1.add(8);
       set1.add(0);
       set1.add(4);
       System.out.println("Expecting to see: 7 1 8 0 4");
       System.out.print("Result: ");
       System.out.println(Arrays.toString(set1.toArray()));
       System.out.println();
      
       // Test union()
       System.out.println("Testing union of 7 1 8 0 4 with 2 3 8 0 6");
       System.out.println("Expecting to see: 7 1 8 0 4 2 3 6");
       // Create another set for union & intersection
       ResizableArraySet<Integer> set2 = new ResizableArraySet<>();
       ResizableArraySet<Integer> unionSet = new ResizableArraySet<>();
       set2.add(2);
       set2.add(3);
       set2.add(8);
       set2.add(0);
       set2.add(6);
       unionSet = (ResizableArraySet<Integer>)set1.union(set2);
       System.out.print("Result: ");
       System.out.println(Arrays.toString(unionSet.toArray()));
       System.out.println();
      
       // Test intersection()
       System.out.println("Testing intersection of 7 1 8 0 4 with 2 3 8 0 6");
       System.out.println("Expecting to see: 8 0");
       ResizableArraySet<Integer> intersectionSet = new ResizableArraySet<>();
       intersectionSet = (ResizableArraySet<Integer>)set1.intersection(set2);
       System.out.print("Result: ");
       System.out.println(Arrays.toString(intersectionSet.toArray()));
       System.out.println();
   }

}

Set.java

public interface Set<T> {
   /**
   * Gets the current number of entries in this set.
   *
   * @return The integer number of entries currently in the set.
   */
   public int getSize();

   /**
   * Sees whether this set is empty.
   *
   * @return True if the set is empty, or false if not.
   */
   public boolean isEmpty();

   /**
   * Adds a new entry to this set, avoiding duplicates.
   *
   * @param newEntry
   *            The object to be added as a new entry.
   * @return True if the addition is successful, or false if the item already
   *         is in the set.
   */
   public boolean add(T newEntry);

   /**
   * Removes a specific entry from this set, if possible.
   *
   * @param anEntry
   *            The entry to be removed.
   * @return True if the removal was successful, or false if not.
   */
   public boolean remove(T anEntry);

   /**
   * Removes one unspecified entry from this set, if possible.
   *
   * @return Either the removed entry, if the removal was successful, or null.
   */
   public T remove();

   /** Removes all entries from this set. */
   public void clear();

   /**
   * Tests whether this set contains a given entry.
   *
   * @param anEntry
   *            The entry to locate.
   * @return True if the set contains anEntry, or false if not.
   */
   public boolean contains(T anEntry);

   /**
   * Computes the union of this set with a given set
   *
   * @param anotherSet
   *            another set
   * @return the union of this set with anotherSet
   */
   public Set<T> union(Set<T> anotherSet);
  
   /**
   * Computes the intersection of this set with a given set
   *
   * @param anotherSet
   *            another set
   * @return the intersection of this set with anotherSet
   */
   public Set<T> intersection(Set<T> anotherSet);

   /**
   * Retrieves all entries that are in this set.
   *
   * @return A newly allocated array of all the entries in the set, where the
   *         size of the array is equal to the number of entries in the set.
   */
   public T[] toArray();
} // end SetInterface

ResizableArraySet.java

public class ResizableArraySet<T> implements Set<T>{

   private T[] arr;
   private int numberOfEntries;
   private final static int DEFAULT_CAPACITY = 10;
  
   /**
   * Default Constructor
   */
   public ResizableArraySet() {
       this(DEFAULT_CAPACITY);
   }
  
   /**
   * Parameterized Constructor
   *
   * @param startSize The size to initialize the set with
   */
   public ResizableArraySet(int startSize) {
       @SuppressWarnings("unchecked")
       T[] temp = (T[]) new Object[startSize];
       arr = temp;
       numberOfEntries = 0;
   }
  
   /**
   * Gets the current number of entries in this set.
   *
   * @return The integer number of entries currently in the set.
   */
   @Override
   public int getSize() {
       return numberOfEntries;
   }

   /**
   * Sees whether this set is empty.
   *
   * @return True if the set is empty, or false if not.
   */
   @Override
   public boolean isEmpty() {
       return numberOfEntries == 0;
   }

   /**
   * Adds a new entry to this set, avoiding duplicates.
   *
   * @param newEntry The object to be added as a new entry.
   *
   * @return True if the addition is successful, or false if the item already
   *         is in the set.
   */
   @Override
   public boolean add(T newEntry) {
       boolean success = false;
      
       for(int count = 0; count < numberOfEntries; count++) {
           if(arr[count].equals(newEntry))
               return success;
       }
      
       if(numberOfEntries == arr.length) {
           @SuppressWarnings("unchecked")
           T[] temp = (T[]) new Object[numberOfEntries*2];
           for(int count = 0; count < numberOfEntries; count++)
               temp[count] = arr[count];
           arr = temp;
       }
      
       arr[numberOfEntries] = newEntry;
       numberOfEntries++;
       success = true;
          
       return success;
   }

   /**
   * Removes a specific entry from this set, if possible.
   *
   * @param anEntry The entry to be removed.
   *
   * @return True if the removal was successful, or false if not.
   */
   @Override
   public boolean remove(T anEntry) {
       if(numberOfEntries == 0)
           return false;
      
       for(int i = 0; i < numberOfEntries; i++) {
           if(arr[i].equals(anEntry)) {
               arr[i] = arr[numberOfEntries-1];
               arr[numberOfEntries] = null;
               numberOfEntries--;
              
               if(numberOfEntries < arr.length/2) {
                   @SuppressWarnings("unchecked")
                   T[] temp = (T[]) new Object[arr.length/2];
                   for(int count = 0; count < numberOfEntries; count++)
                       temp[count] = arr[count];
                   arr = temp;
               }
              
               return true;
           }
       }
       return false;
   }

   /**
   * Removes one unspecified entry from this set, if possible.
   *
   * @return Either the removed entry, if the removal was successful, or null.
   */
   @Override
   public T remove() {
       if(numberOfEntries == 0)
           return null;
      
       T removed = arr[numberOfEntries-1];
       arr[numberOfEntries-1] = null;
       numberOfEntries--;
      
       if(numberOfEntries < arr.length/2) {
           @SuppressWarnings("unchecked")
           T[] temp = (T[]) new Object[arr.length/2];
           for(int count = 0; count < numberOfEntries; count++)
               temp[count] = arr[count];
           arr = temp;
       }
      
       return removed;
   }

   /** Removes all entries from this set. */
   @Override
   public void clear() {
       for(int i = 0; i < numberOfEntries; i++)
           arr[i] = null;
      
       numberOfEntries = 0;
      
   }

   /**
   * Tests whether this set contains a given entry.
   *
   * @param anEntry The entry to locate.
   *
   * @return True if the set contains anEntry, or false if not.
   */
   @Override
   public boolean contains(T anEntry) {
       for(int count = 0; count < numberOfEntries; count++) {
           if(arr[count].equals(anEntry))
               return true;
       }
       return false;
   }

   /**
   * Computes the union of this set with a given set
   *
   * @param anotherSet Another set
   *
   * @return the union of this set with anotherSet
   */
   @Override
   public Set<T> union(Set<T> anotherSet) {
       Set<T> unionArr = new ResizableArraySet<T>();
       T[] tempArr = anotherSet.toArray();
      
       for(int count = 0; count < numberOfEntries; count++)
           unionArr.add(arr[count]);
      
      
       for(int count = 0; count < anotherSet.getSize(); count++)
               unionArr.add(tempArr[count]);
      
       return unionArr;
   }

   /**
   * Computes the intersection of this set with a given set
   *
   * @param anotherSet Another set
   *
   * @return the intersection of this set with anotherSet
   */
   @Override
   public Set<T> intersection(Set<T> anotherSet) {
       Set<T> intersectionArr = new ResizableArraySet<T>();
       T[] tempArr = anotherSet.toArray();
      
       for(int count1 = 0; count1 < numberOfEntries; count1++) {
           for(int count2 = 0; count2 < anotherSet.getSize(); count2++) {
               if(arr[count1].equals(tempArr[count2]))
                   intersectionArr.add(arr[count1]);
           }
       }
      
       return intersectionArr;
   }

   /**
   * Retrieves all entries that are in this set.
   *
   * @return A newly allocated array of all the entries in the set, where the
   *         size of the array is equal to the number of entries in the set.
   */
   @Override
   public T[] toArray() {
       T[] newArr;
       @SuppressWarnings("unchecked")
       T[] temp = (T[]) new Object[numberOfEntries];
       for(int count = 0; count < numberOfEntries; count++)
           temp[count] = arr[count];
      
       newArr = temp;
      
       return newArr;
   }

}