register
other register

Friday, August 10, 2007

Sorting Map

The following definition is from Java API.

HashMap:

Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

LinkedHashMap:

Hash table and linked list implementation of the Map interface, with predictable iteration order. This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order). Note that insertion order is not affected if a key is re-inserted into the map. (A key k is reinserted into a map m if m.put(k, v) is invoked when m.containsKey(k) would return true immediately prior to the invocation.)

TreeMap:

Red-Black tree based implementation of the SortedMap interface. This class guarantees that the map will be in ascending key order, sorted according to the natural order for the key's class (see Comparable), or by the comparator provided at creation time, depending on which constructor is used.

Problem Solving:
One university department has three levels of courses, namely undergraduate, postgraduate taught, and postgraduate research to offer. The department wants to show these courses in alphabatical order within respective level of course. The order of the level should be: undergraduate, postgraduate taught, postgraduate research.


LinkedHashMap courseMap = new LinkedHashMap();
TreeMap ugCourseTreeMap = new TreeMap();
courseMap.put("UG", ugCourseTreeMap);

TreeMap pgtCourseTreeMap = new TreeMap();
courseMap.put("PGT", pgtCourseTreeMap);

TreeMap pgrCourseTreeMap = new TreeMap();
courseMap.put("PGR", pgrCourseTreeMap);

// looping begins
// courseName is a String
// course is a class

ugCourseTreeMap.put(courseName, course);
pgtCourseTreeMap.put(courseName, course);
pgrCourseTreeMap.put(courseName, course);

// looping end

Iterator it = ugCourseTreeMap.values().iterator();
while(it.hasNext()) {

}


/**************No need to do the following************
/**************Because TreeMap is ordered*************
ArrayList keysUG = new ArrayList();
keysUG.addAll(ugCourseMap.keySet());
Collections.sort(keysUG);

ArrayList keysPGT = new ArrayList();
keysPGT.addAll(pgtCourseMap.keySet());
Collections.sort(keysPGT);

ArrayList keysPGR = new ArrayList();
keysPGR.addAll(pgrCourseMap.keySet());
Collections.sort(keysPGR);

// Iteration example
Iterator it = ugCourseMap.keySet().iterator();
while (it.hasNext()) {
..
}

/**********************************************

No comments: