public class LinkedBag
1: import java.util.Arrays;
2: import java.util.Collection;
3: import java.util.Iterator;
4: import java.util.NoSuchElementException;
5: import java.util.Objects;
7: /**
8: * An implementation of the Bag interface using a chain to hold its elements.
9: * This implementation is missing the iterator method and the X-All methods.
10: * (That is, they are present, but throw UnsupportedOperationExceptions.)
11: *
12: * @author Mark Young (A00000000)
13: * @param <E> the base class of this Bag
14: */
15: public class LinkedBag<E> implements Bag<E> {
17: // ---------- instance variables ---------- //
18: private Node first;
19: private int numInBag;
21: // ---------- constructor ----------------- //
22: /**
23: * Create an empty Bag using a chain representation.
24: */
25: public LinkedBag() {
26: numInBag = 0;
27: first = null;
28: }
30: // ---------- core methods ---------------- //
31: @Override
32: public boolean add(E e) {
33: first = new Node(e, first);
34: ++numInBag;
35: return true;
37: // no sense trying to catch an OutOfMemoryError
38: }
40: @Override
41: public String toString() {
42: return Arrays.toString(toArray());
43: }
45: @Override
46: public Object[] toArray() {
47: return toArray(new Object[numInBag]);
48: }
50: @SuppressWarnings("unchecked")
51: @Override
52: public <T> T[] toArray(T[] a) {
53: // check if given array is big enuf
54: if (a.length < numInBag) {
55: // replace with a bigger array of the same runtime type
56: a = Arrays.copyOf(a, numInBag);
57: }
59: // fill in the array elements
60: Node cur = first;
61: for (int i = 0; i < numInBag; ++i) {
62: a[i] = (T) cur.data;
63: cur = cur.next;
64: }
66: // add a null at the end (if space available)
67: if (a.length > numInBag) {
68: a[numInBag] = null;
69: }
71: // return the revised array
72: return a;
73: }
75: // ---------- removal methods ------------- //
76: @Override
77: public E remove() {
78: // check for error condition: nothing to remove
79: if (first == null) {
80: throw new NoSuchElementException();
81: }
83: // remove first item from the bag
84: Node toDelete = first;
85: E result = first.data;
86: first = first.next;
87: --numInBag;
89: // null out for express garbage collection
90: toDelete.next = null;
91: toDelete.data = null;
93: // send back the removed data
94: return result;
95: }
97: @Override
98: public boolean remove(Object o) {
99: Node itsNode = findNode(o);
100: if (itsNode == null) {
101: return false;
102: } else {
103: deleteDataAt(itsNode);
104: return true;
105: }
106: }
108: private void deleteDataAt(Node toRemove) {
109: // move data from first item to here
110: toRemove.data = first.data;
112: // remove first item
113: remove(); // updates numInBag
114: return true;
115: }
117: // ---------- other public methods -------- //
118: @Override
119: public int size() {
120: return numInBag;
121: }
123: @Override
124: public boolean isEmpty() {
125: return numInBag == 0;
126: }
128: @Override
129: public boolean contains(Object o) {
130: return findNode(o) != null;
131: }
133: @Override
134: public void clear() {
135: numInBag = 0;
136: while (first != null) {
137: first.data = null;
138: first = first.next;
139: }
140: }
142: @Override
143: public int getFrequency(E anItem) {
144: int count = 0;
145: Node cur = first;
146: while (cur != null) {
147: if (Objects.equals(anItem, cur.data)) {
148: ++count;
149: }
150: cur = cur.next;
151: }
152: return count;
153: }
155: // ---------- unimplemented methods ------- //
156: @Override
157: public Iterator<E> iterator() {
158: throw new UnsupportedOperationException("Not supported yet.");
159: }
161: @Override
162: public boolean containsAll(Collection<?> c) {
163: throw new UnsupportedOperationException("Not supported yet.");
164: }
166: @Override
167: public boolean addAll(Collection<? extends E> c) {
168: throw new UnsupportedOperationException("Not supported yet.");
169: }
171: @Override
172: public boolean removeAll(Collection<?> c) {
173: throw new UnsupportedOperationException("Not supported yet.");
174: }
176: @Override
177: public boolean retainAll(Collection<?> c) {
178: throw new UnsupportedOperationException("Not supported yet.");
179: }
181: // ---------- private methods ------------- //
182: /**
183: * Find the Node with {@code anItem} as its data. Return null if
184: * {@code anItem} is not {@code Objects.equals} to any element of this Bag.
185: *
186: * @param anItem the item to find
187: * @return the Node containing it, or null if it's not in the chain
188: */
189: private Node findNode(Object anItem) {
190: Node cur = first;
191: while (cur != null) {
192: if (Objects.equals(cur.data, anItem)) {
193: return cur;
194: }
195: cur = cur.next;
196: }
197: return null;
198: }
200: // ---------- private class --------------- //
201: /**
202: * A class adding a pointer to each data element, forming the links in the
203: * chain holding a Bag's elements.
204: *
205: * NOTES TO STUDENTS:
206: * - This class is not static, so it has access to the type parameter of
207: * its enclosing class.
208: * - I have made its instance variables private, but because it is part of
209: * its enclosing class, its enclosing class has access.
210: */
211: private class Node {
213: private E data;
214: private Node next;
216: public Node(E e) {
217: this(e, null);
218: }
220: private Node(E e, Node first) {
221: data = e;
222: next = first;
223: }
224: }
226: }