[Bug classpath/22782] LinkedList and Collections.binarySearch()

[gcc-bugzilla at gcc dot gnu dot org]

While running a performance test on something unrelated, I noticed a problem
with the Collections.binarySearch() method on a LinkedList:

0 --> 18 (239928 / 1048568)
1 --> 62 (235528 / 1048568)
java.util.NoSuchElementException
   at java.util.LinkedList$LinkedListItr.next (LinkedList.java:861)
   at java.util.Collections.binarySearch (Collections.java:581)
   at java.util.Collections.binarySearch (Collections.java:535)
   at org.jfree.data.time.TimeSeries.add (TimeSeries.java:443)
   at org.jfree.data.time.TimeSeries.add (TimeSeries.java:476)
   at demo.PerformanceTest1.main (PerformanceTest1.java:145)

The problem disappears if I switch to using an ArrayList.  I put together a
Mauve test to illustrate the bug - from trial and error, it *seems* to require
>16 items in the list to trigger the bug (I didn't look into the LinkedList
source code yet).

I'll also post the test to the mauve-patches mailing list.

Regards,

Dave Gilbert
www.jfree.org


------- Comment #1 from from-classpath at savannah dot gnu dot org  2004-09-20 
22:52 -------
Could you test the attached patch?


------- Comment #2 from from-classpath at savannah dot gnu dot org  2004-09-21 
07:03 -------
New patch. The original patch only fixed the problem for that one mauve test.

The confusion came from the fact that the position of a ListIterator is between
elements. So to go back after you went forward, you need to explicitly reverse
the direction first.

New patch attached.


------- Comment #3 from from-classpath at savannah dot gnu dot org  2004-09-21 
17:04 -------
Thanks, the patch works for me.  I've added a few extra cases to the Mauve test
- everything passes.  I've attached the revised test source file.


------- Comment #4 from from-classpath at savannah dot gnu dot org  2004-09-21 
18:44 -------
Thanks! I checked in your new tests into Mauve as follows:

2004-09-21  David Gilbert  <address@hidden>

       * gnu/testlet/java/util/Collections/binarySearch.java: Add more
       generic tests for ArrayList, LinkedList and Vector.

I made one small change. Instead of using TestHarness.check(boolean) I used
TestHarness.check(int result, int excepted). In that case a FAIL also gives
information about what precisely failed.

Also checked in my Collections patch as:

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

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


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=22782