Source of ResizableArrayBag.java


  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: }