[ Data Structures with Java ] Section 20.3 : Implementing a Collection View

Preface : 
In this section, we focus on the design and implementation of the keySet collection view for a map. The entrySet collection view will be discussed in Chapter 21 when we implement the HashMap collection. Understanding the difference between a collection and a collection view is critical. A collection is an object consisting of data and operations that specify elements and methods to access and update their values. A collection-view object doesn't have its own data. It uses the data in the backing collection. The view object does have operations, however, but these are tied to the operations in the backing collection. They have the effect of accessing and updating elements in the backing collection. A keySet view for a map has operations that reference the key fields among the key-value elements in the collection. The keySet methods implement the Set interface but with the add() operation disallowed by having the method throw an exception. 

Examining a View : 
The concept of a view is relatively straightforward. The implementation is more difficult since it involves specialized concepts and techniques. A very simple example illustrates the techniques. Extending them to the keySet collection view becomes a matter of details. 
The class StoreOneTwo has data members one and two that hold integer values. A constructor initializes the values and toString() provides a representation of the object in the form one=two. The class defines the method setOneTwo() that allow the programmer to update the instance variables. Associated with the class we create an interface called View. The interface defines methods get() and set(), which may be used by a view object to access and update a field in the backing object : 

- View interface :

view plaincopy to clipboardprint?

1. public interface View {  
2.     int get();  
3.     void set(int value);  
4. }  

The StoreOneTwo class defines the method viewOne(), which returns a View object that is associated with filed one in a StoreOneTwo object. The method is responsible for creating an object of type View and for implementing the interface methods as they pertain to the variable one in StoreOneTwo, the backing collection. The following is an implementation of the StoreOneTwo class. Only the method header for viewOne() is included. Its implementation will be the focus of this section : 

- Class StoreOneTwo :

view plaincopy to clipboardprint?

1. package dwj.ch20;  
2.   
3. public class StoreOneTwo {  
4.     private int one,two;  
5.       
6.     public StoreOneTwo(int o, int t) {  
7.         one = o;  
8.         two = t;  
9.     }  
10.       
11.     public String toString(){return one+"="+two;}  
12.     public void setOneTwo(int one, int two){this.one = one; this.two = two;}  
13.     private View viewObj = null;  
14.     public View viewOne(){...}  
15. }  

Implementing a View : 
In the StoreOneTwo class, the method viewOne() returns an object that implements the View interface. The object does not have its one data; rather, it relies on access to the variable one in a StoreOneTwo object. To create the View object returned by viewOne(), we use an anonymous inner class; that is, an inner class that does not have a name. An anonymous inner class combines the declaration of an inner class with the creation of an instance of the class in one step. In our example, the anonymous inner-class declaration creates a variable that is an instance of a class that implements the View interface. 
Prior to its implementation of the method viewOne(), the StoreOneTwo class declares the instance variable viewObj of the type View and assign it the value null. The variables is instantiated in the method viewOne() as an object of anonymous class type that implements the View interface. The body for the anonymous class is provided in a block that accompanies the declaration of viewObj. The anonymous class implements, View and so must implement the methods get() and set(), which access the variable one in the outer class. 
In the implementation of viewOne(), the instance variable viewObj is instantiated with the operation new View(). This looks strange since a variable cannot be instantiated as an interface object. In fact, viewObj is not an interface object but rather an object of anonymous class type that implements View : 

- Method viewOne() : Return an anonymous object which implements View interface

view plaincopy to clipboardprint?

1. private View viewObj = null;  
2.   
3. public View viewOne(){  
4.     if(viewObj==null) {  
5.         viewObj = new View(){  
6.             @Override  
7.             public int get() {                    
8.                 return one;  
9.             }  
10.             @Override  
11.             public void set(int value) {  
12.                 one = value;                      
13.             }                 
14.         };  
15.     }  
16.     return viewObj;  
17. }  

The keySet Collection View : 
In the TreeMap class, the method keySet() returns a collection view that implements the Set interface. Using the approach discussed in the previous section, we implement the method keySet() by creating an anonymous inner-class object and making it the return value. 
We must implement the methods defined in the interface. Remember that all of the methods work on the backing map collection. The Set methods size(), isEmpty() and clear() have implementations that use the corresponding TreeMap methods. Note that when you use "this" in an inner class, it references the inner-class object! To reference "this" for the enclosing class, preface it by the name of the enclosing class followed by the "." operator. For instance, TreeMap.this.size() refers to the method size() in the TreeMap class. Here is the implementation for size() in the collection view : 

- keySet collection view size() :

view plaincopy to clipboardprint?

1. @Override  
2. public int size() {  
3.                                     // access size in the backing map  
4.     return TreeMap.this.size();  
5. }  

The methods contains() and remove() have a single Object argument. In the keySet view, the argument represents a key in a key-value entry in the map. Their implementations use corresponding TreeMap methods that require the key for their argument. 
The Set method add() requires special attention. Since it is in the interface, the method must be implemented. However, the Set add() operation makes no sense in the collection view. Inserting an object in KeySet should correspond to adding a key-value entry in the map. The object would become a key without any associated value. The implementation of add() in KeySet throws an UnsupportedOperationException, which has the effect of making the operation invalid. 
The KeySet and the entrySet collection view provide an iterator that scans the keys in the map. In the implementation of keySet(), the method iterator() returns an Iterator object of type KeyIterator. In the implementation of entrySet(), the return Interator object is of type EntryIterator. Both of these Iterator classes must implement next(), hasNext() and remove(). We simplify the take be creating a single generic iterator class InteratorImpl that sequences through the key-value pairs in the map and implements all of the iterator methods except next(). The inner class KeyIterator is a subclass of the inner class IteratorImpl with generic type K. The class KeyIterator adds an implementation for next() that returns the key in the map. As well as the EntryIterator which is a subclass of the inner class IteratorImpl with generic type Map.Entry. Below is the brief view on the implementations of KeySet and KeyIterator : 

