RFR 8024709 : TreeMap.DescendingKeyIterator 'remove' confuses iterator position

[Brent Christian]

I've beefed up the test case, as suggested by Alan and Paul.  It tries 
removing at the start, middle, and end of the iteration.

FWIW, all but one of the test scenarios pass even without the fix.  The 
failing case is:

checkDescItrRmMid(m.keySet(), m.navigableKeySet().descendingIterator());

(that is, remove an element from the middle of the iteration, the 
specific case of this bug).

So most of the new tests are of code that is already correct, but IMO it 
doesn't hurt to make sure it stays correct. :)

http://cr.openjdk.java.net/~bchristi/8024709/webrev.01/

Thanks,
-Brent

On 10/4/13 1:51 AM, Paul Sandoz wrote:
>
> On Oct 4, 2013, at 7:28 AM, Alan Bateman <Alan.Bateman at oracle.com> wrote:
>
>> On 03/10/2013 16:31, Brent Christian wrote:
>>> Please review my fix for 8024709 : "TreeMap.DescendingKeyIterator 'remove' confuses iterator position"
>>>
>>> There are two possible code paths for performing a "descending" iteration over the elements in a TreeMep, depending on how the iteration is setup.
>>>
>>> For instance,
>>>   treemap.descendingKeySet().iterator();
>>> will use a
>>>   TreeMap.NavigableSubMap.DescendingSubMapIterator
>>> This code correctly handles Iterator.remove().
>>>
>>> On the other hand,
>>>   treemap.navigableKeySet().descendingIterator();
>>> will use a
>>>   TreeMap.DescendingKeyIterator.
>>> This code does not correctly handle remove(), and results in a "confused" iterator.
>>>
>>>
>>> TreeMap.DescendingKeyIterator should override remove() with code
>>> similar to that in TreeMap.NavigableSubMap.SubMapIterator.removeDescending().
>>>
>>>
>>> Bug report:
>>> https://bugs.openjdk.java.net/browse/JDK-8024709
>>>
>>> Webrev:
>>> http://cr.openjdk.java.net/~bchristi/8024709/webrev.00/
>> The remove looks right to me and next() should return the predecessor that is already set.
>>
>
> Looks ok to me too.
>
>
>> The test looks okay (although you might want to align the parameters to checkDescendingIteratorRemove), I just wonder if you would be worth generating additional cases to exercise this code a bit more.
>>
>
> One could write a general test without having to pass in expicit values and if so i suspect it is better to pass in the ascending collection and descending iterator (since the toArray could be implemented using an iterator):
>
> <T> void checkTraverse2Remove1Traverse1(Collection<T> aC, Iterator<T> dIt) {
>    T[] values = (T) aC.toArray();
>    int n = values.length -1;
>
>    equalNext(dIt, values[n--]);
>    equalNext(dIt, values[n--]);
>    it.remove();
>    equalNext(dIt, values[n]);
> }
>
> Might also be useful to have a test that removes the last traversed element.
>
> Paul.
>