程式扎記: [ Data Structures with Java ] Section 20.2 : Implementing the TreeMap Class

標籤

2011年3月29日 星期二

[ Data Structures with Java ] Section 20.2 : Implementing the TreeMap Class


Preface :
We are about to roll up our sleeves and go to work implementing the TreeMap class. Before we start, however, let us step back and examine the tasks and requirements. The TreeMap class implements the Map interface, which defines methods such as get(), put() and remove() that access and update elements in a map collection. The Map interface specifies the interface Map.Entry as an inner interface. Map.Entry defines the structure of key-value pairs that are inserted into a map. It also defines a restricted set of methods for access and update to a key-value pair. A programmer can use a MapEntry reference to access the key and value with the methods getKey() and getValue() and can update the value component using setValue(). No update to the key component is available since the operation could destroy the tree ordering of the map. This interface, like the OrderedSet interface, defines methods that return minimum and maximum elements. The method firstKey() returns the first (least) key in the ordered map, and the method lastKey() returns the last(greatest) key in the map. Besides all the methods specified by the interfaces, the TreeMap class provides a constructor and the method toString(), which creates a string that describes the elements in the map.The UML diagram in below figure provides a blueprint for the methods and inner actions that must be designed into the implementation of the TreeMap class :

The implementation of TreeMap builds a binary search tree. The nodes are Entry objects that contains a key-value pair and references to the left and right subtrees of the node as well as a reference to the parent of the node :

The similarity between an Entry node for a TreeMap object and an STNode for an STree object is apparent. The difference, of course, is that an Entry has a key-value pair for its "value" component. The Entry objects in the search tree are ordered by the key.
The class Entry is defined as a static inner class within the TreeMap class. It implements the Map.Entry interface. The class is designated as static because it makes no reference to any variables in the outer class TreeMap. All of the features of the Entry class are shown in the following declaration of the class, including a constructor and the method toString() that returns a representation of an interface in the form 'key=value' :
- TreeMap class : Inner class Entry implementation
  1. import java.util.Collection;  
  2. import java.util.Map;  
  3. import java.util.Set;  
  4.   
  5. public class TreeMapextends Comparablesuper K>,V> implements OrderedMap{  
  6.     private Entry root;  
  7.     // size of the map  
  8.     private int mapSize;  
  9.     private int modCount;  
  10.   
  11.     public TreeMap(){  
  12.         root = null;  
  13.         mapSize = 0;  
  14.         modCount = 0;  
  15.     }  
  16. ...  
  17.     private static class Entry implements Map.Entry {  
  18.         K key;  
  19.         V value;  
  20.           
  21.         // child links and link to the node's parent  
  22.         Entry left, right, parent;  
  23.           
  24.         public Entry(K key, V value, Entry parent) {  
  25.             this.key = key;  
  26.             this.value = value;  
  27.             left = null;  
  28.             right = null;  
  29.             this.parent = parent;  
  30.         }  
  31.           
  32.         @Override  
  33.         public K getKey() {           
  34.             return key;  
  35.         }  
  36.   
  37.         @Override  
  38.         public V getValue() {  
  39.             return value;  
  40.         }  
  41.   
  42.         @Override  
  43.         public V setValue(V value) {  
  44.             V oldValue = this.value;  
  45.             this.value = value;  
  46.             return oldValue;              
  47.         }  
  48.           
  49.         public String toString(){return key+"="+value;}  
  50.     }  
  51. ...  
  52. }  

The TreeMap Class Design :
The TreeMap class builds a binary search tree of Entry objects. The private instance variable root is a reference to an Entry node that defines the search tree. Two integer variables mapSize and modCount maintain the size of the collection and the number of tree modification (insertions and deletions). The class constructor creates an empty map and toString() displays the entries as a comma-separated list of elements in braces "{" and "}". Each element has the form key=value. The other methods implement OrderedMap interface operations. The following is a skeletal declaration of the TreeMap class that includes an implementation of the constructor :
- TreeMap class : base design structure
  1. public class TreeMapextends Comparablesuper K>,V> implements OrderedMap{  
  2.     private Entry root;  
  3.     // size of the map  
  4.     private int mapSize;  
  5.     private int modCount;  
  6.   
  7.     public TreeMap(){  
  8.         root = null;  
  9.         mapSize = 0;  
  10.         modCount = 0;  
  11.     }  
  12. ...  
  13.     private static class Entry implements Map.Entry {...}   
  14. }  

Key Access to an Entry :
Map methods such as get(), containsKey() and remove() use a key argument to access an entry in the map. We provide access with the private method getEntry(), which takes a key and searches the tree for a pair with the specified key. It returns a reference to the key-value pair in the tree or null of it failed to locate an entry with the key. The getEntry() method is the search engine that provides low-level access to the entry nodes based only on the key :
- Method getEntry :
  1. private Entry getEntry(K key) {  
  2.     Entry entry = root;  
  3.     while(entry!=null) {  
  4.         if(entry.key.compareTo(key)==0)  
  5.             return entry;  
  6.         else if(key.compareTo(entry.key)>0)  
  7.             entry = entry.right;  
  8.         else   
  9.             entry = entry.left;  
  10.     }  
  11.     return null;  
  12. }  

