Traits

Systems in Rust

Preamble

You know what a queue is. Now make one in Rust.

• Review pattern matching.
• Review the humble tuple
• Review the immortal struct
• Review ownership.
• Use generics to create a stack and queue that can store any type.
• Use traits to implement push and pop operations for both data types.

Design Decision

• With the addition of a queue, you get to decide:
  • Whether to head push and tail pop, or…

  >>> # Tail push, head pop
  >>> _ = [q.append(i) for i in range(3)]
  >>> q
  [0, 1, 2]
  >>> q.pop(0)
  0

  • Whether to tail push and head pop.

  >>> # Head push, tail pop
  >>> q = list()
  >>> _ = [q.insert(0,i) for i in range(3)]
  >>> q
  [2, 1, 0]
  >>> q.pop(-1)
  0

• This is the added difficulty incurred by adding a queue.

Review: Box

• To put some x in a Box, simply:

let x = String::from("I'm a capital-S String.");
let b = Box::new(x);

• To remove x from the `Box, simply use the special “unary asterisk” operator, also called “dereference”.

let s : String = *b;

Novel: Generics

• You are welcome to read Rustbook on Generics
• We previously “hard-coded” the Stack to accept strings.

pub struct Stack {
    data: String...

• We instead append a type annotation to the end of stack, like so:

pub struct Stack<T> ...

• By convention, Rust uses T to refer to a type variable.
• Then, within the declaration we may refer to T:

pub struct Stack<T> {
    data: T...

• Upon making this change, you will get a series of rustc complaints about not specifying types in a variety of locations.
• You will have relatively little difficulty working through these, and should learn something valuable in the process.

Novel: Traits

• It is customary for programmers with a background in object-oriented langauges, such as Python, JavaScript, or Java, to have an affinity for methods.
• In the lab, we used functional style:

s = push(val, s);

• Now we will use traits to implement methods to get the following style:

s = s.push(val);

• It is not required to use traits to achieve this, and possible to write methods directly, I simply found this uninteresting.
• Have two parts:

1. A declaration:

pub trait Push<T> {
    fn push(self, val: T) -> Self;
}

2. An implementation:

impl<T> Push<T> for Stack<T> {
    fn push(mut self, val: T) -> Stack<T> {
        todo!();
    }
}

• An astute observer will notice that T occurs seven (7) times just within the declarations.
  • Form your own opinion about that.

Starter Code

src/main.rs

• I am providing a fairly enormous testing script via Gist.



• I have removed dbg!() calls and simply check popped values.

Fin

$ wc src/lib.rs
 104  296 2484 src/lib.rs