2

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?

Heath Borders
  • 30,998
  • 16
  • 147
  • 256
  • Did you take at look a [LinkedHashSet](http://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashSet.html) ? – A4L Apr 02 '14 at 17:09
  • extend LinkedHashSet and maintain reverse order – jmj Apr 02 '14 at 17:10
  • What collection should I use flow chart, by @TimB: http://stackoverflow.com/questions/21974361/what-java-collection-should-i-use – aliteralmind Apr 02 '14 at 17:10

3 Answers3

5

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.

Community
  • 1
  • 1
Giovanni Botta
  • 9,626
  • 5
  • 51
  • 94
  • Is there any way to reverse-iterate over the `LinkedHashSet`? Or are you required to create a reverse `LinkedList` representation of it? – Maarten Bodewes Apr 02 '14 at 17:27
  • 2
    I think you have to convert the set to a list and then you can use Guava's [`Lists.reverse`](https://code.google.com/p/guava-libraries/wiki/CollectionUtilitiesExplained#Lists) method to create a reversed view. – Giovanni Botta Apr 02 '14 at 17:31
  • Having reviewed a few other options (`descendingIterator()`, `Collections.reverse(List)` and `ListIterator.previous()` I guess that Guava's method is probably both the easiest to use and the most efficient at the same time. – Maarten Bodewes Apr 02 '14 at 18:05
  • Creating a `LinkedList` representation of it will require an iteration of the entire `Set`. I want a collection that keeps this up to date itself. – Heath Borders Apr 02 '14 at 19:39
  • Then `LinkedHashSet` is not the right tool for the job. How large can the set be? – Giovanni Botta Apr 02 '14 at 19:42
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.

Prabhaker A
  • 8,317
  • 1
  • 18
  • 24
  • Somehow the Apache API's always make me itch a bit, using a special insertion method is not as clean as it should be, it's not a method that is part of the `Set` interface. – Maarten Bodewes Apr 02 '14 at 18:09
  • Yeah, the Apache collections are quite obsolete. Also I don't think this will work. Per the javadoc for the add method: "Inserts the specified element at the specified position if it is not yet contained in this ordered set (optional operation)." meaning if it is in there already the position won't change. – Giovanni Botta Apr 02 '14 at 19:47
1

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);
}
M. Justin
  • 14,487
  • 7
  • 91
  • 130