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