[commit-cp] [bugs #10447] LinkedList and Collections.binarySearch()

[Mark Wielaard]

This mail is an automated notification from the bugs tracker
 of the project: classpath.

/**************************************************************************/
[bugs #10447] Latest Modifications:

Changes by: 
                Mark Wielaard <address@hidden>
'Date: 
                Tue 09/21/04 at 18:44 (Europe/Amsterdam)

            What     | Removed                   | Added
---------------------------------------------------------------------------
          Resolution | None                      | Fixed
              Status | Open                      | Closed


------------------ Additional Follow-up Comments ----------------------------
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.







/**************************************************************************/
[bugs #10447] Full Item Snapshot:

URL: <http://savannah.gnu.org/bugs/?func=detailitem&item_id=10447>
Project: classpath
Submitted by: David Gilbert
On: Mon 09/20/04 at 10:17

Category:  None
Severity:  5 - Average
Resolution:  Fixed
Privacy:  Public
Assigned to:  mark
Status:  Closed
Platform Version:  None


Summary:  LinkedList and Collections.binarySearch()

Original Submission:  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

Follow-up Comments
------------------


-------------------------------------------------------
Date: Tue 09/21/04 at 18:44         By: Mark Wielaard <mark>
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.


-------------------------------------------------------
Date: Tue 09/21/04 at 17:04         By: David Gilbert <trebligd>
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.

-------------------------------------------------------
Date: Tue 09/21/04 at 07:03         By: Mark Wielaard <mark>
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.

-------------------------------------------------------
Date: Mon 09/20/04 at 22:52         By: Mark Wielaard <mark>
Could you test the attached patch?






File Attachments
-------------------

-------------------------------------------------------
Date: Tue 09/21/04 at 17:04  Name: binarySearch.java  Size: 6.11KB   By: 
trebligd
Updated Mauve test
http://savannah.gnu.org/bugs/download.php?item_id=10447&amp;item_file_id=1694

-------------------------------------------------------
Date: Tue 09/21/04 at 07:03  Name: Collections-2.patch  Size: 1.19KB   By: mark

http://savannah.gnu.org/bugs/download.php?item_id=10447&amp;item_file_id=1691

-------------------------------------------------------
Date: Mon 09/20/04 at 22:52  Name: Collections.patch  Size: 990B   By: mark

http://savannah.gnu.org/bugs/download.php?item_id=10447&amp;item_file_id=1689

-------------------------------------------------------
Date: Mon 09/20/04 at 10:17  Name: binarySearch.java  Size: 2.77KB   By: 
trebligd
Mauve test
http://savannah.gnu.org/bugs/download.php?item_id=10447&amp;item_file_id=1687






For detailed info, follow this link:
<http://savannah.gnu.org/bugs/?func=detailitem&item_id=10447>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.gnu.org/