CODEWITHSUNDEEP
javadata-structurescollectionsguava
Heath Borders
Heath Borders

Reputation: 32117

Collection that prevents duplicates but preserves reversible duplicate insertion order?

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?

Upvotes: 2

Views: 313

Answers (3)

M. Justin
M. Justin

Reputation: 21123

As of Java 21, the addFirst(E e) method can be used to add an element to the front of a LinkedHashSet, relocating it if it already exists in the set. Using this results in 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: Java 21 also has the reversed() method on LinkedHashSet. However, the 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);
}

Upvotes: 1

Giovanni Botta
Giovanni Botta

Reputation: 9816

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.

Upvotes: 5

Prabhaker A
Prabhaker A

Reputation: 8473

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.

Upvotes: 1

Related Questions