Re: [External] : Re: ReversibleCollection proposal
On 20/05/2021 08:35, dfranken@gmail.com wrote: I also think the proposal of Stuart is reasonable though, but it seemed to me that we had reached some sort of impasse in this discussion. As Remi points out, we have (default) methods which sometimes throw exceptions when they are implemented to signify they don't actually implement the given feature, but we also have interfaces which add new methods. So any choice we make here seems to be inconsistent with some choice we made in the past, but such is the nature of software development I guess. I think progress is still possible. The discussion has shown some alternatives which are not better than new ReversibleCollection/ReversibleSet types. The discussion has raised some concerns about compatibility but they are not to hard to overcome (mostly just source-level). There is clearly a benefit from new types although migration to use them will not be fast. But it might be faster than we are used to. The most difficult was (and for some still is) a JDK 8 -> JDK 9 jump, but once you are on JDK 9+ it is relatively easy to follow latest JDK release. With LTS JDK 17 around the corner, I expect most production code which now runs on JDK 11 will relatively quickly migrate to JDK 17 just for improvements in JVM/GC if not for Language/APIs. I think adding these types will surely trigger some disturbance but nothing major. Peter
Re: [External] : Re: ReversibleCollection proposal
Dear Brian,
I understand this would be a massive undertaking.
Still, the date-time library was a mess before Java 8 and it has been
rewritten and found its way to most other libraries.
So while I understand this isn't going to be done any time soon, my
only question was whether it had been thought about at any time in the
past. And if the consensus at that time was 'well, it would be great
if we could do it, but it's totally impractical, so let's not do it' I
would be okay with that.
I also think the proposal of Stuart is reasonable though, but it seemed
to me that we had reached some sort of impasse in this discussion. As
Remi points out, we have (default) methods which sometimes throw
exceptions when they are implemented to signify they don't actually
implement the given feature, but we also have interfaces which add new
methods. So any choice we make here seems to be inconsistent with some
choice we made in the past, but such is the nature of software
development I guess.
Given the choices of what is actually possible, I would go the
interface route.
Kind regards,
Dave
On Wed, 2021-05-19 at 17:23 -0400, Brian Goetz wrote:
>
> > Has it ever been conceived to create an entire new API like how it
> > was
> > done for Dates and Times? Obviously this would be a massive
> > undertaking, but it seems to me we've just about reached the limits
> > of
> > how far we can stretch the current API.
>
> "This code is a mess, we should throw it away and rewrite it"
>
> -- every developer
>
> Don't confuse the volume of "I would rather do it this way" replies
> with
> the complexity of this issue; I think that's just the nature of the
> game
> ("Being the biggest crime of the last 50 years, and everybody wanted
> to
> get in the newspaper story about it.") Stuart's proposal is a
> measured,
> responsible, carefully-thought-through way to extend the framework we
> have.
>
> In addition to "massive undertaking", and in addition to "if you
> think
> you can't get people to agree on something the size of a golf ball,
> try
> to get them to agree on something the size of Montana", there's
> another
> massive problem here: migration. It's not just a matter of having a
> "better" Collections library; the collection interfaces we have
> (Collection, List, Map, Set) have found their way into the API of
> nearly
> every Java library. Moving to Collections II would then force a
> migration on every one of those libraries (or consumer of those
> libraries.)
>
>
Re: [External] : Re: ReversibleCollection proposal
Has it ever been conceived to create an entire new API like how it was
done for Dates and Times? Obviously this would be a massive
undertaking, but it seems to me we've just about reached the limits of
how far we can stretch the current API.
"This code is a mess, we should throw it away and rewrite it"
-- every developer
Don't confuse the volume of "I would rather do it this way" replies with
the complexity of this issue; I think that's just the nature of the game
("Being the biggest crime of the last 50 years, and everybody wanted to
get in the newspaper story about it.") Stuart's proposal is a measured,
responsible, carefully-thought-through way to extend the framework we have.
In addition to "massive undertaking", and in addition to "if you think
you can't get people to agree on something the size of a golf ball, try
to get them to agree on something the size of Montana", there's another
massive problem here: migration. It's not just a matter of having a
"better" Collections library; the collection interfaces we have
(Collection, List, Map, Set) have found their way into the API of nearly
every Java library. Moving to Collections II would then force a
migration on every one of those libraries (or consumer of those libraries.)
Re: [External] : Re: ReversibleCollection proposal
In reading all of the messages in this discussion, it becomes clear to me that this is not a trivial change, because we are mostly hindered by the Collection API as it currently exists. Adding interfaces seems like the correct OOP way to do things, but it may hinder adoption, because we have to wait for it to cascade through the ecosystem. Adding default methods seems like the most compatible way, but then we create even more confusion in the Collection class. If add() can throw an exception, but getFirst() never will but may just return a random element, that does not seem consistent to me. Has it ever been conceived to create an entire new API like how it was done for Dates and Times? Obviously this would be a massive undertaking, but it seems to me we've just about reached the limits of how far we can stretch the current API. When given the choice between the current proposals to add interfaces or default methods, I'm kind of torn. Maybe we should just yield and add the methods to the different sub-interfaces like List, etc? This seems to be the least disruptive, but obviously it doesn't greatly improve the overall design. Kind regards, Dave On Fri, 2021-05-14 at 00:15 +0200, fo...@univ-mlv.fr wrote: > - Mail original - > > De: "Anthony Vanelverdinghe" > > À: "Remi Forax" > > Cc: "Stuart Marks" , "core-libs-dev" > > > > Envoyé: Jeudi 13 Mai 2021 21:18:22 > > Objet: Re: [External] : Re: ReversibleCollection proposal > > > Hi Rémi > > > > The discussion "new types? or new default methods?" is indeed a > > valid one. In > > fact, I think this choice has already been made once in favor of a > > default > > method, when adding `List::sort` was chosen over adding > > `SortedList` (though I > > imagine that choice was a no-brainer). > > yes, very true, there is no SortedList even if it would be useful to > know if a list is already sorted, by example, we can add > binarySearch() on it with no problem of people using it on an > unsorted list. > > > > > In this case I prefer adding new types though, so I wanted to share > > my take on > > this. > > > > In the following diagram (see [1] in case it got mangled), I've > > tried to arrange > > all relevant Collection types by their defining characteristics: > > > > > - Collection > > > - > > > --| > > > unordered ordered > > > sorted distinct > > > distinct & ordered distinct & sorted | > > > > > > Set | > > > Queue = (get|remove)First + addLast > > > PriorityQueue > > > | > > > Stack = (add|get|remove)Last > > > | > > > Deque = Queue + Stack + addFirst > > > LinkedHashSet SortedSet | > > > List = Deque + (add|get|remove)Indexed List::sort > > > NavigableSet | > > > - > > > ---| > > > > As I see it, there are a couple of issues with this: > > * conceptually, every List is a Deque, but List doesn't extend > > Deque. If it > > would, all uses of List (e.g. as a parameter type in APIs) where > > the indexed > > access isn't required could be replaced with Deque instead. Or e.g. > > when you > > need to take a stack as argument: currently Deque is the > > recommended parameter > > type, but that means you can't just pass a List to the method as- > > is. With RC, > > you'd be able to use that as parameter type and pass both Deque and > > List. > > You can use the same argument to have a common super type between Map > and Collection, it would be very useful. > > Until you think what methods are available on that type, size() and > isEmpty(), meh, this is useless. > > RC has the same issue, it's stuck in between Collection and List, so > the cases where you don't want a Collection because it has not enough > methods you want to use but at the same time you don't want a List > because it has too many methods are vanishingly small. > > The problem is that adding RC is not source compatible, so you are > asking to add something in the JDK which serve a corner case but at > the same time forces people to change th
Re: [External] : Re: ReversibleCollection proposal
- Mail original - > De: "Anthony Vanelverdinghe" > À: "Remi Forax" > Cc: "Stuart Marks" , "core-libs-dev" > > Envoyé: Jeudi 13 Mai 2021 21:18:22 > Objet: Re: [External] : Re: ReversibleCollection proposal > Hi Rémi > > The discussion "new types? or new default methods?" is indeed a valid one. In > fact, I think this choice has already been made once in favor of a default > method, when adding `List::sort` was chosen over adding `SortedList` (though I > imagine that choice was a no-brainer). yes, very true, there is no SortedList even if it would be useful to know if a list is already sorted, by example, we can add binarySearch() on it with no problem of people using it on an unsorted list. > > In this case I prefer adding new types though, so I wanted to share my take on > this. > > In the following diagram (see [1] in case it got mangled), I've tried to > arrange > all relevant Collection types by their defining characteristics: > >|- Collection >|---| >|unorderedordered sorted >distinct >|distinct & ordereddistinct & sorted | >|Set > | >| Queue = (get|remove)First + addLast PriorityQueue >| | >| Stack = (add|get|remove)Last >| | >| Deque = Queue + Stack + addFirst >| LinkedHashSet SortedSet | >| List = Deque + (add|get|remove)IndexedList::sort >| NavigableSet | >|| > > As I see it, there are a couple of issues with this: > * conceptually, every List is a Deque, but List doesn't extend Deque. If it > would, all uses of List (e.g. as a parameter type in APIs) where the indexed > access isn't required could be replaced with Deque instead. Or e.g. when you > need to take a stack as argument: currently Deque is the recommended parameter > type, but that means you can't just pass a List to the method as-is. With RC, > you'd be able to use that as parameter type and pass both Deque and List. You can use the same argument to have a common super type between Map and Collection, it would be very useful. Until you think what methods are available on that type, size() and isEmpty(), meh, this is useless. RC has the same issue, it's stuck in between Collection and List, so the cases where you don't want a Collection because it has not enough methods you want to use but at the same time you don't want a List because it has too many methods are vanishingly small. The problem is that adding RC is not source compatible, so you are asking to add something in the JDK which serve a corner case but at the same time forces people to change their code even if they don't use RC. It's a loose / loose situation, we will have to maintain a collection forever in the JDK that nobody uses but everybody will pay for it. [...] > > On Wednesday, May 12, 2021 13:22 CEST, fo...@univ-mlv.fr wrote: > >> First, i think we have overlooked ReversibleMap, if you have a LinkedHashMap, >> the keySet should be a ReversibleSet. > > I'm not sure what you meant, but the PR already defines > `LinkedHashMap::keySet` > as `public ReversibleSet keySet()`. LinkedHashMap is perhaps the only implementation which has a keySet which is reversible, but there are a lot of other collection implementations, Apache collection, Guava, Eclipse, clojure-core, etc that may have such kind of implementation too. The same way you want RC between Queue and List, you want ReversibleMap between those Map implementations. > >> Again, we have seen that introducing those interfaces >> - is not source backward compatible thus it will be painful for some of our >> users, >> I believe NavigableSet/NavigableMap did not have that issue because only >> one >> existing implementation per interface was retrofitted to implement those >> interfaces, TreeSet for NavigableSet and TreeMap for NavigableMap. >> ConcurrentSkipListSet/ConcurrentSkipListMap were added at the same time, so >> there was no existing code doing a lub (lowest upper bound) between >> TreeSet and >> ConcurrentSkipListSet. >> Here, they are a lot of implementations that will implement be retrofitted >> to >> ReversibleCollection, ReversibleSet and ReversibleMap. > > As far as I understand, both options might cau
Re: [External] : Re: ReversibleCollection proposal
Hi Rémi The discussion "new types? or new default methods?" is indeed a valid one. In fact, I think this choice has already been made once in favor of a default method, when adding `List::sort` was chosen over adding `SortedList` (though I imagine that choice was a no-brainer). In this case I prefer adding new types though, so I wanted to share my take on this. In the following diagram (see [1] in case it got mangled), I've tried to arrange all relevant Collection types by their defining characteristics: |- Collection ---| |unorderedordered sorted distinctdistinct & ordereddistinct & sorted | |Set | | Queue = (get|remove)First + addLast PriorityQueue | | Stack = (add|get|remove)Last | | Deque = Queue + Stack + addFirst LinkedHashSet SortedSet | | List = Deque + (add|get|remove)IndexedList::sort NavigableSet | || As I see it, there are a couple of issues with this: * conceptually, every List is a Deque, but List doesn't extend Deque. If it would, all uses of List (e.g. as a parameter type in APIs) where the indexed access isn't required could be replaced with Deque instead. Or e.g. when you need to take a stack as argument: currently Deque is the recommended parameter type, but that means you can't just pass a List to the method as-is. With RC, you'd be able to use that as parameter type and pass both Deque and List. * LinkedHashSet and SortedSet lack a common ancestor which asserts "this is an ordered set". So when defining an API, I'm forced to choose between SortedSet, which is more specific than I want, or List, which is more generic than I want (usually I go with SortedSet, because enforcing something through Javadoc isn't very reliable (cf. Collectors::toList: even though the spec clearly says the result might not be modifiable, people tend to simply assume it is)). Now with RC/RS these issues would be solved, where RC is ~ Deque + reversed, and RS ~ Deque + distinct + reversed. In terms of the diagram, they group together a bunch of closely-related Collection types (see [1] if needed): |- Collection ---| |unorderedordered sorted distinctdistinct & ordereddistinct & sorted | |Set | | Queue = (get|remove)First + addLast PriorityQueue | | Stack = (add|get|remove)Last | ||- ReversibleCollection ---| |- ReversibleSet ---|| ||Deque = Queue + Stack + addFirst | |LinkedHashSet SortedSet|| ||List = Deque + (add|get|remove)IndexedList::sort | | NavigableSet || ||--| |---|| || On Wednesday, May 12, 2021 13:22 CEST, fo...@univ-mlv.fr wrote: > First, i think we have overlooked ReversibleMap, if you have a LinkedHashMap, > the keySet should be a ReversibleSet. I'm not sure what you meant, but the PR already defines `LinkedHashMap::keySet` as `public ReversibleSet keySet()`. > Again, we have seen that introducing those interfaces > - is not source backward compatible thus it will be painful for some of our > users, > I believe NavigableSet/NavigableMap did not have that issue because only > one existing implementation per interface was retrofitted to implement those > interfaces, TreeSet for NavigableSet and TreeMap for NavigableMap. > ConcurrentSkipListSet/ConcurrentSkipListMap were added at the same time, so > there was no existing code doing a lub (lowest upper bound) between TreeSet > and ConcurrentSkipListSet. > Here, they are a lot of implementations that will implement be retrofitted > to
Re: [External] : Re: ReversibleCollection proposal
- Mail original - > De: "Peter Levart" > À: "Stuart Marks" > Cc: "core-libs-dev" > Envoyé: Mercredi 12 Mai 2021 08:28:07 > Objet: Re: [External] : Re: ReversibleCollection proposal > On 5/12/21 2:55 AM, Stuart Marks wrote: >> As you point out, add() is kind of like addLast(), except without the >> reordering semantics for LinkedHashSet. And reversed().add() is a >> roundabout way of saying addFirst() -- also without the reordering >> semantics for LinkedHashSet. I think most people's reactions would be >> "Why didn't they just provide addFirst/addLast?" Plus the reordering >> would be missing for LHS. >> >> A second-order issue is performance. I'd expect that implementations >> would want to provide a fast-path for addFirst() that is amenable to >> JIT optimization; this seems harder to achieve with reversed().add(). > > > The allocation of a reversed view instance typically goes away when C2 > compiles the method (if the instance isn't cached like in > AbstractMap.keySet/values) so this can be as performant as specialized > addFirst(), but lack of reordering of existent element in LinkedHashSet > is a different problem I haven thought about. Don't forget that the default method implementation is just that a default method, at least the JDK implementations like LinkedHashSet can/should provide a better implementation. > > > Regards, Peter regards, Rémi
Re: [External] : Re: ReversibleCollection proposal
- Mail original - > De: "Stuart Marks" > À: "Remi Forax" > Cc: "core-libs-dev" > Envoyé: Mercredi 12 Mai 2021 07:27:51 > Objet: Re: [External] : Re: ReversibleCollection proposal >>> I'm certain that uses of RC/RS will be rare in the beginning, because they >>> will >>> be >>> new, and people won't be familar with them. And then there will the people >>> who >>> say >>> "I can't use them because I'm stuck on JDK 11 / 8 / 7 / 6 " It was the >>> same >>> thing with lambdas and streams in Java 8, with List.of() etc in Java 9, >>> records >>> in >>> Java 16, etc. This wasn't an argument not to add them, and it isn't an >>> argument >>> not >>> to add RC/RS. >> >> All the changes you are listing here are "client side" changes, the ones that >> can be adopted quickly because they do not require to change the API side of >> any libraries. >> ReversibleCollection is an API side change, like generics is, those changes >> have >> a far higher cost because you have to wait your library dependencies to be >> updated. >> On the Valhalla list, we have discussed several times about how to alleviate >> those API side change cost using automatic bridging or methods forwarding, >> even >> for Valhalla, we are currently moving in a state where those mechanisms are >> not >> needed. > > This isn't an argument against RC/RS. Application code can find uses for the > new > APIs, e.g. getFirst and addLast on List, or more ordering flexibility on > LinkedHashSet, on day one. Applications' internal APIs can also benefit on day > one. > Certainly libraries will have to wait for their clients to catch up to later > JDKs. > This has *always* been the case, even for library internals (such as use of > lambdas > or APIs introduced in newer JDKs) because libraries need to be compiled for > the > lowest version of the JDK their clients support. For example, you can't use > List.of() in a library -- even internally -- if your clients are still on JDK > 8. > There are no new issues here. First, i think we have overlooked ReversibleMap, if you have a LinkedHashMap, the keySet should be a ReversibleSet. It is because with RC/RS/RM, you have to wait far longer, being able to use the JDK version is not enough to be able to introduce a public method that takes a ReversibleCollection, you also need to be sure that all clients of your library are using collections that have been upgraded to implement ReversibleCollection. In practice, enough client might be Ok, but that's a huge difference. Instead, if we follow the path of using default methods on Collection and not new interfaces, you only need to wait until you decide to upgrade the library to the JDK version, because with default methods all existing collections are "automatically" upgraded. > >> The abstraction already exists but it's not defined in term of interface >> because >> it's an implementation decision and those are cleanly separated in the >> current >> Collection design. >> >> Let take a step back, the collection API defines basic data structure >> operations >> in term of interfaces like List, Deque, Set, etc those interfaces are >> decoupled >> from implementation capabilities like mutable, nullable, ordered and checked. >> >> Depending on the implementation capabilities, the interfaces method >> implementation may throw an exception, non-mutable implementations use >> UnsupportedOperationException, non-nullable implementations use NPE and >> checked >> implementations use CCE. >> >> So what is missing is methods on Collection interfaces that require the >> collection implementation to be ordered like descendingList(), getFirst(), >> etc. >> Those methods that may throw a specific exception if the implementation is >> not >> ordered, not UnsupportedOperationException but a new one like >> NotOrderedException. >> >> So to answer to your question about LinkedHashSet, the reverse-ordered >> LinkedHashSet is a Set with a method descendingSet() that do not throw >> NotOrderedException like any Set with an order. >> >> To summarize, if we introduce ReversibleCollection, we should also introduce >> ImmutableCollection, NonNullableCollection and CheckedCollection. >> I think it's better to consider the fact that being ordered as a capability >> (hint: this is already what the Spliterator API does) and not as a specific >> interface. > > This discussion, and your ensuing prop
Re: [External] : Re: ReversibleCollection proposal
On 5/12/21 2:55 AM, Stuart Marks wrote: As you point out, add() is kind of like addLast(), except without the reordering semantics for LinkedHashSet. And reversed().add() is a roundabout way of saying addFirst() -- also without the reordering semantics for LinkedHashSet. I think most people's reactions would be "Why didn't they just provide addFirst/addLast?" Plus the reordering would be missing for LHS. A second-order issue is performance. I'd expect that implementations would want to provide a fast-path for addFirst() that is amenable to JIT optimization; this seems harder to achieve with reversed().add(). The allocation of a reversed view instance typically goes away when C2 compiles the method (if the instance isn't cached like in AbstractMap.keySet/values) so this can be as performant as specialized addFirst(), but lack of reordering of existent element in LinkedHashSet is a different problem I haven thought about. Regards, Peter
Re: [External] : Re: ReversibleCollection proposal
I'm certain that uses of RC/RS will be rare in the beginning, because they will be new, and people won't be familar with them. And then there will the people who say "I can't use them because I'm stuck on JDK 11 / 8 / 7 / 6 " It was the same thing with lambdas and streams in Java 8, with List.of() etc in Java 9, records in Java 16, etc. This wasn't an argument not to add them, and it isn't an argument not to add RC/RS. All the changes you are listing here are "client side" changes, the ones that can be adopted quickly because they do not require to change the API side of any libraries. ReversibleCollection is an API side change, like generics is, those changes have a far higher cost because you have to wait your library dependencies to be updated. On the Valhalla list, we have discussed several times about how to alleviate those API side change cost using automatic bridging or methods forwarding, even for Valhalla, we are currently moving in a state where those mechanisms are not needed. This isn't an argument against RC/RS. Application code can find uses for the new APIs, e.g. getFirst and addLast on List, or more ordering flexibility on LinkedHashSet, on day one. Applications' internal APIs can also benefit on day one. Certainly libraries will have to wait for their clients to catch up to later JDKs. This has *always* been the case, even for library internals (such as use of lambdas or APIs introduced in newer JDKs) because libraries need to be compiled for the lowest version of the JDK their clients support. For example, you can't use List.of() in a library -- even internally -- if your clients are still on JDK 8. There are no new issues here. The abstraction already exists but it's not defined in term of interface because it's an implementation decision and those are cleanly separated in the current Collection design. Let take a step back, the collection API defines basic data structure operations in term of interfaces like List, Deque, Set, etc those interfaces are decoupled from implementation capabilities like mutable, nullable, ordered and checked. Depending on the implementation capabilities, the interfaces method implementation may throw an exception, non-mutable implementations use UnsupportedOperationException, non-nullable implementations use NPE and checked implementations use CCE. So what is missing is methods on Collection interfaces that require the collection implementation to be ordered like descendingList(), getFirst(), etc. Those methods that may throw a specific exception if the implementation is not ordered, not UnsupportedOperationException but a new one like NotOrderedException. So to answer to your question about LinkedHashSet, the reverse-ordered LinkedHashSet is a Set with a method descendingSet() that do not throw NotOrderedException like any Set with an order. To summarize, if we introduce ReversibleCollection, we should also introduce ImmutableCollection, NonNullableCollection and CheckedCollection. I think it's better to consider the fact that being ordered as a capability (hint: this is already what the Spliterator API does) and not as a specific interface. This discussion, and your ensuing proposal to add a bunch of throwing default methods to Collection, is based on a flawed premise. That premise is that there is a fundamental distinction between "data structure operations" which must be embodied as types, and "implementation capabilities" which must manifest at runtime either by allowing the operation or by throwing an exception. But this distinction isn't fundamental. In what way is being ordered not a "basic data structure" issue? In what way is indexed access (as for List) not an "implementation capability"? Really, these are two different aspects of the same thing. Over time, new "data structure operations" and new "implementation capabilities" have been added to the collections framework. Some of them were embodied as types, and some were not. Which ones were embodied as types was the result of design decisions that considered a bunch of tradeoffs. What you're attempting to do is to declare absolutes. This drives you to one of two extremes, which is either 1) to never add new types and to always add possibly-throwing operations to existing types (which seems to be what you're describing as an alternative); or 2) to claim that everything needs to be manifested as a new type (giving rise to your straw-man argument that we should also have ImmutableCollection, NonNullableCollection, CheckedCollection, etc.). The argument seems to be that we wouldn't want to add all those other types, so we mustn't add ReversibleCollection either. No. In summary, I reject the premise that adding ReversibleCollection implies that a bunch of other types also need to be added, so I don't accept this line of reasoning as an argument against ReversibleCollection. s'marks
Re: [External] : Re: ReversibleCollection proposal
On 5/1/21 7:36 AM, Peter Levart wrote:
On 4/30/21 9:25 PM, Stuart Marks wrote:
So I think we're stuck with void-returning add{First,Last} methods.
Have you thought of perhaps not adding them at all?
Collection.add() for:
List(s) - behaves the same as addLast()
LinkedHashSet - behaves the same as addLast()
Deque - behaves the same as addLast()
So for all ReversibleCollection(s) where it works, addLast() would be equivalent to
add()
addFirst(x) can be written as: reversed().add(x) if reversed() is specified to
return a reversed view over the underlying ReversibleCollection.
To me, and I think to most people, add, get, and remove all belong together, just
like offer/peek/poll. (See the tables in the Deque class spec.) Of course the issue
is that addX can't be implemented for SortedSet (or it can be, but only with some
contrivances discussed previously). The choice is between which asymmetry we want:
1. add/get/remove across most of the ReversibleCollection implementations except for
SortedSet, or
2. get/remove across all ReversibleCollection implementations, with addX() "missing"
from the set of operations.
As you point out, add() is kind of like addLast(), except without the reordering
semantics for LinkedHashSet. And reversed().add() is a roundabout way of saying
addFirst() -- also without the reordering semantics for LinkedHashSet. I think most
people's reactions would be "Why didn't they just provide addFirst/addLast?" Plus
the reordering would be missing for LHS.
A second-order issue is performance. I'd expect that implementations would want to
provide a fast-path for addFirst() that is amenable to JIT optimization; this seems
harder to achieve with reversed().add().
s'marks
Re: [External] : Re: ReversibleCollection proposal
- Mail original -
> De: "Peter Levart"
> À: "Remi Forax" , "dfranken jdk"
> Cc: "Stuart Marks" , "core-libs-dev"
>
> Envoyé: Mardi 11 Mai 2021 13:44:08
> Objet: Re: [External] : Re: ReversibleCollection proposal
> Hi Remi,
Hi Peter,
>
>
> I see you avoided addFirst/addLast methods. While getFirst/removeFirst
> could be specified to be consistent with iterator().next(), so the
> "first" part of the name would be softer, addFirst is cursed two times:
> it has no equivalent in current API and it clashes with void returning
> method in Deque. So the best "soft" alternative seems to be the existing
> Collection.add(E) method which is equivalent to addFirst() when
> Collection is ordered or something totally different when it is sorted
> (i.e. SortedSet) and again different when it is neither.
yes, i've chosen to not have addFirst/addLast because of addFirst/addLast on
Deque returning void.
To simplify the issue of adding addFirst/addLast on List,
SortedSet/NavigableSet, EnumSet, LinkedHashSet and adding
addFirstEntry/addLastEntry on SortedMap/NavigableMap, EnumMap and LinkedHashMap
can be discussed separately.
>
> To avoid bugs when an API expects an ordered Collection but has no
> static type to express that, a means to perform a runtime check would be
> needed. Marker interface is a way to add a bit of static typing to be
> used in generic methods like:
>
>
> & Ordered> void doSomething(C
> orderedCollection);
>
>
> ...but that's very limited. So probably not worth it.
yes,
and also if we go with Ordered people will also want Sorted, NoDuplicate,
NonNullable, etc.
> Stream API choose a different approach: Spliterator.characteristics(). So
> probably,
> Collection.characteristics() could also be added. The set of bit
> constants in Spliterator is applicable also to Collection (except
> SUBSIZED which has no sense in Collection, while SIZED is always present):
>
> ORDERED
> DISTINCT
> SORTED
> SIZED
> NONNULL
> IMMUTABLE
> CONCURRENT
>
> Specifically for Collection I would also add:
>
> REVERSIBLE
>
> ...to indicate that Collection.reversed() would succeed.
>
>
> The question is what would the default value of
> Collection.characteristics() be. The most sensible would be SIZED with
> overrides in:
>
> - List (SIZED | ORDERED | REVERSIBLE)
> - Set (SIZED | DISTINCT)
> - SortedSet (SIZED | SORTED | REVERSIBLE | DISTINCT)
> - LinkedHashSet (SIZED | ORDERED | REVERSIBLE | DISTINCT)
> - Queue (SIZED | ORDERED)
> - Deque (SIZED | ORDERED | REVERSIBLE)
>
> ... Immutable JDK List and Set implementations could also add IMMUTABLE
>| NONNULL, while concurrent JDK implementations would add CONCURRENT |
> NONNULL.
>
>
> ...but one could also base default value on something like this:
>
>
> default int characteristics() {
> return stream().spliterator().characteristics() &
> ~Spliterator.SUBSIZED;
> }
There is already a method Collection.spliterator() [1], no need to use an
intermediary stream
and also collection.spliterator() != collection.stream().spliterator(), but i'm
not sure if it is specified somewhere.
For me, adding a method characteristics() to Collection is also a separate
issue,
perhaps it's more a documentation issue, so adding a paragraph in the javadoc
explaining what are the Spliterator characteristics of each collections is
enough.
>
>
> Wrappers like Collections.unmodifiableXXX() would just delegate to the
> underlying Collection and augment the returned bits (with IMMUTABLE for
> example).
>
>
> An API that expects a particular kind of collection could then check
> that at runtime. Some of existing collections would have to be updated
> to express the correct characteristics, but defaults in interfaces would
> be sufficient for most and conservative.
>
>
> WDYT?
>
> Peter
Rémi
[1]
https://docs.oracle.com/en/java/javase/16/docs/api/java.base/java/util/Collection.html#spliterator()
>
>
> On 5/11/21 9:26 AM, fo...@univ-mlv.fr wrote:
>>
>>> Are you proposing to just add methods to the root Collection interface,
>>> because it already has methods which may or may not be implemented or
>>> throw Exceptions by its implementations ?
>> yes, the idea is to add getFirst/getLast/removeFirst/removeLast and reversed
>> on
>> Collection as default methods.
>> Something like
>>
>> interface Collection {
>>/**
>> * throws NoSuchElementException if the collection is empty
>> */
>>public default E getFirst() {
>> return iterator().next
Re: [External] : Re: ReversibleCollection proposal
* throws NoSuchElementException if the map is empty
* throws NonOrderedCollectionException if the map.keySet() is non ordered
*/
public default E getLastEntry() {
return reversedMap().getFirstEntry();
}
/**
* throws NoSuchElementException if the map is empty
* throws UnsupportedOperationException if the map is non mutable
* throws NonOrderedCollectionException if the map.keySet() is non ordered
*/
public default E removeLast() {
return reversedMap().removeFirstEntry();
}
}
And adds an implementation of reversedMap(), getLastEntry() and
removeLastEntry() on NavigableMap/LinkedHasMap and EnumMap.
But we could also view "having (possibly duplicate) items in a
sequence" as a capability and that is defined by an actual interface,
List.
It already exist for a Spliterator, the capability is called DISTINCT, by
example, set.stream() and list.stream().distinct() are both Streams with no
duplicate.
I do fear that if we add methods to the Collection interface, users
might not expect them to throw exceptions. E.g. if we add getFirst(),
users may just expect it to return the element that iterator().next()
or .stream().findFirst().orElseThrow() would return instead of an
UnsupportedOperationException. And while HashSet does not have a
defined order, it would in practice always return the same element.
I agree, getFirst() and removeFirst() should have their semantics based on
iterator (see above),
because as you said, it's already how findFirst() is specified.
So while I accept that some hidden capabilities are surfaced only
through return values of certain methods, I think an interface is still
a better choice here. However, if we go that route, I also agree on the
fact that we might need to explore defining proper interfaces for the
other capabilities at some point.
Kind regards,
Dave
regards,
Rémi
On Mon, 2021-05-10 at 12:22 +0200, fo...@univ-mlv.fr wrote:
- Mail original -
De: "dfranken jdk"
À: "Remi Forax" , "Stuart Marks"
Cc: "core-libs-dev"
Envoyé: Dimanche 9 Mai 2021 12:13:58
Objet: Re: [External] : Re: ReversibleCollection proposal
When I thought about Collection's role in the hierarchy, it seemed
to
me that 'Collection' is an interface for describing how elements
are
stored in a cardboard box (we can and and remove them) and that we
might need a different, yet related, interface to describe how to
retrieve the items from the box. This way we are not tied to the
Collection hierarchy and we could have one Set implementation which
is
ordered and another Set implementation which is not and they would
both
still implement Collection, but only one would implement the
interface.
So you want to model ReversibleSet as Set + Reversible,
Reversible being an interface with a small number of method specific
to the fact that the implementation is reversible.
This does not work well for two reasons,
- there is no syntax to represent the union of types in Java,
Set & Reversible set = ...
is not a valid syntax. You can use a type variable with several
bounds instead but it does work nicely with the rest of the language
(overidding, overloading, etc).
- having public methods that takes an interface with few methods is a
common design error.
Let suppose you have a method foo that only prints the elements of
a collection, in that case you may want to type the first parameter
as Iterable or Collection.
But requirements change an now you want to prints the elements
sorted, oops, you have to change the signature of the public method
which may be something not possible
depending how many "clients" this method has.
Providing interfaces with a small number of access methods will
lead to this kind of issue.
Imagine an interface like 'java.lang.OrderedEnumerable` if you will
with methods such as 'first(), last(), etc', then each
implementation
would be free to choose to implement the interface or not. I also
thought about 'OrderedIterable', but there would be too much
confusion
with 'Iterable', but I think these are related too. Retrieving
items is
an iteration problem, not a storage problem.
The problem is that is you multiply the number of interfaces to
access the elements, you add the dilemma of choice in the mix.
The first iteration of the Scala Collection were like this, too many
interfaces, at least for my taste.
While I would love to see the Collection hierarchy redesigned to
also
allow for ImmutableCollection which for instance would not have an
`add(T e)` method, I don't think we can simply do something like
that
without breaking too many things.
Dear Santa, i want an interface BuilderCollection that only allows
add() but no remove()/clear(), because if you can not remove
elements, then all the iterators can implement the snapshot at the
beginning semantics,
so no ConcurrentModificationException anymore. For me, being able to
snapshot/freeze a collection is better
Re: [External] : Re: ReversibleCollection proposal
- Mail original -
> De: "dfranken jdk"
> À: "Remi Forax"
> Cc: "Stuart Marks" , "core-libs-dev"
>
> Envoyé: Mardi 11 Mai 2021 08:45:15
> Objet: Re: [External] : Re: ReversibleCollection proposal
> Dear mr. Forax,
Hi Dave,
>
> I understand your point of view. You don't like to have separate
> standalone interfaces for things that seem to belong in a hierarchy, is
> that correct? Now that I thought about it, I agree.
yes,
>
> So if a reversable/ordered set is a specialized form of a reversable
> collection where reversable collection is a specialized form of a
> collection, it makes sense to add it into the hierarchy.
>
> Are you proposing to just add methods to the root Collection interface,
> because it already has methods which may or may not be implemented or
> throw Exceptions by its implementations ?
yes, the idea is to add getFirst/getLast/removeFirst/removeLast and reversed on
Collection as default methods.
Something like
interface Collection {
/**
* throws NoSuchElementException if the collection is empty
*/
public default E getFirst() {
return iterator().next();
}
/**
* throws NoSuchElementException if the collection is empty
* throws UnsupportedOperationException if the collection is non mutable
*/
public default E removeFirst() {
var it = iterator();
var element = it.next();
it.remove();
return element;
}
/**
* throws NonOrderedCollectionException if the collection is non ordered
*/
public default Collection reversed() {
throw new NonOrderedCollectionException();
}
/**
* throws NoSuchElementException if the collection is empty
* throws NonOrderedCollectionException if the collection is non ordered
*/
public default E getLast() {
return reversed().getFirst();
}
/**
* throws NoSuchElementException if the collection is empty
* throws UnsupportedOperationException if the collection is non mutable
* throws NonOrderedCollectionException if the collection is non ordered
*/
public default E removeLast() {
return reversed().removeFirst();
}
}
And adds an implementation of reversed(), getLast() and removeLast() on
NavigableSet/LinkedHashSet/EnumSet/Deque and List.
And do the same thing for Map:
interface Map {
/**
* throws NoSuchElementException if the map is empty
*/
public default Map.Entry getFirstEntry() {
return entrySet().iterator().next();
}
/**
* throws NoSuchElementException if the map is empty
* throws UnsupportedOperationException if the map is non mutable
*/
public default Map.Entry removeFirstEntry() {
var it = entrySet().iterator();
var element = it.next();
it.remove();
return element;
}
/**
* throws NonOrderedCollectionException if the map.keySet() is non ordered
*/
public default Map reversedMap() {
throw new NonOrderedCollectionException();
}
/**
* throws NoSuchElementException if the map is empty
* throws NonOrderedCollectionException if the map.keySet() is non ordered
*/
public default E getLastEntry() {
return reversedMap().getFirstEntry();
}
/**
* throws NoSuchElementException if the map is empty
* throws UnsupportedOperationException if the map is non mutable
* throws NonOrderedCollectionException if the map.keySet() is non ordered
*/
public default E removeLast() {
return reversedMap().removeFirstEntry();
}
}
And adds an implementation of reversedMap(), getLastEntry() and
removeLastEntry() on NavigableMap/LinkedHasMap and EnumMap.
>
> But we could also view "having (possibly duplicate) items in a
> sequence" as a capability and that is defined by an actual interface,
> List.
It already exist for a Spliterator, the capability is called DISTINCT, by
example, set.stream() and list.stream().distinct() are both Streams with no
duplicate.
>
> I do fear that if we add methods to the Collection interface, users
> might not expect them to throw exceptions. E.g. if we add getFirst(),
> users may just expect it to return the element that iterator().next()
> or .stream().findFirst().orElseThrow() would return instead of an
> UnsupportedOperationException. And while HashSet does not have a
> defined order, it would in practice always return the same element.
I agree, getFirst() and removeFirst() should have their semantics based on
iterator (see above),
because as you said, it's already how findFirst() is specified.
>
> So while I accept that some hidden capabilities are surfaced only
> through return values of certain methods, I think an interface is still
> a better choice here. However, if we go that route, I also agree on the
> fact that we might need to explore defining proper interfaces for the
> other capabilities at some point.
>
> Kind regards,
>
> Dave
Re: [External] : Re: ReversibleCollection proposal
Dear mr. Forax, I understand your point of view. You don't like to have separate standalone interfaces for things that seem to belong in a hierarchy, is that correct? Now that I thought about it, I agree. So if a reversable/ordered set is a specialized form of a reversable collection where reversable collection is a specialized form of a collection, it makes sense to add it into the hierarchy. Are you proposing to just add methods to the root Collection interface, because it already has methods which may or may not be implemented or throw Exceptions by its implementations? Or were you just pointing out that's just how it works now? That the capabilities a certain collection has, like unmodifiability or not allowing null elements, are not exposed through a proper interface but through what it returns for certain methods? But we could also view "having (possibly duplicate) items in a sequence" as a capability and that is defined by an actual interface, List. I do fear that if we add methods to the Collection interface, users might not expect them to throw exceptions. E.g. if we add getFirst(), users may just expect it to return the element that iterator().next() or .stream().findFirst().orElseThrow() would return instead of an UnsupportedOperationException. And while HashSet does not have a defined order, it would in practice always return the same element. So while I accept that some hidden capabilities are surfaced only through return values of certain methods, I think an interface is still a better choice here. However, if we go that route, I also agree on the fact that we might need to explore defining proper interfaces for the other capabilities at some point. Kind regards, Dave On Mon, 2021-05-10 at 12:22 +0200, fo...@univ-mlv.fr wrote: > - Mail original - > > De: "dfranken jdk" > > À: "Remi Forax" , "Stuart Marks" > > > > Cc: "core-libs-dev" > > Envoyé: Dimanche 9 Mai 2021 12:13:58 > > Objet: Re: [External] : Re: ReversibleCollection proposal > > > When I thought about Collection's role in the hierarchy, it seemed > > to > > me that 'Collection' is an interface for describing how elements > > are > > stored in a cardboard box (we can and and remove them) and that we > > might need a different, yet related, interface to describe how to > > retrieve the items from the box. This way we are not tied to the > > Collection hierarchy and we could have one Set implementation which > > is > > ordered and another Set implementation which is not and they would > > both > > still implement Collection, but only one would implement the > > interface. > > So you want to model ReversibleSet as Set + Reversible, > Reversible being an interface with a small number of method specific > to the fact that the implementation is reversible. > > This does not work well for two reasons, > - there is no syntax to represent the union of types in Java, > Set & Reversible set = ... > is not a valid syntax. You can use a type variable with several > bounds instead but it does work nicely with the rest of the language > (overidding, overloading, etc). > > - having public methods that takes an interface with few methods is a > common design error. > Let suppose you have a method foo that only prints the elements of > a collection, in that case you may want to type the first parameter > as Iterable or Collection. > But requirements change an now you want to prints the elements > sorted, oops, you have to change the signature of the public method > which may be something not possible > depending how many "clients" this method has. > Providing interfaces with a small number of access methods will > lead to this kind of issue. > > > > > Imagine an interface like 'java.lang.OrderedEnumerable` if you will > > with methods such as 'first(), last(), etc', then each > > implementation > > would be free to choose to implement the interface or not. I also > > thought about 'OrderedIterable', but there would be too much > > confusion > > with 'Iterable', but I think these are related too. Retrieving > > items is > > an iteration problem, not a storage problem. > > The problem is that is you multiply the number of interfaces to > access the elements, you add the dilemma of choice in the mix. > The first iteration of the Scala Collection were like this, too many > interfaces, at least for my taste. > > > > > While I would love to see the Collection hierarchy redesigned to > > also > > allow for ImmutableCollection which for instance would not have an > > `add(T e)` method, I don't think we can simply do something like > > that > > w
Re: [External] : Re: ReversibleCollection proposal
- Mail original - > De: "dfranken jdk" > À: "Remi Forax" , "Stuart Marks" > Cc: "core-libs-dev" > Envoyé: Dimanche 9 Mai 2021 12:13:58 > Objet: Re: [External] : Re: ReversibleCollection proposal > When I thought about Collection's role in the hierarchy, it seemed to > me that 'Collection' is an interface for describing how elements are > stored in a cardboard box (we can and and remove them) and that we > might need a different, yet related, interface to describe how to > retrieve the items from the box. This way we are not tied to the > Collection hierarchy and we could have one Set implementation which is > ordered and another Set implementation which is not and they would both > still implement Collection, but only one would implement the interface. So you want to model ReversibleSet as Set + Reversible, Reversible being an interface with a small number of method specific to the fact that the implementation is reversible. This does not work well for two reasons, - there is no syntax to represent the union of types in Java, Set & Reversible set = ... is not a valid syntax. You can use a type variable with several bounds instead but it does work nicely with the rest of the language (overidding, overloading, etc). - having public methods that takes an interface with few methods is a common design error. Let suppose you have a method foo that only prints the elements of a collection, in that case you may want to type the first parameter as Iterable or Collection. But requirements change an now you want to prints the elements sorted, oops, you have to change the signature of the public method which may be something not possible depending how many "clients" this method has. Providing interfaces with a small number of access methods will lead to this kind of issue. > > Imagine an interface like 'java.lang.OrderedEnumerable` if you will > with methods such as 'first(), last(), etc', then each implementation > would be free to choose to implement the interface or not. I also > thought about 'OrderedIterable', but there would be too much confusion > with 'Iterable', but I think these are related too. Retrieving items is > an iteration problem, not a storage problem. The problem is that is you multiply the number of interfaces to access the elements, you add the dilemma of choice in the mix. The first iteration of the Scala Collection were like this, too many interfaces, at least for my taste. > > While I would love to see the Collection hierarchy redesigned to also > allow for ImmutableCollection which for instance would not have an > `add(T e)` method, I don't think we can simply do something like that > without breaking too many things. Dear Santa, i want an interface BuilderCollection that only allows add() but no remove()/clear(), because if you can not remove elements, then all the iterators can implement the snapshot at the beginning semantics, so no ConcurrentModificationException anymore. For me, being able to snapshot/freeze a collection is better than an ImmutableCollection, because it can be immutable when you want. Anyway, it's not gonna to happen, there is so many ways to slice an onion and each have pros and cons and providing all the possible interfaces is a good.way to make something simple complex. > > So in short, separating retrieval aspects from storage aspects with a > different interface might be the way to go. > > Kind regards, > > Dave Franken > regards, Rémi > On Wed, 2021-05-05 at 12:41 +0200, fo...@univ-mlv.fr wrote: >> - Mail original - >> > De: "Stuart Marks" >> > À: "Remi Forax" >> > Cc: "core-libs-dev" >> > Envoyé: Mercredi 5 Mai 2021 02:00:03 >> > Objet: Re: [External] : Re: ReversibleCollection proposal >> >> > On 5/1/21 5:57 AM, fo...@univ-mlv.fr wrote: >> > > I suppose the performance issue comes from the fact that >> > > traversing a >> > > LinkedHahSet is slow because it's a linked list ? >> > > >> > > You can replace a LinkedHashSet by a List + Set, the List keeps >> > > the values in >> > > order, the Set avoids duplicates. >> > > >> > > Using a Stream, it becomes >> > > Stream.of(getItemsFromSomeplace(), getItemsFromAnotherPlace(), >> > > getItemsFromSomeplaceElse()) >> > > .flatMap(List::stream) >> > > .distinct() // use a Set internally >> > > .collect(toList()); >> > >> > The problem with any example is that simplifying assumptions are >> > necessary for >> > showing the example, but those assumptions enable it
Re: [External] : Re: ReversibleCollection proposal
When I thought about Collection's role in the hierarchy, it seemed to me that 'Collection' is an interface for describing how elements are stored in a cardboard box (we can and and remove them) and that we might need a different, yet related, interface to describe how to retrieve the items from the box. This way we are not tied to the Collection hierarchy and we could have one Set implementation which is ordered and another Set implementation which is not and they would both still implement Collection, but only one would implement the interface. Imagine an interface like 'java.lang.OrderedEnumerable` if you will with methods such as 'first(), last(), etc', then each implementation would be free to choose to implement the interface or not. I also thought about 'OrderedIterable', but there would be too much confusion with 'Iterable', but I think these are related too. Retrieving items is an iteration problem, not a storage problem. While I would love to see the Collection hierarchy redesigned to also allow for ImmutableCollection which for instance would not have an `add(T e)` method, I don't think we can simply do something like that without breaking too many things. So in short, separating retrieval aspects from storage aspects with a different interface might be the way to go. Kind regards, Dave Franken On Wed, 2021-05-05 at 12:41 +0200, fo...@univ-mlv.fr wrote: > - Mail original - > > De: "Stuart Marks" > > À: "Remi Forax" > > Cc: "core-libs-dev" > > Envoyé: Mercredi 5 Mai 2021 02:00:03 > > Objet: Re: [External] : Re: ReversibleCollection proposal > > > On 5/1/21 5:57 AM, fo...@univ-mlv.fr wrote: > > > I suppose the performance issue comes from the fact that > > > traversing a > > > LinkedHahSet is slow because it's a linked list ? > > > > > > You can replace a LinkedHashSet by a List + Set, the List keeps > > > the values in > > > order, the Set avoids duplicates. > > > > > > Using a Stream, it becomes > > > Stream.of(getItemsFromSomeplace(), getItemsFromAnotherPlace(), > > > getItemsFromSomeplaceElse()) > > > .flatMap(List::stream) > > > .distinct() // use a Set internally > > > .collect(toList()); > > > > The problem with any example is that simplifying assumptions are > > necessary for > > showing the example, but those assumptions enable it to be easily > > picked apart. > > Of > > course, the example isn't just a particular example; it is a > > *template* for a > > whole > > space of possible examples. Consider the possibility that the items > > processing > > client needs to do some intermediate processing on the first group > > of items > > before > > adding the other groups. This might not be possible to do using > > streams. Use > > your > > imagination. > > > > > I think there are maybe some scenarios where ReversibleCollection > > > can be useful, > > > but they are rare, to the point where when there is a good > > > scenario for it > > > people will not recognize it because ReversibleCollection will > > > not be part of > > > their muscle memory. > > > > I'm certain that uses of RC/RS will be rare in the beginning, > > because they will > > be > > new, and people won't be familar with them. And then there will the > > people who > > say > > "I can't use them because I'm stuck on JDK 11 / 8 / 7 / 6 " It > > was the same > > thing with lambdas and streams in Java 8, with List.of() etc in > > Java 9, records > > in > > Java 16, etc. This wasn't an argument not to add them, and it isn't > > an argument > > not > > to add RC/RS. > > All the changes you are listing here are "client side" changes, the > ones that can be adopted quickly because they do not require to > change the API side of any libraries. > ReversibleCollection is an API side change, like generics is, those > changes have a far higher cost because you have to wait your library > dependencies to be updated. > On the Valhalla list, we have discussed several times about how to > alleviate those API side change cost using automatic bridging or > methods forwarding, even for Valhalla, we are currently moving in a > state where those mechanisms are not needed. > > > > > > There is a real value to add methods like > > > descendingSet/descendingList()/getFirst/getLast on existing > > > collections, but we > > > don't need a new interface (or two) for that. > > > > It depends on what you mean by "n
Re: [External] : Re: ReversibleCollection proposal
- Mail original - > De: "Stuart Marks" > À: "Remi Forax" > Cc: "core-libs-dev" > Envoyé: Mercredi 5 Mai 2021 02:00:03 > Objet: Re: [External] : Re: ReversibleCollection proposal > On 5/1/21 5:57 AM, fo...@univ-mlv.fr wrote: >> I suppose the performance issue comes from the fact that traversing a >> LinkedHahSet is slow because it's a linked list ? >> >> You can replace a LinkedHashSet by a List + Set, the List keeps the values in >> order, the Set avoids duplicates. >> >> Using a Stream, it becomes >>Stream.of(getItemsFromSomeplace(), getItemsFromAnotherPlace(), >>getItemsFromSomeplaceElse()) >> .flatMap(List::stream) >> .distinct() // use a Set internally >> .collect(toList()); > > The problem with any example is that simplifying assumptions are necessary for > showing the example, but those assumptions enable it to be easily picked > apart. > Of > course, the example isn't just a particular example; it is a *template* for a > whole > space of possible examples. Consider the possibility that the items processing > client needs to do some intermediate processing on the first group of items > before > adding the other groups. This might not be possible to do using streams. Use > your > imagination. > >> I think there are maybe some scenarios where ReversibleCollection can be >> useful, >> but they are rare, to the point where when there is a good scenario for it >> people will not recognize it because ReversibleCollection will not be part of >> their muscle memory. > > I'm certain that uses of RC/RS will be rare in the beginning, because they > will > be > new, and people won't be familar with them. And then there will the people who > say > "I can't use them because I'm stuck on JDK 11 / 8 / 7 / 6 " It was the > same > thing with lambdas and streams in Java 8, with List.of() etc in Java 9, > records > in > Java 16, etc. This wasn't an argument not to add them, and it isn't an > argument > not > to add RC/RS. All the changes you are listing here are "client side" changes, the ones that can be adopted quickly because they do not require to change the API side of any libraries. ReversibleCollection is an API side change, like generics is, those changes have a far higher cost because you have to wait your library dependencies to be updated. On the Valhalla list, we have discussed several times about how to alleviate those API side change cost using automatic bridging or methods forwarding, even for Valhalla, we are currently moving in a state where those mechanisms are not needed. > >> There is a real value to add methods like >> descendingSet/descendingList()/getFirst/getLast on existing collections, but >> we >> don't need a new interface (or two) for that. > > It depends on what you mean by "need". Sure, we could get away without this; > after > all, we've survived the past twenty years without it, so we could probably > survive > the next twenty years as well. > > It would indeed be useful to add various methods to List, Deque, SortedSet, > and > LinkedHashSet to provide a full set of methods on all of them. And it would > also > be > nice to have those methods be similar to one another. An interface helps with > that, > but I agree, that's not really the reason to have an interface though. > > The reversed-view concept could also be added individually to the different > places. > A reverse-ordered List is a List, a reverse-ordered Deque is a Deque, a > reverse-ordered SortedSet is a SortedSet, and a reverse-ordered LinkedHashSet > is > a > ... ? And what is the type of the keySet of a LinkedHashMap, that enables one > to > (say) get the last element? see below > > After working with a system like this for a while, it begins to emerge that > there is > an abstraction missing from the collections framework, something like an > "ordered > collection". People have been missing this for quite a long time. The most > recent > example (which this proposal builds on) is Tagir's proposal from a year ago. > And > it's been asked about several times before that. ReversibleCollection fills in > that > missing abstraction. The abstraction already exists but it's not defined in term of interface because it's an implementation decision and those are cleanly separated in the current Collection design. Let take a step back, the collection API defines basic data structure operations in term of interfaces like List, Deque, Set, etc those interfaces are decoupled from implementation capabilities like mutable, nullable, ordered
Re: [External] : Re: ReversibleCollection proposal
On 5/1/21 5:57 AM, fo...@univ-mlv.fr wrote: I suppose the performance issue comes from the fact that traversing a LinkedHahSet is slow because it's a linked list ? You can replace a LinkedHashSet by a List + Set, the List keeps the values in order, the Set avoids duplicates. Using a Stream, it becomes Stream.of(getItemsFromSomeplace(), getItemsFromAnotherPlace(), getItemsFromSomeplaceElse()) .flatMap(List::stream) .distinct() // use a Set internally .collect(toList()); The problem with any example is that simplifying assumptions are necessary for showing the example, but those assumptions enable it to be easily picked apart. Of course, the example isn't just a particular example; it is a *template* for a whole space of possible examples. Consider the possibility that the items processing client needs to do some intermediate processing on the first group of items before adding the other groups. This might not be possible to do using streams. Use your imagination. I think there are maybe some scenarios where ReversibleCollection can be useful, but they are rare, to the point where when there is a good scenario for it people will not recognize it because ReversibleCollection will not be part of their muscle memory. I'm certain that uses of RC/RS will be rare in the beginning, because they will be new, and people won't be familar with them. And then there will the people who say "I can't use them because I'm stuck on JDK 11 / 8 / 7 / 6 " It was the same thing with lambdas and streams in Java 8, with List.of() etc in Java 9, records in Java 16, etc. This wan't an argument not to add them, and it isn't an argument not to add RC/RS. There is a real value to add methods like descendingSet/descendingList()/getFirst/getLast on existing collections, but we don't need a new interface (or two) for that. It depends on what you mean by "need". Sure, we could get away without this; after all, we've survived the past twenty years without it, so we could probably survive the next twenty years as well. It would indeed be useful to add various methods to List, Deque, SortedSet, and LinkedHashSet to provide a full set of methods on all of them. And it would also be nice to have those methods be similar to one another. An interface helps with that, but I agree, that's not really the reason to have an interface though. The reversed-view concept could also be added individually to the different places. A reverse-ordered List is a List, a reverse-ordered Deque is a Deque, a reverse-ordered SortedSet is a SortedSet, and a reverse-ordered LinkedHashSet is a ... ? And what is the type of the keySet of a LinkedHashMap, that enables one to (say) get the last element? After working with a system like this for a while, it begins to emerge that there is an abstraction missing from the collections framework, something like an "ordered collection". People have been missing this for quite a long time. The most recent example (which this proposal builds on) is Tagir's proposal from a year ago. And it's been asked about several times before that. ReversibleCollection fills in that missing abstraction. s'marks
Re: [External] : Re: ReversibleCollection proposal
The line of discussion here was introduced by Remi, who was making an argument of the form "introducing a type cannot solve this particular problem, therefore, introducing a new type is not useful at all." I was providing an example of where the new type is useful as a method parameter. That's all. Have you considered the alternative of a collection providing a Reversed view of itself, in the same sense that unmodifiable collections are views of an underlying collection? The proposal does define ReversibleCollection::reversed as providing a reversed view, through which modifications to the underlying collection are visible, and to which modifications are written through to the underlying collection. Or are you talking about something different? s'marks On 4/30/21 4:15 PM, Alan Snyder wrote: It sounds like the items processing maintainer would be looking for OrderedCollection and might or might not find ReversibleCollection. :-) I suspect you would agree that OrderedCollection by itself is too weak to justify being a type. It’s basically Iterable with the extra bit that the iteration order is not an implementation artifact. In this example, using the type system to detect a bug like the old bug seems like overkill. Even if the parameter were Ordered, it still might not be the *right* order. The maintainer of the client code needs to understand that. Suppose the items processor wants to require that the parameter collection not contain duplicates. Would you suggest adding a type for that? Clearly Set would be just as unnecessarily restrictive as List was for ordering. Absurdity approaches… The issue of Reversible remains, above and beyond Ordered. Have you considered the alternative of a collection providing a Reversed view of itself, in the same sense that unmodifiable collections are views of an underlying collection? Alan On Apr 30, 2021, at 3:42 PM, Stuart Marks wrote: Consider the case of a large application or other system, one that's large enough to have lots of internal APIs, but that is built as a single unit, so release-to-release compatibility isn't an issue. Suppose there is some method processItemsInOrder(List items) that has to process items in the order in which they occur, because processing of later items might depend the processing of earlier ones. The maintainer of this API chose to accept a List as a parameter, because it's a common interface and it's clearly an ordered collection. Now consider a client that gets items from different places, keeping them in order, but removing duplicates. It might do something like this: var items = new LinkedHashSet(); items.addAll(getItemsFromSomeplace()); items.addAll(getItemsFromAnotherPlace()); items.addAll(getItemsFromSomeplaceElse()); processItemsInOrder(new ArrayList<>(items)); It turns out the copying of the items into an ArrayList is a performance bottleneck, so the maintainer of the client code asks the maintainer of the items processing code to change the API to accept Collection instead. The items processing maintainer demurs, recalling that the API *did* accept Collection in the past, and a bug where somebody accidentally passed a HashSet resulted in a customer escalation because of item processing irregularities. In the aftermath of that escalation, the API was changed to List. The client maintainer reluctantly pursues alternatives for generating a deduplicated List. But wait! Those Java guys added a ReversibleCollection interface in Java N. It has the desired property of being ordered, and conveniently it's a supertype of both List and LinkedHashSet. The items processing maintainer adjusts the API to consume ReversibleCollection, and the client maintainer removes the temporary ArrayList, and everybody is happy. s'marks
Re: [External] : Re: ReversibleCollection proposal
On 4/30/21 9:25 PM, Stuart Marks wrote:
So I think we're stuck with void-returning add{First,Last} methods.
Have you thought of perhaps not adding them at all?
Collection.add() for:
List(s) - behaves the same as addLast()
LinkedHashSet - behaves the same as addLast()
Deque - behaves the same as addLast()
So for all ReversibleCollection(s) where it works, addLast() would be
equivalent to add()
addFirst(x) can be written as: reversed().add(x) if reversed() is
specified to return a reversed view over the underlying
ReversibleCollection.
Peter
Re: [External] : Re: ReversibleCollection proposal
OK, I think we can wrap up this portion of the thread.
As the proposal stands, it has add{First,Last} returning void instead of some useful
value. For SortedSet and for LinkedHashMap's views, these throw UOE. Can we do better?
Collection has add(), Deque has add{First,Last} and offer{First,Last}, and
BlockingDeque has put{First,Last}. I'm loathe to add new insertion methods that
differ from these, either in signatures or semantics.
The BlockingDeque putX methods have blocking behavior, which only makes sense for a
concurrent collection. Still, because these exist, we mustn't add putX methods
elsewhere that have different semantics.
After having thought about this for a couple days, I think it's a really bad idea to
reuse offerX methods. These would allow a collection to refuse the addition of an
element and merely return a boolean indicating that. I can easily see people writing
offerX code that doesn't check the return value, and if things shift around in their
program, elements can be silently dropped. This would set a new precedent, as the
present behavior is that collections can reject adding an element only by throwing
an exception. Allowing refusal by returning 'false' would be a bad precedent.
So I think we're stuck with void-returning add{First,Last} methods.
Regarding throwing UOE, I think it's useful to distinguish between the LinkedHashMap
views and SortedSet. Today, it's already the case that Map's view collections don't
support addition, so the ReversibleX views of LinkedHashMap are similar in this regard.
SortedSet is different, as it's a top-level collection interface instead of a view
collection. It's unusual for it not to support the addX operations. We explored some
alternatives, such as throwing exceptions if preconditions aren't met. These seem
fairly rare, and the alternative behaviors don't seem all that useful. In any case
nothing emerged that was clearly better than simple UOE-throwing behavior.
OK, I think it's been useful to analyze various alternatives -- in particular I
hadn't seriously considered the offerX methods -- but I'll leave the proposal as it
stands regarding add{First,Last} methods.
s'marks
On 4/28/21 6:54 AM, Peter Levart wrote:
On 4/28/21 7:19 AM, Stuart Marks wrote:
On 4/27/21 9:17 AM, Anthony Vanelverdinghe wrote:
On Tuesday, April 27, 2021 11:25 CEST, Peter Levart
wrote:
Now just some of my thoughts about the proposal:
- SortedSet.addFirst/.addLast - I think an operation that would be used
in situations like: "I know this element should always be greater than
any existing element in the set and I will push it to the end which
should also verify my assumption" is a perfectly valid operation. So
those methods throwing IllegalStateException in case the invariant can't
be kept seem perfectly fine to me.
This was raised before and addressed by Stuart in [0]:
"An alternative as you suggest might be that SortedSet::addFirst/addLast could
throw
something like IllegalStateException if the element is wrongly positioned.
(Deque::addFirst/addLast will throw ISE if the addition would exceed a capacity
restriction.) This seems error-prone, though, and it's easier to understand and
specify that these methods simply throw UOE unconditionally. If there's a good
use
case for the alternative I'd be interested in hearing it though."
Yes, to be clear, it was Stephen Coleborne who raised this previously [1] and it's
my response that's quoted above.
Some further thoughts on this.
This is an example where, depending on the current state of the collection, the
method might throw or it might succeed. This is useful in concurrent collections
(such as the capacity-restricted Deque above), where the caller cannot check
preconditions beforehand, because they might be out of date by the time the
operation is attempted. In such cases the caller might not want to block, but
instead it might catch the exception and report an error to its caller (or drop
the request). Thus, calling the exception-throwing method is appropriate.
Something like SortedSet::addLast seems different, though. The state is the
*values* of the elements already in the collection. This is something that can
easily be checked, and probably should be checked beforehand:
if (sortedSet.isEmpty() || sortedSet.last().compareTo(e) <= 0)
sortedSet.add(e);
else
// e wouldn't be the last element, do something different
I was thinking more of a case where the else branch would actually throw
IllegalStateException and do nothing else - a kind of add with precondition check. A
precondition in the sense of Objects.requireNonNull(). I can't currently think of a
real usecase now, so this kind of operation is probably very rare. Probably not
useful since if you're adding to SortedSet, the order of elements added should not
matter because SortedSet will sort them. If you just want to check the order of
elements added and you are not willing
Re: [External] : Re: ReversibleCollection proposal
On 4/28/21 7:19 AM, Stuart Marks wrote: On 4/27/21 9:17 AM, Anthony Vanelverdinghe wrote: On Tuesday, April 27, 2021 11:25 CEST, Peter Levart wrote: Now just some of my thoughts about the proposal: - SortedSet.addFirst/.addLast - I think an operation that would be used in situations like: "I know this element should always be greater than any existing element in the set and I will push it to the end which should also verify my assumption" is a perfectly valid operation. So those methods throwing IllegalStateException in case the invariant can't be kept seem perfectly fine to me. This was raised before and addressed by Stuart in [0]: "An alternative as you suggest might be that SortedSet::addFirst/addLast could throw something like IllegalStateException if the element is wrongly positioned. (Deque::addFirst/addLast will throw ISE if the addition would exceed a capacity restriction.) This seems error-prone, though, and it's easier to understand and specify that these methods simply throw UOE unconditionally. If there's a good use case for the alternative I'd be interested in hearing it though." Yes, to be clear, it was Stephen Coleborne who raised this previously [1] and it's my response that's quoted above. Some further thoughts on this. This is an example where, depending on the current state of the collection, the method might throw or it might succeed. This is useful in concurrent collections (such as the capacity-restricted Deque above), where the caller cannot check preconditions beforehand, because they might be out of date by the time the operation is attempted. In such cases the caller might not want to block, but instead it might catch the exception and report an error to its caller (or drop the request). Thus, calling the exception-throwing method is appropriate. Something like SortedSet::addLast seems different, though. The state is the *values* of the elements already in the collection. This is something that can easily be checked, and probably should be checked beforehand: if (sortedSet.isEmpty() || sortedSet.last().compareTo(e) <= 0) sortedSet.add(e); else // e wouldn't be the last element, do something different I was thinking more of a case where the else branch would actually throw IllegalStateException and do nothing else - a kind of add with precondition check. A precondition in the sense of Objects.requireNonNull(). I can't currently think of a real usecase now, so this kind of operation is probably very rare. Probably not useful since if you're adding to SortedSet, the order of elements added should not matter because SortedSet will sort them. If you just want to check the order of elements added and you are not willing to pay the price of SortedSet, you will be adding them to a List or LinkedHashSet, but then the method would not do the check... Now this is a fair bit of code, and it would be shorter just to call sortedSet.addLast(e). But does that actually help? What if e is already in the set and is the last element? In that case the operation would be a no-op (or it would replace the element with the parameter - a slight difference as the element can be .equals() but not the same instance). Is catching an exception really what we want to do if e wouldn't be the last element? Maybe we'd want to do nothing instead. If so, catching an exception in order to do nothing is extra work. I was only thinking of situations where propagating the exception would be the desired thing. Again, I'd like to hear about use cases for a conditionally-throwing version of addLast et. al. I don't want to be limited by failure of imagination, but it does seem like this kind of behavior would be useful only in a narrow set of cases where it happens to do exactly the right thing. Otherwise, it just gets in the way, and its behavior is pretty obscure. So, color me skeptical. Right, I don't know how common such operation would be. Probably not very. Peter which are a continual source of errors.) I'll think about this more, but it doesn't seem promising. s'marks
Re: [External] : Re: ReversibleCollection proposal
Hi,
(I think the first version of this message never went through, so here it
goes just in case)
I just read quickly the proposal and it made me think about another common
issue. I wonder if we could tackle it as well.
I will call it the "find the first element when there is only one" problem.
It happens on unordered collections like a HashSet. It forces to do
Set s = new HashSet<>();
if (s.size() == 1) {
return s.iterator().next();
// or
return s.stream().findFirst().get();
}
Which is a lot of ugliness and object instantiations just to get the first
element.
I would be nice to have a public T findFirst() directly on Iterable.
With a default implementation returning iterator().next(). Things like
ArrayList will want to override will return elementData[0]. It would return
null when the list is empty. Or NoSuchElementException.
It needs to be polished of course but will that be acceptable?
Thanks,
Henri
Re: [External] : Re: ReversibleCollection proposal
On 4/27/21 9:17 AM, Anthony Vanelverdinghe wrote: On Tuesday, April 27, 2021 11:25 CEST, Peter Levart wrote: Now just some of my thoughts about the proposal: - SortedSet.addFirst/.addLast - I think an operation that would be used in situations like: "I know this element should always be greater than any existing element in the set and I will push it to the end which should also verify my assumption" is a perfectly valid operation. So those methods throwing IllegalStateException in case the invariant can't be kept seem perfectly fine to me. This was raised before and addressed by Stuart in [0]: "An alternative as you suggest might be that SortedSet::addFirst/addLast could throw something like IllegalStateException if the element is wrongly positioned. (Deque::addFirst/addLast will throw ISE if the addition would exceed a capacity restriction.) This seems error-prone, though, and it's easier to understand and specify that these methods simply throw UOE unconditionally. If there's a good use case for the alternative I'd be interested in hearing it though." Yes, to be clear, it was Stephen Coleborne who raised this previously [1] and it's my response that's quoted above. Some further thoughts on this. This is an example where, depending on the current state of the collection, the method might throw or it might succeed. This is useful in concurrent collections (such as the capacity-restricted Deque above), where the caller cannot check preconditions beforehand, because they might be out of date by the time the operation is attempted. In such cases the caller might not want to block, but instead it might catch the exception and report an error to its caller (or drop the request). Thus, calling the exception-throwing method is appropriate. Something like SortedSet::addLast seems different, though. The state is the *values* of the elements already in the collection. This is something that can easily be checked, and probably should be checked beforehand: if (sortedSet.isEmpty() || sortedSet.last().compareTo(e) <= 0) sortedSet.add(e); else // e wouldn't be the last element, do something different Now this is a fair bit of code, and it would be shorter just to call sortedSet.addLast(e). But does that actually help? What if e is already in the set and is the last element? Is catching an exception really what we want to do if e wouldn't be the last element? Maybe we'd want to do nothing instead. If so, catching an exception in order to do nothing is extra work. Again, I'd like to hear about use cases for a conditionally-throwing version of addLast et. al. I don't want to be limited by failure of imagination, but it does seem like this kind of behavior would be useful only in a narrow set of cases where it happens to do exactly the right thing. Otherwise, it just gets in the way, and its behavior is pretty obscure. So, color me skeptical. [0] https://mail.openjdk.java.net/pipermail/core-libs-dev/2021-April/076518.html [1] http://mail.openjdk.java.net/pipermail/core-libs-dev/2021-April/076505.html - ReversibleCollection.addFirst/.addLast are specified to have void return type. This works for List and Deque which always add element and so have no information to return. OTOH Collection.add is specified to return boolean to indicate whether collection was modified or not, but Set modifies the specification of that method a bit to be: return false or true when Set already contained an element equal to the parameter or not. So ReversibleCollection.addFirst/.addLast could play the same trick. for List(s) and Deque(s) it would always return true, but for ReversibleSet(s) it would return true only if the set didn't contain an element equal to the parameter, so re-positioning of equal element would return false although the collection was modified as a result. If addFirst/addLast were to return boolean, Deque would no longer compile due to its existing methods being incompatible with the new ones. Right, the current proposal copies the addX method signatures from Deque into ReversibleCollection. I think it was Mike Duigou who said that a method that returns void is a missed opportunity. The idea is, the library probably has some useful bit of information it can return. If the caller doesn't need it, the caller can just ignore it. On Collection::add returning a boolean, most calls to this ignore the return value, and the boolean "did this collection change as a result of this call?" is only occasionally useful. Sometimes it can be used for little tricks, such as an easy way to determine if a stream contains all unique elements: stream.allMatch(new HashSet<>()::add) But really, the boolean return value doesn't seem all that useful. Still, it could be added. The methods couldn't be called addFirst/addLast as Anthony pointed out, as this would clash with those methods already on Deque. However, Deque already contains boolean-returning
Re: [External] : Re: ReversibleCollection proposal
- Mail original -
> De: "Stuart Marks"
> À: "Remi Forax"
> Cc: "core-libs-dev"
> Envoyé: Mercredi 21 Avril 2021 20:53:25
> Objet: Re: [External] : Re: ReversibleCollection proposal
> On 4/19/21 2:01 PM, Remi Forax wrote:
>> - Mail original -
>> Thinking a little bit about your proposal,
>> introducing an interface right in the middle of a hierarchy is not a backward
>> compatible change
>> (you have an issue when the compiler has to use the lowest upper bound).
>>
>> By example
>>void m(List> list) { ... }
>>
>>var list = List.of(new LinkedHashSet(), List.of("foo"));
>>m(list); // does not compile anymore
>>
>> currently the type of list is List> but with your
>> proposal,
>> the type will be List>
>
> Yes, interesting. Not too difficult to fix though. Either change the method
> declaration to
>
> void m(List> list)
>
> or change the 'var' to an explicit declaration of List>.
or specify the type argument in between '.' and 'of'
var list = List.>of(new LinkedHashSet(),
List.of("foo"));
anyway, the issue here is that adding ReversibleCollection is a source breaking
change,
which significantly raises the bar to add this interface.
>
> s'marks
Rémi
Re: [External] : Re: ReversibleCollection proposal
On 4/19/21 2:01 PM, Remi Forax wrote:
- Mail original -
Thinking a little bit about your proposal,
introducing an interface right in the middle of a hierarchy is not a backward
compatible change
(you have an issue when the compiler has to use the lowest upper bound).
By example
void m(List> list) { ... }
var list = List.of(new LinkedHashSet(), List.of("foo"));
m(list); // does not compile anymore
currently the type of list is List> but with your proposal, the type
will be List>
Yes, interesting. Not too difficult to fix though. Either change the method
declaration to
void m(List> list)
or change the 'var' to an explicit declaration of List>.
s'marks
