//------------------------------------------------------------------------- /** * The ArraySet class represents an array-based implementation of a set * collection that internally uses an array to hold its contents. It * dynamically enlarges its array as necessary to accommodate as many * items as desired. * * This is a PARTIAL IMPLEMENTATION that needs completion. * * @param The type of items this bag will hold. * * @author John Lewis (authored class skeleton) * @author Partner 1's name (pid) * @author Partner 2's name (pid) * @version (place the date here, in this format: yyyy.mm.dd) */ public class ArraySet implements Set { //~ Instance/static variables ............................................. private static final int DEFAULT_CAPACITY = 10; private int size; // the current number of items in the collection private Item[] contents; // the set's contents //~ Constructors .......................................................... // ---------------------------------------------------------- /** * Creates an empty set using the default capacity. */ public ArraySet() { this(DEFAULT_CAPACITY); } // ---------------------------------------------------------- /** * Creates an empty set using the given initial capacity. * * @param initialCapacity the initial capacity of the set */ public ArraySet(int initialCapacity) { size = 0; // It is not possible in Java to create a new array containing // objects of a generic type like Item, so we have to use a "trick", // creating an Object[] array and then telling the compiler to // treat it as a Item[] array instead: @SuppressWarnings("unchecked") Item[] newArray = (Item[])(new Object[initialCapacity]); // Now that we have created the array, we can use it as the // initial value for our field contents = newArray; } //~ Public methods ........................................................ // ---------------------------------------------------------- /** * Returns true if this set contains the specified item. * * @param target item to be found * @return true if target is in the collection, false otherwise * * @precondition target != null * @postcondition returned value == true if this set contains target, * and false if it does not */ public boolean contains(Item target) { assert target != null : "target cannot be null"; // TODO: implement // TODO: remove this throw statement when you complete this method throw new UnsupportedOperationException( "You have not implemented contains() yet"); } // ---------------------------------------------------------- /** * Adds the specified item to this set if it is not already * present. If this set already contains the item, the call * leaves the set unchanged and returns false. * * @param element item to be added to this set * @return True if this set did not already contain the specified item * * @precondition element != null * @postcondition returned value == true if this set was changed * as a result of the call */ public boolean add(Item element) { assert element != null : "element cannot be null"; if (size() == contents.length) { expandCapacity(); } // TODO: store item // TODO: remove this throw statement when you complete this method throw new UnsupportedOperationException( "You have not implemented add() yet"); } // ---------------------------------------------------------- /* * Creates a new array to store the contents of the collection with * twice the capacity of the old one. */ private void expandCapacity() { @SuppressWarnings("unchecked") Item[] larger = (Item[])(new Object[contents.length * 2]); // TODO: Write a loop that transfers the items from "contents" to // "larger". // This replaces the old content array with the new, larger one. contents = larger; // TODO: remove this throw statement when you complete this method throw new UnsupportedOperationException( "You have not implemented expandCapacity() yet"); } // ---------------------------------------------------------- /** * Removes the specified item from this set if it is present. * Returns true if this set contained the item (or equivalently, if * this set changed as a result of the call). (This set will not * contain the element once the call returns.) * * @param target item to be removed from this set, if present * @return true if this set contained the specified item * @precondition target != null * @postcondition returned value == true if this set was changed * as a result of the call */ public boolean remove(Item target) { assert target != null : "target cannot be null"; // TODO: find and remove the item // TODO: remove throw statement when you complete this method throw new UnsupportedOperationException( "You have not completed remove() yet"); } // ---------------------------------------------------------- /** * Removes and returns an arbitrary item from the set. * * @return the item removed * @precondition this set is not empty * @postcondition returned value is some item X such that contains(X) * would have been true before the call, and contains(X) * will be false after the call */ public Item removeAny() { assert size > 0 : "set cannot be empty"; // There is no guarantee about which item will be removed--any // item is OK. But, instead of selecting one at random, pick // the one you believe is *easiest* to remove (and avoid calling // the other remove() method!). // TODO: implement // TODO: remove this throw statement when you complete this method throw new UnsupportedOperationException( "You have not implemented removeRandom() yet"); } // ---------------------------------------------------------- /** * Returns true if this set contains no items. * * @return true if this set contains no items, false otherwise */ public boolean isEmpty() { return (size == 0); } // ---------------------------------------------------------- /** * Returns the number of items in this set (its cardinality). * * @return the number of items in this set (its cardinality) */ public int size() { return size; } // ---------------------------------------------------------- /** * Removes all of the elements from this set. The set will be empty * after this call returns. * * @postcondition this set will be empty, meaning isEmpty() == true, * size() == 0, and for all items X: contains(X) == false */ public void clear() { // TODO: implement // TODO: remove this throw statement when you complete this method throw new UnsupportedOperationException( "You have not implemented clear() yet"); } // ---------------------------------------------------------- /** * Compares the specified object with this set for equality. Returns * true if the specified object is also a set, the two sets have the * same size, and every member of the specified set is contained * in this set (or equivalently, every member of this set is * contained in the specified set). This definition ensures that * the equals method works properly across different implementations * of the set interface. * * @param other object to be compared for equality with this set * @return true if the specified object is equal to this set */ public boolean equals(Object other) { if (other instanceof Set) { @SuppressWarnings("unchecked") Set otherSet = (Set) other; // TODO: check the size of this set and otherSet; if they're not // the same, you know they're not equal. If they're the same size, // check that otherSet contains every item in this set. // TODO: remove this throw statement when you complete this method throw new UnsupportedOperationException( "You have not implemented equals() yet"); } else { return false; } } // ---------------------------------------------------------- /** * Returns a string representation of this set. A set's string * representation is written as a comma-separated list of its * contents (in some arbitrary order) surrounded by curly braces, * like this: * 
     * {52, 14, 12, 119, 73, 80, 35}
     *
*

* An empty string is simply {}. *

* * @return a string representation of the set */ public String toString() { String result = "{"; for (int i = 0; i < size; i++) { if (i > 0) { result += ", "; } result += contents[i].toString(); } return result + "}"; } }