Collection that prevents duplicates but preserves reversible duplicate insertion order?

Question

Is there a collection that preserves reversible duplicate insertion order?

Specifically, if I insert the following items:

1
2
3
1

I want to be able to iterate over them and receive them in the following order:

1
3
2

That is, I want them in descending insertion order with duplicate insertions causing a reorder. Guava's LinkedListMultimap is the closest I've found, but it doesn't support descending traversal.

Java's LinkedHashSet doesn't work because it doesn't allow descending traversal.

I could also use an LRU cache, but most LRU libraries I've found don't support retrieving objects in LRU order.

Does this thing have a standard name?

Answer 1

Try ListOrderedSet class of org.apache.commons.collections4.set.

For example:

listOrderedSet.add(1,1);
listOrderedSet.add(1,2);
listOrderedSet.add(1,3);
listOrderedSet.add(1,1);  

This will give you the expected out put.

Answer 2

How about using a LinkedHashSet and whenever you detect that the item is in there you remove it and reinsert it? That's the only way to guarantee the insertion order is what you expect (or the inverse thereof).

You can iterate over the LinkedHashSet by creating a LinkedList over the LinkedHashSet and reversing over it in any way you like, e.g. by using Guava's Lists.reverse method.

Answer 3

JEP 431: Sequenced Collections in the upcoming version 21 of Java adds an addFirst(E e) method to add an element to the front of a LinkedHashSet. Using this gets exactly the requested behavior.

SequencedSet<Integer> set = new LinkedHashSet<>();
set.addFirst(1);
set.addFirst(2);
set.addFirst(3);
set.addFirst(1);

// 1 then 3 then 2
for (Integer i : set) {
  System.out.println(i);
}

---

Note: the sequenced collections feature also adds a reversed() method to LinkedHashSet. However, the existing add(E e) method doesn't change the order of existing elements, so it won't quite work to solve the problem as described.

Note that encounter order is not affected if an element is re-inserted into the set with the add method.

SequencedSet<Integer> set = new LinkedHashSet<>().reversed();
set.add(1);
set.add(2);
set.add(3);
set.add(1);

// 3 then 2 then 1
for (Integer i : set) {
  System.out.println(i);
}