Iterator filtrujący, czyli kontrakt iteratora w dwóch odsłonach

Dziś o tym, że kontrakt zawarty w dokumentacji można interpretować na wiele sposobów oraz dlaczego SRP jest istotne.

Na 4p padło pytanie, jak ogarnąć problem iteratora, który będzie przy okazji filtrował kolekcję. Sama implementacja jest stosunkowo prosta:

Listing 1. Iterator filrtujący

public class FilteringIterator<T> implements Iterator<Optional<T>> {

	private final Iterator<T> iter;

	private final Predicate<T> predicate;

	public FilteringIterator(Collection<T> collection, Predicate<T> predicate) {
		this.iter = collection.iterator();
		this.predicate = predicate;
	}

	@Override
	public boolean hasNext() {
		return iter.hasNext();
	}

	@Override
	public Optional<T> next() {
		T next = iter.next();
		return Optional.ofNullable(next).filter(predicate);
	}
}

Założenie jest następujące. Idziemy przez kolekcję i delegujemy zachowania iteratora do iteratora powiązanego z tą kolekcją. Przy czym metoda next pełni role adaptera, który zwraca Optional[T] zamiast T. jarekr000000, zwrócił mi jednak uwagę, że należało by logikę predykatu przenieść do metody hasNext. Tyle tylko, że w takim wypadku otrzymamy iterator, który będzie iteratorem until (limitującym). To znaczy, będzie zwracać jakąś wartość, dopóki warunek jest spełniony.

Listing 2. Iterator limitujący

public class UntilIterator<T> implements Iterator<T> {

	private final Iterator<T> iter;

	private final Predicate<T> predicate;
	private Optional<T> current;


	public UntilIterator(Collection<T> collection, Predicate<T> predicate) {
		this.iter = collection.iterator();
		this.predicate = predicate;
	}

	@Override
	public boolean hasNext() {
		boolean b = iter.hasNext();
		if (b) {
			current = Optional.ofNullable(iter.next())
					.filter(predicate);
			return current
					.map($ -> Boolean.TRUE) // element istnieje i spełnia warunek
					.orElse(false); // element nieistnieje albo niespełnia waruneku
		}
		return false;
	}

	@Override
	public T next() {
		return current.orElseThrow(NoSuchElementException::new);
	}
}

Implementacja jest oczywiście po łebkach i nie zapewnia prawidłowego działania w środowisku współbieżnym.

Na czym polega różnica?

Na początek rzućmy okiem na kontrakt metody hasNext:

Returns true if the iteration has more elements. (In other words, returns true if next() would return an element rather than throwing an exception.)

źródło

Pierwszy z iteratorów będzie zwracał coś, Optional albo Empty, dla każdego elementu w oryginalnej kolekcji. Oznacza to też, że metoda hasNext będzie zwracać true dopóki w oryginalnej kolekcji są jeszcze elementy. Oznacza to też, że jeżeli element nie spełnia warunków testu, to i tak metoda next nie powinna rzucać wyjątkiem.

Drugi z iteratrów zachowa się zupełnie inaczej. W tym przypadku, hasNext zwróci false dla pierwszego elementu niespełniającego warunku. Stanie się tak nawet wtedy, gdy oryginalna kolekcja będzie miała jeszcze elementy. Tym samym metoda next może rzucić wyjątek, nawet wtedy, gdy kolekcja nadal posiada elementy spełniające warunek.

Kolejna różnica, to wartość zwracana z metody next. Pierwszy z iteratorów opakuje ją w Optional. Drugi zwróci wartość taką jakiej oczekujemy iterując przez kolekcję obiektów o danym typie. Czy ta różnica ma znaczenie? Czasami ma, ponieważ dla pierwszego iteratora musimy wykonać operację „rozpakowania” wartości. W przypadku drugiego już nie. Dobrze obrazują to testy:

Listing 3. Test dla iteratora filtrujacego

public class FilteringIteratorTest {

	@Rule
	public ErrorCollector collector;

