Collections IV, Exercises

exercise No. 197

Implementing a set of strings

Q:

We want to partly implement a simplified version of Set:

package de.hdm_stuttgart.mi.sd1.stringset;


/**
 * A collection of Strings that contains no duplicate elements.
 * More formally, sets contain no pair of Strings s1 and s2 such that
 * s1.equals(s2), and no null elements. As implied by its name,
 * this class models the mathematical set abstraction.
 *
 * The StringSet class places stipulations on the contracts of the add,
 * equals and hashCode methods.
 *
 * The stipulation on constructors is, not surprisingly, that all constructors
 * must create a set that contains no duplicate elements (as defined above).
 *
 */
public interface Set_String {

  /**
   * Returns the number of strings in this set (its cardinality).
   *
   * @return the number of elements in this set (its cardinality)
   */
  public int size() ;

  /**
   * Returns true if this set contains no elements.
   *
   * @return true if this set contains no elements
   */
  public boolean isEmpty();

  /**
   * Returns true if this set contains the specified element. More
   * formally, returns true if and only if this set contains an
   * element e such that (o==null ? e==null : o.equals(e)).
   *
   * @param o element whose presence in this set is to be tested
   * @return true if this set contains the specified element.
   * A null value will be treated as "not in set".
   *
   */
  public boolean contains(Object o);

  /**
   * Returns an array containing all strings in this set.
   *
   * The returned array will be "safe" in that no references to it are
   * maintained by this set. (In other words, this method allocates
   * a new array). The caller is thus free to modify the returned array.
   *
   * @return an array containing all strings in this set.
   */
  public String[] toArray();

  /**
   * Adds the specified element to this set if it is not already present.
   * More formally, adds the specified element e to this set if the set
   * contains no element e2 such that (e==null ? e2==null : e.equals(e2)).
   * If this set already contains the element, the call leaves the set
   * unchanged and returns false. In combination with the restriction on
   * constructors, this ensures that sets never contain duplicate elements.
   *
   * null values will be discarded
   *
   * @param s string to be added to this set
   *
   * @return true if this set did not already contain the specified element.
   * The attempted insert of a null value will return false.
   */
  public boolean add(String s);

  /**
   * Removes the specified string from this set if it is present
   * (optional operation). More formally, removes a string s
   * such that (o==null ? s==null : o.equals(s)), if this set
   * contains such a string. Returns true if this set contained
   * the string (or equivalently, if this set changed as a result
   * of the call). (This set will not contain the string once the
   * call returns.)
   *
   * @param s String to be removed from this set, if present.
   * @return true if this set contained the specified string.
   */
  public boolean remove(Object s);

  /**
   * Removes all of the strings from this set (optional operation).
   * The set will be empty after this call returns.
   */
  public void clear();
}

Implement this interface:

public class MySet_String implements Set_String {

  /**
   * Constructs a new, empty set;
   */
  public MySet_String() {
    ...
  }

  /**
   * Copy array values into this set excluding duplicates.
   *
   * @param source The array to copy values from
   */
  public MySet_String(final String[] source) {
    ...
  }

  @Override
  public int size() {
    ...
  }
 ...
}

Hints:

  1. Store strings among with corresponding hash code values in two separate arrays. You may use the amortized doubling strategy from Allow for variable capacity holding integer values to accommodate arbitrary numbers of instances.

  2. On lookup use hash code values prior to comparing via equals() in order to gain performance.

Write appropriate tests to assure a sound implementation.

A: