[
https://issues.apache.org/jira/browse/COLLECTIONS-310?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13580821#comment-13580821
]
Thomas Vahrst edited comment on COLLECTIONS-310 at 3/4/13 8:32 PM:
-------------------------------------------------------------------
SetUniqueList.patch contains JUnit Tests and Variant No. 1 for SetUniqueList. I
am not sure whether the patch has a correct format (I am not able to re-apply
the patch in Netbeans...) so I attached the corresponding java files as well.
Some comment to this solution:
1. During the implementation I recognized, that the existing implementation of
subList() uses the subList() method on the decorated list and then creates a
new Set and fills all elements of the sublist into the set.
Now this issue requires, that a parent list has to be modified on certain
invocations on a sublist - for example when adding an element to the sublist
which exists in the parent list somewhere outside the range of the sublist.
With the current sublist implementation, any attempt to modify a parent list
fails with a ConcurrentModifiationException. So we have to reimplement the
sublist functionality inside SetUniqueList and can not reuse the service of
AbstractListDecorator.
2. When we create a subList on a SetUniqueList, this sublist has to obbey the
SetUniqueList contracts. The original parent list will have slightly different
behavior when adding or setting values. When we create a second sublist based
on the first sublist, this top most list has to provide SetUniqueList semantics.
Example (from JUnit Tests)
{noformat}
subList2 ! e ! f ! g ! offset = 2
subList1 ! c ! d ! e ! f ! g ! h ! offset = 2
list ! a ! b ! c ! d ! e ! f ! g ! h ! i ! j ! offset = 0
-----------------------------------------
Index 0 1 2 3 4 5 6 7 8 9
Adds a 'd' to subList2. This should move the 'd' in subList1 and list in the
range of subList2
Expected result:
subList2 ! e ! f ! g ! d ! offset = 1
subList1 ! c ! e ! f ! g ! d ! h ! offset = 2
list ! a ! b ! c ! e ! f ! g ! d ! h ! i ! j ! offset = 0
-----------------------------------------
Index 0 1 2 3 4 5 6 7 8 9
{noformat}
(The 'movement' of 'd' causes the ConcurrentModificationException mentioned
above.)
Because of this requirements I decided for Variant No. 1, that every
SetUniqueList holds its own list and set and maintains a reference to it's
parent SetUniqueList and an offset value. The SetUniqueList garantees, that all
parent lists are updated according to the required functionality and that all
offset values are adjusted if necessary. This solution does not use the sublist
functionality of the decorated list but creates allway a new Set *and* List.
I copied the existing code for creating a new Set to also create a new List
based on the existing list.
At this time, there are two things missing:
# a very details javadoc comment for the subList() method, explaining the
behavior.
# the implementation for listIterator().
... to be continued with variant no. 2 ...
was (Author: t.vahrst):
SetUniqueList.patch contains JUnit Tests and Variant No. 1 for
SetUniqueList. I am not sure whether the patch has a correct format (I am not
able to re-apply the patch in Netbeans...) so I attached the corresponding java
files as well.
Some comment to this solution:
1. During the implementation I recognized, that the existing implementation of
subList() uses the subList() method on the decorated list and then creates a
new Set and fills all elements of the sublist into the set.
Now this issue requires, that a parent list has to be modified on certain
invocations on a sublist - for example when adding an element to the sublist
which exists in the parent list somewhere outside the range of the sublist.
With the current sublist implementation, any attempt to modify a parent list
fails with a ConcurrentModifiationException. So we have to reimplement the
sublist functionality inside SetUniqueList and can not reuse the service of
AbstractListDecorator.
2. When we create a subList on a SetUniqueList, this sublist has to obbey the
SetUniqueList contracts. The original parent list will have slightly different
behavior when adding or setting values. When we create a second sublist based
on the first sublist, this top most list has to provide SetUniqueList semantics.
Example (from JUnit Tests)
{noformat}
subList2 ! e ! f ! g ! offset = 2
subList1 ! c ! d ! e ! f ! g ! h ! offset = 2
list ! a ! b ! c ! d ! e ! f ! g ! h ! i ! j ! offset = 0
-----------------------------------------
Index 0 1 2 3 4 5 6 7 8 9
Adds a 'd' to subList2. This should move the 'd' in subList1 and list in the
range of subList2
Expected result:
subList2 ! e ! f ! g ! d ! offset = 1
subList1 ! c ! e ! f ! g ! d ! h ! offset = 2
list ! a ! b ! c ! e ! f ! g ! d ! h ! i ! j ! offset = 0
-----------------------------------------
Index 0 1 2 3 4 5 6 7 8 9
{noformat}
(The 'movement' of 'd' causes the ConcurrentModificationException mentioned
above.)
Because of this requirements I decided for Variant No. 1, that every
SetUniqueList holds its own list and set and maintains a reference to it's
parent SetUniqueList and an offset value. The SetUniqueList garantees, that all
parent lists are updated according to the required functionality and that all
offset values are adjusted if necessary. This solution does not use the sublist
functionality of the decorated list but creates allway a new Set *and* List.
I copied the existing code for creating a new Set to also create a new List
based on the existing list.
At this time, there are two things missing:
# a very details javadoc comment for the subList() method, explaining the
behavior.
# the implementation for listIterator(). As already mentioned, a ListIterator
may itself become a sublist (when specifying a start index).
... to be continued with variant no. 2 ...
> Modifications of a SetUniqueList.subList() invalidate the parent list
> ---------------------------------------------------------------------
>
> Key: COLLECTIONS-310
> URL: https://issues.apache.org/jira/browse/COLLECTIONS-310
> Project: Commons Collections
> Issue Type: Bug
> Components: List
> Affects Versions: 3.2, Nightly Builds
> Reporter: Christian Semrau
> Priority: Minor
> Fix For: 4.0
>
> Attachments: SetUniqueList.java, SetUniqueList.patch,
> SetUniqueListTest.java
>
>
> The List returned by SetUniqueList.subList() is again a SetUniqueList. The
> contract for List.subList() says that the returned list supports all the
> operations of the parent list, and it is backed by the parent list.
> We have a SetUniqueList uniqueList equal to {"Hello", "World"}. We get a
> subList containing the last element. Now we add the element "Hello",
> contained in the uniqueList but not in the subList, to the subList.
> What should happen?
> Should the subList behave like a SetUniqueList and add the element - meaning
> that it changes position in the uniqueList because at the old place it gets
> removed, so now uniqueList equals {"World", "Hello"} (which fails)?
> Or should the element not be added, because it is already contained in the
> parent list, thereby violating the SetUniqueList-ness of the subList (which
> fails)?
> I prefer the former behaviour, because modifications should only be made
> through the subList and not through the parent list (as explained in
> List.subList()).
> What should happen if we replace (using set) the subList element "World" with
> "Hello" instead of adding an element?
> The subList should contain only "Hello", and for the parent list, the old
> element 0 (now a duplicate of the just set element 1) should be removed
> (which fails).
> And of course the parent list should know what happens to it (specifically,
> its uniqueness Set) (which fails in the current snapshot).
> public void testSubListAddNew() {
> List uniqueList = SetUniqueList.decorate(new ArrayList());
> uniqueList.add("Hello");
> uniqueList.add("World");
> List subList = uniqueList.subList(1, 2);
> subList.add("Goodbye");
> List expectedSubList = Arrays.asList(new Object[] { "World",
> "Goodbye" });
> List expectedParentList = Arrays.asList(new Object[] { "Hello",
> "World", "Goodbye" });
> assertEquals(expectedSubList, subList);
> assertEquals(expectedParentList, uniqueList);
> assertTrue(uniqueList.contains("Goodbye")); // fails
> }
> public void testSubListAddDuplicate() {
> List uniqueList = SetUniqueList.decorate(new ArrayList());
> uniqueList.add("Hello");
> uniqueList.add("World");
> List subList = uniqueList.subList(1, 2);
> subList.add("Hello");
> List expectedSubList = Arrays.asList(new Object[] { "World",
> "Hello" });
> List expectedParentList = Arrays.asList(new Object[] { "World",
> "Hello" });
> assertEquals(expectedSubList, subList);
> assertEquals(expectedParentList, uniqueList); // fails
> }
> public void testSubListSetDuplicate() {
> List uniqueList = SetUniqueList.decorate(new ArrayList());
> uniqueList.add("Hello");
> uniqueList.add("World");
> List subList = uniqueList.subList(1, 2);
> subList.set(0, "Hello");
> List expectedSubList = Arrays.asList(new Object[] { "Hello" });
> List expectedParentList = Arrays.asList(new Object[] { "Hello"
> });
> assertEquals(expectedSubList, subList);
> assertEquals(expectedParentList, uniqueList); // fails
> }
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
