CODEWITHSUNDEEP
rustunsignedinteger-overflowunsigned-integer
Alex Coleman
Alex Coleman

Reputation: 647

Canonical way to check for integer overflow in usize

I was trying to solve the following leetcode problem in Rust:

impl Solution {
    pub fn merge(nums1: &mut Vec<i32>, m: i32, nums2: &mut Vec<i32>, n: i32) {
        let mut backwards_idx: usize = (m + n - 1) as usize;
        let (m_size, n_size) = (m as usize, n as usize);
        let (mut m_idx, mut n_idx) = ((m-1) as usize, (n-1) as usize);
        while 0 <= m_idx && 0 <= n_idx {
            let (nums1_elem, nums2_elem) = (nums1[m_idx], nums2[n_idx]);
            if nums1_elem <= nums2_elem {
                nums1[backwards_idx] = nums2_elem;
                n_idx = n_idx - 1;
            } else {
                nums1[backwards_idx] = nums1_elem;
                m_idx = m_idx - 1;
            }
            backwards_idx = backwards_idx - 1;
        }
        while 0 <= m_idx {
            nums1[backwards_idx] = nums1[m_idx];
            m_idx = m_idx - 1;
            backwards_idx = backwards_idx - 1;
        }
        while 0 <= n_idx {
            nums1[backwards_idx] = nums2[n_idx];
            n_idx = n_idx - 1;
            backwards_idx = backwards_idx - 1;
        }
    }
}

However, this won't work, since m_size and n_size will overflow when subtracted from 0. I know this isn't canonical Rust, but since the problem is given in i32, I can't change it much.

There is the checked method, but that seems pretty hard to read instead of writing it directly it in the while loop condition. Somehow having the exit condition in the body of the while loop doesn't seem like a good idea.

Upvotes: 1

Views: 1119

Answers (2)

Ian Graham
Ian Graham

Reputation: 376

One simple way to avoid having to check for overflow is by guaranteeing that your usize types, which are only ever being subtracted by 1, are never 0 to start in those loops. Refactoring the idx types to be counts, and subtracting by 1 when we want to obtain an index, is one way to do this ...

impl Solution {
    pub fn merge(nums1: &mut Vec<i32>, m: i32, nums2: &mut Vec<i32>, n: i32) {
        let mut numbers_left: usize = (m + n) as usize;
        let (mut m_left, mut n_left) = (m as usize, n as usize);
        while m_left > 0 && n_left > 0 {
            let (nums1_elem, nums2_elem) = (nums1[m_left-1], nums2[n_left-1]);
            if nums1_elem <= nums2_elem {
                nums1[numbers_left-1] = nums2_elem;
                n_left = n_left - 1;
            } else {
                nums1[numbers_left-1] = nums1_elem;
                m_left = m_left - 1;
            }
            numbers_left = numbers_left - 1;
        }
        while m_left > 0 {
            nums1[numbers_left-1] = nums1[m_left-1];
            m_left = m_left - 1;
            numbers_left = numbers_left - 1;
        }
        while n_idx > 0 {
            nums1[numbers_left-1] = nums2[n_left-1];
            n_left = n_left - 1;
            numbers_left = numbers_left - 1;
        }
    }
}

Upvotes: 1

Todd
Todd

Reputation: 5395

A way to avoid overflow, is to structure the loops differently.... Rust doesn't have the explicit do-while syntax, but it does have loop which can you can break from, and even break out to any number of outer loops using labels.

    loop {
        nums1[backwards_idx] = nums1[m_idx];
        if m_idx == 0 { break; }
        m_idx -= 1;
        backwards_idx -= 1;
    }

Upvotes: 0

Related Questions