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: try {
34: first = new Node(e, first);
35: ++numInBag;
36: return true;
37: } catch (OutOfMemoryError oome) {
38: return false;
39: }
40: }
42: @Override
43: public String toString() {
44: return Arrays.toString(toArray());
45: }
47: @Override
48: public Object[] toArray() {
49: return toArray(new Object[numInBag]);
50: }
52: @SuppressWarnings("unchecked")
53: @Override
54: public <T> T[] toArray(T[] a) {
55: // check if given array is big enuf
56: if (a.length < numInBag) {
57: // replace with a bigger array of the same runtime type
58: a = Arrays.copyOf(a, numInBag);
59: }
61: // fill in the array elements
62: Node cur = first;
63: for (int i = 0; i < numInBag; ++i) {
64: a[i] = (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: E result = first.data;
84: first = first.next;
85: --numInBag;
86: return result;
87: }
89: @Override
90: public boolean remove(Object o) {
91: Node posn = findNode(o);
92: if (posn == null) {
93: return false;
94: } else {
95: posn.data = first.data;
96: remove();
97: return true;
98: }
99: }
101: // ---------- other public methods -------- //
102: @Override
103: public int size() {
104: return numInBag;
105: }
107: @Override
108: public boolean isEmpty() {
109: return numInBag == 0;
110: }
112: @Override
113: public boolean contains(Object o) {
114: return findNode(o) != null;
115: }
117: @Override
118: public void clear() {
119: numInBag = 0;
120: while (first != null) {
121: first.data = null;
122: first = first.next;
123: }
124: }
126: @Override
127: public int getFrequency(E anItem) {
128: int count = 0;
129: Node cur = first;
130: while (cur != null) {
131: if (Objects.equals(anItem, cur.data)) {
132: ++count;
133: }
134: cur = cur.next;
135: }
136: return count;
137: }
139: // ---------- unimplemented methods ------- //
140: @Override
141: public Iterator<E> iterator() {
142: throw new UnsupportedOperationException("Not supported yet.");
143: }
145: @Override
146: public boolean containsAll(Collection<?> c) {
147: throw new UnsupportedOperationException("Not supported yet.");
148: }
150: @Override
151: public boolean addAll(Collection<? extends E> c) {
152: throw new UnsupportedOperationException("Not supported yet.");
153: }
155: @Override
156: public boolean removeAll(Collection<?> c) {
157: throw new UnsupportedOperationException("Not supported yet.");
158: }
160: @Override
161: public boolean retainAll(Collection<?> c) {
162: throw new UnsupportedOperationException("Not supported yet."); // Generated from nbfs://nbhost/SystemFileSystem/Templates/Classes/Code/GeneratedMethodBody
163: }
165: // ---------- private methods ------------- //
166: /**
167: * Find the Node with {@code anItem} as its data. Return null if
168: * {@code anItem} is not {@code Objects.equals} to any element of this Bag.
169: *
170: * @param anItem the item to find
171: * @return the Node containing it, or null if it's not in the chain
172: */
173: private Node findNode(Object anItem) {
174: Node cur = first;
175: while (cur != null) {
176: if (Objects.equals(cur.data, anItem)) {
177: return cur;
178: }
179: cur = cur.next;
180: }
181: return null;
182: }
184: // ---------- private class --------------- //
185: /**
186: * A class adding a pointer to each data element, forming the links in the
187: * chain holding a Bag's elements.
188: */
189: private class Node {
191: E data;
192: Node next;
194: public Node(E e) {
195: this(e, null);
196: }
198: private Node(E e, Node first) {
199: data = e;
200: next = first;
201: }
202: }
204: }