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