[ Data Structures with Java ] Section 8.4 : Implementing the Bag Class

Preface :
The Bag class is a simple data structure that affords us the opportunity to discuss implementation design techniques. The ideas extends to more complex collection classes. A concrete collection class implements an interface that characterizes the structure. Its implementation begins with a definition of the underlying storage structure and supporting data that maintain the size of the collection. The main task is to create constructors and implement the methods defined in the interface. Like any class, a collection class may have private methods that facilitate implementation of public methods.
For the Bag class, the storage structure is a fixed length array of elements of generic type called begArr. The integer variable bagSize maintains the current size of the collection. The attribute is updated by the add() and remove() operations. The method grab() returns the value of a random object in the collection. The Bag class provides a private static Random object for the implementation of the method. The Bag class has a constructor that takes a capacity argument that fixes the size of the storage array. Its implementation allocates the array and sets bagSize to 0 to specify that the collection is initially empty. The following is a partial listing of the class with its private variables and constructors.

- 類別 Bag.java 部分代碼 :

view plaincopy to clipboardprint?

1. public class Bag implements Collection{  
2.     private T[] bagArr;  
3.     private int bagSize;  
4.     private static Random rnd = new Random();  
5.       
6.     public Bag(int capacity) {  
7.         bagArr = (T[])new Object[capacity];  
8.         bagSize = 0;  
9.     }  
10.     // interface methods and the grab method  
11. ...  
12. }  

In the next two sections, we will implement selected methods of the Bag class.

Private remove() Method :
The Collection interface define a general remove() method that deletes an item from the collection. The method returns true if the items if found and false if it is not. As we will discover, an iterator also defines a remove() method that deletes the element currently referenced by the iterator. Because elements in the Bag class are stored in an array, removing an element requires shifting the tail of the list down one position. This operation is required for both the general remove() method and the iterator version. For simplicity and code reuse, we implement the shift in a private remove(i) method that deletes an element at index i. The private method decrements bagSize as well :

- 函式 remove(i) 代碼 :

view plaincopy to clipboardprint?

1. private void remove(int i) {  
2.     if(i
3.         for(int j=i; j<(bagSize-1); j++) {  
4.             bagArr[j] = bagArr[j+1];  
5.         }  
6.         bagSize--;  
7.     }  
8. }  

The public interface method remove() scans the array sequentially looking for the target argument of type Object. If found, a call is made to the private method remove() method and the return value is true; otherwise, the return value is false :

- General remove() method :

view plaincopy to clipboardprint?

1. public boolean remove(Object o) {  
2.     for(int i=0; i
3.         if(bagArr[i].equals(o)) {  
4.             remove(i);  
5.             return true;  
6.         }  
7.     }  
8.     return false;  
9. }  

Insert and Access Methods :
The add() method inserts a new element in the bag only if space is available. The condition is true when bagSize is less than the length of bagArr and the element is assigned to bagArr[bagSize]. Otherwise, the method simply return false :

- add() 代碼 :

view plaincopy to clipboardprint?

1. public boolean add(T e) {  
2.     if(bagSize
3.         bagArr[bagSize] = e;  
4.         bagSize++;  
5.         return true;  
6.     }  
7.     return false;  
8. }  

The grab() method uses a random number generator to return an element in the range 0 to bagSize-1. If the bag is empty, the return value is null :

- grab() :

view plaincopy to clipboardprint?

1. public T grab() {  
2.     if(bagSize==0)  
3.         return null;  
4.     else   
5.         return bagArr[rnd.nextInt(bagSize)];  
6.           
7. }  

Collection toString() :
Any collection that implements the Collection interface can access the elements using toArray(). The method returns an array, which is a copy of the elements in the collection. The array can be converted to a display string using toString(arr) in the java.util.Arrays class. The format is a comma-separated list of elements in brackets. We use this strategy to implement toString() for collection classes :

- toArray() 和 toString() 代碼 :

view plaincopy to clipboardprint?

1. public Object[] toArray() {  
2.     if(bagSize>0) {  
3.         Object copyArr[] = new Object[bagSize];  
4.         copyArr = bagArr.clone();  
5.         return copyArr;  
6.     }  
7.     return null;  
8. }  
9. public String toString() {  
10.     if(bagSize>0) {  
11.         return java.util.Arrays.toString(toArray());  
12.     }  
13.     return "[]";  
14. }  

This message was edited 4 times. Last update was at 26/09/2010 13:03:58