Source of LinkedBag.java


  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: }