1: /**
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: @version 4.0
6: */
7: public final class LinkedBag1<T> implements BagInterface<T>
8: {
9: private Node firstNode; // Reference to first node
10: private int numberOfEntries;
11:
12: public LinkedBag1()
13: {
14: firstNode = null;
15: numberOfEntries = 0;
16: } // end default constructor
17:
18: /** Adds a new entry to this bag.
19: @param newEntry The object to be added as a new entry.
20: @return True. */
21: public boolean add(T newEntry) // OutOfMemoryError possible
22: {
23: // Add to beginning of chain:
24: Node newNode = new Node(newEntry);
25: newNode.next = firstNode; // Make new node reference rest of chain
26: // (firstNode is null if chain is empty)
27: firstNode = newNode; // New node is at beginning of chain
28: numberOfEntries++;
29:
30: return true;
31: } // end add
32:
33: /** Retrieves all entries that are in this bag.
34: @return A newly allocated array of all the entries in this bag. */
35: public T[] toArray()
36: {
37: // The cast is safe because the new array contains null entries.
38: @SuppressWarnings("unchecked")
39: T[] result = (T[])new Object[numberOfEntries]; // Unchecked cast
40:
41: int index = 0;
42: Node currentNode = firstNode;
43: while ((index < numberOfEntries) && (currentNode != null))
44: {
45: result[index] = currentNode.data;
46: index++;
47: currentNode = currentNode.next;
48: } // end while
49:
50: return result;
51: // Note: The body of this method could consist of one return statement,
52: // if you call Arrays.copyOf
53: } // end toArray
54:
55: /** Sees whether this bag is empty.
56: @return True if the bag is empty, or false if not. */
57: public boolean isEmpty()
58: {
59: return numberOfEntries == 0;
60: } // end isEmpty
61:
62: /** Gets the number of entries currently in this bag.
63: @return The integer number of entries currently in the bag. */
64: public int getCurrentSize()
65: {
66: return numberOfEntries;
67: } // end getCurrentSize
68:
69: // STUBS:
70:
71: /** Removes one unspecified entry from this bag, if possible.
72: @return Either the removed entry, if the removal
73: was successful, or null. */
74: public T remove()
75: {
76: return null; // STUB
77: } // end remove
78:
79: /** Removes one occurrence of a given entry from this bag.
80: @param anEntry The entry to be removed.
81: @return True if the removal was successful, or false otherwise. */
82: public boolean remove(T anEntry)
83: {
84: return false; // STUB
85: } // end remove
86:
87: /** Removes all entries from this bag. */
88: public void clear()
89: {
90: // STUB
91: } // end clear
92:
93: /** Counts the number of times a given entry appears in this bag.
94: @param anEntry The entry to be counted.
95: @return The number of times anEntry appears in the bag. */
96: public int getFrequencyOf(T anEntry)
97: {
98: return 0; // STUB
99: } // end getFrequencyOf
100:
101: /** Tests whether this bag contains a given entry.
102: @param anEntry The entry to locate.
103: @return True if the bag contains anEntry, or false otherwise. */
104: public boolean contains(T anEntry)
105: {
106: return false; // STUB
107: } // end contains
108:
109: private class Node
110: {
111: private T data; // Entry in bag
112: private Node next; // Link to next node
113:
114: private Node(T dataPortion)
115: {
116: this(dataPortion, null);
117: } // end constructor
118:
119: private Node(T dataPortion, Node nextNode)
120: {
121: data = dataPortion;
122: next = nextNode;
123: } // end constructor
124: } // end Node
125: } // end LinkedBag1
126:
127:
128: