1

Is there a java collection interface that guarantees no duplicates as well as the preservation of insertion order at the same time?

This is exactly what LinkedHashSet is doing? However, I am wondering if there is also an interface guaranteeing the same thing in order to avoid direct dependency on some specific class?

SortedSet is referring only to the natural order (and is not implemented by LinkedHashSet).

Essentially, I am looking for an interface that would indicate that the iteration order of elements is significant (and at the same time it contains no duplicates, i.e., List obviously would not apply).

Thanks!

UPDATE this question is not asking for an implementation or a data structure (as in the question to which this was marked as a duplicate). As several people pointed out as clarification, I am looking for an interface that demands both properties (no duplicates and significant order) in its contract. The application for this would be that I can return objects of this type to clients without promising any specific implementation.

UPDATE 2 Moreover, the related question specifically asks for preserving duplicates in contrast to this question. So I am pretty certain it is not a duplicate.

Community
  • 1
  • 1
Mario Boley
  • 341
  • 1
  • 8
  • how do you expect an interface (without any implementation) to guarantee this? for instance, you can say interface MyInt{ void doNotPrintThisString(String s); } class A implements MyInt{ public void doNotPrintThisString(String s){ System.out.println("ha-ha!!"); System.out.println(s); } } It's the implementation that can guarantee something. – Stultuske Jun 01 '15 at 11:32
  • 4
    @Stultuske I think OP means to say he is looking for an Interface that states the mentioned behavior in the contract. – Fildor Jun 01 '15 at 11:34
  • 1
    might be, but no matter what the method names in an interface are, it can guarantee only that the implementing class provides an implementation, and that's it. – Stultuske Jun 01 '15 at 11:36
  • 3
    AFAIK, All the "Linked" collections preserve insertion ordering in their iterators. So the answer to your question is Yes, LinkedHashSet does that. The other answer, as Stultuske pointed out, is No, there is no INTERFACE that guarantees such a thing (you can make your own, though!). – Diego Martinoia Jun 01 '15 at 11:38
  • 2
    No. There is no such *interface* guaranteeing such a contract. `LinkedHashSet` is an *implementation* that does. – Bohemian Jun 01 '15 at 11:40
  • 1
    You are looking for a combination of the `Set` and the `Queue` interface. Even then `Queue` does not demand FIFO behaviour, it also allows LIFO or priority queues. Actually even a `Iterable` would be enough to iterate over the collection, but you still depend on the actual implementation to guarantee FIFO behaviour (like `LinkedHashSet` provides). – Dorus Jun 01 '15 at 11:52
  • `Set s = new LinkedHashSet()` gives you the behavior you want without a dependency on the implementation. If you want that behavior as part of the public contract you either specify `SortedSet` or the `LinkedHashSet` neither is incorrect if you want to expose the contract. –  Jun 01 '15 at 12:22
  • 1
    Guava's [`ImmutableSet`](http://docs.guava-libraries.googlecode.com/git-history/release/javadoc/com/google/common/collect/ImmutableSet.html) does that. If you follow Guava's recommendations, you use `ImmutableSet` everywhere you need it. – Olivier Grégoire Jun 01 '15 at 12:51
  • 1
    @JarrodRoberson How can this be a duplicate of the other answer ? The other is to put a new element in its naturally ordered place explicitely preserving duplicates, this one is to maintain insertion order with no duplicate. – Serge Ballesta Jun 01 '15 at 13:03

1 Answers1

4

No interface in the JDK collections provides that.

You could try to build it by combining Set and List. Any collection implementing Set should not allow duplicate elements, and any collection implementing List should maintain order.

But then, no class in the JDK collection implements both Set and List. Because unfortunately LinkedHashSet does not implement List.

Of course, you could build one implementation easily by wrapping a LinkedHashSet (by composition patter, not by derivation) and adding a get(int i) method, or by wrapping an ArrayList (again by composition) and throwing an IllegalArgumentException when trying to add a new element.

The most tricky part IMHO would be the addAll method as both interfaces define it with different semantics (emphasize mine) :

  • Set: Adds all of the elements in the specified collection to this set if they're not already present
  • List : Appends all of the elements in the specified collection to the end of this list, in the order that they are returned by the specified collection's iterator

As you cannot meet both requirements is source collection contains duplicates, my advice would be that addAll throws an IllegalArgumentException in that case, or more simply that it always throw an UnsupportedOperationException as addAll is an optional operation for both interfaces

Serge Ballesta
  • 143,923
  • 11
  • 122
  • 252
  • Thanks a lot. This is what I was suspecting. It is surprising to me though. BTW: regarding your notes, I just need an iterable collection with significant order and without duplicates. So no index access is actually necessary. I have to see if I just want to add an interface for that. Most importantly, I did not want to miss out on a potentially already existing JDK interface. Cheers. – Mario Boley Jun 02 '15 at 14:55
  • 1+. I deeply _hate_ the omission of such a marker interface as creating generic methods around "Collections" becomes a mess, a huge one. – Eugene Oct 21 '20 at 19:22