Closed GoogleCodeExporter closed 9 years ago
For completeness, where would I use a UniqueList instead of a SortedSet?
Original comment by steve...@gmail.com
on 14 Nov 2007 at 9:22
A List gives you explicit control over the order of the elements; a SortedSet
doesn't
(the comparator decides).
Original comment by kevin...@gmail.com
on 15 Nov 2007 at 1:00
Is a LinkedHashSet an example of a UniqueList?
Original comment by jkwat...@gmail.com
on 24 Apr 2009 at 8:22
No, it doesn't have random access. (It also silently discards duplicates
instead of
throwing an exception.)
Original comment by kevin...@gmail.com
on 24 Apr 2009 at 9:04
More generally, a LinkedHashSet doesn't implement the List interface, which
includes
several additional methods.
Original comment by jared.l....@gmail.com
on 24 Apr 2009 at 9:19
Original comment by kevin...@gmail.com
on 17 Sep 2009 at 6:02
[deleted comment]
I am really looking forward to this. Any progress? Any help needed?
Original comment by w.schoen...@gmail.com
on 6 May 2010 at 2:41
Good to know. No help needed, really, it's just that our internal users have
not seemed to find UniqueList very
useful so far, so it's low-priority.
Original comment by kevin...@gmail.com
on 6 May 2010 at 2:49
Original comment by kevinb@google.com
on 30 Jul 2010 at 3:53
Original comment by kevinb@google.com
on 30 Jul 2010 at 3:56
"There's nothing we can do about that -- it's the price you pay."
Not really.. If the list has elements: A, B, C, D, E and you want to set the
element at index 0 to E then you can simply swap their positions.
Result: E, B, C, D, A
And this doesn't break the contract of the Set operation.
"Replaces the element at the specified position in this list with the specified
element (optional operation). "
All you have to do is to add more specifications to the set method.
It's a pity that Josh couldn't foresee this problem.
Original comment by Koyote13...@gmail.com
on 13 Sep 2010 at 4:18
Original comment by kevinb@google.com
on 27 Jan 2011 at 1:54
Original comment by kevinb@google.com
on 27 Jan 2011 at 1:58
Koyote, I don't understand. I'm saying there's nothing WE can do to make
Collections.sort(uniqueList) work. You're claiming there is?
Original comment by kevinb@google.com
on 3 Feb 2011 at 6:35
[deleted comment]
Yes if you follow the way I described above most of the Collections methods
will work on the list as expected. (the shuffle method doesn't seem to work)
Here is a simple implementation of the UniqueList
import com.google.common.base.Preconditions;
import java.util.AbstractList;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
*
* @author Michael
*/
public class SimpleUniqueList<E> extends AbstractList<E> {
private List<E> data;
public SimpleUniqueList() {
data = new ArrayList<E>();
}
@Override
public void add(int index, E e) {
Preconditions.checkArgument(!data.contains(e));
data.add(index, e);
}
@Override
public E remove(int index) {
return data.remove(index);
}
@Override
public E set(int index, E e) {
int i = data.indexOf(e);
if (i == -1) {
return data.set(index, e);
}
data.set(i, data.get(index));
return data.set(index, e);
}
@Override
public E get(int index) {
return data.get(index);
}
@Override
public int size() {
return data.size();
}
public static void main(String[] args) {
List<String> ul = new SimpleUniqueList<String>();
ul.add("A");
ul.add("B");
ul.add("C");
ul.add("D");
ul.add("E");
System.out.println(ul);
Collections.shuffle(ul); // doesn't work
Collections.sort(ul);
System.out.println(ul);
Collections.reverse(ul);
System.out.println(ul);
Collections.swap(ul, 0, 4);
System.out.println(ul);
}
}
Running the above program will print out the following output:
[A, B, C, D, E]
[A, B, C, D, E]
[E, D, C, B, A]
[A, D, C, B, E]
It would have been good if Josh put a method for swapping two elements in the
List interface. Something like swap(int i, int j)
Original comment by Koyote13...@gmail.com
on 10 Feb 2011 at 8:59
Koyote13, I think the set() method you propose would be confusing... People
would not expect elements to switch positions when they attempt to set an
already stored element! For example:
@Test
public void test() {
List<String> ul = new SimpleUniqueList<String>();
ul.add("D");
ul.add("C");
ul.add("B");
ul.add("A");
ul.set(0, "A");
// "D" was switched to the 4th position instead of being replaced by "A" !?
Assert.assertEquals(ul, ImmutableList.of("A", "C", "B", "D"));
}
I think the UniqueList should throw an IllegalArgumentException when attempting
to "set" an already stored element. This would stop sort() / reverse() / swap()
from working, but it is IMO the only contract that makes sense for the set()
method.
Original comment by nev...@gmail.com
on 10 Feb 2011 at 1:09
... yep, and that's what it does. The idea of corrupting other data in the
list at will is not even something that should be considered.
Original comment by kevinb@google.com
on 10 Feb 2011 at 2:48
Yes indeed, it's quite confusing and the fact that the shuffle method doesn't
work on the list is quite disappointing.
kevinb I'm not sure if that's "corrupting" other data.
Original comment by Koyote13...@gmail.com
on 12 Feb 2011 at 6:15
Original comment by kevinb@google.com
on 13 Jul 2011 at 6:18
I have a UniqueList implementation that I gives the user the option of how
duplicates ought to be handled--ignore, replace, or throw an exception. One
obtains a list by something like UniqueList.ignoreDuplicates() or
UniqueList.replaceDuplicates(), etc.
That said, more often than not, when someone thinks they want a UniqueList, and
LinkedHashSet does just fine. Moreover, given the option, most developers I
work with will pick the most tolerant implementation. They don't want
non-conforming data to be rejected.
That is to say, to Kevin's point (from 2/10) I'm not certain that my approach
is worthwhile. Per the API, List.add is allowed to reject the addition (by
throwing an Exception), but for it to remove another entry, or silently ignore
the addition is certainly breaking the contract and probably a bit perverse.
Original comment by raymond....@gmail.com
on 3 Nov 2011 at 12:55
Original comment by fry@google.com
on 10 Dec 2011 at 3:12
Original comment by fry@google.com
on 16 Feb 2012 at 7:17
Raymond: first, "ignore" and "replace" are the same thing. If they ever aren't,
that object implemented equals() incorrectly. Equals Means Interchangeable.
Second, our UniqueList also gives you the choice of either exception or
silently-collapse. Just use either uniqueList.add(e) or
uniqueList.asSet().add(e), respectively.
Original comment by kevinb@google.com
on 30 May 2012 at 6:07
Honestly, I'm inclined to play up the role of ImmutableSet.asList() here, since
it satisfies a sensible "unique list" contract, has unambiguous semantics
(since it is, of course, immutable), and all the other fun stuff.
Do we have any actual use cases that this doesn't address?
Original comment by wasserman.louis
on 30 May 2012 at 7:18
Original comment by kevinb@google.com
on 30 May 2012 at 7:43
Original comment by kevinb@google.com
on 22 Jun 2012 at 6:16
[deleted comment]
[deleted comment]
Sorry for the bump. Did this get resolved?
If anything, a unique list should always be an ImmutableList. The user has no
knowledge of the contents of the list, so even throwing an exception or
returning false is an ideal hair-pulling scenario to debug (in which case it
could be an interface not extending Collection to clearly define it's own
behavior)
Using static factory for ImmutableList:
ImmutableList<T> ImmutableList.uniqueListOf(Iterable<? extends T> elements,
Equivalence<? super T> elemEq) {
return new DefaultUniqueListImpl<>(elements, elemEq).asList();
}
Using a dedicated interface just for UniqueList (like java.util.Map), as it
preserves the "Equivalence" instance used for computing equality, . This cannot
extend Collection, as it violates the "contains(Object)" contract in using
Object.equals; instead uses the provided "Equivalence" :
interface UniqueList<T> {
Equivalence<? super T> elementEquivalence();
ImmutableList<T> asList();
int size();
// ....collection + list/random access methods....
// can freely throw exceptions as this interface is concrete and does not extend
// Collection, hence not compelled to adhere to contract
void shuffle();
void sort();
void swap(int i, int j);
// ... etc, all those methods that can trip
}
Will also be nice to have simple default operation in Collections2, for quick
checks. Something like:
boolean Collections2.containsUniqueElements(Collection<?> c)
{
if (list instanceof Set) {
return true;
}
if (c instanceof Multiset) {
Multiset<?> m = (Multiset<?>) c;
for (E e : m) {
if (m.count(e) > 1) {
return false;
}
}
return true;
}
return containsUniqueElements(c, Equivalence.objectEquals());
}
boolean Collections2.containsUniqueElements(Collection<T> c,
Equivalence<? super T> elemEq) {
return c.size() == ImmutableList.<T>uniqueListOf(c, elemEq).size();
// or
return c.size() == new FastComputingSizeUniqueListImpl<>(c, elemEq).size();
}
Comments and/or critiques?
Original comment by linaks...@gmail.com
on 10 Jan 2014 at 9:13
This issue has been migrated to GitHub.
It can be found at https://github.com/google/guava/issues/<id>
Original comment by cgdecker@google.com
on 1 Nov 2014 at 4:16
Original comment by cgdecker@google.com
on 1 Nov 2014 at 4:19
Original comment by cgdecker@google.com
on 3 Nov 2014 at 9:10
Original issue reported on code.google.com by
kevin...@gmail.com
on 23 Oct 2007 at 4:14