Asking how to write more idiomatic code - simple function

code review
1

Hi to everyone! I'm quite new to Rust and I'm looking for ways to write more idiomatic code. The following is a correct linear solution to the sliding window maximum problem:

use std::cmp::Ordering;
use std::collections::VecDeque;

#[derive(Copy, Clone, Debug, Eq)]
struct IndexValuePair(usize, i32);

impl Ord for IndexValuePair {
    fn cmp(&self, other: &Self) -> Ordering {
        (self.1).cmp(&(other.1))
    }
}

impl PartialOrd for IndexValuePair {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl PartialEq for IndexValuePair {
    fn eq(&self, other: &Self) -> bool {
        (self.1) == (other.1)
    }
}

pub fn linear(nums: &Vec<i32>, k: i32) -> Vec<i32> {
    let k = k as usize;
    let mut ret = Vec::with_capacity(nums.len() - k + 1);
    let mut deq: VecDeque<IndexValuePair> = VecDeque::with_capacity(nums.len());

    for (current_index, &current_value) in nums.iter().enumerate() {
        while !deq.is_empty()
            && deq.front().expect("something has gone wrong").0 + k <= current_index
        {
            deq.pop_front();
        }

        while !deq.is_empty() && current_value >= deq.back().expect("something has gone wrong").1 {
            deq.pop_back();
        }

        deq.push_back(IndexValuePair(current_index, current_value));

        if current_index >= k - 1 {
            ret.push(*deq.front().expect("something has gone wrong"));
        }
    }

    ret.iter().map(|cp| cp.1).collect()
}

The only constraint I have is the signature of the function that I cannot change, but any suggestion is welcome :smile:.

2

That signature is fairly strange, in fact - it's generally unreasonable to use &Vec<T>, since it's not different API-wise from &[T], but less efficient due to the double-indirection.

2 Likes
3

What is that function supposed to do ? It seems to return all items after the index k (or panic if k is larger than the slice's length). [edit, found the definition, disreguard this question)

On the idiomatic side:

while !deq.is_empty()
    && deq.front().expect("something has gone wrong").0 + k <= current_index
{
    deq.pop_front();
}

Is better written [edit: there should be a break in the else branch]:

while let Some(i) = deq.front() {
    if i.0 + k <= current_index {
        deq.pop_front();
    }
}

And you should take a slice not a vec.

1 Like
4

Is the one requested by leetcode, but I am with you on this

6

Thanks for your hint on the loop, I didn't know about it. Yes, the signature should take a slice but this is the one forced by leetcode.

7

Aren't these two loops different? The second will loop forever if some item doesn't satisfy the condition, while the original one will exit immediately.

1 Like
8

Yep... It's missing a break in the else branch I think.

9 
while let Some(i) = deq.front() {
  if i.0 + k <= current_index {
    deq.pop_front();
  } else {
    break;
  }
}

This version is correct, but dunno if I like it anymore ahah

10

It's a couple years old, but here's a summary of various exercise sites and some views on how well they present idiomatic Rust (or not). (Spoilers: Leetcode will often force you into non-idiomatic patterns.)

3 Likes
11

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.