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