Picking elements of a list until condition is met

Question

I am trying to switch my mind to think the functional way and recently faced a situation in which I needed to pick up elements from a list until a condition is met and I could not find an easy natural way of achieving this. Obviously I am still learning.

Say I have this list:

List<String> tokens = Arrays.asList("pick me", "Pick me", "pick Me",
    "PICK ME", "pick me and STOP", "pick me", "pick me and Stop", "pick me");

// In a non lambdas was you would do it like below
List<String> myTokens = new ArrayList<>();
for (String token : tokens) {
    myTokens.add(token);
    if (token.toUpperCase().endsWith("STOP")) {
        break;
    }
}

Thank you in advance for your inputs

NOTE: Before publishing this I read Limit a stream by a predicate but I could not see how I can adapt that answer to my problem. Any help would be appreciated thanks.

Answer 1

Using strictly just Java 8 API:

public static <R> Stream<? extends R> takeUntil(Iterator<R> iterator, Predicate<? super R> stopFilter) {

    return StreamSupport.stream(Spliterators.spliteratorUnknownSize(new Iterator<R>() {
        private R next = null;
        private boolean hasTaken = true;
        private boolean stopIteration = !iterator.hasNext();
        @Override
        public boolean hasNext() {
            if (stopIteration) {
                return false;
            }

            if (!hasTaken) {
                return true;
            }

            if (!iterator.hasNext()) {
                stopIteration = true;
                return false;
            }

            next = iterator.next();
            stopIteration = stopFilter.test(next);
            hasTaken = stopIteration;
            return !stopIteration;
        }

        @Override
        public R next() {
            if (!hasNext()) {
                throw new NoSuchElementException("There are no more items to consume");
            }
            hasTaken = true;
            return next;
        }
    }, 0), false);
}

You can then specialize it in the following ways:

For streams

public static <R> Stream<? extends R> takeUntil(Stream<R> stream, Predicate<? super R> stopFilter) {
    return takeUntil(stream.iterator(), stopFilter);
}

For collections

public static <R> Stream<? extends R> takeUntil(Collection<R> col, Predicate<? super R> stopFilter) {
    return takeUntil(col.iterator(), stopFilter);
}

Answer 2

In JDK9 there will be a new Stream operation called takeWhile which does the thing similar to what you need. I backported this operation to my StreamEx library, so you can use it even in Java-8:

List<String> list = StreamEx.of(tokens)
                            .takeWhile(t -> !t.toUpperCase().endsWith("STOP"))
                            .toList();

Unfortunately it does not take the "STOP" element itself, so the second pass is necessary to add it manually:

list.add(StreamEx.of(tokens).findFirst(t -> t.toUpperCase().endsWith("STOP")).get());

Note that both takeWhile and findFirst are short-circuit operations (they will not process the whole input stream if unnecessary), so you can use them with very long or even infinite streams.

However using StreamEx you can solve it in single pass using the trick with groupRuns. The groupRuns method groups adjacent Stream elements to the List based on the supplied predicate which tells whether two given adjacent elements should be grouped or not. We may consider that the group ends with the element containing "STOP". Then we just need to take the first group:

List<String> list = StreamEx.of(tokens)
                            .groupRuns((a, b) -> !a.toUpperCase().endsWith("STOP"))
                            .findFirst().get();

This solution also will not do extra work when the first group is finished.

Answer 3

Althought the above answers are perfectly valid, they require to collect and/or pre-fetch the elements before processing them (both can be an issue if the Stream is very long).

For my needs, I therefore adapted Louis's answer to the question pointed out by Julian and adapted it to keep the stop/break item. See the keepBreak parameter ::

public static <T> Spliterator<T> takeWhile(final Spliterator<T> splitr, final Predicate<? super T> predicate, final boolean keepBreak) {
    return new Spliterators.AbstractSpliterator<T>(splitr.estimateSize(), 0) {
        boolean stillGoing = true;

        @Override
        public boolean tryAdvance(final Consumer<? super T> consumer) {
            if (stillGoing) {
                final boolean hadNext = splitr.tryAdvance(elem -> {
                    if (predicate.test(elem)) {
                        consumer.accept(elem);
                    } else {
                        if (keepBreak) {
                            consumer.accept(elem);
                        }
                        stillGoing = false;
                    }
                });
                return hadNext && (stillGoing || keepBreak);
            }
            return false;
        }
    };
}

public static <T> Stream<T> takeWhile(final Stream<T> stream, final Predicate<? super T> predicate, final boolean keepBreak) {
    return StreamSupport.stream(takeWhile(stream.spliterator(), predicate, keepBreak), false);
}

Usage:

public List<String> values = Arrays.asList("some", "words", "before", "BREAK", "AFTER");

    @Test
    public void testStopAfter() {
        Stream<String> stream = values.stream();
        //how to filter stream to stop at the first BREAK
        stream = stream.filter(makeUntil(s -> "BREAK".equals(s)));
        final List<String> actual = stream.collect(Collectors.toList());

        final List<String> expected = Arrays.asList("some", "words", "before", "BREAK");
        assertEquals(expected, actual);
    }

Disclaimer: I am not 100% sure this will work on parallel (the new Stream is certainly not parallel) or non-sequential streams. Please comment/edit if you have some hints on this.

Answer 4

If you really must use Streams API, keep it simple and use a stream of indexes:

int lastIdx = IntStream.range(0, tokens.size())
        .filter(i -> tokens.get(i).toUpperCase().endsWith("STOP"))
        .findFirst()
        .orElse(-1);

List<String> myTokens = tokens.subList(0, lastIdx + 1);

Or make a new List out of the sublist if you want an independent copy that's not backed by the original list.

Answer 5

One option uses a collector requiring two functions one that adds strings to lists and another which combines lists previously potentially created in parallel. For each it adds the string or the whole list only if the previous partial output doesn't end with an element that that ends with STOP:

tokens.stream().collect(() -> new ArrayList<String>(), (l, e) -> {
    if(l.isEmpty() || !l.get(l.size()-1).toUpperCase().endsWith("STOP"))
        l.add(e);
}, (l1, l2) -> {
    if(l1.isEmpty() || !l1.get(l1.size()-1).toUpperCase().endsWith("STOP"))
        l1.addAll(l2);
});