1: /** FixedSizeArrayBag.java
2: A class of bags whose entries are stored in a fixed-size array.
3: @author Frank M. Carrano
4: @version 4.0
5: */
6: public final class FixedSizeArrayBag<T> implements BagInterface<T>
7: {
8: private final T[] bag;
9: private int numberOfEntries;
10: private boolean initialized = false;
11: private static final int DEFAULT_CAPACITY = 25;
12: private static final int MAX_CAPACITY = 10000;
14: //********************************************************************
15: //This section contains two constructors and two public core methods.
16: //********************************************************************
17: /**
18: Create an empty bag whose initial capacity is 25.
19: */
20: public FixedSizeArrayBag()
21: {
22: this(DEFAULT_CAPACITY);
23: }
25: /**
26: Create an empty bag having a given capacity.
27: @param desiredCapacity The integer capacity desired.
28: */
29: public FixedSizeArrayBag(int desiredCapacity)
30: {
31: if (desiredCapacity <= MAX_CAPACITY)
32: {
33: //Notes:
34: //1. bag = new T[desiredCapacity]; //syntax error
35: // Cannot create array of generic type
36: //2. bag = new Object[desiredCapacity]; //syntax error
37: // Incompatible types
38: //3. bag = (T[]) new Object[desiredCapacity];
39: // Gives a compiler warning about an "unchecked cast"
40: //We can tell the compiler that the cast is safe because the new
41: //array contains null entries, which we do with the following
42: //annotation:
43: @SuppressWarnings("unchecked")
44: //But this annotation can only be placed in front of a method
45: //definition or a variable declaration, and since bag has already
46: //been declared we have to do this:
47: T[] tempBag = (T[]) new Object[desiredCapacity]; //Unchecked cast
48: bag = tempBag;
49: numberOfEntries = 0;
50: initialized = true;
51: }
52: else
53: {
54: throw new IllegalStateException
55: (
56: "Attempt to create a bag "
57: + "whose capacity exceeds allowed maximum."
58: );
59: }
60: }
62: /**
63: Add a new entry to this bag.
64: @param newEntry The object to be added as a new entry.
65: @return true if the addition is successful, or false if not.
66: */
67: public boolean add(T newEntry)
68: {
69: checkInitialization();
70: boolean result = true;
71: if (isArrayFull())
72: {
73: result = false;
74: }
75: else
76: {
77: //Assertion: result is true here
78: bag[numberOfEntries] = newEntry;
79: numberOfEntries++;
80: }
81: return result;
82: }
84: /**
85: Retrieve all entries that are in this bag and put them into an array.
86: @return A newly allocated array of all the entries in this bag.
87: */
88: //public <T> T[] toArray() //Also OK
89: public T[] toArray()
90: {
91: checkInitialization();
93: //The cast is safe because the new array contains null entries.
94: @SuppressWarnings("unchecked")
95: T[] result = (T[]) new Object[numberOfEntries]; // Unchecked cast
97: for (int index = 0; index < numberOfEntries; index++)
98: {
99: result[index] = bag[index];
100: }
101: return result;
102: //Note that we could have made the body of this method
103: //much shorter by using the Arrays.copyOf() method.
104: }
106: //********************************************************************
107: //This section contains seven additional public methods.
108: //********************************************************************
109: /**
110: Test whether this bag is empty.
111: @return True if this bag is empty, or false if not.
112: */
113: public boolean isEmpty()
114: {
115: return numberOfEntries == 0;
116: }
118: /**
119: Get the current number of entries in this bag.
120: @return The integer number of entries currently in this bag.
121: */
122: public int getCurrentSize()
123: {
124: return numberOfEntries;
125: }
127: /**
128: Count the number of times a given entry appears in this bag.
129: @param anEntry The entry to be counted.
130: @return The number of times anEntry appears in this bag.
131: */
132: public int getFrequencyOf(T anEntry)
133: {
134: checkInitialization();
135: int counter = 0;
136: for (int index = 0; index < numberOfEntries; index++)
137: {
138: if (anEntry.equals(bag[index]))
139: {
140: counter++;
141: }
142: }
143: return counter;
144: }
146: /**
147: Test whether this bag contains a given entry.
148: @param anEntry The entry to locate.
149: @return true if this bag contains anEntry, or false otherwise.
150: */
151: public boolean contains(T anEntry)
152: {
153: checkInitialization();
154: return getIndexOf(anEntry) > -1; // or >= 0
155: }
157: /**
158: Remove all entries from this bag.
159: */
160: public void clear()
161: {
162: while (!isEmpty())
163: {
164: remove();
165: }
166: }
168: /**
169: Remove one unspecified entry from this bag, if possible.
170: @return Either the removed entry, if removal was successful, or null.
171: */
172: public T remove()
173: {
174: checkInitialization();
175: T result = removeEntry(numberOfEntries - 1);
176: return result;
177: }
179: /**
180: Remove one occurrence of a given entry from this bag.
181: @param anEntry The entry to be removed.
182: @return true if the removal was successful, or false if not.
183: */
184: public boolean remove(T anEntry)
185: {
186: checkInitialization();
187: int index = getIndexOf(anEntry);
188: T result = removeEntry(index);
189: return anEntry.equals(result);
190: }
192: //********************************************************************
193: //This section contains four private helper methods.
194: //********************************************************************
195: //Return true if the array bag is full, or false if not.
196: private boolean isArrayFull()
197: {
198: return numberOfEntries >= bag.length;
199: }
201: //Locate a given entry within the array bag.
202: //Return the index of the entry if located, -1 otherwise.
203: //Pre-condition: checkInitialization() has been called.
204: private int getIndexOf(T anEntry)
205: {
206: int where = -1;
207: boolean found = false;
208: int index = 0;
209: while (!found && (index < numberOfEntries))
210: {
211: if (anEntry.equals(bag[index]))
212: {
213: found = true;
214: where = index;
215: }
216: index++;
217: }
218: //Assertion: If where > -1, anEntry is in the array bag, and it
219: //equals bag[where]; otherwise, anEntry is not in the array.
221: return where;
222: }
224: //Remove and return the entry at a given index within the array.
225: //If no such entry exists, return null.
226: //Pre-condition: 0 <= givenIndex < numberOfEntries.
227: //Pre-condition: checkInitialization() has been called.
228: private T removeEntry(int givenIndex)
229: {
230: T result = null;
232: if (!isEmpty() && (givenIndex >= 0))
233: {
234: result = bag[givenIndex]; //Entry to remove
235: int lastIndex = numberOfEntries - 1;
237: //Replace entry to remove with last entry, then
238: //remove reference to last entry and adjust numberOfEntries.
239: bag[givenIndex] = bag[lastIndex];
240: bag[lastIndex] = null;
241: numberOfEntries--;
242: }
243: return result;
244: }
246: //Throw an exception if this object is not initialized.
247: private void checkInitialization()
248: {
249: if (!initialized)
250: {
251: throw new SecurityException
252: (
253: "FixedSizeArrayBag object is not "
254: + "initialized properly."
255: );
256: }
257: }
258: }