RustCurious.com
Rust explained carefully.
Lesson 9
Traits are Interfaces
A trait specifies an interface, a capability that types can choose to implement. Trait bounds specify the capabilities required for a generic type to work with an API.
Coding Practice
Exercise 1: Stack Iterator
// https://rustcurious.com/9
// Exercise: Stack Iterator
//
// See TODO at the very bottom.
//
// Implement the Iterator trait to pass the unit tests.
// Iterating a Stack should behave the same as `pop()`
// so a char is removed and returned at each step.
//
// SPOILER WARNING:
// Contains a solution to the Stack exercise.
/// A first-in-last-out container of up to 25 chars.
pub struct Stack {
buf: [char; 25],
len: usize,
}
impl Stack {
/// Returns an empty Stack.
pub fn new() -> Stack {
Stack {
buf: [' '; 25],
len: 0,
}
}
/// Returns the current number of items (chars) held.
pub fn len(&self) -> usize {
self.len
}
/// Pushes the item `c` onto the stack.
pub fn push(&mut self, c: char) {
self.buf[self.len] = c;
self.len += 1;
}
/// Removes the top item from the stack and returns it.
///
/// Returns None if the stack is empty.
pub fn pop(&mut self) -> Option<char> {
if self.len > 0 {
self.len -= 1;
Some(self.buf[self.len])
} else {
None
}
}
}
#[test]
fn test_for_consume() {
let mut stack = Stack::new();
stack.push('a');
stack.push('b');
stack.push('c');
// consumes stack
for _ in stack {}
}
#[test]
fn test_for_drain() {
let mut stack = Stack::new();
stack.push('a');
stack.push('b');
stack.push('c');
for _ in &mut stack {}
// stack still exists but is empty
assert_eq!(stack.len(), 0);
}
#[test]
fn test_next() {
let mut stack = Stack::new();
stack.push('a');
stack.push('b');
stack.push('c');
assert_eq!(stack.next(), Some('c'));
assert_eq!(stack.next(), Some('b'));
assert_eq!(stack.next(), Some('a'));
assert_eq!(stack.next(), None);
}
#[test]
fn test_zip() {
let mut stack = Stack::new();
stack.push('a');
stack.push('b');
stack.push('c');
// The `zip` method comes for free on any type
// that implements Iterator.
for (x, y) in stack.zip(['c', 'b', 'a']) {
assert_eq!(x, y);
}
}
#[test]
fn test_enumerate() {
let mut stack = Stack::new();
stack.push('a');
stack.push('b');
stack.push('c');
// The `enumerate` method comes for free on any type
// that implements Iterator.
let expected = ['c', 'b', 'a'];
for (i, x) in stack.enumerate() {
assert_eq!(x, expected[i]);
}
}
// No need to change anything above this line.
// -------------------------------------------------------
// TODO: impl Iterator so that next() calls pop().
Exercise 2: Slab Index
// https://rustcurious.com/9
// Exercise: Slab Index
//
// See TODO at the very bottom.
//
// This Slab type implements a collection based
// on a fixed-length array. It can hold up to N
// items, with each entry in the array either
// occupied or vacant.
//
// Implement Index and IndexMut so a Slab can be
// indexed using square brackets with a usize index.
//
// Accessing a vacant index should panic, just like
// indexing beyond the end of an array panics.
//
// SPOILER WARNING:
// Contains a solution to the Slab exercise.
use std::array; // for array::from_fn
use std::mem; // for mem::replace
enum Entry<T> {
Occupied(T),
Vacant(usize),
}
pub struct Slab<T, const N: usize> {
buf: [Entry<T>; N],
head: usize,
}
impl<T, const N: usize> Slab<T, N> {
pub fn new() -> Self {
Slab {
buf: array::from_fn(|i| Entry::Vacant(i + 1)),
head: 0,
}
}
pub fn insert(&mut self, item: T) -> Result<usize, T> {
let index = self.head;
if index == N {
return Err(item);
}
let Entry::Vacant(next) = self.buf[index] else {
panic!("head must be vacant");
};
self.buf[index] = Entry::Occupied(item);
self.head = next;
Ok(index)
}
pub fn remove(&mut self, index: usize) -> Option<T> {
if let Entry::Vacant(_) = self.buf[index] {
return None;
}
let Entry::Occupied(item) = mem::replace(
&mut self.buf[index],
Entry::Vacant(self.head),
) else {
unreachable!();
};
self.head = index;
Some(item)
}
/// Get a shared reference to the item at `index`.
///
/// Returns `None` if the entry is vacant.
pub fn get(&self, index: usize) -> Option<&T> {
match &self.buf[index] {
Entry::Occupied(item) => Some(item),
Entry::Vacant(_) => None,
}
}
/// Get a mutable reference to the item at `index`.
///
/// Returns `None` if the entry is vacant.
pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
match &mut self.buf[index] {
Entry::Occupied(item) => Some(item),
Entry::Vacant(_) => None,
}
}
}
#[test]
#[should_panic]
fn test_index_panic() {
#[derive(Debug)]
struct Foo; // private type prevents cheating
let mut slab: Slab<Foo, 5> = Slab::new();
let i = slab.insert(Foo).unwrap();
slab.remove(i).unwrap();
let _ = slab[i]; // panic
}
#[test]
#[should_panic]
fn test_index_mut_panic() {
let mut slab: Slab<char, 5> = Slab::new();
slab[0] = 'x'; // panic
}
#[test]
fn test() {
let mut slab: Slab<char, 3> = Slab::new();
let i = slab.insert('a').unwrap();
let a = slab[i]; // uses Index
assert_eq!(a, 'a');
slab[i] = 'b'; // uses IndexMut
slab[i].make_ascii_uppercase(); // uses IndexMut
let b = slab[i]; // uses Index
assert_eq!(b, 'B');
}
// No need to change anything above this line.
// -------------------------------------------------------
use std::ops::{Index, IndexMut};
// TODO: impl Index
// TODO: impl IndexMut
Exercise 3: Enumerate
// https://rustcurious.com/9
// Exercise: Enumerate
//
// See TODO at the very bottom.
//
// Implement Iterator for the Enumerate iterator adapter
// so the unit tests pass. See commented-out unit tests
// for bonus challenges.
/// An iterator adapter that tracks the iteration count.
pub struct Enumerate<I> {
// The underlying iterator
iter: I,
// The iteration count
n: usize,
}
/// Wraps the iterator `iter` in the Enumerate adapter.
pub fn enumerate<I: Iterator>(iter: I) -> Enumerate<I> {
Enumerate {
iter,
n: 0,
}
}
#[test]
fn test_for() {
for (i, x) in enumerate(0..10) {
assert_eq!(i, x);
}
}
#[test]
fn test_next() {
let mut iter = enumerate('a'..='e');
assert_eq!(iter.next(), Some((0, 'a')));
assert_eq!(iter.next(), Some((1, 'b')));
assert_eq!(iter.next(), Some((2, 'c')));
assert_eq!(iter.next(), Some((3, 'd')));
assert_eq!(iter.next(), Some((4, 'e')));
assert_eq!(iter.next(), None);
}
#[test]
fn test_for_array() {
let arr = [0, 1, 2, 3];
for (i, x) in enumerate(arr.iter()) {
assert_eq!(i, *x);
}
}
// BONUS:
// Uncomment this test and override size_hint so it calls
// the size_hint method on the underlying iterator.
/*
#[test]
fn test_size_hint() {
let iter = enumerate('a'..='e');
assert_eq!(iter.size_hint(), (5, Some(5)));
assert_eq!(Iterator::size_hint(&iter), (5, Some(5)));
}
*/
// BONUS:
// Uncomment this test and implement ExactSizeIterator
// if the underlying iterator I implements it.
/*
#[test]
fn test_exact_size() {
let iter = enumerate(10..15);
assert_eq!(iter.len(), 5);
assert_eq!(ExactSizeIterator::len(&iter), 5);
}
*/
// BONUS that I thought of after recording the video:
// Uncomment this test and change the enumerate function
// so it accepts any type that implements IntoIterator.
// (Requires making changes above, only to `enumerate`.)
/*
#[test]
fn test_intoiter() {
let arr = [0, 1, 2, 3];
// &arr is not Iterator, but it is IntoIterator
for (i, x) in enumerate(&arr) {
assert_eq!(i, *x);
}
}
*/
// No need to change anything above this line.
// -------------------------------------------------------
// TODO: impl Iterator
//
// The Item type should be a tuple containing the iteration
// count and the item from the underlying iterator.