为算术级数制作一个惰性迭代器？

Question

下面是我编写的一个类，它为算术级数实现了 Iterable（从 start 到 stop，步骤为 step code>)

package com.example.test;

import java.util.Iterator;
import com.google.common.collect.AbstractIterator;

public class ArithmeticSeries implements Iterable<Integer>
{
    final private int start, step, stop;
    public int getStart() { return this.start; } 
    public int getStep() { return this.step; } 
    public int getStop() { return this.stop; }

    public ArithmeticSeries(int start, int step, int stop)
    {
        this.start = start;
        this.step = step;
        this.stop = stop;
    }
    @Override public Iterator<Integer> iterator()
    {
        return new AbstractIterator<Integer>() {
            private Integer n = null;
            @Override protected Integer computeNext() {
                int next;
                if (this.n == null)
                {
                    next = getStart(); 
                }
                else
                {
                    next = this.n + getStep();
                    if ((getStep() > 0 && next > getStop()) 
                     || (getStep() < 0 && next < getStop()))
                        return endOfData();
                }
                this.n = next;
                return next;
            }
        };
    }
    @Override public String toString() {
        return getStart()+":"+getStep()+":"+getStop();
    }

    public static void main(String[] args) {
        Iterable<Integer> range = new ArithmeticSeries(100,-1,80);
        System.out.println(range);
        for (int i : range)
            System.out.println(i);
    }
}

有没有一种更优雅的实现 iterator() 的方法？我不喜欢空检查和使用Integer（替代方案是一个额外的标志boolean firstTime），这似乎是错误的。

Answer 1

return new AbstractIterator<Integer>() {
  int next = getStart();

  @Override protected Integer computeNext() {
    if (isBeyondEnd(next)) {
      return endOfData();
    }
    Integer result = next;
    next = next + getStep();
    return result;
  }
};

如果您愿意，您可以将其实现为不可变的 List。如果您扩展 AbstractList 那么 Iterator 将会为您处理。实际上，我认为 AbstractList 确实是最好的方法。整个类看起来像这样（我没有检查它是否在所有情况下都能正常工作）：

public class ArithmeticSeries extends AbstractList<Integer> {
  private final int start;
  private final int step;
  private final int size;

  public ArithmeticSeries(int start, int end, int step) {
    this.start = start;
    this.step = (start < end) ? step : -step;
    this.size = (end - start) / this.step + 1;
  }

  @Override public Integer get(int index) {
    return start + step * index;
  }

  @Override public int size() {
    return size;
  }
}

Answer 2

您可以使用函数来抽象连续值，并使用谓词来控制迭代的结束，最终创建一个 Unfold 实现：

public final class UnfoldIterator<E> implements Iterator<E> {
    public static <E> Iterator<E> unfold(E initial, Function<? super E, ? extends E> next, Predicate<? super E> finished) {
        return new UnfoldIterator<E>(initial, next, finished)
    }
    private final Function<? super E, ? extends E> next;
    private final Predicate<? super E> finished;
    private E element;

    public UnfoldIterator(E initial, Function<? super E, ? extends E> next, Predicate<? super E> finished) {
        super();
        this.next = next;
        this.finished = finished;
        this.element = initial;
    }
    @Override protected Integer computeNext() {
        if (finished.apply(element)) {
            return endOfData();
        }
        E result = element;
        element = next.apply(element);
        return result;
    }
}

然后 ArithmeticSeries 变为：

public Iterable<Integer> series(final int start, final int step, final int stop) {
    return new Iterable<Integer>() {
        public Iterator<Integer> iterator() {
            return new UnfoldIterator<Integer>(start, new Function<Integer, Integer>() {
                public Integer apply(Integer from) {
                    return from - step;
                }
            }, new Predicate<Integer>() {
                public boolean apply(Integer input) {
                    return input >= stop;
                }
            });
        }
    };
}

当然，代码现在看起来更复杂，但是使用适当的用于比较和代数的基本函数，调用变得更加清晰：

return unfold(start, subtractBy(step), not(lessThan(stop)));

Answer 3

我认为解决番石榴问题的最佳工具是 AbstractLinkedIterator。您的示例的实现如下所示：

final Iterator<Integer> series = new AbstractLinkedIterator<Integer>(100) {

    @Override protected Integer computeNext(final Integer previous) {
        return previous == 80 ? null : previous - 1;
    }
};
while (series.hasNext()) {
    System.out.println(series.next());
}

您可以轻松地为此迭代器创建一个 Iterable 适配器，例如：

package sk.the0retico.guava;

import java.util.Iterator;

import com.google.common.base.Function;
import com.google.common.collect.AbstractLinkedIterator;

public class LinkedIterable<T> implements Iterable<T> {

    public static final <T> Iterable<T> from(final T first,
        final Function<T, T> computeNext) {
        return new LinkedIterable<T>(first, computeNext);
    }

    public static void main(final String[] args) {
        final Iterable<Integer> series = LinkedIterable.from(100,
                                             new Function<Integer, Integer>() {

            @Override public Integer apply(final Integer input) {
                return input == 80 ? null : input - 1;
            }
        });
        for (final Integer value : series) {
            System.out.println(value);
        }
    }

    private final Function<T, T> computeNext;

    private final T first;

    public LinkedIterable(final T first, final Function<T, T> computeNext) {
        this.first = first;
        this.computeNext = computeNext;
    }

    @Override public Iterator<T> iterator() {
        return new AbstractLinkedIterator<T>(first) {

            @Override protected T computeNext(final T previous) {
                return computeNext.apply(previous);
            }
        };
    }
}

但是，这种方法对返回 null 的提供函数做出了特殊约束。