The method containsKey() indicates whether an entry with the specified key is in the map or not. Its implementation is a direct application of getEntry(). It simply returns true if the return reference is non-null and false otherwise :
- Method containsKey() :
  1. @Override  
  2. public boolean containsKey(Object key) {  
  3.     return getEntry((K)key)!=null;  
  4. }  

Access to the value component of a key-value pair is provided by the method get(). After calling getEntry() to locate the entry, the method return null or the contents of the value field depending on whether the entry is in the map. The contents are accessed using the method getValue() :
- Method get() :
  1. @Override  
  2. public V get(Object key) {  
  3.     Entry entry = getEntry((K)key);  
  4.     if(entry!=nullreturn entry.getValue();  
  5.     return null;  
  6. }  

Updating an Entry :
For a map, the put() operation with arguments for the key and the value serves a dual purpose. It adds a new entry or it updates the value filed for an existing entry. The algorithm is the binary search tree insertion algorithm. Start at the root and search down a path using search tree ordering. If a match occurs, then an entry with the specified key is already in the map. Simply use setValue() with the value argument to update the value field in the matching entry. Otherwise, the scan ends in an empty tree, which becomes the insertion location. Create an Entry object with the specified key and value arguments and add the new node :
- Method put() :
  1. @Override  
  2. public V put(K key, V value) {  
  3.     Entry entry = root;    
  4.     if(root == null) {  
  5.         root = new Entry(key, value, null);  
  6.     } else {  
  7.         while(entry!=null) {  
  8.             int crst = key.compareTo(entry.key);  
  9.             if(crst==0)   
  10.                 return entry.setValue(value);  
  11.             else if(crst>0)  
  12.                 if(entry.right==null) {  
  13.                     entry.right = new Entry(key, value, entry);  
  14.                     break;  
  15.                 } else {  
  16.                     entry = entry.right;  
  17.                 }  
  18.             else {  
  19.                 if(entry.left==null) {  
  20.                     entry.left = new Entry(key, value, entry);  
  21.                     break;  
  22.                 } else {  
  23.                     entry = entry.left;  
  24.                 }  
  25.             }  
  26.                   
  27.         }  
  28.     }  
  29.     modCount++;  
  30.     mapSize++;  
  31.     return null;  
  32. }  

Removing an Entry :
The implementation of remove() uses getEntry() to determine if there is a key-value pair in the map with specified key. If there is, the private method removeNode() takes a reference to the node and deletes it from the tree. The method removeNode() uses the deletion algorithm for binary search tree discussed in Section 18.3. With remove(), we have some housekeeping to do. The size of the map is decremented, modCount is incremented, and the value of the deleted node is the return value :
- Method remove() :
  1. @Override  
  2. public V remove(Object key) {  
  3.     Entry dNode = getEntry((K)key);  
  4.     if(dNode==null)  
  5.         return null;  
  6.     V returnObj = dNode.value;  
  7.     removeNode(dNode);  
  8.     mapSize--;  
  9.     modCount++;  
  10.     return returnObj;  
  11. }  
  12.   
  13. private V removeNode(Entry entry) {  
  14.     if(entry==null || root ==null)  
  15.         return null;  
  16.     else{  
  17.         V returnVal = entry.value;  
  18.         if(entry.left==null || entry.right==null) {  
  19.             Entry pNode = entry.parent;  
  20.             Entry rNode = entry.left!=null?entry.left:entry.right;  
  21.             if(pNode!=null) {  
  22.                 if(pNode.left == entry) {  
  23.                                            pNode.left = rNode;  
  24.                                            rNode.parent = pNode;  
  25.                 }else{  
  26.                                            pNode.right = rNode;                   
  27.                                            rNode = pNode;  
  28.                                        }  
  29.             } else { // remove root  
  30.                 root = rNode;                         
  31.                 if(root!=null) root.parent = null;  
  32.             }  
  33.         } else {  
  34.             /* Deleted node has two nonnull children */  
  35.             Entry pOfRNode = entry;  
  36.             Entry rNode = entry.right;  
  37.             while(rNode.left!=null) {  
  38.                 pOfRNode = rNode;  
  39.                 rNode = rNode.left;  
  40.             }  
  41.             entry.value = rNode.value;  
  42.             if(pOfRNode == entry) {  
  43.                 entry.right = rNode.right;  
  44.             } else {  
  45.                 pOfRNode.left = rNode.right;  
  46.             }  
  47.             if(rNode.right!=null) rNode.parent = pOfRNode;  
  48.         }  
  49.         return returnVal;  
  50.     }  
  51. }  

Complexity of Insertion and Deletion in TreeSet and TreeMap :
Because the TreeSet and TreeMap classes implement insertion and deletion using a binary search tree, the average running for these operations is O(log2n). However, a binary search tree can be degenerate, so the worst-case running time for these operations is O(n). We can guarantee uniform O(log2n) performance by using balanced trees such as red-black tree or a AVL tree instead of a normal binary search tree.

Supplement :
Java Gossip : 內部類別(Inner class)
使用內部類別的好處在於可以直接存取外部類別的私用(private)成員,舉個例子來說,在視窗程式中,您可以使用內部類別來實作一個事件傾聽者類別,這個視窗傾聽者類別可以直接存取視窗元件,而不用透過參數傳遞.
另一個好處是,當某個Slave類別完全只服務於一個Master類別時,我們可以將之設定為內部類別,如此使用Master類別的人就不用知道 Slave的存在.
This message was edited 2 times. Last update was at 30/03/2011 10:24:05

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!