Deque missing tail to head iterator.

classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

Deque missing tail to head iterator.

Jason Mehrens
Is the absence of "tail to head" iterator (Iterator<E> descendingIterator())
an intensional design decision?  I would think since the Deque has two ends
a user would be able to iterate from either end.   The most apparent case
for the "tail to head" iterator is the asLifoQueue class as it currently
iterates from "head to tail".
An RFE was filed against the Stack
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4475301 for this issue.  
Then again, that bug got zero votes so it must not be too important or maybe
that could be attributed to the number of Stack users.  Just kidding.

Jason Mehrens


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Deque missing tail to head iterator.

Joshua Bloch
Jason,

This was not an intentional design decision on my part  (I designed
this interface jointly with Doug).  Historically, Java collections
haven't had descending iterators.  List has the bidirectional
ListIterator, which is a bit too complex for my tastes (even if I did
design it).  SortedSet was missing this functionality till it was
augmented by NavigableSet.  I think it might well be reasonable to add
a descendingIterator method to Deque.  I wish you had come up with the
idea six months ago.  It would be a nightmare to try to sell this idea
to Sun now, especially because it affects all the subinterfaces and
implementations of Deque:(  On the other hand, interfaces are forever.
 If we don't do add the method now, we can't ever do it.  Let's see
what Doug thinks.

      Regards,

      Josh

On 9/7/05, Jason Mehrens <[hidden email]> wrote:

> Is the absence of "tail to head" iterator (Iterator<E> descendingIterator())
> an intensional design decision?  I would think since the Deque has two ends
> a user would be able to iterate from either end.   The most apparent case
> for the "tail to head" iterator is the asLifoQueue class as it currently
> iterates from "head to tail".
> An RFE was filed against the Stack
> http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4475301 for this issue.
> Then again, that bug got zero votes so it must not be too important or maybe
> that could be attributed to the number of Stack users.  Just kidding.
>
> Jason Mehrens
>
>
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
>

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Deque missing tail to head iterator.

Doug Lea
Joshua Bloch wrote:

> Jason,
>
> This was not an intentional design decision on my part  (I designed
> this interface jointly with Doug).  Historically, Java collections
> haven't had descending iterators.  List has the bidirectional
> ListIterator, which is a bit too complex for my tastes (even if I did
> design it).  SortedSet was missing this functionality till it was
> augmented by NavigableSet.  I think it might well be reasonable to add
> a descendingIterator method to Deque.  I wish you had come up with the
> idea six months ago.  It would be a nightmare to try to sell this idea
> to Sun now, especially because it affects all the subinterfaces and
> implementations of Deque:(  On the other hand, interfaces are forever.
>  If we don't do add the method now, we can't ever do it.  Let's see
> what Doug thinks.
>

I think:
   1. Josh and Jason are right -- we ought to support descendingIterator
   2. The timing is very inconvenient but I'll see what we can do.
   3. Thanks to all the people on this list for trying things out,
      reading our code, spotting problems, and telling us about
      them. It improves java.util.concurrent for the rest of the
      world. But if you want to be even more helpful, tell about
      things sooner rather than later :-)

-Doug

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Deque missing tail to head iterator.

Jason Mehrens
In reply to this post by Jason Mehrens
Josh,

Would getting votes for BUG 4475301 help sell the idea to sun or a new RFE?  
It looks like 82 votes are needed to get into the top 25 RFEs.  I would
think a few the concurrency interest members would have sun accounts for the
bug database so they could vote.

If the AsLifoQueue was modified to return the "tail-to-head" iterator,
should the toArray methods return the elements in "tail-to-head" order?  Is
descendingIterator the correct name as in implies the elements are ordered
(by a Comparator)?

Jason "public Iterator<E> rotareti()" Mehrens

>From: Joshua Bloch <[hidden email]>
>Reply-To: [hidden email]
>To: Jason Mehrens <[hidden email]>
>CC: [hidden email]
>Subject: Re: [concurrency-interest] Deque missing tail to head iterator.
>Date: Wed, 7 Sep 2005 23:01:27 -0700
>
>Jason,
>
>This was not an intentional design decision on my part  (I designed
>this interface jointly with Doug).  Historically, Java collections
>haven't had descending iterators.  List has the bidirectional
>ListIterator, which is a bit too complex for my tastes (even if I did
>design it).  SortedSet was missing this functionality till it was
>augmented by NavigableSet.  I think it might well be reasonable to add
>a descendingIterator method to Deque.  I wish you had come up with the
>idea six months ago.  It would be a nightmare to try to sell this idea
>to Sun now, especially because it affects all the subinterfaces and
>implementations of Deque:(  On the other hand, interfaces are forever.
>  If we don't do add the method now, we can't ever do it.  Let's see
>what Doug thinks.
>
>       Regards,
>
>       Josh
>
>On 9/7/05, Jason Mehrens <[hidden email]> wrote:
> > Is the absence of "tail to head" iterator (Iterator<E>
>descendingIterator())
> > an intensional design decision?  I would think since the Deque has two
>ends
> > a user would be able to iterate from either end.   The most apparent
>case
> > for the "tail to head" iterator is the asLifoQueue class as it currently
> > iterates from "head to tail".
> > An RFE was filed against the Stack
> > http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4475301 for this
>issue.
> > Then again, that bug got zero votes so it must not be too important or
>maybe
> > that could be attributed to the number of Stack users.  Just kidding.
> >
> > Jason Mehrens
> >
> >
> > _______________________________________________
> > Concurrency-interest mailing list
> > [hidden email]
> > http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
> >


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Deque missing tail to head iterator.

Joshua Bloch
Jason,

On 9/8/05, Jason Mehrens <[hidden email]> wrote:
> Josh,
>
> Would getting votes for BUG 4475301 help sell the idea to sun or a new RFE?
> It looks like 82 votes are needed to get into the top 25 RFEs.  I would
> think a few the concurrency interest members would have sun accounts for the
> bug database so they could vote.

It could, but I wouldn't mount a vote drive just yet.  Doug and I can
talk to our contacts at Sun and see where we stand.
>
> If the AsLifoQueue was modified to return the "tail-to-head" iterator,
> should the toArray methods return the elements in "tail-to-head" order?

Not sure I get this.  In fact, I'm a bit confused: the Bug parade says
there's a Collections.asLifoQueue(Queue) method, but the latest
Mustang snapshot shows no such method.  If there were such a method,
I'd imagine that it would do everything backward (iteration and
toArray).  The latest Mustang snapshot doesn't so a Deque interface
either, so I have no idea what's up.

>  Is descendingIterator the correct name as in implies the elements are ordered
> (by a Comparator)?

This is a good question.  On the one hand, it's the same name used by
Navigable set, which reduces the possibility that people will get it
wrong.  On the other hand it does sort of imply ordering based on
value.  Other possibilities include backwardIterator, reverseIterator,
and lastToFirstIterator.  I prefer lastToFirst to tailToHead, as the
other Deque method names contain "first" and "last" rather than "head"
and "tail."

       Regards,

       Josh

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Deque missing tail to head iterator.

Jason Mehrens
In reply to this post by Jason Mehrens
Josh,

>Not sure I get this.  In fact, I'm a bit confused: the Bug parade says
>there's a Collections.asLifoQueue(Queue) method, but the latest
>Mustang snapshot shows no such method.  If there were such a method,
>I'd imagine that it would do everything backward (iteration and
>toArray).  The latest Mustang snapshot doesn't so a Deque interface
>either, so I have no idea what's up.

