不使用 size() 方法的 LinkedList Spliterator

Question

给定一个 LinkedList，我想通过 Spliterator 拆分它。我不能使用方法 size()。我必须在以下条件下实现 trySplit() 方法：如果 Spliterator 至少有 5 个元素，return new Spliterator，它将通过前 4 个元素；否则 return null。我不知道如何用以下条件拆分它。现在我只能得到一批元素。我怎样才能得到所有批次？我在这个任务上苦苦挣扎了 5 个多小时，但没有运气。提前致谢！

https://docs.oracle.com/javase/8/docs/api/java/util/Spliterator.html 提供了当 size() 为 known/allowed 时如何使用 Spliterator 的信息。

接口：

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;
    }
  }
}

主要方法：

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);
}

预期输出：

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

实际输出：

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

now parallel

6
7
8
9
10

Answer 1

终于解决了这个问题。解决方案的要点是 trySplit() 方法实施错误。首先，我必须检查 LL 中的前五个元素是否存在。然后我创建一个新的 LL<>(); 并用给定列表中的前四个元素填充它。然后我正在更改头部 hd = tl.tl.tl.tl.hd; 和尾部 tl = tl.tl.tl.tl.tl; 的引用。之后我返回一个 new MySplitter(temp.hd, temp.tl); 对象。固定工作 LL class 如下：

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;
    }
  }
}

输出为：

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

不使用 size() 方法的 LinkedList Spliterator

LinkedList Spliterator without using size() method

java

parallel-processing

java-stream

spliterator