	private List<Integer> ints;

	@Before
	public void setUp() throws Exception {
		collector = new ErrorCollector();
		ints = asList(4, 3, 2, 1);
	}

	@Test
	public void filterOutSomeInts() throws Exception {
		FilteringIterator<Integer> it = new FilteringIterator<>(ints, i -> i % 2 == 0);

		// 4
		assertThat(it.hasNext()).isTrue();
		assertThat(it.next()).isPresent().contains(4);

		// 3
		assertThat(it.hasNext()).isTrue();
		assertThat(it.next()).isEmpty();

		// 2
		assertThat(it.hasNext()).isTrue();
		assertThat(it.next()).isPresent().contains(2);

		// 1
		assertThat(it.hasNext()).isTrue();
		assertThat(it.next()).isEmpty();

		// no more elements
		assertThat(it.hasNext()).isFalse();

		catchException(it).next();
		collector.checkThat(caughtException(), instanceOf(NoSuchElementException.class));

	}
}

Listing 4. Test dla iteratora limitującego

public class UntilIteratorTest {

	@Rule
	public ErrorCollector collector;

	private List<Integer> ints;

	@Before
	public void setUp() throws Exception {
		collector = new ErrorCollector();
		ints = asList(4, 3, 2, 1);
	}

	@Test
	public void filterUntilSomeInts() throws Exception {
		UntilIterator<Integer> it = new UntilIterator<>(ints, i -> i % 2 == 0);
		// 4
		Assert.assertTrue(it.hasNext());
		Assert.assertEquals(it.next().intValue(), 4);

		// 3 → false
		Assert.assertFalse(it.hasNext());
		catchException(it).next();
		collector.checkThat(caughtException(), instanceOf(NoSuchElementException.class));
	}

}

Wszystko ładnie pięknie, ale jest jeden problem.

SRP

Zasada pojedynczej odpowiedzialności jest całkiem fajna. Tyle tylko, że tu jest złamana. Jak? Nasze iteratory robią dwie rzeczy naraz. Po pierwsze poruszają się po kolekcji. Po drugie manipulują elementami kolekcji. W efekcie już na samym początku mamy problem. Autor pytania łamiąc SRP, wpędził się w kłopoty. Jarek i ja dyskutowaliśmy nad problemem, który w praktyce nie powinien istnieć.

Pozostaje jeszcze kwestia kontraktu metody hasNext. Jest on na tyle ogólny, że oba iteratory mogą w na swój sposób określić, jak go realizują. Ze szczególnym uwzględnieniem co oznacza „brak kolejnych elementów”.

2 myśli na temat “Iterator filtrujący, czyli kontrakt iteratora w dwóch odsłonach

  1. Tyle tylko, że w takim wypadku otrzymamy iterator, który będzie iteratorem until (limitującym). To znaczy, będzie zwracać jakąś wartość, dopóki warunek jest spełniony. Strasznie namnieszałeś – mnie chodzilo o prosty iterator, który na pewno nie ma takiego problemu jak piszesz see below

    class NormalIterator implements Iterator {
        private final Predicate predicate;
        private final Iterator originalIterator;
        private Optional element = Optional.empty();
    
        NormalIterator(Iterator originalIterator, Predicate predicate) {
            this.predicate = predicate;
            this.originalIterator = originalIterator;
        }
    
        @Override
        public boolean hasNext() {
            if (originalIterator.hasNext()) {
                final T elem = originalIterator.next();
                if (predicate.test(elem)) {
                    this.element = Optional.of(elem);
                    return true;
                } else {
                    return hasNext();
                }
            }
            return false;
        }
    
        @Override
        public T next() {
            return element.orElseThrow(() -> new NoSuchElementException("no next element"));
        }
    }    
    

    Pomijając brzydki kod i to, że się da zastąpić jedną liniką: stream().filter(…).iterator() to jest to całkiem dobry iterator – który myślę, że spełnia założenia podane przez ojca pytania….

Napisz odpowiedź

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax