Fixing a few TreeMap bugs found by the latest Harmony tests.
diff --git a/libcore/expectations/brokentests.txt b/libcore/expectations/brokentests.txt
index caf92e7..8521388 100644
--- a/libcore/expectations/brokentests.txt
+++ b/libcore/expectations/brokentests.txt
@@ -740,3 +740,34 @@
 test org.apache.harmony.text.tests.java.text.RuleBasedCollatorTest#testEqualsObject
 result EXEC_FAILED
 pattern .*expected:<0> but was:<1>.*
+
+
+# These Harmony tests are enforcing a buggy behaviour in TreeMap, presumably to be bug-compatible
+# with the RI. Our implementation is more conservative and throws on the bogus inputs.
+test org.apache.harmony.luni.tests.java.util.TreeMapExtendTest#test_AscendingSubMapKeySet_headSet
+result EXEC_FAILED
+pattern .*java.lang.IllegalArgumentException: 100 not in range \(100..109\].*
+
+test org.apache.harmony.luni.tests.java.util.TreeMapExtendTest#test_AscendingSubMapKeySet_tailSet
+result EXEC_FAILED
+pattern .*java.lang.IllegalArgumentException: null not in range \[100..109\).*
+
+test org.apache.harmony.luni.tests.java.util.TreeMapExtendTest#test_DescendingSubMapKeySet_headSet
+result EXEC_FAILED
+pattern .*java.lang.IllegalArgumentException: null not in range \[100..109\).*
+
+test org.apache.harmony.luni.tests.java.util.TreeMapExtendTest#test_DescendingSubMap_tailMap
+result EXEC_FAILED
+pattern .*java.lang.IllegalArgumentException: 100 not in range \(100..109\].*
+
+test org.apache.harmony.luni.tests.java.util.TreeMapExtendTest#test_DescendingSubMapKeySet_tailSet
+result EXEC_FAILED
+pattern .*java.lang.IllegalArgumentException: 100 not in range \(100..109\].*
+
+test org.apache.harmony.luni.tests.java.util.TreeMapExtendTest#test_SubMap_headMap
+result EXEC_FAILED
+pattern .*java.lang.IllegalArgumentException: 100 not in range \(100..109\].*
+
+test org.apache.harmony.luni.tests.java.util.TreeMapExtendTest#test_Entry_setValue
+result EXEC_FAILED
+pattern .*java.lang.UnsupportedOperationException.*.setValue.*
diff --git a/libcore/luni/src/main/java/java/util/TreeMap.java b/libcore/luni/src/main/java/java/util/TreeMap.java
index 7075cec..64eeb38 100644
--- a/libcore/luni/src/main/java/java/util/TreeMap.java
+++ b/libcore/luni/src/main/java/java/util/TreeMap.java
@@ -1050,9 +1050,33 @@
      */
 
     enum Bound {
-        INCLUSIVE,
-        EXCLUSIVE,
-        NO_BOUND
+        INCLUSIVE {
+            @Override public String leftCap(Object from) {
+                return "[" + from;
+            }
+            @Override public String rightCap(Object to) {
+                return to + "]";
+            }
+        },
+        EXCLUSIVE {
+            @Override public String leftCap(Object from) {
+                return "(" + from;
+            }
+            @Override public String rightCap(Object to) {
+                return to + ")";
+            }
+        },
+        NO_BOUND {
+            @Override public String leftCap(Object from) {
+                return ".";
+            }
+            @Override public String rightCap(Object to) {
+                return ".";
+            }
+        };
+
+        public abstract String leftCap(Object from);
+        public abstract String rightCap(Object to);
     }
 
     /**
@@ -1068,7 +1092,7 @@
         BoundedMap(boolean ascending, K from, Bound fromBound, K to, Bound toBound) {
             /*
              * Validate the bounds. In addition to checking that from <= to, we
-             * verify that the comparator supports our bound objets.
+             * verify that the comparator supports our bound objects.
              */
             if (fromBound != NO_BOUND && toBound != NO_BOUND) {
                 if (comparator.compare(from, to) > 0) {
@@ -1105,7 +1129,7 @@
 
         @Override public V put(K key, V value) {
             if (!isInBounds(key)) {
-                throw new IllegalArgumentException();
+                throw outOfBounds(key, fromBound, toBound);
             }
             return putInternal(key, value);
         }
@@ -1157,10 +1181,6 @@
             return node != null && isInBounds(node.getKey(), fromBound, toBound) ? node : null;
         }
 
-        private Entry<K, V> bound(Entry<K, V> node) {
-            return bound(node, fromBound, toBound);
-        }
-
         /*
          * Navigable methods.
          */
@@ -1243,39 +1263,92 @@
             }
         }
 
+        /**
+         * Performs a find on the underlying tree after constraining it to the
+         * bounds of this view. Examples:
+         *
+         *   bound is (A..C)
+         *   findBounded(B, FLOOR) stays source.find(B, FLOOR)
+         *
+         *   bound is (A..C)
+         *   findBounded(C, FLOOR) becomes source.find(C, LOWER)
+         *
+         *   bound is (A..C)
+         *   findBounded(D, LOWER) becomes source.find(C, LOWER)
+         *
+         *   bound is (A..C]
+         *   findBounded(D, FLOOR) becomes source.find(C, FLOOR)
+         *
+         *   bound is (A..C]
+         *   findBounded(D, LOWER) becomes source.find(C, FLOOR)
+         */
+        private Entry<K, V> findBounded(K key, Relation relation) {
+            relation = relation.forOrder(ascending);
+            Bound fromBoundForCheck = fromBound;
+            Bound toBoundForCheck = toBound;
+
+            if (toBound != NO_BOUND && (relation == LOWER || relation == FLOOR)) {
+                int comparison = comparator.compare(to, key);
+                if (comparison <= 0) {
+                    key = to;
+                    if (toBound == EXCLUSIVE) {
+                        relation = LOWER; // 'to' is too high
+                    } else if (comparison < 0) {
+                        relation = FLOOR; // we already went lower
+                    }
+                }
+                toBoundForCheck = NO_BOUND; // we've already checked the upper bound
+            }
+
+            if (fromBound != NO_BOUND && (relation == CEILING || relation == HIGHER)) {
+                int comparison = comparator.compare(from, key);
+                if (comparison >= 0) {
+                    key = from;
+                    if (fromBound == EXCLUSIVE) {
+                        relation = HIGHER; // 'from' is too low
+                    } else if (comparison > 0) {
+                        relation = CEILING; // we already went higher
+                    }
+                }
+                fromBoundForCheck = NO_BOUND; // we've already checked the lower bound
+            }
+
+            return bound(find(key, relation), fromBoundForCheck, toBoundForCheck);
+        }
+
         public Entry<K, V> lowerEntry(K key) {
-            return bound(find(key, LOWER.forOrder(ascending)));
+            return findBounded(key, LOWER);
         }
 
         public K lowerKey(K key) {
-            Entry<K, V> entry = bound(find(key, LOWER.forOrder(ascending)));
+            Entry<K, V> entry = findBounded(key, LOWER);
             return entry != null ? entry.getKey() : null;
         }
 
         public Entry<K, V> floorEntry(K key) {
-            return bound(find(key, FLOOR.forOrder(ascending)));
+            return findBounded(key, FLOOR);
         }
 
         public K floorKey(K key) {
-            Entry<K, V> entry = bound(find(key, FLOOR.forOrder(ascending)));
+            Entry<K, V> entry = findBounded(key, FLOOR);
             return entry != null ? entry.getKey() : null;
         }
 
         public Entry<K, V> ceilingEntry(K key) {
-            return bound(find(key, CEILING.forOrder(ascending)));
+            return findBounded(key, CEILING);
         }
 
         public K ceilingKey(K key) {
-            Entry<K, V> entry = bound(find(key, CEILING.forOrder(ascending)));
+            Entry<K, V> entry = findBounded(key, CEILING);
             return entry != null ? entry.getKey() : null;
         }
 
         public Entry<K, V> higherEntry(K key) {
-            return bound(find(key, HIGHER.forOrder(ascending)));
+            return findBounded(key, HIGHER);
         }
 
         public K higherKey(K key) {
-            Entry<K, V> entry = bound(find(key, HIGHER.forOrder(ascending)));
+            Entry<K, V> entry = findBounded(key, HIGHER);
             return entry != null ? entry.getKey() : null;
         }
 
@@ -1354,31 +1427,39 @@
                 toBound = fromBoundTmp;
             }
 
+            /*
+             * If both the current and requested bounds are exclusive, the isInBounds check must be
+             * inclusive. For example, to create (C..F) from (A..F), the bound 'F' is in bounds.
+             */
+
             if (fromBound == NO_BOUND) {
                 from = this.from;
                 fromBound = this.fromBound;
-            } else if (this.fromBound != NO_BOUND) {
-                int comparison = comparator.compare(from, this.from);
-                if (comparison < 0 || (comparison == 0
-                        && fromBound == INCLUSIVE && this.fromBound == EXCLUSIVE)) {
-                    throw new IllegalArgumentException();
+            } else {
+                Bound fromBoundToCheck = fromBound == this.fromBound ? INCLUSIVE : this.fromBound;
+                if (!isInBounds(from, fromBoundToCheck, this.toBound)) {
+                    throw outOfBounds(to, fromBoundToCheck, this.toBound);
                 }
             }
 
             if (toBound == NO_BOUND) {
                 to = this.to;
                 toBound = this.toBound;
-            } else if (this.toBound != NO_BOUND) {
-                int comparison = comparator.compare(to, this.to);
-                if (comparison > 0 || (comparison == 0
-                        && toBound == EXCLUSIVE && this.toBound == INCLUSIVE)) {
-                    throw new IllegalArgumentException();
+            } else {
+                Bound toBoundToCheck = toBound == this.toBound ? INCLUSIVE : this.toBound;
+                if (!isInBounds(to, this.fromBound, toBoundToCheck)) {
+                    throw outOfBounds(to, this.fromBound, toBoundToCheck);
                 }
             }
 
             return new BoundedMap(ascending, from, fromBound, to, toBound);
         }
 
+        private IllegalArgumentException outOfBounds(Object value, Bound fromBound, Bound toBound) {
+            return new IllegalArgumentException(value + " not in range "
+                    + fromBound.leftCap(from) + ".." + toBound.rightCap(to));
+        }
+
         /*
          * Bounded view implementations.
          */