Spliterator LinkedList без использования метода size () - PullRequest
Новая
       18

Spliterator LinkedList без использования метода size ()

0 голосов
/ 29 апреля 2018

Учитывая LinkedList, который я хочу разделить с помощью Spliterator. Я не могу использовать метод size(). Я должен реализовать метод trySplit() со следующим условием: если Spliterator имеет хотя бы 5 элементов, верните new Spliterator, который пройдет через первые 4 элемента; остальное return null. Я не понимаю, как разделить это с следующим условием. Теперь я могу получить только одну партию элементов. как я могу получить все партии? Я борюсь с этой задачей более 5 часов без удачи. Заранее спасибо!

https://docs.oracle.com/javase/8/docs/api/java/util/Spliterator.html предоставляет информацию о том, как использовать Spliterator, когда size() известен / разрешен.

Интерфейс: 

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

Класс: 

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

1 Ответ

0 голосов
/ 03 мая 2018

Наконец-то я решил эту проблему. Основным моментом на пути к решению является то, что метод trySplit() был неправильно реализован. Во-первых, я должен проверить, присутствуют ли первые пять элементов в LL. Затем я создаю новый LL<>(); и заполняю его первыми четырьмя элементами из данного списка. Затем я меняю референс головы hd = tl.tl.tl.tl.hd; и хвоста tl = tl.tl.tl.tl.tl;. После этого я возвращаю объект new MySplitter(temp.hd, temp.tl);. Фиксированный рабочий класс LL ниже: 

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
...