In my previous post I discussed about sorting a view column using java.util.TreeMap. In this post I shall discuss about some optimizations to address the issue with duplicate values (refer to the line 1921 in previous post).
Let us calculate time complexity of existing code:
From here: http://java.sun.com/javase/6/docs/api/java/util/TreeMap.html
This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations. Therefore,
Time complexity of TreeMap.containsKey, T1 = log(n)
Time complexity of TreeMap.put, T2 = log(n)
Time complexity of inner while loop, T3 = n * T1
Total time complexity,
T = n * (T3 + log(n)) log(n) for TreeMap.put
T = n * (n * T1 + log(n))
T = n * (n * log(n) + log(n))
T = n * (n + 1) * log(n)
From above calculation we can hardly do anything with T1 and T2, but we can optimize T3.
Let us modify the code to optimize:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

var loView:NotesView = null; var loEntryColl:NotesViewEntryCollection = null; var loTreeMap:java.util.TreeMap = new java.util.TreeMap(); var lsSortBy = viewScope.get("sortBy"); try { loView = database.getView("view"); if(null == lsSortBy  "" == lsSortBy) { lsSortBy = 0; } if(null != loView && loView.getEntryCount() > 0) { loEntryColl = loView.getAllEntries(); var loEntry:NotesViewEntry = loEntryColl.getFirstEntry(); var loTempEntry:NotesViewEntry = null; var keys:java.util.HashMap = new java.util.HashMap(); while(null != loEntry) { loDoc = loEntry.getDocument(); var lsKey = loEntry.getColumnValues().get(lsSortBy); if(keys.containsKey(lsKey)) { var k = keys.get(lsKey); lsKey = @LowerCase(lsKey); k += "~"; keys.put(lsKey, k); lsKey += k; } else { keys.put(lsKey, '~'); } /*while(loTreeMap.containsKey(lsKey)) { lsKey += "~"; }*/ loTreeMap.put(lsKey, loEntry.getColumnValues()); loTempEntry = loEntryColl.getNextEntry(loEntry); loEntry.recycle(); loEntry = loTempEntry; } } } catch(e) { print("Error : " + e); } finally { if(null != loView) loView.recycle(); if(null != loEntryColl) loEntryColl.recycle(); } return loTreeMap.values(); 
From the API doc of HashMap:
This implementation provides constanttime performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets.
Let us calculate the time complexity of this code:
Time complexity of HashMap.containsKey, T4 = K1 , where K is constant
Time complexity of HashMap.get, T5 = K2 , where K2 is constant
Time complexity of HashMap.put, T6 = K3 , where K3 is constant
Total time complexity,
T’ = n * (T4 + T5 + T6 + log(n))
T’ = n * (K1 + K2 + K3 + log(n))
T’ = n * (K + log(n)) , where K = K1 + K2 + K3
It is clear that T’ < T. Hence our new algorithm is much more better than previous one.