public class ArrayBag
2: import java.util.Arrays;
3: import java.util.Collection;
4: import java.util.Iterator;
5: import java.util.NoSuchElementException;
6: import java.util.Objects;
8: /**
9: * An implementation of the Bag interface that uses an array to hold its
10: * elements. This version has incomplete implementations of {@code iterator},
11: * {@code addAll}, {@code containsAll}, {@code removeAll} and {@code retainAll}
12: * (each of which throws an {@code UnsupportedOperationException}).
13: *
14: * @author Mark Young (A00000000)
15: *
16: * @param <T> Base type of this Bag
17: */
18: public class ArrayBag<T> implements Bag<T> {
20: // ---------- capacity constants -------------------------------------- //
21: // Capacity for a Bag when the user declines to provide one
22: private static final int DEFAULT_SIZE = 11;
24: // Maximum capacity we allow -- hoping to avoid OutOfMemoryError
25: private static final int MAX_SIZE = Integer.MAX_VALUE - 8;
27: // ---------- instance variables -------------------------------------- //
28: // Array to hold the Bag's contents
29: private T[] contents;
31: // Count of items in Bag
32: private int numInBag;
34: // ---------- constructors -------------------------------------------- //
36: /**
37: * Create an array-based Bag.
38: *
39: * @param capacity the maximum capacity of the Bag.
40: */
41: @SuppressWarnings("unchecked")
42: public ArrayBag(int capacity) {
43: if (0 <= capacity && capacity <= MAX_SIZE) {
44: contents = (T[]) new Object[capacity];
45: numInBag = 0;
46: } else {
47: throw new IllegalArgumentException("Invalid capacity: " + capacity);
48: }
49: }
51: /**
52: * Create an array-based Bag with default capacity.
53: */
54: public ArrayBag() {
55: this(DEFAULT_SIZE);
56: }
58: // ---------- Bag interface methods ----------------------------------- //
60: /**
61: * Gets the current number of entries in this bag. That is, the count of
62: * items that have been added minus the items that have been removed.
63: *
64: * @return The integer number of entries currently in the bag.
65: */
66: @Override
67: public int size() {
68: return numInBag;
69: }
71: /**
72: * Sees whether this bag is empty. That is, the count of items in this bag
73: * is zero.
74: *
75: * @return True if the bag is empty, or false if not.
76: */
77: @Override
78: public boolean isEmpty() {
79: return numInBag == 0;
80: }
82: /**
83: * Adds a new entry to this bag. The add method will fail if the bag is
84: * full and cannot be made larger.
85: *
86: * @param newEntry The object to be added as a new entry.
87: * @return True if the addition is successful, or false if not.
88: */
89: @Override
90: public boolean add(T newEntry) {
91: if (numInBag == contents.length && !resize()) {
92: return false;
93: } else {
94: // add new entry at first available location in array
95: contents[numInBag] = newEntry;
96: ++numInBag;
97: return true;
98: }
99: }
101: @Override
102: public String toString() {
103: return Arrays.toString(toArray());
104: }
106: /**
107: * Removes one occurrence of a given entry from this bag. If anything
108: * equals to anEntry is already in the bag, the bag will afterwards
109: * contain one fewer copies of that element.
110: *
111: * @param anItem The entry to be removed.
112: * @return True if the removal was successful, or false if not.
113: */
114: @Override
115: public boolean remove(Object anItem) {
116: int posn = findPosn(anItem);
117: if (posn < 0) {
118: return false;
119: } else {
120: removeItemAt(posn);
121: return true;
122: }
123: }
125: /**
126: * Removes one unspecified entry from this bag, if possible. Throws a
127: * NoSuchElementException if the bag was already empty.
128: *
129: * @return the removed entry
130: * @throws NoSuchElementException if the bag was already empty
131: */
132: @Override
133: public T remove() {
134: if (numInBag == 0) {
135: throw new NoSuchElementException();
136: } else {
137: T result = removeItemAt(numInBag - 1);
138: return result;
139: }
140: }
142: /**
143: * Removes all entries from this bag. Makes the bag empty.
144: */
145: @Override
146: public void clear() {
147: for (int i = 0; i < numInBag; ++i) {
148: contents[i] = null;
149: }
150: numInBag = 0;
151: }
153: /**
154: * Tests whether this bag contains a given entry. Any entry that claims to
155: * be equals to anItem will cause the method to return true.
156: *
157: * @param anItem The entry to locate.
158: * @return True if the bag contains anItem, or false if not.
159: */
160: @Override
161: public boolean contains(Object anItem) {
162: return findPosn(anItem) >= 0;
163: }
165: /**
166: * Counts the number of times a given entry appears in this bag. All
167: * entries that say they are equals to anItem will be counted.
168: *
169: * @param anItem The entry to be counted.
170: * @return The number of times anItem appears in the bag.
171: */
172: @Override
173: public int getFrequency(T anItem) {
174: int count = 0;
175: for (int i = 0; i < numInBag; ++i) {
176: if (Objects.equals(contents[i], anItem)) {
177: ++count;
178: }
179: }
180: return count;
181: }
183: /**
184: * Retrieves all entries that are in this bag. The result is an array that
185: * is exactly the correct size for the number of elements in the bag (for
186: * example, the array will have length zero if the bag is empty). The
187: * array contains as many copies of each element as the bag itself does.
188: *
189: * @return A newly allocated array of all the entries in the bag. Note: If
190: * the bag is empty, the returned array is empty.
191: */
192: @Override
193: public Object[] toArray() {
194: return Arrays.copyOf(contents, numInBag);
195: }
197: /**
198: * Retrieves all entries that are in this bag, placing them in the given
199: * array, if it has enuf space. Otherwise a new array of exactly the
200: * required size is created and returned.
201: *
202: * @param a the array to put the elements into
203: * @return The given array, if it was large enuf to hold all the elements
204: * from this Bag; otherwise a newly allocated array of all the entries in
205: * the bag.
206: */
207: @SuppressWarnings("unchecked")
208: @Override
209: public <T> T[] toArray(T[] a) {
210: // check if the given array is large enuf
211: if (a.length < numInBag) {
212: a = Arrays.copyOf(a, numInBag);
213: }
215: // copy elements into the return array
216: for (int i = 0; i < numInBag; ++i) {
217: a[i] = (T)contents[i];
218: }
220: // add a null afterwards, if there's space
221: if (a.length > numInBag) {
222: a[numInBag] = null;
223: }
225: // return the filled-in array
226: return a;
227: }
229: // ---------- unimplemented methods ----------------------------------- //
230: @Override
231: public Iterator<T> iterator() {
232: throw new UnsupportedOperationException("Not implemented yet");
233: }
235: @Override
236: public boolean containsAll(Collection<?> c) {
237: throw new UnsupportedOperationException("Not implemented yet");
238: }
240: @Override
241: public boolean addAll(Collection<? extends T> c) {
242: throw new UnsupportedOperationException("Not implemented yet");
243: }
245: @Override
246: public boolean removeAll(Collection<?> c) {
247: throw new UnsupportedOperationException("Not implemented yet");
248: }
250: @Override
251: public boolean retainAll(Collection<?> c) {
252: throw new UnsupportedOperationException("Not implemented yet");
253: }
256: // ---------- helper methods ------------------------------------------ //
258: /**
259: * Get the array index of an item in the Bag. Any location will do (if
260: * there's more than one), and return an invalid value if there's none.
261: *
262: * @param anItem the item to locate
263: * @return the location of one such item in the array, or -1 if there are
264: * no such elements.
265: */
266: private int findPosn(Object anItem) {
267: for (int posn = 0; posn < numInBag; ++posn) {
268: if (Objects.equals(contents[posn], anItem)) {
269: return posn;
270: }
271: }
272: return -1;
273: }
275: /**
276: * Deal with the details of removing one item from the array. Move the last
277: * item up into the emptied space and null out the link from that location.
278: *
279: * @param posn the position of the item to be removed.
280: * @return the item removed.
281: */
282: private T removeItemAt(int posn) {
283: T result = contents[posn];
284: contents[posn] = contents[numInBag - 1];
285: contents[numInBag - 1] = null;
286: --numInBag;
287: return result;
288: }
290: /**
291: * Make the array bigger, if possible.
292: *
293: * @return true if the array could be made bigger; false otherwise
294: */
295: private boolean resize() {
296: int oldSize = contents.length;
297: int newSize = (oldSize > MAX_SIZE / 2) ? MAX_SIZE : 2 * oldSize;
298: if (newSize > oldSize) {
299: contents = Arrays.copyOf(contents, newSize);
300: return true; // resized successsfully
301: } else {
302: return false; // failed to resize
303: }
304: }
306: }