Java 8 Stream and maintaining index while performing reduction

Question

I have been crashing my head these days trying to figure out how can I use Java 8 stream API perform a reduction and at the same time maintain an index. Here is one example:

I have the following string:

String charSequence = "kjsfjsfajdsfjsaaaaaasssddfddddbbbdddaaa";

I would like as a result of a Stream operation to return a triplet (I, N, C)

Where:

• C is a character
• N is a number of occurrences - should be maximum
• I is the index of the first occurrence of the string (first if there are more than one)

Examples:

• "ddaaaacccjcccccjjj" returns (10, 5, c)
• "ddaaacccaaa" the first occurrence of "aaa" is 2 so the result would be: (2, 3, a)

Answer 1

I am trying to understand why maintaining index is difficult...

The purpose of Stream API is to perform operations through pipelines focused on the elements, not the indices. Indexing of every element requires a sequential processing of Stream which is in conflict with the point of parallel streaming which would have to synchronize to work with indices - and it kills the idea.

or why it can not be done if that is the case.

Yet, there is surprisingly still a way of iterating two or more sources (Collection, array...) at once using IntStream::range to iterate the index itself that is iterated:

IntStream.range(0, 10).map(i -> list.get(i) + array[i])...

... trying figure out how can I using Java 8 Stream API perform a reduction and at the same time maintain an index

... but neither the solution above nor any other care the previous n elements. The processed element should be independent of the others.

Forget the Stream API in this case. Go back to traditional and procedural for-loop. You can get a result with a single loop.

Answer 2

Don't think that streams are very helpful here. Here is a solution using regex and a List of of results:

    Pattern p = Pattern.compile("(\\w)\\1+");
    Matcher m = p.matcher(charSequence);

    List<Triple> list = new ArrayList<>();

    while (m.find()) {
        int start = m.start();
        int end = m.end();
        int diff = end - start;

        if (list.isEmpty()) {
            list.add(new Triple(m.group(0).charAt(0), diff, start));
        } else if (list.get(list.size() - 1).getN() == diff) {
            list.add(new Triple(m.group(0).charAt(0), diff, start));
        } else if (diff > list.get(list.size() - 1).getN()) {
            list.clear();
            list.add(new Triple(m.group(0).charAt(0), diff, start));
        }
    }

And a Triple:

   static class Triple {
    private final Character c;

    private final long n;

    private final int i;

    public Triple(Character c, long n, int i) {
        this.c = c;
        this.n = n;
        this.i = i;
    }

    // getters

} 

I have a solution like this for example:

 List<Triple> result = p.matcher(charSequence).results()
            .collect(
                    Collector.of(
                            ArrayList::new,
                            (l, mr) -> {
                                int diff = mr.end() - mr.start();

                                if (!l.isEmpty() && l.get(l.size() - 1).getN() < diff) {
                                    l.clear();
                                }

                                if (l.isEmpty() || l.get(l.size() - 1).getN() == diff) {
                                    l.add(new Triple(mr.group(0).charAt(0), diff, mr.start()));
                                }

                            },
                            (left, right) -> {
                                throw new UnsupportedOperationException("Not for parallel");
                            }));

Answer 3

It could be like this:

I wrote in several step.

result1 : the first step splits repeated character then grouping it by first char.

example for char c:

{'c',["ccc","ccccc"]}

Map<Character,List<String>> result1 =  Stream.of(charSequence.split("(?<=(.))(?!\\1)"))
            .collect(Collectors.groupingBy(s->s.charAt(0)));

result2 : in this step the result is list of string with max length of previous result. as you see we had ["ccc","ccccc"], so here we just use ccccc sequence.

  List<String> result2 =   result1.entrySet()
            .stream()
            .map(entry->entry.getValue()
                .stream().max(Comparator.comparingInt(String::length)).get())
            .collect(Collectors.toList());

result: final step is your expected result.

 List<Triple> result =  result2
          .stream()
          .map(str1->new Triple(str1.charAt(0),str1.length(),charSequence.indexOf(str1)))
          .collect(Collectors.toList());

---

 Stream.of(charSequence.split("(?<=(.))(?!\\1)"))
        .collect(groupingBy(s -> s.charAt(0), 
            collectingAndThen(maxBy(comparingInt(String::length)), Optional::get)))
        .entrySet().stream()
        .map(m1 -> new Triple(m1.getKey(), m1.getValue().length(), charSequence.indexOf(m1.getValue())))
        .collect(Collectors.toList());

Answer 4

Think different and look outside. Here is one of the alternative solutions by StreamEx, and you may not accept it by your declaration:

String str = "ddaaaacccjcccccjjj";

IntStreamEx.range(0, str.length()).boxed() 
    .collapse((i, j) -> str.charAt(i) == str.charAt(j), Collectors.toList()) 
    .maxBy(l -> l.size()) 
    .map(l -> Triple.of(l.get(0), l.size(), str.charAt(l.get(0))))
    .ifPresent(System.out::println);

// output: [10, 5, c]

And to get all:

String str = "ddaaacccaaa";

IntStreamEx.range(0, str.length()).boxed() 
    .collapse((i, j) -> str.charAt(i) == str.charAt(j), Collectors.toList()) 
    .collect(MoreCollectors.maxAll(Comparators.comparingBy(l -> l.size()))) 
    .stream().map(l -> Triple.of(l.get(0), l.size(), str.charAt(l.get(0))))
    .forEach(System.out::println);

// output
// [2, 3, a]
// [5, 3, c]
// [8, 3, a]

To distinct the result by character:

Collector<List<Integer>, ?, StreamEx<List<Integer>>> collector = Collectors.collectingAndThen(
    MoreCollectors.maxAll(Comparators.comparingBy(l -> l.size())), StreamEx::of);

IntStreamEx.range(0, str.length()).boxed() 
    .collapse((i, j) -> str.charAt(i) == str.charAt(j), Collectors.toList()) 
    .collect(collector) 
    .distinct(l -> str.charAt(l.get(0))) 
    .map(l -> Triple.of(l.get(0), l.size(), str.charAt(l.get(0)))) 
    .forEach(System.out::println);

// output
// [2, 3, a]
// [5, 3, c]

Update: Is it good enough? actually no, because it creates unnecessary temporary List. I think there is a better solution by intervalMap.

IntStreamEx.range(0, str.length()).boxed()
    .intervalMap((i, j) -> str.charAt(i) == str.charAt(j), Pair::of)
    .maxBy(p -> p.right - p.left)
    .map(p -> Triple.of(p.left, p.right - p.left + 1, str.charAt(p.left)))
    .ifPresent(System.out::println);