Implement a Custom Iterator in Rust

This challenge focuses on understanding and implementing the Iterator trait in Rust. You will create a custom iterator that generates a sequence of numbers based on a simple rule, allowing you to practice the core concepts of iteration in Rust. Mastering iterators is fundamental for efficient and idiomatic Rust programming.

Problem Description

Your task is to implement a custom iterator for a struct called FibonacciSequence. This iterator should generate numbers following the Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, ...

The FibonacciSequence struct will store the current and next two numbers in the sequence needed to generate the subsequent term.

Requirements:

1. Define a FibonacciSequence struct: This struct should hold the state necessary to generate the Fibonacci sequence. At a minimum, it needs to store the two most recent numbers to calculate the next one.
2. Implement the Iterator trait for FibonacciSequence:
   • The Item type associated with the iterator should be u64 (unsigned 64-bit integer).
   • The next() method should return Option<Self::Item>.
3. The next() method logic:
   • The first call to next() should return Some(0).
   • The second call should return Some(1).
   • Subsequent calls should return the sum of the two preceding numbers in the sequence.
   • The iterator should be able to produce a potentially large number of Fibonacci numbers. Consider the capacity of u64.

Expected Behavior:

When you create a FibonacciSequence and call next() repeatedly, you should observe the standard Fibonacci sequence.

Edge Cases:

• Overflow: The Fibonacci sequence grows quickly. Consider how your implementation will handle reaching the maximum value of u64. For this challenge, you can choose to stop the iterator or panic, but a graceful stopping is preferred.

Examples

Example 1:

Input:
let mut fib = FibonacciSequence::new();
println!("{:?}", fib.next());
println!("{:?}", fib.next());
println!("{:?}", fib.next());
println!("{:?}", fib.next());
println!("{:?}", fib.next());

Output:

Some(0)
Some(1)
Some(1)
Some(2)
Some(3)

Explanation: This demonstrates the initial generation of Fibonacci numbers, starting from 0 and 1.

Example 2:

Input:
let mut fib = FibonacciSequence::new();
for _ in 0..10 {
    if let Some(num) = fib.next() {
        println!("{}", num);
    }
}

Output:

0
1
1
2
3
5
8
13
21
34

Explanation: This shows generating the first 10 numbers of the Fibonacci sequence.

Example 3: Overflow consideration

Input:
// This example might run for a while depending on how overflow is handled.
// If the iterator stops gracefully on overflow, it will terminate.
// If it panics, the program will crash.
let mut fib = FibonacciSequence::new();
let mut count = 0;
while let Some(_) = fib.next() {
    count += 1;
}
println!("Generated {} Fibonacci numbers before overflow/stopping.", count);

Output (example, actual count may vary slightly based on exact overflow detection):

Generated 93 Fibonacci numbers before overflow/stopping.

Explanation: This illustrates that the iterator should eventually stop producing numbers as it approaches the limit of u64. The exact number of generated items before overflow depends on the specific u64 limit.

Constraints

• The Fibonacci numbers should be of type u64.
• The next() method should return Option<u64>.
• The implementation should avoid unnecessary recalculations.
• The iterator should ideally stop gracefully when the next Fibonacci number would overflow u64.

Notes

• Consider how to store the state within the FibonacciSequence struct. You'll need at least two variables to keep track of the previous two numbers.
• The Iterator trait is defined in std::iter.
• Think about how to handle the initial two numbers (0 and 1) correctly within your next() method.
• For overflow detection, Rust's checked arithmetic methods (like checked_add) can be very useful.