Hi Stuart Will EnumSet also be updated to implement ReversibleSet? Or will it be updated to implement NavigableSet [1] independently of this enhancement?
I'd also like to propose adding `ReversibleSet::of` factory methods. This is something I miss having on SortedSet occasionally, but ReversibleSet would actually be a better fit for such methods. Kind regards, Anthony [1] https://bugs.openjdk.java.net/browse/JDK-6278287 On Friday, April 16, 2021 19:40 CEST, Stuart Marks <stuart.ma...@oracle.com> wrote: > This is a proposal to add a ReversibleCollection interface to the Collections > Framework. I'm looking for comments on overall design before I work on > detailed > specifications and tests. Please send such comments as replies on this email > thread. > > Here's a link to a draft PR that contains the code diffs. It's prototype > quality, > but it should be good enough to build and try out: > > https://github.com/openjdk/jdk/pull/3533 > > And here's a link to a class diagram showing the proposed additions: > > > https://cr.openjdk.java.net/~smarks/ReversibleCollection/ReversibleCollectionDiagram.pdf > > Thanks, > > s'marks > > > # Ordering and Reversibility > > > A long-standing concept that's been missing from collections is that of the > positioning, sequencing, or arrangement of elements as a structural property > of a > collection. (This is sometimes called the "iteration order" of a collection.) > For > example, a HashSet is not ordered, but a List is. This concept is mostly not > manifested in the collections API. > > Iterating a collection produces elements one after another in *some* > sequence. The > concept of "ordered" determines whether this sequence is defined or whether > it's a > coincidence of implementation. What does "having an order" mean? It implies > that > there is a first element and that each element has a successor. Since > collections > have a finite number of elements, it further implies that there is a last > element > that has no successor. However, it is difficult to discern whether a > collection has > a defined order. HashSet generally iterates its elements in the same undefined > order, and you can't actually tell that it's not a defined order. > > Streams do have a notion of ordering ("encounter order") and this is > preserved, > where appropriate, through the stream pipeline. It's possible to detect this > by > testing whether its spliterator has the ORDERED characteristic. Any > collection with > a defined order will have a spliterator with this characteristic. However, > this is > quite a roundabout way to determine whether a collection has a defined order. > Furthermore, knowing this doesn't enable any additional operations. It only > provides > constraints on the stream's implementations (keeping the elements in order) > and > provides stronger semantics for certain operations. For example, findFirst() > on an > unordered stream is the same as findAny(), but actually finds the first > element if > the stream is ordered. > > The concept of ordering is thus present in the system but is surfaced only in > a > fairly indirect way. We can strengthen abstraction of ordering by making a few > observations and considering their implications. > > Given that there is a first element and a last element, the sequence of > elements has > two ends. It's reasonable to consider operations (add, get, remove) on either > end. > Indeed, the Deque interface has a full complement of operations at each end. > This is > an oft-requested feature on various other collections. > > Each element except for the last has a successor, implying that each element > except > for the first has a predecessor. Thus it's reasonable to consider iterating > the > elements from first to last or from last to first (that is, in forward or > reverse > order). Indeed, the concept of iterating in reverse order appears already in > bits > and pieces in particular places around the collections: > > - List has indexOf() and lastIndexOf() > - Deque has removeFirstOccurrence() and removeLastOccurrence() > - List has a ListIterator with hasPrevious/previous methods > - Deque and NavigableSet have descendingIterator methods > > Given an ordered collection, though, there's no general way to iterate it in > reverse > order. Reversed iteration isn't the most common operation, but there are some > frequent use cases, such as operating on elements in most-recently-added > order. > Questions and bug reports about this have come up repeatedly over the years. > > Unfortunately, iterating in reverse order is much harder than iterating in > forward > order. There are a variety of ways to iterate in forward order. For example, > given a > List, one can do any of the following: > > for (var e : list) { ... } > list.forEach(...) > list.stream() > list.toArray() > > However, to iterate a list in reverse order, one must use an explicit loop > over > ListIterator: > > for (var it = list.listIterator(list.size()); it.hasPrevious(); ) { > var e = it.previous(); > ... > } > > Streaming the elements of a List in reverse order is even worse. One approach > would > be to implement a reverse-ordered Iterator that wraps a ListIterator and > delegates > hasNext/next calls to the ListIterator's hasPrevious/previous methods. Then, > this > Iterator can be turned into a Spliterator, which is then turned into a > Stream. (The > code to do this is left as an exercise for the reader.) Obtaining the > elements in > reverse via other means -- forEach() or toArray() -- is similarly difficult. > > Obtaining the elements in reverse order can be accomplished by adopting a > concept > from NavigableSet's descendingSet() method, which provides a reverse-ordered > view > collection. This view is also a NavigableSet, which means that any operation > that > can be performed on the original set can also be applied to the > reverse-ordered > view. If it were possible to obtain a similar reverse-ordered view on any > kind of > ordered collection, this would enable the elements to be processed in reverse > order > in any fashion, not just special-purposes APIs such as ListIterator or > descendingIterator(). > > > # LinkedHashSet > > > The main feature of LinkedHashSet is that it does have a defined ordering, as > opposed to HashSet, which does not. LinkedHashSet clearly has a first and a > last > element. However, LinkedHashSet is deficient in a number of ways: > > - access to and removal of the first element is reasonable (using an > iterator) but > it is not possible to add at the front > > - it is possible to add an element at the end, but access to and removal of > the > last element are expensive > > - it's not possible to iterate in reverse without copying the entire > collection > > Most frustratingly, LinkedHashSet is implemented using a doubly-linked list, > so > there is no fundamental implementation reason that prevents these operations > from > being supported. The main reason these operations aren't supported is > probably that > there hasn't been a good place to push such APIs. > > > # Proposal > > > Introduce a new ReversibleCollection<E> interface. This provides a new method > to > obtain a reverse-ordered view. It also contains several methods (copied from > Deque) > that allow operating on elements at both ends. > > > interface ReversibleCollection<E> extends Collection<E> { > ReversibleCollection<E> reversed(); > default void addFirst(E e) > default void addLast(E e) > default E getFirst() > default E getLast() > default E removeFirst() > default E removeLast() > } > > > The List, Deque, and SortedSet interfaces, and the LinkedHashSet class are > retrofitted to implement ReversibleCollection. They provide covariant > overriding > implementations of the reversed() method. For example, List.reversed() > returns a > List. Default implementations for all of these methods are provided in the > appropriate interfaces. > > Covariant overrides are also provided in several other classes. This presents > a > difficulty for LinkedHashSet, as there's no suitable return type for > reversed(). To > remedy this, we add another interface > > > interface ReversibleSet<E> extends ReversibleCollection<E>, Set<E> { } > > > This adds no new methods but is essentially an intersection of > ReversibleCollection > and Set. As such, it's suitable as the return type of > LinkedHashSet.reversed() and > the set views of LinkedHashMap. > > SortedSet::addFirst and addLast throw UnsupportedOperationException. This is > because > SortedSet's ordering is determined by the comparison method and cannot be > controlled > explicitly. > > LinkedHashSet::addFirst and addLast add the element at the appropriate > position or > reposition the element if it is already present in the set. > > New methods are added to LinkedHashMap > > V putFirst(K, V) > V putLast(K, V) > > which put the mapping at the designated position or reposition the mapping if > is > already present in the map. > > > # Design & Implementation Issues > > > Covariant overrides for reversed() are provided where possible. However, > there is a > conflict between List and Deque, as there are examples in the JDK (such as > LinkedList) that implement both List and Deque. Since List is much more > popular than > Deque, I've decided against adding a covariant override to Deque. Instead, a > method > Deque::reversedDeque is added that returns a Deque, and Deque::reversed > returns > ReversibleCollection. > > There is no ReversibleMap interface. Most iteration over maps is over the > entrySet, > keySet, or values views. NavigableMap already has descendingMap(), and > LinkedHashMap > provides ReversibleX views, which cover most of the cases already. > > Introducing new methods into an interface hierarchy always raises the > possibility of > name clashes. I've done some searching but I haven't found any major issues, > but we > should be on the lookout for this. I'll continue to do more searching for such > conflicts. > > Introducing covariant overrides on existing methods (notably LinkedHashMap > entrySet, > keySet, and values) could present incompatibility issues with subclasses that > override these methods. I've done some searching and again I haven't found > major > problems, but this is nonetheless a point of concern. I'll do more searching > here, too. > > The default implementations for List::reversed, Deque::reversed, and > SortedSet::reversed return reverse-ordered views that are implemented using > only > public methods of the original interface. This demonstrates the feasibility of > retrofitting reverse ordering onto any instance of these interfaces. > Similarly, the > various add/get/remove methods' default implementations are all implementable > in > terms of an iterator or reverse-ordered iterator. That said, some concurrent > collection implementations will need to override these default > implementations in > order to preserve their safety invariants. It would probably also be wise to > add > optimized implementations to the more commonly-used collection > implementations. > > Given that a ReversibleCollection has a defined ordering, any spliterator > obtained > from such a collection should have the Spliterator.ORDERED characteristic. > > This proposal is related to a previous discussion on a similar topic, where > Tagir > Valeev had proposed OrderedSet and OrderedMap: > > > http://mail.openjdk.java.net/pipermail/core-libs-dev/2020-April/066028.html > > I think there were some good ideas in there and in the ensuing discussion, > but it > didn't go anywhere. Several of the concepts in this proposal are an evolution > of > some ideas discussed in that thread. > > One of the ideas from that thread was to use Deque as a common interface for > many > collections to support reversibility and operations at the ends. We've > abandoned > that idea in this proposal. The reasons are that it's cluttered with a bunch > of > methods that are inherited from Queue. Also, some methods are null-returning > instead > of throwing, which introduces confusion for collections that can contain > nulls. > > # END
