Hi Tagir,
I am hesitant to add new interfaces specific to Set/Map for a non-indexed
encounter order.
The interface OrderedSet is tantalizingly queue-like, in fact rather close to
the read-only part of Deque. Did you consider the possibility of LinkedHashSet
implementing Deque?
I have not thought about this too deeply, but since LinkedHashMap is
implemented as a doubly linked list it might be possible (as LinkedList
implements Deque).
If so we could also add the method:
LinkedHashSet<Map.Entry<K,V>> LinkedHashMap.entryLinkedSet()
and thereby avoid the addition of any new interfaces, although it might require
some refinement to the specification of Deque; a new notion of an unmodifiable
queue, which I admit is a little odd, and as a result is probably not be a good
idea.
More generally I think the core abstraction is really a new form Iterable
supporting access to first + last elements and reverse iteration (and possibly
iteration starting from a containing element).
Paul.
> On Apr 25, 2020, at 9:51 AM, Tagir Valeev <amae...@gmail.com> 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.
