UniqueList<E> about guava HOT 30 CLOSED

Original comment posted by stevelle on 2007-11-14 at 09:22 PM

For completeness, where would I use a UniqueList instead of a SortedSet?

from guava.

Original comment posted by kevinb9n on 2007-11-15 at 01:00 AM

A List gives you explicit control over the order of the elements; a SortedSet doesn't
(the comparator decides).

from guava.

Original comment posted by jkwatson on 2009-04-24 at 08:22 PM

Is a LinkedHashSet an example of a UniqueList?

from guava.

Original comment posted by kevinb9n on 2009-04-24 at 09:04 PM

No, it doesn't have random access. (It also silently discards duplicates instead of
throwing an exception.)

from guava.

Original comment posted by jared.l.levy on 2009-04-24 at 09:19 PM

More generally, a LinkedHashSet doesn't implement the List interface, which includes
several additional methods.

from guava.

Original comment posted by kevinb9n on 2009-09-17 at 06:02 PM

(No comment entered for this change.)

Labels: Milestone-Post1.0

from guava.

Original comment posted by w.schoenborn on 2010-05-06 at 02:41 PM

I am really looking forward to this. Any progress? Any help needed?

from guava.

Original comment posted by kevinb9n on 2010-05-06 at 02:49 PM

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.

from guava.

Original comment posted by [email protected] on 2010-07-30 at 03:53 AM

(No comment entered for this change.)

Labels: -Milestone-Post1.0

from guava.

Original comment posted by [email protected] on 2010-07-30 at 03:56 AM

(No comment entered for this change.)

Labels: -Priority-Medium

from guava.

Original comment posted by Koyote130708 on 2010-09-13 at 04:18 AM

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

from guava.

Original comment posted by [email protected] on 2011-01-27 at 01:54 PM

(No comment entered for this change.)

Owner: [email protected]

from guava.

Original comment posted by [email protected] on 2011-01-27 at 01:58 PM

(No comment entered for this change.)

Owner: ---

from guava.

Original comment posted by [email protected] on 2011-02-03 at 06:35 AM

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?

from guava.

Original comment posted by Koyote130708 on 2011-02-10 at 08:59 AM

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)

from guava.

Original comment posted by neveue on 2011-02-10 at 01:09 PM

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.

from guava.

Original comment posted by [email protected] on 2011-02-10 at 02:48 PM

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

from guava.

Original comment posted by Koyote130708 on 2011-02-12 at 06:15 AM

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.

from guava.

Original comment posted by [email protected] on 2011-07-13 at 06:18 PM

(No comment entered for this change.)

Status: Triaged

from guava.

Original comment posted by raymond.rishty on 2011-11-03 at 12:55 AM

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.

from guava.

Original comment posted by [email protected] on 2011-12-10 at 03:12 PM

(No comment entered for this change.)

Labels: Package-Collect

from guava.

Original comment posted by [email protected] on 2012-02-16 at 07:17 PM

(No comment entered for this change.)

Status: Acknowledged

from guava.

Original comment posted by [email protected] on 2012-05-30 at 06:07 PM

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.

from guava.

Original comment posted by wasserman.louis on 2012-05-30 at 07:18 PM

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?

from guava.

Original comment posted by [email protected] on 2012-05-30 at 07:43 PM

(No comment entered for this change.)

Labels: -Type-Enhancement, Type-Addition

from guava.

Original comment posted by [email protected] on 2012-06-22 at 06:16 PM

(No comment entered for this change.)

Status: Research

from guava.

Original comment posted by linakster on 2014-01-10 at 09:13 PM

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?

from guava.

I needed a kind of "unique list" as well and struggled to implement something I was happy with. As pointed out above, a UniqueList breaks Collection utility methods like sort and shuffle. But I also realized that I really didn't need to use indices in these collections much at all. Because their are not duplicates, I could refer to the position I wanted in the list by the element itself.

So with some hesitation, I ultimately gave up on it being a "List" at all and created a new type of Collection. This collection doesn't present the user with index-based access. My collection has methods getFirst() and getLast(), but then methods like getBefore(e) and getAfter(e), to return the elements before and after the specified element. It also has addBefore, addAfter, removeBefore, removeAfter, all of which accept element arguments.

I struggled to name the new kind of Collection. I initially wanted to use "Ordering", but Guava already has something else with that name. I settled on "Chain" for now. I'm open to other name suggestions.

For my primary implementation of the interface, I effectively re-implemented a LinkedList but with the addition of a HashMap mapping elements to its bucket in the list. So I get constant-time contains, insert, and remove. One of the benefitsI get by not implementing List is that I don't worry users might use the slower index-based operations that come from the linked list implementation.

from guava.

Surely you can at least add an ImmutableUniqueList.
It wont have the problem with set, sort, shuffle etc. (since immutable)
Or at least provide a distinct() method to ImmutableList.Builder such that build() fails if there are duplicates.

from guava.

Well... I think 15 years have proven sufficiently to us that need for this type isn't widespread. This isn't to belittle your use cases; I also like UniqueList for them (if it had already existed). But for the most part (by far) people have "enough" collection types that are adaptable "enough" to their needs, and introducing another has costs.

Our internal UniqueList implementation is imported six times in the Google codebase. That divided by the size of the codebase can be effectively estimated as zero.

from guava.