rusttraitsborrowing

impl push(self , item : T) for a struct with 2 Vecs<T>

I've been trying to impl the push for this struct:

struct StackMin<T: std::cmp::Ord>
{
    stack : Vec<T>,
    min : Vec<T>
}

like this:

fn push(&mut self, item: T) {
    let l = self.stack.len();
    let x: T;
    match l {
        0 => println!("There is nothing in the stack."),
        n => {
            if item <= self.stack[l - 1] {
                self.stack.push(item); //item moved here
                self.min.push(item); // so I can't use it again here
            } else {
                self.stack.push(item);
            }
        }
    }
}

The problem is item moves with the first Vec<T>::push so I can't use it immediately at the second call of push(). I thought about making a variable let a = &item and use it in the second call, but push requires "T" and not "&T".

Also, if I try to do a=self.stack[l-1], it's an error because the T type doesn't have the Copy/Clone traits.

LATER EDIT: I also need to print the last value from the min Vector. But it doesn't have the std::fmt::Display , and I don't think it can be impl!? Any ideas?

How would you approach this?

Solution

  • Assuming you can change the inner values of the struct StackMin, but not the trait requirements, you could do something like this:

    struct MinStack<T: std::cmp::Ord> {
    // T is the data you want to store
    // and usize points to the smallest T
    inner: Vec<(T, usize)>
}

impl<T: std::cmp::Ord> MinStack<T> {
    fn push(&mut self, val: T) {
        let min_index = self.inner.last()
            // get last min value and its index
            .map(|(_, index)| (&self.inner[*index].0, index))
            // check if it is smaller then the current value
            .and_then(|(prev_min, min_index)| 
                (prev_min < &val).then(|| *min_index)
            )
            // if not smaller or does not exist
            // set it to the current index
            .unwrap_or(self.inner.len());

        self.inner.push((val, min_index));
    }
}

    Here is a full implementation of the MinStack challenge Rust Playground.
    Let me know if i should clarify something in the above code.

    Docs for the used methods: