javaparallel-processingjava-streamspliterator

LinkedList Spliterator without using size() method


Given a LinkedList, which I want to split via Spliterator. I cannot use method size(). I have to implement trySplit() method with following condition: if Spliterator has at least 5 elements, return new Spliterator, which will go through first 4 elements; else return null. I don't get how to split it with following condition. Now I can get only one batch of elements. how can I get all batches? I'm struggling with this task more than 5 hours with no luck. Thank you in advance!

https://docs.oracle.com/javase/8/docs/api/java/util/Spliterator.html provides information how to use Spliterator, when the size() is known/allowed.

Interface:

import java.util.Spliterator;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;

public interface Li<A> {
  Spliterator<A> getSpliterator();

  default Stream<A> stream() {
    return StreamSupport.stream(getSpliterator(), false);
  }

  default Stream<A> parallelStream() {
    return StreamSupport.stream(getSpliterator(), true);
  }
}

Class:

import java.util.Spliterator;
import java.util.function.Consumer;

public class LL<A> implements Li<A>{
  private A hd;
  private LL<A> tl;

  public boolean isEmpty(){
    return hd == null && tl == null;
  }

  public void add(A a){
    if (isEmpty()){
      tl = new LL<>();
      hd = a;
    }else{
      tl.add(a);
    }
  }

  public LL(A hd, LL<A> tl){
    this.hd = hd;
    this.tl = tl;
  }

  public LL() {
    this(null, null);
  }

  public A get(int i) {
    return i==0 ? hd : tl.get(i-1);
  }

  @Override
  public Spliterator<A> getSpliterator(){
    return new MySplitter(0, Integer.MAX_VALUE,this);
  }

  private class MySplitter implements Spliterator<A>{
    private LL<A> ll;
    int start;
    int end;

    MySplitter(int start, int end, LL<A> ll){
      this.ll = ll;
      this.start = start;
      this.end = end;
    }

    public A get(int i){
      return i==0 ? hd : tl.get(i-1);
    }

    @Override
    public boolean tryAdvance(Consumer<? super A> action){
      if (this.get(start) != null && start < end) {
        action.accept(ll.get(start++));
        return true;
      }else {
        return false;
      }
    }

    @Override
    public Spliterator<A> trySplit(){
      try {
        ll.get(start + 5);
        end = start + 5;
      }catch (Exception e){
        return null;
      }
      start = end;
      end += 5;
      return new MySplitter(start, start + 4, ll).trySplit();
    }

    @Override
    public long estimateSize(){
      return Long.MAX_VALUE;
    }

    @Override
    public int characteristics(){
      return ORDERED | SUBSIZED;
    }
  }
}

Main method:

public static void main (String[] args){
  LL<String> l = new LL();
  l.add("1");
  l.add("2");
  l.add("3");
  l.add("4");
  l.add("5");
  l.add("6");
  l.add("7");
  l.add("8");
  l.add("9");
  l.add("10");
  l.add("11");
  l.add("12");
  l.add("13");

  l.stream().forEach(System.out::println);
  System.out.println();
  System.out.println("now parallel");
  System.out.println();
  l.parallelStream().forEach(System.out::println);
}

Expected output:

1
2
3
4
5
6
7
8
9
10
11
12
13

now parallel

5
6
7
8
1
2
3
4
13
9
10
11
12

Actual output:

1
2
3
4
5
6
7
8
9
10
11
12
13

now parallel

6
7
8
9
10

Solution

  • Finally I have solved this problem. The main point on the way to the solution is the thing, that trySplit() method was wrong implemented. Firstly I have to check if the first five elements in LL are present. Then I am creating a new LL<>(); and populate it with the first four elements from given list. Then I am changing the reference of the head hd = tl.tl.tl.tl.hd; and tail tl = tl.tl.tl.tl.tl;. After that I am returning a new MySplitter(temp.hd, temp.tl); object. The fixed working LL class is below:

    public class LL<A> implements Li<A>{
      private A hd;
      private LL<A> tl;
    
      private boolean isEmpty(){
        return hd == null && tl == null;
      }
    
      public void add(A a){
        if (isEmpty()){
          tl = new LL<>();
          hd = a;
        }else{
          tl.add(a);
        }
      }
    
      private LL(A hd, LL<A> tl){
        this.hd = hd;
        this.tl = tl;
      }
    
      private LL() {
        this(null, null);
      }
    
      @Override
      public Spliterator<A> getSpliterator(){
        return new MySplitter(hd, tl);
      }
    
      public static void main (String[] args) {
        LL<String> l = new LL();
        l.add("1");
        l.add("2");
        l.add("3");
        l.add("4");
        l.add("5");
        l.add("6");
        l.add("7");
        l.add("8");
        l.add("9");
        l.add("10");
        l.add("11");
        l.add("12");
        l.add("13");
    
        l.stream().forEach(System.out::println);
        System.out.println();
        System.out.println("now parallel");
        System.out.println();
        l.parallelStream().forEach(System.out::println);
      }
    
      private class MySplitter implements Spliterator<A> {
        private LL<A> tl;
        private A hd;
    
        MySplitter(A hd, LL<A> tl){
          this.tl = tl;
          this.hd = hd;
        }
    
        @Override
        public boolean tryAdvance(Consumer<? super A> action){
          if (hd != null) {
            action.accept(hd);
            hd = tl.hd;
            tl = tl.tl;
            return true;
          }else {
            return false;
          }
        }
    
        @Override
        public Spliterator<A> trySplit(){
          if(hd != null && tl.hd != null && tl.tl.hd != null && tl.tl.tl.hd != null
              && tl.tl.tl.tl.hd != null && tl.tl.tl.tl.tl.hd != null){
            LL<A> temp = new LL<>();
            temp.add(hd);
            temp.add(tl.hd);
            temp.add(tl.tl.hd);
            temp.add(tl.tl.tl.hd);
            hd = tl.tl.tl.tl.hd;
            tl = tl.tl.tl.tl.tl;
            return new MySplitter(temp.hd, temp.tl);
          }
          return null;
        }
    
        @Override
        public long estimateSize(){
          return Long.MAX_VALUE;
        }
    
        @Override
        public int characteristics(){
          return ORDERED;
        }
      }
    }
    

    Output is:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    
    now parallel
    
    5
    6
    7
    8
    9
    10
    11
    12
    13
    1
    2
    3
    4