[cp-patches] FYI: Fix for bug #10447 Collections.binarySearch()

[Mark Wielaard]

Hi,

This fixes Collections.binarySearch() for large LinkedLists.
David Gilbert wrote 100 new mauve tests that all pass with this change.

2004-09-21  Mark Wielaard  <address@hidden>

        Fixes bug #10447
        * java/util/Collections.java
        (binarySearch(List, Object, Comparator): Explicitly reverse direction
        in list iterator.

Committed,

Mark

Index: java/util/Collections.java
===================================================================
RCS file: /cvsroot/classpath/classpath/java/util/Collections.java,v
retrieving revision 1.29
diff -u -r1.29 Collections.java
--- java/util/Collections.java  19 Sep 2004 22:02:35 -0000      1.29
+++ java/util/Collections.java  21 Sep 2004 18:42:02 -0000
@@ -574,14 +574,26 @@
       {
        ListIterator itr = l.listIterator();
         int i = 0;
+       Object o = itr.next(); // Assumes list is not empty (see isSequential)
+       boolean forward = true;
         while (low <= hi)
           {
             pos = (low + hi) >> 1;
             if (i < pos)
-              for ( ; i != pos; i++, itr.next());
+             {
+               if (!forward)
+                 itr.next(); // Changing direction first.
+               for ( ; i != pos; i++, o = itr.next());
+               forward = true;
+             }
             else
-              for ( ; i != pos; i--, itr.previous());
-           final int d = compare(key, itr.next(), c);
+             {
+               if (forward)
+                 itr.previous(); // Changing direction first.
+               for ( ; i != pos; i--, o = itr.previous());
+               forward = false;
+             }
+           final int d = compare(key, o, c);
            if (d == 0)
               return pos;
            else if (d < 0)

signature.asc
Description: This is a digitally signed message part