ListIterator that supports remove() #110

gissuebot · 2014-10-31T17:04:47Z

Original issue created by jim.andreou on 2008-12-12 at 11:16 PM

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), 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

gissuebot · 2014-10-31T18:04:44Z

Original comment posted by jared.l.levy on 2008-12-13 at 12:10 AM

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.

gissuebot · 2014-10-31T18:04:46Z

Original comment posted by jim.andreou on 2008-12-13 at 12:56 AM

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).

gissuebot · 2014-10-31T18:13:14Z

Original comment posted by kevinb9n on 2009-09-17 at 05:57 PM