1: /** ResizableArray.java 2: A class that implements a bag of objects by using an array. 3: The bag is never full. 4: @author Frank M. Carrano 5: @version 4.0 6: */ 7: import java.util.Arrays; 9: public final class ResizableArrayBag<T> implements BagInterface<T> 10: { 11: private T[] bag; // Cannot be final due to doubling 12: private int numberOfEntries; 13: private boolean initialized = false; 14: private static final int DEFAULT_CAPACITY = 25; //Initial capacity of bag 15: private static final int MAX_CAPACITY = 1000000; 17: //********************************************************************* 18: //This section contains three constructors and two public core methods. 19: //********************************************************************* 20: /** 21: Create an empty bag whose initial capacity is 25. 22: */ 23: public ResizableArrayBag() 24: { 25: this(DEFAULT_CAPACITY); 26: } 28: /** 29: Create an empty bag having a given initial capacity. 30: @param initialCapacity The integer capacity desired. 31: */ 32: public ResizableArrayBag(int initialCapacity) 33: { 34: checkCapacity(initialCapacity); 36: //The cast is safe because the new array contains null entries 37: @SuppressWarnings("unchecked") 38: T[] tempBag = (T[]) new Object[initialCapacity]; //Unchecked cast 39: bag = tempBag; 40: numberOfEntries = 0; 41: initialized = true; 42: } 44: /** 45: Create a bag containing given entries. 46: @param contents An array of objects. 47: */ 48: public ResizableArrayBag(T[] contents) 49: { 50: checkCapacity(contents.length); 51: bag = Arrays.copyOf(contents, contents.length); 52: numberOfEntries = contents.length; 53: initialized = true; 54: } 56: /** 57: Add a new entry to this bag. 58: @param newEntry The object to be added as a new entry. 59: @return true. 60: */ 61: public boolean add(T newEntry) 62: { 63: checkInitialization(); 64: if (isArrayFull()) 65: { 66: doubleCapacity(); 67: } 68: bag[numberOfEntries] = newEntry; 69: numberOfEntries++; 70: return true; 71: } 73: /** 74: Retrieve all entries that are in this bag and put them into an array. 75: @return A newly allocated array of all the entries in this bag. 76: */ 77: public T[] toArray() 78: { 79: checkInitialization(); 80: @SuppressWarnings("unchecked") 81: T[] result = (T[]) new Object[numberOfEntries]; //Unchecked cast 82: for (int index = 0; index < numberOfEntries; index++) 83: { 84: result[index] = bag[index]; 85: } 86: return result; 87: } 89: //******************************************************************** 90: //This section contains seven additional public methods. 91: //******************************************************************** 92: /** 93: Test whether this bag is empty. 94: @return true if this bag is empty, or false if not. 95: */ 96: public boolean isEmpty() 97: { 98: return numberOfEntries == 0; 99: } 101: /** 102: Get the current number of entries in this bag. 103: @return The integer number of entries currently in this bag. 104: */ 105: public int getCurrentSize() 106: { 107: return numberOfEntries; 108: } 110: /** 111: Count the number of times a given entry appears in this bag. 112: @param anEntry The entry to be counted. 113: @return The number of times anEntry appears in this bag. 114: */ 115: public int getFrequencyOf(T anEntry) 116: { 117: checkInitialization(); 118: int counter = 0; 119: for (int index = 0; index < numberOfEntries; index++) 120: { 121: if (anEntry.equals(bag[index])) 122: { 123: counter++; 124: } 125: } 126: return counter; 127: } 129: /** 130: Test whether this bag contains a given entry. 131: @param anEntry The entry to locate. 132: @return true if this bag contains anEntry, or false otherwise. 133: */ 134: public boolean contains(T anEntry) 135: { 136: checkInitialization(); 137: return getIndexOf(anEntry) > -1; //or >= 0 138: } 140: /** 141: Removes all entries from this bag. 142: */ 143: public void clear() 144: { 145: while (!isEmpty()) 146: { 147: remove(); 148: } 149: } 151: /** 152: Remove one unspecified entry from this bag, if possible. 153: @return Either the removed entry, if removal was successful, or null. 154: */ 155: public T remove() 156: { 157: checkInitialization(); 158: T result = removeEntry(numberOfEntries - 1); 159: return result; 160: } 162: /** 163: Remove one occurrence of a given entry from this bag. 164: @param anEntry The entry to be removed. 165: @return true if the removal was successful, or false if not. 166: */ 167: public boolean remove(T anEntry) 168: { 169: checkInitialization(); 170: int index = getIndexOf(anEntry); 171: T result = removeEntry(index); 172: return anEntry.equals(result); 173: } 175: //******************************************************************** 176: //This section contains six private helper methods. 177: //******************************************************************** 178: //Return true if the array bag is full, or false if not. 179: private boolean isArrayFull() 180: { 181: return numberOfEntries >= bag.length; 182: } 184: //Locate a given entry within the array bag. 185: //Returns the index of the entry if located, -1 otherwise. 186: //Pre-condition: checkInitialization has been called. 187: private int getIndexOf(T anEntry) 188: { 189: int where = -1; 190: boolean found = false; 191: int index = 0; 192: while (!found && (index < numberOfEntries)) 193: { 194: if (anEntry.equals(bag[index])) 195: { 196: found = true; 197: where = index; 198: } 199: index++; 200: } 201: //Assertion: If where > -1, anEntry is in the array bag, and it 202: //equals bag[where]; otherwise, anEntry is not in the array. 204: return where; 205: } 207: //Remove and return the entry at a given index within the array. 208: //If no such entry exists, returns null. 209: //Precondition: 0 <= givenIndex < numberOfEntries. 210: //Precondition: checkInitialization has been called. 211: private T removeEntry(int givenIndex) 212: { 213: T result = null; 215: if (!isEmpty() && (givenIndex >= 0)) 216: { 217: result = bag[givenIndex]; //Entry to remove 218: int lastIndex = numberOfEntries - 1; 220: //Replace entry to remove with last entry, then 221: //remove reference to last entry and adjust numberOfEntries. 222: bag[givenIndex] = bag[lastIndex]; 223: bag[lastIndex] = null; 224: numberOfEntries--; 225: } 226: return result; 227: } 229: //Throws an exception if receiving object is not initialized. 230: private void checkInitialization() 231: { 232: if (!initialized) 233: { 234: throw new SecurityException 235: ( 236: "Uninitialized object used " 237: + "to call an ArrayBag method." 238: ); 239: } 240: } 242: //Throw an exception if the client requests a capacity that is too large. 243: private void checkCapacity(int capacity) 244: { 245: if (capacity > MAX_CAPACITY) 246: { 247: throw new IllegalStateException 248: ( 249: "Attempt to create a bag whose " 250: + "capacity exceeds allowed maximum of " + MAX_CAPACITY + "." 251: ); 252: } 253: } 255: //Double the size of the array bag. 256: //Pre-condition: checkInitialization has been called. 257: private void doubleCapacity() 258: { 259: int newLength = 2 * bag.length; 260: checkCapacity(newLength); 261: bag = Arrays.copyOf(bag, newLength); 262: } 263: }