1: /** LinkedBag.java
2: A class of bags whose entries are stored in a chain of linked nodes.
3: The bag is never full.
4: @author Frank M. Carrano
5: @author Timothy M. Henry
6: @version 4.0
7: */
8: public final class LinkedBag<T> implements BagInterface<T>
9: {
10: private Node firstNode;
11: private int numberOfEntries;
13: public LinkedBag()
14: {
15: firstNode = null;
16: numberOfEntries = 0;
17: }
19: /**
20: Tests whether this bag is empty.
21: @return True if this bag is empty, or false if not.
22: */
23: public boolean isEmpty()
24: {
25: return numberOfEntries == 0;
26: }
28: /**
29: Gets the capacity of this bag.
30: @return The integer number of entries that this bag can hold.
31: */
32: public int getCapacity()
33: {
34: return Integer.MAX_VALUE;
35: }
37: /**
38: Gets the number of entries currently in this bag.
39: @return The integer number of entries currently in this bag.
40: */
41: public int getCurrentSize()
42: {
43: return numberOfEntries;
44: }
46: /**
47: Adds a new entry to this bag.
48: @param newEntry The object to be added as a new entry
49: @return true if the addition is successful, or false if not.
50: */
51: public boolean add(T newEntry) //OutOfMemoryError possible
52: {
53: //Add to beginning of chain:
54: Node newNode = new Node(newEntry);
55: newNode.next = firstNode; //Make new node reference rest of chain
56: //(firstNode is null if chain is empty)
57: firstNode = newNode; //New node is at beginning of chain
58: numberOfEntries++;
59: return true;
60: }
62: /**
63: Retrieves all entries that are in this bag.
64: @return A newly allocated array of all the entries in this bag.
65: */
66: public T[] toArray()
67: {
68: //The cast is safe because the new array contains null entries
69: @SuppressWarnings("unchecked")
70: T[] result = (T[]) new Object[numberOfEntries]; //Unchecked cast
71: int index = 0;
72: Node currentNode = firstNode;
73: while ((index < numberOfEntries) && (currentNode != null))
74: {
75: result[index] = currentNode.data;
76: index++;
77: currentNode = currentNode.next;
78: }
79: return result;
80: }
82: /**
83: Counts the number of times a given entry appears in this bag.
84: @param anEntry The entry to be counted.
85: @return The number of times anEntry appears in this bag.
86: */
87: public int getFrequencyOf(T anEntry)
88: {
89: int frequency = 0;
90: int counter = 0;
91: Node currentNode = firstNode;
92: while ((counter < numberOfEntries) && (currentNode != null))
93: {
94: if (anEntry.equals(currentNode.data))
95: {
96: frequency++;
97: }
98: counter++;
99: currentNode = currentNode.next;
100: }
101: return frequency;
102: }
104: /**
105: Tests whether this bag contains a given entry.
106: @param anEntry The entry to locate.
107: @return true if the bag contains anEntry, or false otherwise.
108: */
109: public boolean contains(T anEntry)
110: {
111: boolean found = false;
112: Node currentNode = firstNode;
113: while (!found && (currentNode != null))
114: {
115: if (anEntry.equals(currentNode.data))
116: {
117: found = true;
118: }
119: else
120: {
121: currentNode = currentNode.next;
122: }
123: }
124: return found;
125: }
127: //Locates a given entry within this bag.
128: //Returns a reference to the node containing the entry, if located,
129: //or null otherwise.
130: private Node getReferenceTo(T anEntry)
131: {
132: boolean found = false;
133: Node currentNode = firstNode;
134: while (!found && (currentNode != null))
135: {
136: if (anEntry.equals(currentNode.data))
137: {
138: found = true;
139: }
140: else
141: {
142: currentNode = currentNode.next;
143: }
144: }
145: return currentNode;
146: }
148: /**
149: Removes all entries from this bag.
150: */
151: public void clear()
152: {
153: while (!isEmpty())
154: {
155: remove();
156: }
157: }
159: /**
160: Removes one unspecified entry from this bag, if possible.
161: @return Either the removed entry, if removal was successful, or null.
162: */
163: public T remove()
164: {
165: T result = null;
166: if (firstNode != null)
167: {
168: result = firstNode.data;
169: firstNode = firstNode.next; //Remove first node from chain
170: numberOfEntries--;
171: }
172: return result;
173: }
175: /**
176: Removes one occurrence of a given entry from this bag, if possible.
177: @param anEntry The entry to be removed.
178: @return true if the removal was successful, or false otherwise.
179: */
180: public boolean remove(T anEntry)
181: {
182: boolean result = false;
183: Node nodeN = getReferenceTo(anEntry);
184: if (nodeN != null)
185: {
186: //Replace located entry with entry in first node
187: //then remove first node and adjust numberOfEntries.
188: nodeN.data = firstNode.data;
189: firstNode = firstNode.next;
190: numberOfEntries--;
191: result = true;
192: }
193: return result;
194: }
196: private class Node
197: {
198: private T data; //Entry in bag
199: private Node next; //Link to next Node
201: public Node(T dataPortion)
202: {
203: this(dataPortion, null);
204: }
206: public Node
207: (
208: T dataPortion,
209: Node nextNode
210: )
211: {
212: data = dataPortion;
213: next = nextNode;
214: }
215: }
216: }