From 66c777f23e032d445e29b1b40faa8e1799b4930c Mon Sep 17 00:00:00 2001 From: Ralf Jung Date: Mon, 6 Jul 2015 17:53:42 +0200 Subject: [PATCH] part 09: iterator for BigInt --- src/part09.rs | 60 +++++++++++++++++++++++++++++++++++++++++ workspace/src/part09.rs | 59 ++++++++++++++++++++++++++++++++++++++++ 2 files changed, 119 insertions(+) diff --git a/src/part09.rs b/src/part09.rs index 0045c7a..482b293 100644 --- a/src/part09.rs +++ b/src/part09.rs @@ -1,4 +1,64 @@ // Rust-101, Part 09: Iterators (WIP) // ================================== +use part05::BigInt; + +// In the following, we will look into the iterator mechanism of Rust and make our `BigInt` compatible +// with the `for` loops. Of course, this is all about implementing particular traits again. In particular, +// an iterator is something that implements the `Iterator` trait. As you can see in [the documentation](http://doc.rust-lang.org/beta/std/iter/trait.Iterator.html), +// this trait mandates a single function `next` returning an `Option`, where `Item` is an +// associated type chosen by the implementation. (There are many more methods provided for `Iterator`, +// but they all have default implementations, so we don't have to worry about them right now). +// +// For the case of `BigInt`, we want our iterator to iterate over the digits in normal, notational order: The most-significant +// digit comes first. So, we have to write down some type, and implement `Iterator` for it such that `next` returns the digits +// one-by-one. Clearly, the iterator must somehow be able to access the number it iterates over, and it must store its current +// location. However, it cannot *own* the `BigInt`, because then the number would be gone after iteration! That'd certainly be bad. +// The only alternative is for the iterator to *borrow* the number. + +// In writing this down, we again have to be explicit about the lifetime of the borrow: We can't just have an +// `Iter`, we must have an `Iter<'a>` that borrowed the number for lifetime `'a`.
+// `usize` here is the type of unsigned, pointer-sized numbers. It is typically the type of "lengths of things", +// in particular, it is the type of the length of a `Vec` and hence the right type to store an offset into the vector of digits. +struct Iter<'a> { + num: &'a BigInt, + idx: usize, // the index of the last number that was returned +} + +// Now we are equipped to implement `Iterator` for `Iter`. +impl<'a> Iterator for Iter<'a> { + // We choose the type of things that we iterate over to be the type of digits, i.e., `u64`. + type Item = u64; + + fn next(&mut self) -> Option { + // First, check whether there's any more digits to return. + if self.idx == 0 { + // We already returned all the digits. + None /*@*/ + } else { + // Decrement, and return next digit. + self.idx = self.idx - 1; /*@*/ + Some(self.num.data[self.idx]) /*@*/ + } + } +} + +// All we need now is a function that creates such an iterator for a given `BigInt`. +impl BigInt { + // Notice that when we write the type of `iter`, we don't actually have to give the lifetime parameter of `Iter`. Just as it is + // the case with functions returning borrowed data, you can elide the lifetime. The rules for adding the lifetimes are exactly the + // same. (See the last section of [part 06](part06.html).) + fn iter(&self) -> Iter { + Iter { num: self, idx: self.data.len() } /*@*/ + } +} + +// We are finally ready to iterate! Remember to edit `main.rs` to run this function. +pub fn main() { + let b = BigInt::new(1 << 63) + BigInt::new(1 << 16) + BigInt::new(1 << 63); + for digit in b.iter() { + println!("{}", digit); + } +} + //@ [index](main.html) | [previous](part08.html) | [next](main.html) diff --git a/workspace/src/part09.rs b/workspace/src/part09.rs index 8e82f03..d6b8bba 100644 --- a/workspace/src/part09.rs +++ b/workspace/src/part09.rs @@ -1,3 +1,62 @@ // Rust-101, Part 09: Iterators (WIP) // ================================== +use part05::BigInt; + +// In the following, we will look into the iterator mechanism of Rust and make our `BigInt` compatible +// with the `for` loops. Of course, this is all about implementing particular traits again. In particular, +// an iterator is something that implements the `Iterator` trait. As you can see in [the documentation](http://doc.rust-lang.org/beta/std/iter/trait.Iterator.html), +// this trait mandates a single function `next` returning an `Option`, where `Item` is an +// associated type chosen by the implementation. (There are many more methods provided for `Iterator`, +// but they all have default implementations, so we don't have to worry about them right now). +// +// For the case of `BigInt`, we want our iterator to iterate over the digits in normal, notational order: The most-significant +// digit comes first. So, we have to write down some type, and implement `Iterator` for it such that `next` returns the digits +// one-by-one. Clearly, the iterator must somehow be able to access the number it iterates over, and it must store its current +// location. However, it cannot *own* the `BigInt`, because then the number would be gone after iteration! That'd certainly be bad. +// The only alternative is for the iterator to *borrow* the number. + +// In writing this down, we again have to be explicit about the lifetime of the borrow: We can't just have an +// `Iter`, we must have an `Iter<'a>` that borrowed the number for lifetime `'a`.
+// `usize` here is the type of unsigned, pointer-sized numbers. It is typically the type of "lengths of things", +// in particular, it is the type of the length of a `Vec` and hence the right type to store an offset into the vector of digits. +struct Iter<'a> { + num: &'a BigInt, + idx: usize, // the index of the last number that was returned +} + +// Now we are equipped to implement `Iterator` for `Iter`. +impl<'a> Iterator for Iter<'a> { + // We choose the type of things that we iterate over to be the type of digits, i.e., `u64`. + type Item = u64; + + fn next(&mut self) -> Option { + // First, check whether there's any more digits to return. + if self.idx == 0 { + // We already returned all the digits. + unimplemented!() + } else { + // Decrement, and return next digit. + unimplemented!() + } + } +} + +// All we need now is a function that creates such an iterator for a given `BigInt`. +impl BigInt { + // Notice that when we write the type of `iter`, we don't actually have to give the lifetime parameter of `Iter`. Just as it is + // the case with functions returning borrowed data, you can elide the lifetime. The rules for adding the lifetimes are exactly the + // same. (See the last section of [part 06](part06.html).) + fn iter(&self) -> Iter { + unimplemented!() + } +} + +// We are finally ready to iterate! Remember to edit `main.rs` to run this function. +pub fn main() { + let b = BigInt::new(1 << 63) + BigInt::new(1 << 16) + BigInt::new(1 << 63); + for digit in b.iter() { + println!("{}", digit); + } +} + -- 2.30.2