LinkedHashMap/LinkedHashSet enhancement: OrderedMap/OrderedSet

[Stuart Marks]

Hi Tagir,

A few quick thoughts on this.

There does seem to be a conceptual hole here. Most collections implementations 
have an obvious interface that provides a reasonable abstraction of that 
implementation. However, one is "missing" for LinkedHashSet, since there's no 
interface more specialized than Set. This leaves it undifferentiated from 
HashSet. This proposal seems to fill that gap.

I'm having trouble seeing where this would be used in an API, though. A method 
could consume an OrderedSet, to prevent somebody from accidentally providing an 
unordered set. An OrderedSet as a return type would be good documentation that 
the returned set has an order, but this is pretty thin.

One point to consider is: not everything needs to be in the type system. Streams 
have a runtime flag that indicates ordering; there's no OrderedStream or 
anything like that. It seems to be sufficient.

There's also kind of a clash with SortedSet. Conceptually, SortedSet is an 
OrderedSet, but this would force some additional methods into SortedSet (or it 
would limit the methods provided by this one, possibly making it not very useful).

Setting aside the types, the added functionality of getting the last element and 
iterating in the reverse order seems somewhat useful. Does this justify a whole 
new interface?

This boils down to the questions,

  - Do we need a new type that indicates that the set has an order?
  - Or are we more interested in the added functionality?

This tells me that we should do some thinking about use cases. There was some 
Twitter chatter on this topic the other day that I suspect might have led to 
this proposal. (The tweets were a bit scattered, as it typical for Twitter, so 
I'm not sure it's worth linking to them.) In any case a couple things seemed to 
come out of it, namely, the ability to iterate a LHS in reverse, or possibly to 
get its last element. As I recall, you even mused about a Deque view of an LHS. 
(The methods proposed here seem well aligned with Deque.) It seems like this 
approach could be useful, and it's much lighter weight than introducing a new type.

Could you come up with some use cases and see whether and how they could be 
satisfied by different approaches?

s'marks




On 4/25/20 9:51 AM, Tagir Valeev wrote:
> 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.
>