Thursday, September 12, 2013

TreeMap

TreeMap is a data structure that most its operations (e.g. containsKey, get,put, remove) cost log(n) time. Like HashMap, TreeMap can be used to store pairs of keys and values. However, the TreeMap uses Binary Search Tree technique in its internal structure. You can sort entries in the TreeMap (key-based sorting).  The following code fragment creates a TreeMap object with default native sorting.

import java.util.Comparator;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeMap;

public class TreeMapDemo {
TreeMap<String,String> tmap;
TreeMapDemo(){
tmap=new TreeMap<String, String>(); //create TreeMap object with default sort order

}

public static void main(String[] args){
TreeMapDemo hmd=new TreeMapDemo();

}


}
You can add a new entry that contains key and value by using the put<Object key,Object value) method. The following code adds some entries to the TreeMap, tmap.
public void addEntries(){

tmap.put("85516500379","Sunrise Child Care & Development Center");
tmap.put("85523880502","Krousar Thmey - Temporary Street Children");
tmap.put("855545483","Ming Hour Home Service");
tmap.put("85515907797","Happy Kid Care");


}

The get(Object key) method can be used to return a value for a specified key input. The following code fragment accepts the key input. Then its checks whether the key contains in the TreeMap, tmap. If true, the value of an entry that contains the specified key will be returned.

public String searchMap(String key){
if(tmap.containsKey(key)) return tmap.get(key);
else return null;
}

To traverse through the TreeMap, you can use its keySet method. The keySet method returns a set object that contains all keys in the TreeMap. The set object has the iterator method that can be used to read every key in the set object. The following code below displays all keys and their values in the TreeMap, tmap.

public void showTreeMapContent(){
Set<String> keys=tmap.keySet();
Iterator<String> i=keys.iterator();
while(i.hasNext()){
String key=i.next();
System.out.println(key+"\t"+tmap.get(key));

}

}

For the native sorting, the smaller key comes first, then the next is the larger key. You can change this order by using the Comparator interface. You need to create a class that implements this interface and override the compare(Object obj1, Object obj2) method. Then create an instance of the class and supply it to the constructor of the TreeMap. The program below can be compiled and run to see the result. First, you can give -1 value to the Sorter and compile and run the program. Again give 1 value to the Sorter and compile and run the program. You will notice that different sort orders are made to the entries of the TreeMap.

import java.util.Comparator;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeMap;

public class TreeMapDemo {
TreeMap<String,String> tmap;
TreeMapDemo(){
tmap=new TreeMap<String, String>(new Sorter(-1));
}

class Sorter implements Comparator<Object>{
int order=-1;
Sorter(int order){
this.order=order;
}

public int compare(Object ob1,Object ob2){
if(ob1.toString().compareTo(ob2.toString())==0) return 0;
else if(ob1.toString().compareTo(ob2.toString())<0)
return order;
else
return(-1*order);
}

}

public void addEntries(){
tmap.put("85516500379","Sunrise Child Care & Development Center");
tmap.put("85523880502","Krousar Thmey - Temporary Street Children");
tmap.put("855545483","Ming Hour Home Service");
tmap.put("85515907797","Happy Kid Care");


}

public String searchMap(String key){
if(tmap.containsKey(key)) return tmap.get(key);
else return null;
}
public void showTreeMapContent(){
Set<String> keys=tmap.keySet();
Iterator<String> i=keys.iterator();
while(i.hasNext()){
String key=i.next();
System.out.println(key+"\t"+tmap.get(key));

}

}

public static void main(String[] args){
TreeMapDemo tmd=new TreeMapDemo();
tmd.addEntries();
tmd.showTreeMapContent();

}


}

No comments:

Post a Comment