ListIterator that supports remove()

[GoogleCodeExporter]

Hi,

Some days ago I exchanged some emails on the list regarding the possibility
of a ListIterator that supported remove(). I contribute such an
implementation, which skips filtered elements bidirectionally to support
hasNext()/next() and hasPrevious()/previous().

It would be neat to have in Iterators a signature of the form:
ListIterator<E> filtered(ListIterator<E> listIterator, Predicate<? super E>
filter);

Thus an API can provide filtered ListIterators to internal structures
without having to clumsily work around the difficult-to-support remove()
issue. I believe the cost of a single iteration with removals does not, in
the worst case, cost more than O(3n), which should be optimal. In any case,
this is intended to fill a functional gap.

I'm also quite confident about its robustness. I tested it to filter a
ArrayList's ListIterator, for more than half million random actions
(comprising all methods defined by ListIterator), side-by-side with a
ListIterator of ArrayList which only contains accepted elements, and
verified that they both behave identically (i.e. one can't tell whether the
list is filtered or is just contains only the correct elements). I also
submit my (unpolished) test code for verification.

Note that ListIterator#add(E e) is curiously defined in a filtered iterator.

For example, in this list:
[A1, R2, R3, R4, A5]
(where A1, A5 are "accepted" elements, and R2, R3, R4 are "rejected"), and
a filtered iterator being between A1 and A5 (the client won't see R2-R4),
an add() operation surely does insert an element between A1 and A5 as
defined by the contract, but the exact place in the underlying list is not
specified. (In this implementation it will be either immediately before A5,
or immediately after A1) 

Comments?
Thanks,
Dimitris

Original issue reported on code.google.com by jim.andreou on 12 Dec 2008 at 11:16

Attachments:

• Iterators2.java
• FilteringListIteratorTest.java

[GoogleCodeExporter]

Thanks for the contribution!

When considering new functionality, my first question is how helpful it would 
be.
Since I haven't seen much code that uses ListIterators, it's not clear that 
there
would be much demand for a filtered ListIterator. That makes me reluctant to 
add this
code to the Google Collections library.

Original comment by jared.l....@gmail.com on 13 Dec 2008 at 12:10

[GoogleCodeExporter]

I take for granted that: a) ListIterators per se are useful (Bloch would agree 
I 
guess :)), b) filtering views are useful - you already provide filtered views 
for 
Iterable and Iterator among others. For me it makes perfect sense to also 
support the 
remaining interface as well. It's a gap.

And besides, the api cost is so minimal (merely an overloading of an existing 
method 
that targets ListIterator instead of Iterator) that I don't understand what 
worries 
you.

(Even that is not *really* required, in the case that even this cost is deemed 
as 
high to pay: make the existing Iterators#filtered method do an "unfiltered 
instanceof 
ListIterator" test and return appropriately... wouldn't hurt anyone).

Original comment by jim.andreou on 13 Dec 2008 at 12:56

[GoogleCodeExporter]

Original comment by kevin...@gmail.com on 17 Sep 2009 at 5:57

• Added labels: Type-Enhancement

[GoogleCodeExporter]

Original comment by kevin...@gmail.com on 17 Sep 2009 at 6:02

• Added labels: Milestone-Post1.0

[GoogleCodeExporter]

Original comment by kevinb@google.com on 30 Jul 2010 at 3:53

• Removed labels: Milestone-Post1.0

[GoogleCodeExporter]

Original comment by fry@google.com on 26 Jan 2011 at 10:41

• Changed state: Accepted

[GoogleCodeExporter]

Original comment by kevinb@google.com on 13 Jul 2011 at 6:18

• Changed state: Triaged

[GoogleCodeExporter]

Original comment by fry@google.com on 10 Dec 2011 at 3:34

• Added labels: Package-Collect

[GoogleCodeExporter]

Original comment by fry@google.com on 16 Feb 2012 at 7:17

• Changed state: Acknowledged

[GoogleCodeExporter]

Lists.filter is in the Idea Graveyard, no?  Why would we provide this, then?

Original comment by wasserman.louis on 16 May 2012 at 2:12

[GoogleCodeExporter]

Sure, this can be closed, and save some maintenance (e.g. updating all these 
tags over the years!)

Original comment by jim.andreou on 16 May 2012 at 3:21

• Changed state: WontFix

[GoogleCodeExporter]

Graveyard says: "The biggest concern here is that too many operations become 
expensive, linear-time propositions."

I think that this meant things like List.get.  I suppose that it's technically 
true here, too, in the case of ListIterator.remove, but the same was true of 
Iterables.filter's hasNext/next calls, and that didn't stop us from providing 
that.

Still, given that Dimitris is fine with closing this, I'm fine with it.

Original comment by cpov...@google.com on 16 May 2012 at 4:09

[GoogleCodeExporter]

This issue has been migrated to GitHub.

It can be found at https://github.com/google/guava/issues/<id>

Original comment by cgdecker@google.com on 1 Nov 2014 at 4:16

• Added labels: MigratedToGitHub

[GoogleCodeExporter]

Original comment by cgdecker@google.com on 3 Nov 2014 at 9:10

• Added labels: Restrict-AddIssueComment-Commit