From 369875f931d841112dd2b6651fc968bb6c569cdb Mon Sep 17 00:00:00 2001 From: Ralf Jung Date: Tue, 16 Jun 2015 18:22:39 +0200 Subject: [PATCH] tweaking here and there, plans for the future --- solutions/src/bigint.rs | 36 ++++++++++++++++++++++++++++++++++++ src/main.rs | 12 ++++++++---- src/part02.rs | 7 ++++--- src/part03.rs | 4 ++-- src/part05.rs | 30 +++++++++++++++++------------- src/part09.rs | 4 ++++ 6 files changed, 71 insertions(+), 22 deletions(-) create mode 100644 src/part09.rs diff --git a/solutions/src/bigint.rs b/solutions/src/bigint.rs index 0abb6b3..80ac63d 100644 --- a/solutions/src/bigint.rs +++ b/solutions/src/bigint.rs @@ -64,6 +64,26 @@ impl BigInt { BigInt { data: v } } + /// Increments the number by 1. Solution to 05.1. + pub fn inc1(&mut self) { + let mut idx = 0; + // This loop adds "(1 << idx)". If there is no more carry, we leave. + while idx < self.data.len() { + let cur = self.data[idx]; + let sum = u64::wrapping_add(cur, 1); + self.data[idx] = sum; + if sum >= cur { + // No overflow, we are done. + return; + } else { + // We need to go on. + idx += 1; + } + } + // If we came here, there is a last carry to add + self.data.push(1); + } + /// Increments the number by "by". pub fn inc(&mut self, mut by: u64) { let mut idx = 0; @@ -191,6 +211,7 @@ impl ops::Add for BigInt { #[cfg(test)] mod tests { + use std::u64; use super::overflowing_add; use super::BigInt; @@ -203,6 +224,21 @@ mod tests { assert_eq!(overflowing_add(1 << 63, (1 << 63) -1 , true), (0, true)); } + #[test] + fn test_inc1() { + let mut b = BigInt::new(0); + b.inc1(); + assert_eq!(b, BigInt::new(1)); + b.inc1(); + assert_eq!(b, BigInt::new(2)); + + b = BigInt::new(u64::MAX); + b.inc1(); + assert_eq!(b, BigInt::from_vec(vec![0, 1])); + b.inc1(); + assert_eq!(b, BigInt::from_vec(vec![1, 1])); + } + #[test] fn test_power_of_2() { assert_eq!(BigInt::power_of_2(0), BigInt::new(1)); diff --git a/src/main.rs b/src/main.rs index 88a4e96..31537df 100644 --- a/src/main.rs +++ b/src/main.rs @@ -59,8 +59,10 @@ // // The actual course is in the partXX.rs files. The part 00-03 cover some basic of the language, // to give you a feeling for Rust's syntax and pervasive mechanisms like pattern matching and traits. -// Parts 04-?? introduce the heart of the language, the mechanism making it different from anything -// else out there. +// Parts 04-06 introduce the heart of the language, the mechanism making it different from anything +// else out there: Ownership, borrowing, lifetimes. In part 07-??, we continue our tour through +// Rust. Finally, in parts ??-??, we implement our own version of `grep`, exhibiting useful Rust +// features as we go. // // I suggest you get started with [the first part](part00.html), or jump directly to where you left off: // @@ -70,7 +72,8 @@ // * [Part 03: Input](part03.html) // * [Part 04: Ownership, Borrowing](part04.html) // * [Part 05: Clone](part05.html) (WIP) -// * [Part 06: Copy](part06.html) (WIP) +// * [Part 06: Copy, Lifetimes](part06.html) (WIP) +// * [Part 07: Operator Overloading, Tests, Output](part07.html) (WIP) // * (to be continued) #![allow(dead_code, unused_imports, unused_variables, unused_mut)] mod part00; @@ -82,12 +85,13 @@ mod part05; mod part06; mod part07; mod part08; +mod part09; // To actually run the code of some part (after filling in the blanks, if necessary), simply edit the `main` // function. fn main() { - part00::main(); + part03::main(); } // Additional material diff --git a/src/part02.rs b/src/part02.rs index f81672b..12faed8 100644 --- a/src/part02.rs +++ b/src/part02.rs @@ -33,7 +33,8 @@ type NumberOrNothing = SomethingOrNothing; // The types are so similar, that we can provide a generic function to construct a `SomethingOrNothing` // from an `Option`, and vice versa. // **Exercise 02.1**: Implement such functions! I provided a skeleton of the solution. Here, -// `panic!` is another macro. This one terminates execution with the given message. +// `unimplemented!` is another macro. This one terminates execution saying that something has not yet +// been implemented. // // Notice the syntax for giving generic implementations to generic types: Think of the first `` // as *declaring* a type variable ("I am doing something for all types `T`"), and the second `` as @@ -44,11 +45,11 @@ type NumberOrNothing = SomethingOrNothing; // Remember that `self` is the `this` of Rust, and implicitly has type `Self`. impl SomethingOrNothing { fn new(o: Option) -> Self { - panic!("Not yet implemented.") + unimplemented!() } fn to_option(self) -> Option { - panic!("Not yet implemented.") + unimplemented!() } } // Observe how `new` does *not* have a `self` parameter. This corresponds to a `static` method diff --git a/src/part03.rs b/src/part03.rs index ddaa47e..45caaec 100644 --- a/src/part03.rs +++ b/src/part03.rs @@ -76,7 +76,7 @@ fn read_vec() -> Vec { // as the documentation is quite easy to navigate and you should get used to that. // For the rest of the code, we just re-use part 02 by importing it with `use`. -// I already sneaked a bunch of `pub` in the other module to make this possible: Only +// I already sneaked a bunch of `pub` in part 02 to make this possible: Only // items declared public can be imported elsewhere. use part02::{SomethingOrNothing,Something,Nothing,vec_min}; @@ -103,7 +103,7 @@ trait Print { } impl SomethingOrNothing { fn print2(self) { - panic!("Not yet implemented.") + unimplemented!() } } diff --git a/src/part05.rs b/src/part05.rs index d7cf64a..a4478f8 100644 --- a/src/part05.rs +++ b/src/part05.rs @@ -2,15 +2,13 @@ // ======================== // ## Big Numbers -// In the course of the next few parts, we are going to build a data-structure for -// computations with *bug* numbers. We would like to not have an upper bound -// to how large these numbers can get, with the memory of the machine being the -// only limit. +// In the course of the next few parts, we are going to build a data-structure for computations with +// *big* numbers. We would like to not have an upper bound to how large these numbers can get, with +// the memory of the machine being the only limit. // // We start by deciding how to represent such big numbers. One possibility here is -// to use a vector of "small" numbers, which we will then consider the "digits" -// of the big number. This is like "1337" being a vector of 4 small numbers (1, 3, 3, 7), -// except that we will use `u64` as type of our base numbers. Now we just have to decide +// to use a vector "digits" of the big number. This is like "1337" being a vector of four digits (1, 3, 3, 7), +// except that we will use `u64` as type of our digits. Now we just have to decide // the order in which we store numbers. I decided that we will store the least significant // digit first. This means that "1337" would actually become (7, 3, 3, 1).
// Finally, we declare that there must not be any trailing zeros (corresponding to @@ -18,11 +16,10 @@ // the same number can only be stored in one way. // To write this down in Rust, we use a `struct`, which is a lot like structs in C: -// Just a collection of a bunch of named fields. Every field can be private to the current module -// (which is the default), or public (which would be indicated by a `pub` in front of the name). -// For the sake of the tutorial, we make `dat` public - otherwise, the next parts of this -// course could not work on `BigInt`s. Of course, in a real program, one would make the field -// private to ensure that the invariant (no trailing zeros) is maintained. +// Just a bunch of named fields. Every field can be private to the current module (which is the default), +// or public (which is indicated by a `pub` in front of the name). For the sake of the tutorial, we make +// `data` public - otherwise, the next parts of this course could not work on `BigInt`s. Of course, in a +// real program, one would make the field private to ensure that the invariant (no trailing zeros) is maintained. pub struct BigInt { pub data: Vec, } @@ -62,6 +59,11 @@ impl BigInt { } } +// **Exercise 05.1**: Write a function on `BigInt` that returns the number of digits. Write another one +// that increments the number by 1. +// +// *Hint*: To take `self` as a mutable borrow, write `fn inc1(&mut self)`. + // ## Cloning // If you have a close look at the type of `BigInt::from_vec`, you will notice that it // consumes the vector `v`. The caller hence loses access. There is however something @@ -88,6 +90,8 @@ impl Clone for BigInt { // Making a type clonable is such a common exercise that Rust can even help you doing it: // If you add `#[derive(Clone)]` right in front of the definition of `BigInt`, Rust will // generate an implementation of `Clone` that simply clones all the fields. Try it! +// These `#[...]` annotations at types (and functions, modules, crates) are called *attributes*. +// We will see some more examples of attributes later. // We can also make the type `SomethingOrNothing` implement `Clone`. However, that // can only work if `T` is `Clone`! So we have to add this bound to `T` when we introduce @@ -141,6 +145,6 @@ fn work_on_variant(mut var: Variant, text: String) { // that address, and Rust would eat your laundry - or whatever.) // // I hope this example clarifies why Rust has to rule out mutation in the presence of aliasing *in general*, -// not just for the specific +// not just for the specific case of a buffer being reallocated, and old pointers becoming hence invalid. // [index](main.html) | [previous](part04.html) | [next](part06.html) diff --git a/src/part09.rs b/src/part09.rs new file mode 100644 index 0000000..023a48f --- /dev/null +++ b/src/part09.rs @@ -0,0 +1,4 @@ +// Rust-101, Part 09: Iterators +// ============================ + +// [index](main.html) | [previous](part08.html) | [next](main.html) -- 2.30.2