- TreeMap class : Implementation on method keySet()

view plaincopy to clipboardprint?

1. ...  
2.     private Set keySet = null;  
3.     @Override  
4.     public Set keySet() {  
5.         if(keySet==null) {  
6.             keySet = new Set(){  
7.                 class KeyIterator extends IteratorImpl{  
8.                       
9.                     public KeyIterator(){super();}  
10.                       
11.                     @Override  
12.                     public K next() {  
13.                         checkIteratorState();  
14.                         if(nextNode==null)  
15.                             throw new NoSuchElementException();  
16.                         lastReturned = nextNode;  
17.                         Entry p;  
18.                         if(nextNode.right!=null) {  
19.                             nextNode = nextNode.right;  
20.                             while(nextNode.left!=null) nextNode = nextNode.left;  
21.                         } else {  
22.                             p = nextNode.parent;  
23.                             while(p!=null && p.right == nextNode) {  
24.                                 nextNode = p;  
25.                                 p = nextNode.parent;  
26.                             }  
27.                             nextNode = p;                         
28.                         }  
29.                         return lastReturned.key;  
30.                     }  
31.                       
32.                 }  
33.                   
34.                 @Override  
35.                 public boolean add(K item) {  
36.                     throw new UnsupportedOperationException("Unsupported operation(add)!");  
37.                 }  
38.   
39.                 @Override  
40.                 public boolean addAll(Collectionextends K> arg0) {  
41.                     throw new UnsupportedOperationException("Unsupported operation(addAll)!");  
42.                 }  
43.   
44.                 @Override  
45.                 public void clear() {  
46.                     TreeMap.this.clear();  
47.                 }  
48.   
49.                 @Override  
50.                 public boolean contains(Object key) {  
51.                     return TreeMap.this.containsKey(key);  
52.                 }  
53.   
54.                 @Override  
55.                 public boolean containsAll(Collection arg0) {  
56.                     throw new UnsupportedOperationException("Unsupported operation(entrySet)!");  
57.                 }  
58.   
59.                 @Override  
60.                 public boolean isEmpty() {  
61.                     return TreeMap.this.isEmpty();  
62.                 }  
63.   
64.                 @Override  
65.                 public Iterator iterator() {  
66.                     return new KeyIterator();  
67.                 }  
68.   
69.                 @Override  
70.                 public boolean remove(Object key) {  
71.                     return TreeMap.this.remove(key)!=null;  
72.                 }  
73.   
74.                 @Override  
75.                 public boolean removeAll(Collection arg0) {  
76.                     throw new UnsupportedOperationException("Unsupported operation(removeAll)!");  
77.                 }  
78.   
79.                 @Override  
80.                 public boolean retainAll(Collection arg0) {  
81.                     throw new UnsupportedOperationException("Unsupported operation(retainAll)!");  
82.                 }  
83.   
84.                 @Override  
85.                 public int size() {  
86.                     return TreeMap.this.size();  
87.                 }  
88.   
89.                 @Override  
90.                 public Object[] toArray() {  
91.                     throw new UnsupportedOperationException("Unsupported operation(toArray)!");  
92.                 }  
93.   
94.                 @Override  
95.                 public  T[] toArray(T[] arg0) {  
96.                     throw new UnsupportedOperationException("Unsupported operation(toArray)!");  
97.                 }  
98.                   
99.             };  
100.         }  
101.         return keySet;  
102.     }  
103. ...  
104.     private abstract class IteratorImpl implements Iterator{  
105.         // set expectedModCount to the number of list changes   
106.         // at the time of iterator creation  
107.         protected int expectedModCount = modCount;  
108.         // node of the last value returned by next() if that  
109.         // value was deleted by the iterator method remove().  
110.         protected Entry lastReturned = null;  
111.         // node whose value is returned a subsequent call to next;  
112.         protected Entry nextNode = null;  
113.           
114.         IteratorImpl(){           
115.             nextNode = root;  
116.             //System.out.println("Root is "+nextNode.key+" with parent="+nextNode.parent);  
117.             if(nextNode!=null)  
118.                 while(nextNode.left!=null)  
119.                     nextNode = nextNode.left;  
120.         }  
121.           
122.         protected void checkIteratorState(){  
123.             if(expectedModCount!=modCount) throw new ConcurrentModificationException("Concurrent Modification Exception!");  
124.         }         
125.         @Override  
126.         public boolean hasNext() {  
127.             return nextNode!=null;  
128.         }  
129.         @Override  
130.         public void remove() {  
131.             throw new java.lang.UnsupportedOperationException();              
132.         }  
133.     }  
134. ...  

Supplement : 
* Java In a Nutshell : Anonymous Classes 

An anonymous class is a local class without a name. An anonymous class is defined and instantiated in a single succinct expression using the new operator. While a local class definition is a statement in a block of Java code, an anonymous class definition is an expression, which means that it can be included as part of a larger expression, such as a method call. When a local class is used only once, consider using anonymous class syntax, which places the definition and use of the class in exactly the same place.