Implementing Iterator using an underlying iterator

implement iterable java
how to implement iterator java
iterator vs iterable java
iterable interface in java javatpoint
list iterator implementation java
iterator hasnext implementation java
java list to iterable example
java iterator internal implementation

Editor's note: This question uses some functions and types that were removed before Rust 1.0. The ideas are still valid but the code does not run in Rust 1.0.

I'm trying to solve Project Euler's problem #3 using Rust by implementing Eratosthenes Sieve as an iterator.

After some brain-exploding tries with lifetimes, I stopped here.

use std::iter::count;

struct EratosthenesStream<'a> {
    sieve: &'a (Iterator + 'a),
}

impl<'a> EratosthenesStream<'a> {
    fn new() -> EratosthenesStream<'a> {
        EratosthenesStream {
            sieve: &count(2, 1),
        }
    }
}

impl<'a> Iterator for EratosthenesStream<'a> {
    type Item = isize;

    fn next(&mut self) -> Option<isize> {
        let prime = self.sieve.next().expect("Out of numbers");
        self.sieve = self.sieve.filter(|&x| x % prime == 0);
        Some(prime)
    }
}

fn main() {
    // let sieve = EratosthenesStream::new();
    // for i in sieve.take(5) {
    //   println!("{}", i);
    // }
}

Building that thing gives me:

Compiling problem3 v0.0.1 (file:///home/franza/Projects/euler-project-rust/problem3)
/home/franza/Projects/euler-project-rust/problem3/src/main.rs:16:33: 16:45 error: the value of the associated type `Item` (from the trait `core::iter::Iterator`) must be specified
/home/franza/Projects/euler-project-rust/problem3/src/main.rs:16     EratosthenesStream { sieve: &count(2, 1) }
                                                                                                 ^~~~~~~~~~~~
/home/franza/Projects/euler-project-rust/problem3/src/main.rs:25:29: 25:56 error: type `&'a core::iter::Iterator + 'a` does not implement any method in scope named `filter`
/home/franza/Projects/euler-project-rust/problem3/src/main.rs:25     self.sieve = self.sieve.filter(|&x| x % prime == 0);
                                                                                             ^~~~~~~~~~~~~~~~~~~~~~~~~~~
/home/franza/Projects/euler-project-rust/problem3/src/main.rs:25:41: 25:42 error: the type of this value must be known in this context
/home/franza/Projects/euler-project-rust/problem3/src/main.rs:25     self.sieve = self.sieve.filter(|&x| x % prime == 0);
                                                                                                         ^
/home/franza/Projects/euler-project-rust/problem3/src/main.rs:25:36: 25:55 error: can't infer the "kind" of the closure, explicitly annotate it. e.g. `|&:| {}`
/home/franza/Projects/euler-project-rust/problem3/src/main.rs:25     self.sieve = self.sieve.filter(|&x| x % prime == 0);
                                                                                                    ^~~~~~~~~~~~~~~~~~~
/home/franza/Projects/euler-project-rust/problem3/src/main.rs:26:5: 26:16 error: mismatched types: expected `core::option::Option<isize>`, found `core::option::Option<<core::iter::Iterator as core::iter::Iterator>::Item>` (expected isize, found associated type)
/home/franza/Projects/euler-project-rust/problem3/src/main.rs:26     Some(prime)
                                                                     ^~~~~~~~~~~
error: aborting due to 5 previous errors
Could not compile `problem3`.

I'm starting out in Rust so I don't know a lot about this

UPDATE:

  • rustc 1.0.0-nightly (44a287e6e 2015-01-08 17:03:40 -0800)
  • cargo 0.0.1-pre-nightly (8c01b6b 2015-01-08 20:52:43 +0000)

Editor's note: This answer uses some functions and types that were removed before Rust 1.0. The ideas are still valid but the code does not run in Rust 1.0. Some bugs have been fixed since then as well.

This is an interesting approach to computing primes, but I'm not sure it's going to work well with Rust as it stands right now. There's a lot of bugs we're ironing out with trait objects that make them... not great.

Still, I can address some issues.

You're trying to store a shared reference to the iterator in your struct. That's not going to work for two reasons: iterators require mutability for next, and the iterators aren't going to live long enough.

Presumably, you want something like Box<Iterator + 'static> in your struct, but due to the aforementioned bugs, that just doesn't work for no particularly good reason.

For now I'm afraid you'll have to maintain the list of primes you've seen explicitly. I suggest something like:

struct Foo {
    odds: Counter<u32>,
    primes: Vec<u32>,
}

And a more "procedural" approach with explicit for-loops:

(not sure if it's totally appropriate to give a full solution here, so don't read ahead if you don't want spoilers, I guess?)

struct Foo {
    odds: Counter<u32>,
    primes: Vec<u32>,
}

impl Foo {
    fn new() -> Foo {
        Foo {
            odds: count(2, 1),
            primes: Vec::new(),
        }
    }
}

impl Iterator for Foo {
    type Item = u32;

    fn next(&mut self) -> Option<u32> {
        'main: for i in self.odds {
            for &prime in self.primes.iter() {
                if i % prime == 0 {
                    continue 'main;
                }
            }
            self.primes.push(i);
            return Some(i);
        }
        None
    }
}

fn main() {
    let foo = Foo::new();
    for i in foo.take(10) {
        println!("{}", i);
    }
}

How to use Iterator in Java?, , we need a cursor or pointer to keep track of which element we currently are on. Depending on the underlying data structure, we can progress from one element to another. This is done in the next() method which returns the current element and the cursor advances to next element. That's not going to work for two reasons: iterators require mutability for next, and the iterators aren't going to live long enough. Presumably, you want something like Box<Iterator + 'static> in your struct, but due to the aforementioned bugs, that just doesn't work for no particularly good reason.

Now that #21361 has been closed, you can implement it this way:

use std::{iter, mem};

struct Sieve {
    iter: Box<Iterator<Item = u64> + 'static>,
}

impl Sieve {
    fn new() -> Sieve {
        Sieve {
            iter: Box::new(2..),
        }
    }
}

impl Iterator for Sieve {
    type Item = u64;

    fn next(&mut self) -> Option<u64> {
        let mut iter = mem::replace(&mut self.iter, Box::new(iter::empty()));

        match iter.next() {
            Some(prime) => {
                self.iter = Box::new(iter.filter(move |x| x % prime != 0));
                Some(prime)
            }
            None => None,
        }
    }
}

fn main() {
    let v: Vec<_> = Sieve::new().take(20).collect();
    println!("{:?}", v);
}

Some notes about the implementation:

  1. Your logic was backwards. You want to filter x % prime != 0. ^_^
  2. filter consumes the iterator, but that would cause problem here. If we were allowed to consume it, then the Sieve struct would no longer be whole and valid. To work around this, we use mem::replace to put in a placeholder value. That lets us consume the iterator before we update the struct with the new value.
  3. Every iteration adds more function calls to the stack. I was only able get the first 6466 prime numbers with this technique before I ran out of stack space.

Iterator, What is the iterator concept What methods are part of an iterator? The easiest way to do this is to employ an iterator, which is an object that implements either the Iterator or the ListIterator interface. Iterator enables you to cycle through a collection, obtaining or removing elements. ListIterator extends Iterator to allow bidirectional traversal of a list, and the modification of elements.

The key of this problem is to filter the iterator without moving it, which can be done by using take_mut.

Add take_mut = "0.2.2"(or any other compatible versions) to your dependencies, then you can do something like:

extern crate take_mut;

struct Primes {
    iter: Box<Iterator<Item=i64>>,
}

impl Iterator for Primes {
    type Item=i64;

    fn next(&mut self) -> Option<i64> {
        let result = self.iter.next();
        if let Some(prime) = result {
            take_mut::take(&mut self.iter, 
                |primes| Box::new(primes.filter(move |p| p % prime != 0)));
        }
        result
    }
}

impl Primes {
    fn new() -> Primes {
        Primes { iter: Box::new(2..)}
    }
}

fn main() {
    println!("First 10 primes:");
    for p in Primes::new().take(10) {
        println!("{}", p);
    }
}

Edit: Option::take can also do this job.

struct Primes {
    iter: Option<Box<Iterator<Item = u64>>>,
}

impl Primes {
    fn new() -> Primes {
        Primes {
            iter: Some(Box::new(2..)),
        }
    }
}

impl Iterator for Primes {
    type Item = u64;

    fn next(&mut self) -> Option<u64> {
        let mut iter = self.iter.take()?;
        let result = iter.next();
        if let Some(prime) = result {
            self.iter = Some(Box::new(iter.filter(move |n| n % prime != 0)));
        }
        result
    }
}

A Guide to Iterator in Java, : void add(Object object): It inserts object immediately before the element that is returned by the next( ) function. boolean hasNext( ): It returns true if the list has a next element. They implement something known as the Iterator protocol in Python. What is that? Well, the Iterator protocol allows us to loop over items in an iterable using two methods: __iter__() and __next__(). All iterables and iterators have the __iter__() method which returns an iterator. An iterator keeps track of the current state of an iterable.

is to allow a user to process every element of a container while isolating the user from the internal structure of the container. This allows the container to store elements in any manner it wishes while allowing the user to treat it as if it were a simple sequence or list. Also, the user will not have to worry about keeping track of the number of items traversed, remaining, and whether to check for boundary conditions as all this is already being done in the iterator object (as these things will depend on the underlying structure and implementation of the collection object).

from the underlying collection the last element returned by the iterator (optional Scanner class is an example of a class that implements the Iterator interface. an ArrayList of Strings and iterates through the collection printing each value. Each Iterator provides a next() and hasNext() method, and may optionally support a remove() method. Iterators are created by the corresponding container class, typically by a method named iterator(). The next() method advances the iterator and returns the value pointed to by the iterator. The first element is obtained upon the first call to next().

This Java Iterator tutorial explains how to use the Iterator interface. Iteration; forEachRemaining(); ListIterator; Implement the Iterator If you modify the underlying collection while iterating through an Iterator pointing to that  One advantage of Iterable is, when you implement Iterable then those object gets support for for:each loop syntax. Removing elements using Iterator. Iterator has a remove method using which we can delete elements from the underlying object. It removes the last element returned by the iterator. Difference between Iterator and Enumeration interfaces

Comments
  • I think that issue #21361 would help by allowing filter on a Box<Iterator<Item=...>>.