I actually think the specs in the api doc are just worded very badly. They just mean to say that if the comparator is not consistent with equals, the Set-contract is broken, just because that contract is based on (and worded in terms of) equals. This may lead to odd behavior for other code that assumes the Set-contract on such collections. The removeAll/retainAll oddities you demonstrated are bugs. Somebody should file a bug report with sun...
On Thu, 05 Mar 2009 14:05 +0100, "Johan Compagner" <[email protected]> wrote: > yes i know but the TreeSet does also say that in the javadoc that it is > an > exception because of the Comparator > > And they could really just make it a black box. The only things they just > need to fix then is the removeAll and retainAll methods > > Why the removeAll iterates by default over itself and ask for a contains > on > the other and then removes itself again is beyond me > I wouldnt never implement it that way. Why would you do that in the first > place? > It wouldnt come into my mind to do it like that > > besides that AbstractSet.removeAll makes it even worse: > > public boolean removeAll(Collection<?> c) { > boolean modified = false; > > if (size() > c.size()) { > for (Iterator<?> i = c.iterator(); i.hasNext(); ) > modified |= remove(i.next()); > } else { > for (Iterator<?> i = iterator(); i.hasNext(); ) { > if (c.contains(i.next())) { > i.remove(); > modified = true; > } > } > } > return modified; > } > > see partly it does what i expect to happen (the if) > but what sun wants to happen is the else.. > > So now we just have 2 behaviors depending on what size the collection > has... > nice.. > > > > On Thu, Mar 5, 2009 at 13:58, Maarten Bosteels > <[email protected]>wrote: > > > It is in the javadoc for Comparator > > > > "Caution should be exercised when using a comparator capable of imposing an > > ordering inconsistent with equals to order a sorted set (or sorted map). > > Suppose a sorted set (or sorted map) with an explicit comparator c is used > > with elements (or keys) drawn from a set S. If the ordering imposed by c on > > S is inconsistent with equals, the sorted set (or sorted map) will behave > > "strangely." In particular the sorted set (or sorted map) will violate the > > general contract for set (or map), which is defined in terms of equals." > > > > > > http://java.sun.com/javase/6/docs/api/java/util/Comparator.html > > > > On Thu, Mar 5, 2009 at 1:50 PM, Johan Compagner <[email protected] > > >wrote: > > > > > For example. > > > > > > You want a tree set with a case insensitive comparator.. Because you want > > > to > > > order case insensitive.. > > > That breaks the equals contract. > > > > > > So that "note" in the doc just makes the TreeSet completely worthless > > > > > > johan > > > > > > > > > On Thu, Mar 5, 2009 at 13:46, Johan Compagner <[email protected]> > > > wrote: > > > > > > > that is then the wrong spec that i talk about > > > > That is completely stupid > > > > > > > > With a comparator you just OVERRIDE the equals, thats the whole point! > > > > > > > > johan > > > > > > > > > > > > > > > > On Thu, Mar 5, 2009 at 13:44, Pointbreak < > > [email protected] <pointbreak%[email protected]>< > > pointbreak%[email protected] <pointbreak%[email protected]>> > > > <pointbreak%[email protected] <pointbreak%[email protected]> < > > pointbreak%[email protected] <pointbreak%[email protected]> > > >> > > > > > wrote: > > > > > > > >> Sorry, I have to correct myself. According to the API-docs, the > > compare > > > >> method in a TreeSet must be consistent with equals. In Johan's example > > > >> it is not. > > > >> > > > >> On Thu, 05 Mar 2009 13:36 +0100, "Pointbreak" > > > >> <[email protected] <pointbreak%[email protected]> < > > pointbreak%[email protected] <pointbreak%[email protected]>> < > > > pointbreak%[email protected] <pointbreak%[email protected]> < > > pointbreak%[email protected] <pointbreak%[email protected]> > > >>> > > > >> wrote: > > > >> > You are missing the point. With a string it will work, because the > > > >> > elements will actually be the same string objects, so the > > > String.equals > > > >> > and the overridden compare method will give the same results in the > > > >> > example. Johan's point is that while set1.removeAll() is called, it > > is > > > >> > not the compare method of set1 that is used, which seems > > > >> > counterintuitive. > > > >> > > > > >> > On Thu, 05 Mar 2009 13:13 +0100, "Dave Schoorl" < > > > [email protected]> > > > >> > wrote: > > > >> > > If I change every MyObject in a String, everything is fine. > > Perhaps > > > >> the > > > >> > > MyObject is not obeying the necessary contracts? > > > >> > > > > > >> > > See adjusted code below: > > > >> > > > > > >> > > > > > >> > > > > > >> > > import java.util.ArrayList; > > > >> > > import java.util.Collection; > > > >> > > import java.util.Comparator; > > > >> > > import java.util.HashSet; > > > >> > > import java.util.Iterator; > > > >> > > import java.util.TreeSet; > > > >> > > > > > >> > > public class TestWithStrings > > > >> > > { > > > >> > > public static void main(String[] args) > > > >> > > { > > > >> > > TreeSet<String> set1 = getCleanSet(); > > > >> > > > > > >> > > HashSet<String> set2 = new HashSet<String>(); > > > >> > > set2.add("johan"); > > > >> > > > > > >> > > > > > >> > > set1.removeAll(set2); > > > >> > > > > > >> > > System.err.println("this works: " + set1.size() + " == 1, > > > and > > > >> > > remaining object is " + set1.iterator().next() + " == rob"); > > > >> > > > > > >> > > // add removed back in > > > >> > > set1 = getCleanSet(); > > > >> > > > > > >> > > // increase the size of set2 with some other random others > > > >> > > set2.add("random1"); > > > >> > > set2.add("random2"); > > > >> > > > > > >> > > // now size is bigger then set1, call removeall again: > > > >> > > set1.removeAll(set2); > > > >> > > > > > >> > > System.err.println("this doesnt work: " + set1.size() + " > > != > > > >> 1, > > > >> > > so now both objects stil remain! This is because " + > > > >> > > "removeAll isnt overwritten by TreeSet and > > > AbstractSet > > > >> > > walks over the smallest set but then compare fails"); > > > >> > > > > > >> > > // same for retainAll that also compares wrong. > > > >> > > set1 = getCleanSet(); > > > >> > > set1.retainAll(set2); > > > >> > > > > > >> > > System.err.println("set1 is now completely empty, but it > > > >> should > > > >> > > have 1 left: " + set1); > > > >> > > > > > >> > > // so both methods should always iterator through the > > > >> colleciton > > > >> > > they get and do the compare on its self > > > >> > > > > > >> > > set1 = getCleanFixedSet(); > > > >> > > > > > >> > > set1.removeAll(set2); > > > >> > > > > > >> > > System.err.println("now this works: " + set1.size() + " == > > > 1, > > > >> > > and remainng object is " + set1.iterator().next() + " == rob"); > > > >> > > > > > >> > > // add removed back in > > > >> > > set1 = getCleanFixedSet(); > > > >> > > > > > >> > > set1.retainAll(set2); > > > >> > > > > > >> > > System.err.println("set1 is now correct, it has 1 left: " > > + > > > >> > > set1); > > > >> > > > > > >> > > } > > > >> > > > > > >> > > public static TreeSet<String> getCleanSet() { > > > >> > > TreeSet<String> set1 = new TreeSet<String>(new > > > >> > > Comparator<String>(){ > > > >> > > > > > >> > > public int compare(String o1, String o2) > > > >> > > { > > > >> > > return o1.compareToIgnoreCase(o2); > > > >> > > } > > > >> > > }); > > > >> > > > > > >> > > set1.add("johan"); > > > >> > > set1.add("rob"); > > > >> > > > > > >> > > return set1; > > > >> > > } > > > >> > > > > > >> > > public static TreeSet<String> getCleanFixedSet() { > > > >> > > TreeSet<String> set1 = new MyFixedTreeSet<String>(new > > > >> > > Comparator<String>(){ > > > >> > > > > > >> > > public int compare(String o1, String o2) > > > >> > > { > > > >> > > return o1.compareToIgnoreCase(o2); > > > >> > > } > > > >> > > }); > > > >> > > > > > >> > > set1.add("johan"); > > > >> > > set1.add("rob"); > > > >> > > return set1; > > > >> > > } > > > >> > > > > > >> > > public static class MyFixedTreeSet<E> extends TreeSet<E> > > > >> > > { > > > >> > > public MyFixedTreeSet(Comparator<? super E> comparator) > > > >> > > { > > > >> > > super(comparator); > > > >> > > } > > > >> > > > > > >> > > @Override > > > >> > > public boolean retainAll(Collection<?> c) > > > >> > > { > > > >> > > ArrayList<E> list = new ArrayList<E>(); > > > >> > > Iterator<?> e = c.iterator(); > > > >> > > while (e.hasNext()) { > > > >> > > Object next = e.next(); > > > >> > > if (contains(next)) { > > > >> > > list.add((E)next); > > > >> > > } > > > >> > > } > > > >> > > boolean modified = list.size() < size(); > > > >> > > if (modified) > > > >> > > { > > > >> > > clear(); > > > >> > > for (E item : list) > > > >> > > { > > > >> > > add(item); > > > >> > > } > > > >> > > } > > > >> > > return modified; > > > >> > > } > > > >> > > > > > >> > > @Override > > > >> > > public boolean removeAll(Collection<?> c) > > > >> > > { > > > >> > > boolean modified = false; > > > >> > > for (Iterator<?> i = c.iterator(); i.hasNext(); ) > > > >> > > modified |= remove(i.next()); > > > >> > > return modified; > > > >> > > } > > > >> > > } > > > >> > > } > > > >> > > > > > >> > > > > > >> > > > > > >> > > > > > --------------------------------------------------------------------- > > > >> > > To unsubscribe, e-mail: [email protected] > > > >> > > For additional commands, e-mail: [email protected] > > > >> > > > > > >> > > > > >> > > > --------------------------------------------------------------------- > > > >> > To unsubscribe, e-mail: [email protected] > > > >> > For additional commands, e-mail: [email protected] > > > >> > > > > >> > > > >> --------------------------------------------------------------------- > > > >> To unsubscribe, e-mail: [email protected] > > > >> For additional commands, e-mail: [email protected] > > > >> > > > >> > > > > > > > > > --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
