UniqueList<E>

[GoogleCodeExporter]

A UniqueList is a List which rejects duplicate elements (recall that the
modification methods on List, add/add/addAll/addAll/set, are permitted
throw IllegalArgumentException if there's anything they don't like about
the offered element(s)). The same goes for the modification methods on the
list's listIterator().

The nice thing about this restriction is that a UniqueList can be viewed as
a Set in a completely "read-through, write-through" fashion.  So the
UniqueList<E> interface would extend List<E> to add this asSet() method. I
don't believe that any subtype of Set is needed for this; AFAIK it just
needs regular Set methods and not much else.

As well, the subList() method could be refined so that it also returns a
UniqueList<E>. Of course, the sublist would throw IAE in response to any
operation that would result in a duplicate element in the *parent* list.

An AbstractUniqueList<E> class could be provided which only needs the
implementing class to supply a backing List and a backing Set, and
optionally override a few methods for better performance.

Unfortunately, the Collections methods sort(), shuffle(), reverse() and
swap() would fail on a UniqueList. They all make the assumption that the
list being acted upon has no problem with temporarily containing the same
element twice.  There's nothing we can do about that -- it's the price you pay.

Original issue reported on code.google.com by kevin...@gmail.com on 23 Oct 2007 at 4:14

[GoogleCodeExporter]

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

[GoogleCodeExporter]

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

[GoogleCodeExporter]

Is a LinkedHashSet an example of a UniqueList?

Original comment by jkwat...@gmail.com on 24 Apr 2009 at 8:22

[GoogleCodeExporter]

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

[GoogleCodeExporter]

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

[GoogleCodeExporter]

Original comment by kevin...@gmail.com on 17 Sep 2009 at 6:02

• Added labels: Milestone-Post1.0

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

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

[GoogleCodeExporter]

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

[GoogleCodeExporter]

Original comment by kevinb@google.com on 30 Jul 2010 at 3:53

• Removed labels: Milestone-Post1.0

[GoogleCodeExporter]

Original comment by kevinb@google.com on 30 Jul 2010 at 3:56

• Removed labels: Priority-Medium

[GoogleCodeExporter]

"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

[GoogleCodeExporter]

Original comment by kevinb@google.com on 27 Jan 2011 at 1:54

[GoogleCodeExporter]

Original comment by kevinb@google.com on 27 Jan 2011 at 1:58

[GoogleCodeExporter]

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

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

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

[GoogleCodeExporter]

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

[GoogleCodeExporter]

... 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

[GoogleCodeExporter]

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

[GoogleCodeExporter]

Original comment by kevinb@google.com on 13 Jul 2011 at 6:18

• Changed state: Triaged

[GoogleCodeExporter]

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

[GoogleCodeExporter]

Original comment by fry@google.com on 10 Dec 2011 at 3:12

• Added labels: Package-Collect

[GoogleCodeExporter]

Original comment by fry@google.com on 16 Feb 2012 at 7:17

• Changed state: Acknowledged

[GoogleCodeExporter]

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

[GoogleCodeExporter]

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

[GoogleCodeExporter]

Original comment by kevinb@google.com on 30 May 2012 at 7:43

• Added labels: Type-Addition
• Removed labels: Type-Enhancement

[GoogleCodeExporter]

Original comment by kevinb@google.com on 22 Jun 2012 at 6:16

• Changed state: Research

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

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

[GoogleCodeExporter]

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

• Added labels: MigratedToGitHub

[GoogleCodeExporter]

Original comment by cgdecker@google.com on 1 Nov 2014 at 4:19

• Changed state: Migrated

[GoogleCodeExporter]

Original comment by cgdecker@google.com on 3 Nov 2014 at 9:10

• Added labels: Restrict-AddIssueComment-Commit