Hello! To me, it was always a pity that the internal structure of LinkedHashMap allows doing more things easily, yet this functionality is not exposed to the external clients, so if somebody really needs such things they will need to waste memory/CPU to emulate them. The functionality I'm speaking about includes: - getting the last (i.e. most recently added/accessed) entry - getting the descending iterator going from newest to oldest entries - getting the iterator that starts at given existing entry
It's easy to do such things with TreeMap and other NavigableMap implementations. However, LinkedHashMap provides no additional visible methods in addition to the Map interface (well, except removeEldestEntry()). The same considerations apply to LinkedHashSet. So we can provide new interfaces j.u.OrderedMap and OrderedSet that provide the additional functionality and make LinkedHashMap/LinkedHashSet implement them. Aside from new functionality, the interfaces will carry additional semantics: their iteration order is always predictable and their spliterators return DISTINCT|ORDERED characteristics, so some clients may require OrderedMap/Set just to assert that they rely on predictable iteration order. We can even make existing NavigableMap/Set extend OrderedMap/Set because NavigableMap/Set are ordered. Some of NavigableMap/Set methods will naturally fit the OrderedMap/Set interfaces. I think I can devote my spare time to write the spec, implementation, and tests for this enhancement, participate in the API design discussions and do any other job necessary to make this improvement happen. However, I'd like to know in advance whether such kind of change would be met positively. What do you think? Is it possible to do this or this improvement contradicts the OpenJDK goals and will likely be rejected? Also, do I need to write a JEP for this? It's probably too early to discuss the exact API, but for more specificity of my proposal, here's the quick draft: package java.util; public interface OrderedSet<E> extends Set<E> { // First or NSEE if empty E first() throws NoSuchElementException; // Last or NSEE if empty E last() throws NoSuchElementException; // Retrieve&remove first or null if empty E pollFirst(); // Retrieve&remove last or null if empty E pollLast(); // Iterator starting from element, or NSEE if not found Iterator<E> iteratorFrom(E fromElement) throws NoSuchElementException; // Descending Iterator<E> descendingIterator(); // Descending iterator starting from element, or NSEE if not found Iterator<E> descendingIteratorFrom(E fromElement) throws NoSuchElementException; // TBD: descendingSet() } All the methods except iteratorFrom and descendingIteratorFrom are already present in NavigableSet, so the spec will be mostly copied from there. For iteratorFrom and descendingIteratorFrom it's easy to provide a default implementation in NavigableSet. All methods can be implemented easily in LinkedHashSet and LinkedHashMap::keySet package java.util; public interface OrderedMap<K, V> extends Map<K, V> { // First entry or null if empty Map.Entry<K,V> firstEntry(); // Last entry or null if empty Map.Entry<K,V> lastEntry(); // Retrieve&remove first entry or null if empty Map.Entry<K,V> pollFirstEntry(); // Retrieve&remove last entry or null if empty Map.Entry<K,V> pollLastEntry(); // First key or NSEE if empty K firstKey(); // Last key or NSEE if empty K lastKey(); // Ordered keySet() OrderedSet<K> orderedKeySet(); // TBD: OrderedSet<K> descendingKeySet(); // TBD: OrderedSet<Entry<K,V>> orderedEntrySet(); } All the methods except orderedKeySet() are already present in NavigableMap, and the orderedKeySet() is just an alias for navigableKeySet(). Also, all of them can be implemented easily in LinkedHashMap. Any feedback is welcome. Thank you in advance, Tagir Valeev.