1: import java.util.Arrays;
2: /**
3: A class that implements a bag of objects by using an array.
4: The bag is never full.
5: @author Frank M. Carrano, Timothy M. Henry
6: @version 5.0
7: */
8: public final class ResizableArrayBag<T> implements BagInterface<T>
9: {
10: private T[] bag; // Cannot be final due to doubling
11: private int numberOfEntries;
12: private boolean integrityOK = false;
13: private static final int DEFAULT_CAPACITY = 25; // Initial capacity of bag
14: private static final int MAX_CAPACITY = 10000;
16: /** Creates an empty bag whose initial capacity is 25. */
17: public ResizableArrayBag()
18: {
19: this(DEFAULT_CAPACITY);
20: } // end default constructor
22: /** Creates an empty bag having a given initial capacity.
23: @param initialCapacity The integer capacity desired. */
24: public ResizableArrayBag(int initialCapacity)
25: {
26: checkCapacity(initialCapacity);
27:
28: // The cast is safe because the new array contains null entries
29: @SuppressWarnings("unchecked")
30: T[] tempBag = (T[])new Object[initialCapacity]; // Unchecked cast
31: bag = tempBag;
32: numberOfEntries = 0;
33: integrityOK = true;
34: } // end constructor
36: /** Creates a bag containing given entries.
37: @param contents An array of objects. */
38: public ResizableArrayBag(T[] contents)
39: {
40: checkCapacity(contents.length);
41: bag = Arrays.copyOf(contents, contents.length);
42: numberOfEntries = contents.length;
43: integrityOK = true;
44: } // end constructor
45:
46: /** Adds a new entry to this bag.
47: @param newEntry The object to be added as a new entry.
48: @return True. */
49: public boolean add(T newEntry)
50: {
51: checkintegrity();
52: if (isArrayFull())
53: {
54: doubleCapacity();
55: } // end if
56:
57: bag[numberOfEntries] = newEntry;
58: numberOfEntries++;
59:
60: return true;
61: } // end add
63: /** Retrieves all entries that are in this bag.
64: @return A newly allocated array of all the entries in this bag. */
65: public T[] toArray()
66: {
67: checkintegrity();
68:
69: // The cast is safe because the new array contains null entries.
70: @SuppressWarnings("unchecked")
71: T[] result = (T[])new Object[numberOfEntries]; // Unchecked cast
72: for (int index = 0; index < numberOfEntries; index++)
73: {
74: result[index] = bag[index];
75: } // end for
76:
77: return result;
78: } // end toArray
79:
80: /** Sees whether this bag is empty.
81: @return True if this bag is empty, or false if not. */
82: public boolean isEmpty()
83: {
84: return numberOfEntries == 0;
85: } // end isEmpty
86:
87: /** Gets the current number of entries in this bag.
88: @return The integer number of entries currently in this bag. */
89: public int getCurrentSize()
90: {
91: return numberOfEntries;
92: } // end getCurrentSize
93:
94: /** Counts the number of times a given entry appears in this bag.
95: @param anEntry The entry to be counted.
96: @return The number of times anEntry appears in this ba. */
97: public int getFrequencyOf(T anEntry)
98: {
99: checkintegrity();
100: int counter = 0;
101:
102: for (int index = 0; index < numberOfEntries; index++)
103: {
104: if (anEntry.equals(bag[index]))
105: {
106: counter++;
107: } // end if
108: } // end for
109:
110: return counter;
111: } // end getFrequencyOf
112:
113: /** Tests whether this bag contains a given entry.
114: @param anEntry The entry to locate.
115: @return True if this bag contains anEntry, or false otherwise. */
116: public boolean contains(T anEntry)
117: {
118: checkintegrity();
119: return getIndexOf(anEntry) > -1; // or >= 0
120: } // end contains
121:
122: /** Removes all entries from this bag. */
123: public void clear()
124: {
125: while (!isEmpty())
126: remove();
127: } // end clear
128:
129: /** Removes one unspecified entry from this bag, if possible.
130: @return Either the removed entry, if the removal
131: was successful, or null. */
132: public T remove()
133: {
134: checkintegrity();
135: T result = removeEntry(numberOfEntries - 1);
136: return result;
137: } // end remove
138:
139: /** Removes one occurrence of a given entry from this bag.
140: @param anEntry The entry to be removed.
141: @return True if the removal was successful, or false if not. */
142: public boolean remove(T anEntry)
143: {
144: checkintegrity();
145: int index = getIndexOf(anEntry);
146: T result = removeEntry(index);
147: return anEntry.equals(result);
148: } // end remove
149:
150: // Locates a given entry within the array bag.
151: // Returns the index of the entry, if located,
152: // or -1 otherwise.
153: // Precondition: checkintegrity has been called.
154: private int getIndexOf(T anEntry)
155: {
156: int where = -1;
157: boolean found = false;
158: int index = 0;
159:
160: while (!found && (index < numberOfEntries))
161: {
162: if (anEntry.equals(bag[index]))
163: {
164: found = true;
165: where = index;
166: } // end if
167: index++;
168: } // end while
169:
170: // Assertion: If where > -1, anEntry is in the array bag, and it
171: // equals bag[where]; otherwise, anEntry is not in the array.
172:
173: return where;
174: } // end getIndexOf
175:
176: // Removes and returns the entry at a given index within the array.
177: // If no such entry exists, returns null.
178: // Precondition: 0 <= givenIndex < numberOfEntries.
179: // Precondition: checkintegrity has been called.
180: private T removeEntry(int givenIndex)
181: {
182: T result = null;
183:
184: if (!isEmpty() && (givenIndex >= 0))
185: {
186: result = bag[givenIndex]; // Entry to remove
187: int lastIndex = numberOfEntries - 1;
188: bag[givenIndex] = bag[lastIndex]; // Replace entry to remove with last entry
189: bag[lastIndex] = null; // Remove reference to last entry
190: numberOfEntries--;
191: } // end if
192:
193: return result;
194: } // end removeEntry
195:
196: // Returns true if the array bag is full, or false if not.
197: private boolean isArrayFull()
198: {
199: return numberOfEntries >= bag.length;
200: } // end isArrayFull
201:
202: // Doubles the size of the array bag.
203: // Precondition: checkInitialization has been called.
204: private void doubleCapacity()
205: {
206: int newLength = 2 * bag.length;
207: checkCapacity(newLength);
208: bag = Arrays.copyOf(bag, newLength);
209: } // end doubleCapacity
210:
211: // Throws an exception if the client requests a capacity that is too large.
212: private void checkCapacity(int capacity)
213: {
214: if (capacity > MAX_CAPACITY)
215: throw new IllegalStateException("Attempt to create a bag whose capacity exceeds " +
216: "allowed maximum of " + MAX_CAPACITY);
217: } // end checkCapacity
218:
219: // Throws an exception if receiving object is not initialized.
220: private void checkintegrity()
221: {
222: if (!integrityOK)
223: throw new SecurityException ("ArrayBag object is corrupt.");
224: } // end checkintegrity
225: } // end ResizableArrayBag
227: /*
228: Testing isEmpty with an empty bag:
229: isEmpty finds the bag empty: OK.
230:
231: Adding to the bag more strings than its initial capacity.
232: Adding to the bag: A D B A C A D
233: The bag contains 7 string(s), as follows:
234: A D B A C A D
235: Testing isEmpty with a bag that is not empty:
236: isEmpty finds the bag not empty: OK.
237:
238:
239: Testing the method getFrequencyOf:
240: In this bag, the count of A is 3
241: In this bag, the count of B is 1
242: In this bag, the count of C is 1
243: In this bag, the count of D is 2
244: In this bag, the count of Z is 0
245:
246: Testing the method contains:
247: Does this bag contain A? true
248: Does this bag contain B? true
249: Does this bag contain C? true
250: Does this bag contain D? true
251: Does this bag contain Z? false
252:
253: Removing a string from the bag:
254: remove() returns D
255: The bag contains 6 string(s), as follows:
256: A D B A C A
257:
258: Removing "B" from the bag:
259: remove("B") returns true
260: The bag contains 5 string(s), as follows:
261: A D A A C
262:
263: Removing "A" from the bag:
264: remove("A") returns true
265: The bag contains 4 string(s), as follows:
266: C D A A
267:
268: Removing "C" from the bag:
269: remove("C") returns true
270: The bag contains 3 string(s), as follows:
271: A D A
272:
273: Removing "Z" from the bag:
274: remove("Z") returns false
275: The bag contains 3 string(s), as follows:
276: A D A
277:
278: Clearing the bag:
279: Testing isEmpty with an empty bag:
280: isEmpty finds the bag empty: OK.
281:
282: The bag contains 0 string(s), as follows:
283: */