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;
20: private int numChanges;
22: // ---------- constructor ----------------- //
23: /**
24: * Create an empty Bag using a chain representation.
25: */
26: public LinkedBag() {
27: numInBag = 0;
28: first = null;
29: numChanges = 0;
30: }
32: // ---------- core methods ---------------- //
33: @Override
34: public boolean add(E e) {
35: first = new Node(e, first);
36: ++numInBag;
37: ++numChanges;
38: return true;
39: }
41: @Override
42: public String toString() {
43: return Arrays.toString(toArray());
44: }
46: @Override
47: public Object[] toArray() {
48: return toArray(new Object[numInBag]);
49: }
51: @SuppressWarnings("unchecked")
52: @Override
53: public <T> T[] toArray(T[] a) {
54: // check if given array is big enuf
55: if (a.length < numInBag) {
56: // replace with a bigger array of the same runtime type
57: a = Arrays.copyOf(a, numInBag);
58: }
60: // copy Bag elements
61: int index = 0;
62: Node cur = first;
63: while (cur != null) {
64: a[index++] = (T) cur.data;
65: cur = cur.next;
66: }
68: // add a null at the end (if space available)
69: if (a.length > numInBag) {
70: a[numInBag] = null;
71: }
73: // return the revised array
74: return a;
75: }
77: // ---------- removal methods ------------- //
78: @Override
79: public E remove() {
80: if (first == null) {
81: throw new NoSuchElementException();
82: }
83: return removeNode(first);
84: }
86: @Override
87: public boolean remove(Object o) {
88: Node posn = findNode(o);
89: if (posn == null) {
90: return false;
91: } else {
92: removeNode(posn);
93: return true;
94: }
95: }
97: // ---------- other public methods -------- //
98: @Override
99: public int size() {
100: return numInBag;
101: }
103: @Override
104: public boolean isEmpty() {
105: return numInBag == 0;
106: }
108: @Override
109: public boolean contains(Object o) {
110: return findNode(o) != null;
111: }
113: @Override
114: public void clear() {
115: numInBag = 0;
116: while (first != null) {
117: first.data = null;
118: first = first.next;
119: }
120: }
122: @Override
123: public int count(E anItem) {
124: int count = 0;
125: Node cur = first;
126: while (cur != null) {
127: if (Objects.equals(anItem, cur.data)) {
128: ++count;
129: }
130: cur = cur.next;
131: }
132: return count;
133: }
135: // ---------- unimplemented methods ------- //
136: @Override
137: public Iterator<E> iterator() {
138: throw new UnsupportedOperationException("Not supported yet.");
139: }
141: @Override
142: public boolean containsAll(Collection<?> c) {
143: throw new UnsupportedOperationException("Not supported yet.");
144: }
146: @Override
147: public boolean addAll(Collection<? extends E> c) {
148: throw new UnsupportedOperationException("Not supported yet.");
149: }
151: @Override
152: public boolean removeAll(Collection<?> c) {
153: boolean changed = false;
154: Iterator<E> it = iterator();
155: while (it.hasNext()) {
156: if (c.contains(it.next())) {
157: it.remove();
158: }
159: }
160: return changed;
161: }
163: @Override
164: public boolean retainAll(Collection<?> c) {
165: boolean changed = false;
166: Iterator<E> it = iterator();
167: while (it.hasNext()) {
168: if (!c.contains(it.next())) {
169: it.remove();
170: }
171: }
172: return changed;
173: }
175: // ---------- private methods ------------- //
176: /**
177: * Find the Node with {@code anItem} as its data. Return null if
178: * {@code anItem} is not {@code Objects.equals} to any element of this Bag.
179: *
180: * @param anItem the item to find
181: * @return the Node containing it, or null if it's not in the chain
182: */
183: private Node findNode(Object anItem) {
184: Node cur = first;
185: while (cur != null) {
186: if (Objects.equals(cur.data, anItem)) {
187: return cur;
188: }
189: cur = cur.next;
190: }
191: return null;
192: }
194: /**
195: * Remove the data in the given Node from this Bag. The caller is
196: * responsible for ensuring that {@code cur} is not {@code null}.
197: * <p>
198: * The data is removed by copying the data from the first Node in the chain
199: * into the current Node and removing the first Node from the chain. The
200: * change in element order doesn't matter for a Bag.
201: *
202: * @param cur the Node holding the data to be removed (not null)
203: * @param the value removed
204: */
205: private E removeNode(Node cur) {
206: E result = cur.data;
207: cur.data = first.data;
208: first.data = null;
209: first = first.next;
210: --numInBag;
211: ++numChanges;
212: return result;
213: }
215: // ---------- private class --------------- //
216: /**
217: * A class adding a pointer to each data element, forming the links in the
218: * chain holding a Bag's elements.
219: */
220: private class Node {
222: E data;
223: Node next;
225: public Node(E e) {
226: this(e, null);
227: }
229: private Node(E e, Node first) {
230: data = e;
231: next = first;
232: }
233: }
235: }