I can see why you are confused, because my original question:

>>If the AsLifoQueue was modified to return the "tail-to-head" iterator,
>>should the toArray methods return the elements in "tail-to-head" order?

was based on a misunderstanding of the AsLifoQueue code from the CVS source
on this site.  The AsLifoQueue implementation on this site is correct and
works as expected (backward iteration and toArray).

Thanks for answering my questions,

Jason Mehrens


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Deque missing tail to head iterator.

Joshua Bloch
Jason,

Happy to help.  And I do hope we succeed in amending Deque as your suggested.

                      Josh

On 9/8/05, Jason Mehrens <[hidden email]> wrote:

> Josh,
>
> >Not sure I get this.  In fact, I'm a bit confused: the Bug parade says
> >there's a Collections.asLifoQueue(Queue) method, but the latest
> >Mustang snapshot shows no such method.  If there were such a method,
> >I'd imagine that it would do everything backward (iteration and
> >toArray).  The latest Mustang snapshot doesn't so a Deque interface
> >either, so I have no idea what's up.
>
> I can see why you are confused, because my original question:
>
> >>If the AsLifoQueue was modified to return the "tail-to-head" iterator,
> >>should the toArray methods return the elements in "tail-to-head" order?
>
> was based on a misunderstanding of the AsLifoQueue code from the CVS source
> on this site.  The AsLifoQueue implementation on this site is correct and
> works as expected (backward iteration and toArray).
>
> Thanks for answering my questions,
>
> Jason Mehrens
>
>
>

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest