Rust example of how to organize code using a single trait for multiple implementations using various techniques: duplications, trait objects, generics

!rust-data-structure-api-techniques.md

Our Trait

pub trait StackLike<T> {
    fn new() -> Self; // minor omission, see notes
    
    fn my_push(&mut self, value: T);
    fn my_pop(&mut self) -> Option<T>;
}

This has two implementations

• /// A stack backed by a vector.
  pub struct VecStack<T>(Vec<T>);

• /// A stack that deduplicates consecutive equal elements.
  pub struct CountedStack<T>(Vec<(usize, T)>);

How to write a data structure that uses both of these in a composable way?

Naive

pub struct Foo1 {
    bar: VecStack<i32>,
    baz: CountedStack<i32>,
}

pub struct Foo2 {
    bar: CountedStack<i32>,
    baz: CountedStack<i32>,
}

Trait Objects

In some languages like Go we could write directly

type Foo3 struct {
    bar   StackLike[int32]
    baz   StackLike[int32]
}

We can do this in Rust as follows

pub struct Foo3 {
    bar: Box<dyn StackLike<i32>>,
    baz: Box<dyn StackLike<i32>>,
}

Generics

This last technique is a bit more convoluted but should be more performant that trait objects

pub struct Foo4<S1, S2>
where
    S1: StackLike<i32>,
    S2: StackLike<i32>,
{
    bar: S1,
    baz: S2,
}

We can construct this type simply by passing the necessary implementations for StackLike

let mut foo = Foo4::<
    VecStack<i32>,
    CountedStack<i32>,
>::new();

as we defined the constructor of Foo4 to use the static method defined on the StackTrait trait

pub fn new() -> Self {
    Foo4 {
        bar: S1::new(),
        baz: S2::new(),
    }
}

Notes

1. A method on a trait is called static if it is a function that doesn't take self as first parameter. The difference is that one can be called directly on the type like MyStack::new(...) and is mostly just a function in a special namespace while methods need an instance of that type to be used as in my_stack.my_push(...).

2. In Rust there is the concept of object safety for traits, only this kind of traits can be used as dyn Trait. For example static methods are not object safe, we can explicitly mark methods we do not want by appending where Self: Sized as we did int the definition of StackLike::new

```rs
pub trait StackLike<T: Clone + PartialEq> {
    fn new() -> Self
    where
        Self: Sized;
    ...
}
```

example.rs

#![allow(dead_code)]

///
/// Library Code
///
pub mod library {

    ///
    /// A stack-like trait.
    ///

    pub trait StackLike<T: Clone + PartialEq> {
        fn new() -> Self
        where
            Self: Sized;

        fn my_push(&mut self, value: T);
        fn my_pop(&mut self) -> Option<T>;
    }

    /// A stack backed by a vector.
    pub struct VecStack<T>(Vec<T>);

    impl<T: Clone + PartialEq> StackLike<T> for VecStack<T> {
        fn new() -> Self {
            VecStack(Vec::new())
        }

        fn my_push(&mut self, value: T) {
            self.0.push(value);
        }

        fn my_pop(&mut self) -> Option<T> {
            self.0.pop()
        }
    }

    /// A stack that deduplicates consecutive equal elements.
    pub struct CountedStack<T>(Vec<(usize, T)>);

    impl<T: Clone + PartialEq> StackLike<T> for CountedStack<T> {
        fn new() -> Self {
            CountedStack(Vec::new())
        }

        fn my_push(&mut self, value: T) {
            if let Some((_, last)) = self.0.last_mut() {
                if last == &value {
                    let (count, _) = self.0.pop().unwrap();
                    self.0.push((count + 1, value));
                    return;
                }
            }
            self.0.push((1, value));
        }

        fn my_pop(&mut self) -> Option<T> {
            if let Some((count, value)) = self.0.last_mut() {
                if *count > 1 {
                    *count -= 1;
                    return Some(value.clone());
                }
            }
            self.0.pop().map(|(_, value)| value)
        }
    }
}

///
/// Client Code
///
mod client {
    use super::library::{CountedStack, StackLike, VecStack};

    //
    // With duplication
    //

    pub struct Foo1 {
        bar: VecStack<i32>,
        baz: CountedStack<i32>,
    }

    pub struct Foo2 {
        bar: CountedStack<i32>,
        baz: CountedStack<i32>,
    }

    //
    // Without duplication, using trait objects
    //

    pub struct Foo3 {
        bar: Box<dyn StackLike<i32>>,
        baz: Box<dyn StackLike<i32>>,
    }

    fn example_1() {
        let mut foo = Foo3 {
            bar: Box::new(VecStack::new()),
            baz: Box::new(CountedStack::new()),
        };

        foo.bar.my_push(42);
        foo.baz.my_push(42);
        foo.baz.my_push(42);

        assert_eq!(foo.bar.my_pop(), Some(42));
        assert_eq!(foo.baz.my_pop(), Some(42));
        assert_eq!(foo.baz.my_pop(), Some(42));
        assert_eq!(foo.baz.my_pop(), None);
    }

    //
    // Without duplication, using generics
    //

    pub struct Foo4<S1, S2>
    where
        S1: StackLike<i32>,
        S2: StackLike<i32>,
    {
        bar: S1,
        baz: S2,
    }

    impl<S1, S2> Foo4<S1, S2>
    where
        S1: StackLike<i32>,
        S2: StackLike<i32>,
    {
        pub fn new() -> Self {
            Foo4 {
                bar: S1::new(),
                baz: S2::new(),
            }
        }
    }

    fn example_2() {
        let mut foo = Foo4::<
            // pass the concrete types to the generic struct
            VecStack<i32>,
            CountedStack<i32>,
        >::new();

        foo.bar.my_push(42);
        foo.baz.my_push(42);
        foo.baz.my_push(42);

        assert_eq!(foo.bar.my_pop(), Some(42));
        assert_eq!(foo.baz.my_pop(), Some(42));
        assert_eq!(foo.baz.my_pop(), Some(42));
        assert_eq!(foo.baz.my_pop(), None);
    }
}