1: /**
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 ArrayBag<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;
13:
14: /** Creates an empty bag whose initial capacity is 25. */
15: public ArrayBag()
16: {
17: this(DEFAULT_CAPACITY);
18: } // end default constructor
19:
20: /** Creates an empty bag having a given capacity.
21: @param desiredCapacity The integer capacity desired. */
22: public ArrayBag(int desiredCapacity)
23: {
24: if (desiredCapacity <= MAX_CAPACITY)
25: {
26: // The cast is safe because the new array contains null entries
27: @SuppressWarnings("unchecked")
28: T[] tempBag = (T[])new Object[desiredCapacity]; // Unchecked cast
29: bag = tempBag;
30: numberOfEntries = 0;
31: initialized = true;
32: // Test that contents are nulls - OK
33: // for (int index = 0; index < desiredCapacity; index++)
34: // System.out.print(bag[index] + " ");
35: // System.out.println();
36: }
37: else
38: throw new IllegalStateException("Attempt to create a bag " +
39: "whose capacity exceeds " +
40: "allowed maximum.");
41: } // end constructor
42:
43: /** Adds a new entry to this bag.
44: @param newEntry The object to be added as a new entry.
45: @return True if the addition is successful, or false if not. */
46: public boolean add(T newEntry)
47: {
48: checkInitialization();
49: boolean result = true;
50: if (isArrayFull())
51: {
52: result = false;
53: }
54: else
55: { // Assertion: result is true here
56: bag[numberOfEntries] = newEntry;
57: numberOfEntries++;
58: } // end if
59:
60: return result;
61: } // end add
62:
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> T[] toArray() //OK
66: public T[] toArray() //OK
67: {
68: checkInitialization();
69:
70: // The cast is safe because the new array contains null entries.
71: @SuppressWarnings("unchecked")
72: T[] result = (T[])new Object[numberOfEntries]; // Unchecked cast
73:
74: for (int index = 0; index < numberOfEntries; index++)
75: {
76: result[index] = bag[index];
77: } // end for
78: return result;
79: // Note: The body of this method could consist of one return statement,
80: // if you call Arrays.copyOf
81: } // end toArray
82:
83: /** Sees whether this bag is empty.
84: @return True if this bag is empty, or false if not. */
85: public boolean isEmpty()
86: {
87: return numberOfEntries == 0;
88: } // end isEmpty
89:
90: /** Gets the current number of entries in this bag.
91: @return The integer number of entries currently in this bag. */
92: public int getCurrentSize()
93: {
94: return numberOfEntries;
95: } // end getCurrentSize
96:
97: /** Counts the number of times a given entry appears in this bag.
98: @param anEntry The entry to be counted.
99: @return The number of times anEntry appears in this ba. */
100: public int getFrequencyOf(T anEntry)
101: {
102: checkInitialization();
103: int counter = 0;
104:
105: for (int index = 0; index < numberOfEntries; index++)
106: {
107: if (anEntry.equals(bag[index]))
108: {
109: counter++;
110: } // end if
111: } // end for
112:
113: return counter;
114: } // end getFrequencyOf
115:
116: /** Tests whether this bag contains a given entry.
117: @param anEntry The entry to locate.
118: @return True if this bag contains anEntry, or false otherwise. */
119: public boolean contains(T anEntry)
120: {
121: checkInitialization();
122: return getIndexOf(anEntry) > -1; // or >= 0
123: } // end contains
124:
125: /** Removes all entries from this bag. */
126: public void clear()
127: {
128: while (!isEmpty())
129: remove();
130: } // end clear
131:
132: /** Removes one unspecified entry from this bag, if possible.
133: @return Either the removed entry, if the removal
134: was successful, or null. */
135: public T remove()
136: {
137: checkInitialization();
138: T result = removeEntry(numberOfEntries - 1);
139: return result;
140: } // end remove
141:
142: /** Removes one occurrence of a given entry from this bag.
143: @param anEntry The entry to be removed.
144: @return True if the removal was successful, or false if not. */
145: public boolean remove(T anEntry)
146: {
147: checkInitialization();
148: int index = getIndexOf(anEntry);
149: T result = removeEntry(index);
150: return anEntry.equals(result);
151: } // end remove
152:
153: // Returns true if the array bag is full, or false if not.
154: private boolean isArrayFull()
155: {
156: return numberOfEntries >= bag.length;
157: } // end isArrayFull
158:
159: // Locates a given entry within the array bag.
160: // Returns the index of the entry, if located,
161: // or -1 otherwise.
162: // Precondition: checkInitialization has been called.
163: private int getIndexOf(T anEntry)
164: {
165: int where = -1;
166: boolean found = false;
167: int index = 0;
168:
169: while (!found && (index < numberOfEntries))
170: {
171: if (anEntry.equals(bag[index]))
172: {
173: found = true;
174: where = index;
175: } // end if
176: index++;
177: } // end while
178:
179: // Assertion: If where > -1, anEntry is in the array bag, and it
180: // equals bag[where]; otherwise, anEntry is not in the array.
181:
182: return where;
183: } // end getIndexOf
184:
185: // Removes and returns the entry at a given index within the array.
186: // If no such entry exists, returns null.
187: // Precondition: 0 <= givenIndex < numberOfEntries.
188: // Precondition: checkInitialization has been called.
189: private T removeEntry(int givenIndex)
190: {
191: T result = null;
192:
193: if (!isEmpty() && (givenIndex >= 0))
194: {
195: result = bag[givenIndex]; // Entry to remove
196: int lastIndex = numberOfEntries - 1;
197: bag[givenIndex] = bag[lastIndex]; // Replace entry to remove with last entry
198: bag[lastIndex] = null; // Remove reference to last entry
199: numberOfEntries--;
200: } // end if
201:
202: return result;
203: } // end removeEntry
204:
205: // Throws an exception if this object is not initialized.
206: private void checkInitialization()
207: {
208: if (!initialized)
209: throw new SecurityException("ArrayBag object is not initialized properly.");
210: } // end checkInitialization
211: } // end ArrayBag
212:
213:
214: