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]

This issue has been moved to the Guava project (keeping the same id number). 
Simply replace 'google-collections' with 'guava-libraries' in your address 
bar and it should take you there.

Original comment by kevinb@google.com on 5 Jan 2010 at 11:09

• Changed state: Moved

[GoogleCodeExporter]

Let me to present my use case which would require this functionality:

Setup:
We use db4o as our persistence provider.  Db4o provides us with ObjectSet's of 
objects when we query for 
them.  They are in fact an implementation of the List interface which lazily 
instantiates objects as they are 
required by the application.

Problem:
We want two things:
1. A high-performance pagable web component that should allow users to page 
through possibly massive 
data-sets.
2. The data for this component does come from the database, but only the 
objects that the current web user 
has permission to access should be visible.

This makes guava's Iterators#filter look very interesting.  Only; the fact that 
it only works for Iterators and not 
for ListIterators is a major bummer.  Now, whenever the user pages back instead 
of forward, we have to 
request a new iterator from the database and skip ahead to the correct location 
again.  That sucks.

If guava had a filter method that accepted ListIterators (which seems trivial), 
that would be ideal for this case.

Original comment by lhunath on 6 Jun 2010 at 8:07

[GoogleCodeExporter]

So, it's 2014 now.  How about we make up our mind about this?  Seems too 
trivial to let rot in the issue tracker.

Original comment by lhunath@lyndir.com on 1 Feb 2014 at 4:33