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

[David Gilbert]

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

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

Changes by: 
                David Gilbert <address@hidden>
'Date: 
                Tue 09/21/2004 at 17:04 (GMT)

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






/**************************************************************************/
[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/2004 at 10:17

Category:  None
Severity:  5 - Average
Resolution:  None
Privacy:  Public
Assigned to:  mark
Status:  Open
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/2004 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/2004 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/2004 at 22:52       By: Mark Wielaard <mark>
Could you test the attached patch?






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

-------------------------------------------------------
Date: Tue 09/21/2004 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/2004 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/2004 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/2004 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/