8
\$\begingroup\$

Following-up to my previous question, this class is now based on an iterator. The class, instead of forcing the programmer to use up a bunch of memory just to get each progressive number once, they can now use an iterator. The class itself is also now based on an iterator, which makes my life easier too. No more initFirst()!

Edit note: the main method was there to test, and is there for no other reason.

import java.math.BigInteger;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

/**
 * 
 */
public class InfiniteFibonacci {

    public static void main(String[] args) {
        InfiniteFibonacci i = new InfiniteFibonacci();
        System.out.println(i.getNumberAt(0));
        System.out.println(i.getNumberAt(100));
    }

    /**
     * The default starting amount of numbers in the sequence to be generated.
     */
    public static final int DEFAULT_STARTING_CAP = 64;

    private final Iterator<BigInteger> iterator = new FibonacciIterator();

    private List<SequencePart> parts;

    private int currentSize = 0;

    /**
     * Creates a new <code>InfiniteFibonacci</code> object, with the default
     * amount of numbers.
     */
    public InfiniteFibonacci() {
        this(DEFAULT_STARTING_CAP);
    }

    /**
     * Creates a new <code>InfiniteFibonacci</code> object, with the specified
     * amount of numbers.
     * 
     * @param startCap
     *            The amount of numbers to generate. It will be rounded up to
     *            the nearest 16.
     */
    public InfiniteFibonacci(int startCap) {
        parts = new LinkedList<>();
        initTo(startCap);
    }

    private void initTo(int index) {
        for (; currentSize <= index; currentSize += SequencePart.SIZE) {
            SequencePart part = new SequencePart();
            for (int i = 0; i < SequencePart.SIZE; i++) {
                part.values[i] = iterator.next();
            }
            parts.add(part);
        }
    }

    /**
     * Gets the <code>n</code>th number in the sequence, zero-based.
     * 
     * @param index
     *            the <code>n</code> as described
     * 
     * @return the specified in the sequence, zero-based.
     */
    public BigInteger getNumberAt(int index) {
        if (index > currentSize) {
            initTo(index);
        }
        return parts.get(index / SequencePart.SIZE).values[index
                % SequencePart.SIZE];
    }

    /**
     * Provides a faster <code>Iterator</code> for code that uses only each
     * number once.
     * 
     * @return An <code>Iterator</code> that iterates through each of the
     *         numbers.
     */
    public static Iterator<BigInteger> getIterator() {
        return new FibonacciIterator();
    }

    private class SequencePart {

        private static final int SIZE = 16;

        private BigInteger[] values = new BigInteger[SIZE];

        private SequencePart() {

        }

    }

    private static final class FibonacciIterator implements
            Iterator<BigInteger> {

        private BigInteger current = BigInteger.ONE;
        private BigInteger previous = BigInteger.ZERO;

        private FibonacciIterator() {

        }

        @Override
        public boolean hasNext() {
            // Always has next
            return true;
        }

        @Override
        public BigInteger next() {
            BigInteger temp = current;
            current = previous.add(current);
            previous = temp;
            return temp;
        }

    }

}

Concerns:

  1. Was implementing Iterator<BigInteger> a good idea?
  2. Was the changes an improvement, or was it "poison"?
\$\endgroup\$
4
\$\begingroup\$

Judging by the title of the question and the main class, I expected to see a simple iterator over Fibonacci numbers to infinity. Instead I see a class with too many responsibilities. It would be better to separate these concerns:

  • the infinite iterator
  • one class to get the nth Fibonacci number with caching
  • a utility class that implements the cache storage from a linked list of segments, the logic of which is encapsulated and hidden from users
  • the runner class with the main method

The Iterator<BigInteger> is a very good idea. I thought of perhaps providing an Iterator<Integer> too, but then, Fibonacci numbers tend to get very big very fast, so there's probably not much point. So just the Iterator<BigInteger> makes sense.

What you did with the sequence parts is an interesting way to implement a dynamically growing array-like storage without resize operations. As mentioned, this has nothing to do with Fibonacci numbers, and this logic could live in its own utility class. But I think it's probably not worth it. You can use a simple ArrayList instead. When the performance of the ArrayList becomes a real concern, you could try your alternative List implementation.

|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.