I have run across a couple cases which may or may not be defects in
TreeMap. Or, it's simply a case where I am not understanding the Java
docs for TreeMap & NavigableMap correctly.
When looking at the Java docs for TreeMap / NavigableMap tailMap() I
read, "Returns a view of the portion of this map whose keys are greater
than (or equal to, if |inclusive| is true) |fromKey|. The returned map
is backed by this map, so changes in the returned map are reflected in
this map, and vice-versa. The returned map supports all optional map
operations that this map supports." More importantly, I read this
method will throw an "||IllegalArgumentException if this map itself has
a restricted range, and |fromKey| lies outside the bounds of the range".
I interpret the latter here to mean if I create a subMap(), headMap() or
tailMap() I have a map which has "a restricted range"?
Assuming my interpretation is correct. I wrote a test program on a
TreeMap containing Integer keys and String values. I populated the
TreeMap with keys 5 - 5000 at every 5th integer, (i.e. 5,10,15,20,25,
.... 4985,4990,4995,5000). And, for each key, I just created a string
such as, "Value stored is -> <key>".
I found if I do a
subMap(Integer.valueOf(5),true,Integer.valueOf(5000),true) I get a
NavigableMap back containing the same keys/values as the TreeMap. If I
then do a tailMap(Integer.valueOf(4850),false), I get a NavigableMap
back containing keys 4855 - 5000 and their corresponding values. All as
expected to this point. If I now do a
tailMap(Integer.valueOf(4850,false) on that last NavigableMap I got back
which contains keys 4855 - 5000, according to the Java doc, I would
expect an IllegalArgumentException to be thrown since 4850 is outside
the bounds of 4855 - 5000. But, this is not what happens. I get the
same NavigableMap back containing keys 4855 - 5000.
I can produce a similar result by taking the same initial TreeMap, doing
a descendingMap() on it. Then, doing a headMap(Integer.valueOf(4850))
followed by a headMap(Integer.valueOf(4850)). I am interpreting that a
headMap(K key) on a descendingMap is essentially the same as a tailMap(K
key, false) on an ascending map of the same underlying TreeMap.
Am I interpreting some completely wrong? Or, is the not throwing of an
IllegalArgumentException expected behavior? Or, is this indeed a defect?
Attached is a simple program which illustrates what I have described.
thanks,
charlie ...
--
Charlie Hunt
Java Performance Engineer
<http://java.sun.com/docs/performance/>
import java.util.NavigableMap;
import java.util.SortedMap;
import java.util.TreeMap;
public class TestTreeMap {
private TreeMap<Integer, String> tm;
public TestTreeMap() {
tm = new TreeMap<Integer, String>();
}
private void clearTreeMap() {
System.out.println("Clearing TreeMap ...");
tm.clear();
System.out.println("TreeMap cleared.");
}
private boolean descendingMapTests(NavigableMap<Integer, String> treeMap) {
System.out.println("test descendingMap ...");
boolean passed = true;
this.clearTreeMap();
this.populateTreeMap(1000);
// headMap(toKey) on a descendingMap actually returns tailMap(toKey, false)
Integer firstKey = Integer.valueOf(4850);
// get a descending sorted map of the entire tree,
// sm should have keys 5000 - 5
SortedMap<Integer, String> sm = treeMap.descendingMap();
// get a descending sorted map of keys < 4850 from the descending sorted
// map that has keys 5000 - 5, should return a sorted map with
// keys 5000 - 4855
sm = sm.headMap(firstKey);
boolean caught = false;
try {
// attempt to get a descending sorted map of keys < 4850, from a
// descending sorted map with keys 5000 - 4855
sm = sm.headMap(firstKey);
} catch (IllegalArgumentException iae) {
caught = true;
} finally {
if (!caught) {
passed = false;
System.err.println("Unexpected Error: headMap(4850) on a map " +
"containing keys 5000 - 4855 did not throw " +
"IllegalArgumentException as expected!");
}
}
if (passed) {
System.out.println("PASSED: descendingMap() tests done.");
} else {
System.err.println("FAILED: descendingMapTests().");
}
return passed;
}
private void populateTreeMap(int numberOfEntries) {
StringBuilder sb = new StringBuilder();
int start = 5;
for (int i = 1; i <= numberOfEntries; i++) {
sb.setLength(0);
int key = start * i;
sb.append("Value stored is -> ").append(key);
tm.put(key, sb.toString());
}
}
private void subMapTests(NavigableMap<Integer,String> treeMap) {
System.out.println("test subMaps ...");
boolean passed = true;
this.clearTreeMap();
this.populateTreeMap(1000);
NavigableMap<Integer, String> nm;
Integer startKey = Integer.valueOf(5);
Integer endKey = Integer.valueOf(5000);
Integer firstKey = Integer.valueOf(4850);
// get a subMap keys > 5 and <= 5000, that's keys 10 - 5000
nm = treeMap.subMap(startKey,false,endKey,true);
// get a tailMap of keys > 4850, that's keys 4855 - 5000
nm = nm.tailMap(firstKey, false);
boolean caught = false;
try {
// attempt to get a tailMap of keys > 4850 on a map containing
// keys 4855 - 5000. This should throw IllegalArgumentException
nm = nm.tailMap(firstKey, false);
} catch (IllegalArgumentException iae) {
caught = true;
} finally {
if (!caught) {
passed = false;
System.err.println("Unexpected Error: tailMap(4850,false) on a map " +
"containing keys 4855 - 5000 did not throw " +
"IllegalArgumentException as expected!");
}
}
if (passed) {
System.out.println("PASSED: subMapTests() tests.");
} else {
System.err.println("FAILED: subMapTests().");
}
}
public static void main(String[] args) {
TestTreeMap ttm = new TestTreeMap();
// descendingMap
ttm.descendingMapTests(ttm.tm);
// sub map tests
ttm.subMapTests(ttm.tm);
}
}
