From f6b0c8b47c903d47cedf182e5aa78276283a2f32 Mon Sep 17 00:00:00 2001
From: Narayan Kamath <narayan@google.com>
Date: Wed, 15 Apr 2015 16:04:21 +0100
Subject: Fix bad negation in Collections#binarySearch.

bug: 19749094
Change-Id: Id1d7bcf4abebb423fd3bbb7c8f379bf9e6234969
---
 luni/src/main/java/java/util/Collections.java      | 32 +++++-----
 .../java/libcore/java/util/CollectionsTest.java    | 72 ++++++++++++++++++++++
 2 files changed, 88 insertions(+), 16 deletions(-)

(limited to 'luni')

diff --git a/luni/src/main/java/java/util/Collections.java b/luni/src/main/java/java/util/Collections.java
index c8a6a73..dc4161f 100644
--- a/luni/src/main/java/java/util/Collections.java
+++ b/luni/src/main/java/java/util/Collections.java
@@ -1426,21 +1426,21 @@ public class Collections {
         if (!(list instanceof RandomAccess)) {
             ListIterator<? extends Comparable<? super T>> it = list.listIterator();
             while (it.hasNext()) {
-                int result;
-                if ((result = -it.next().compareTo(object)) <= 0) {
-                    if (result == 0) {
-                        return it.previousIndex();
-                    }
+                final int result = it.next().compareTo(object);
+                if (result == 0) {
+                    return it.previousIndex();
+                } else if (result > 0) {
                     return -it.previousIndex() - 1;
                 }
             }
             return -list.size() - 1;
         }
 
-        int low = 0, mid = list.size(), high = mid - 1, result = -1;
+        int low = 0, mid = list.size(), high = mid - 1, result = 1;
         while (low <= high) {
             mid = (low + high) >>> 1;
-            if ((result = -list.get(mid).compareTo(object)) > 0) {
+            result = list.get(mid).compareTo(object);
+            if (result < 0) {
                 low = mid + 1;
             } else if (result == 0) {
                 return mid;
@@ -1448,7 +1448,7 @@ public class Collections {
                 high = mid - 1;
             }
         }
-        return -mid - (result < 0 ? 1 : 2);
+        return -mid - (result > 0 ? 1 : 2);
     }
 
     /**
@@ -1481,21 +1481,21 @@ public class Collections {
         if (!(list instanceof RandomAccess)) {
             ListIterator<? extends T> it = list.listIterator();
             while (it.hasNext()) {
-                int result;
-                if ((result = -comparator.compare(it.next(), object)) <= 0) {
-                    if (result == 0) {
-                        return it.previousIndex();
-                    }
+                final int result = comparator.compare(it.next(), object);
+                if (result == 0) {
+                    return it.previousIndex();
+                } else if (result > 0) {
                     return -it.previousIndex() - 1;
                 }
             }
             return -list.size() - 1;
         }
 
-        int low = 0, mid = list.size(), high = mid - 1, result = -1;
+        int low = 0, mid = list.size(), high = mid - 1, result = 1;
         while (low <= high) {
             mid = (low + high) >>> 1;
-            if ((result = -comparator.compare(list.get(mid), object)) > 0) {
+            result = comparator.compare(list.get(mid), object);
+            if (result < 0) {
                 low = mid + 1;
             } else if (result == 0) {
                 return mid;
@@ -1503,7 +1503,7 @@ public class Collections {
                 high = mid - 1;
             }
         }
-        return -mid - (result < 0 ? 1 : 2);
+        return -mid - (result > 0 ? 1 : 2);
     }
 
     /**
diff --git a/luni/src/test/java/libcore/java/util/CollectionsTest.java b/luni/src/test/java/libcore/java/util/CollectionsTest.java
index cd89397..bc73817 100644
--- a/luni/src/test/java/libcore/java/util/CollectionsTest.java
+++ b/luni/src/test/java/libcore/java/util/CollectionsTest.java
@@ -19,6 +19,7 @@ package libcore.java.util;
 import java.io.Serializable;
 import java.util.ArrayList;
 import java.util.Collections;
+import java.util.Comparator;
 import java.util.ConcurrentModificationException;
 import java.util.Enumeration;
 import java.util.Iterator;
@@ -113,4 +114,75 @@ public final class CollectionsTest extends TestCase {
         } catch (ConcurrentModificationException expected) {
         }
     }
+
+    /**
+     * A value type whose {@code compareTo} method returns one of {@code 0},
+     * {@code Integer.MIN_VALUE} and {@code Integer.MAX_VALUE}.
+     */
+    static final class IntegerWithExtremeComparator
+            implements Comparable<IntegerWithExtremeComparator> {
+        private final int value;
+
+        public IntegerWithExtremeComparator(int value) {
+            this.value = value;
+        }
+
+        @Override
+        public int compareTo(IntegerWithExtremeComparator another) {
+            if (another.value == this.value) {
+                return 0;
+            } else if (another.value > this.value) {
+                return Integer.MIN_VALUE;
+            } else {
+                return Integer.MAX_VALUE;
+            }
+        }
+    }
+
+    // http://b/19749094
+    public void testBinarySearch_comparatorThatReturnsMinAndMaxValue() {
+        ArrayList<Integer> list = new ArrayList<Integer>(16);
+        list.add(4);
+        list.add(9);
+        list.add(11);
+        list.add(14);
+        list.add(16);
+
+        int index = Collections.binarySearch(list, 9, new Comparator<Integer>() {
+            @Override
+            public int compare(Integer lhs, Integer rhs) {
+                final int compare = lhs.compareTo(rhs);
+                if (compare == 0) {
+                    return 0;
+                } else if (compare < 0) {
+                    return Integer.MIN_VALUE;
+                } else {
+                    return Integer.MAX_VALUE;
+                }
+            }
+        });
+        assertEquals(1, index);
+
+        ArrayList<IntegerWithExtremeComparator> list2 =
+                new ArrayList<IntegerWithExtremeComparator>();
+        list2.add(new IntegerWithExtremeComparator(4));
+        list2.add(new IntegerWithExtremeComparator(9));
+        list2.add(new IntegerWithExtremeComparator(11));
+        list2.add(new IntegerWithExtremeComparator(14));
+        list2.add(new IntegerWithExtremeComparator(16));
+
+        assertEquals(1, Collections.binarySearch(list2, new IntegerWithExtremeComparator(9)));
+    }
+
+    public void testBinarySearch_emptyCollection() {
+        assertEquals(-1, Collections.binarySearch(new ArrayList<Integer>(), 9));
+
+        assertEquals(-1, Collections.binarySearch(new ArrayList<Integer>(), 9,
+                new Comparator<Integer>() {
+                    @Override
+                    public int compare(Integer lhs, Integer rhs) {
+                        return lhs.compareTo(rhs);
+                    }
+                }));
+    }
 }
-- 
cgit v1.1