one-indexed-vec 0.2.0

A one-based (1-indexed) wrapper around Vec<T>: element at position N is accessed via vec[N].
Documentation
//! Classic algorithm implementations: Kadane, Boyer-Moore, reservoir sampling.

use crate::Vec1;

// ============================================================================
// Kadane
// ============================================================================

impl<T> Vec1<T>
where
    T: Copy + core::ops::Add<Output = T> + PartialOrd + Default,
{
    /// Maximum subarray sum, returns `(sum, start, end)` (1-based inclusive).
    ///
    /// ```rust
    /// use one_indexed_vec::vec1;
    /// let v = vec1![-2, 1, -3, 4, -1, 2, 1, -5, 4];
    /// let (s, a, b) = v.max_subarray_sum();
    /// assert_eq!(s, 6);
    /// assert_eq!(a, 4);
    /// assert_eq!(b, 7);
    /// ```
    pub fn max_subarray_sum(&self) -> (T, usize, usize) {
        if self.is_empty() {
            return (T::default(), 0, 0);
        }
        let mut best = self[1];
        let mut cur = self[1];
        let mut cur_start = 1;
        let mut best_start = 1;
        let mut best_end = 1;
        for i in 2..=self.len() {
            if cur < T::default() {
                cur = self[i];
                cur_start = i;
            } else {
                cur = cur + self[i];
            }
            if cur > best {
                best = cur;
                best_start = cur_start;
                best_end = i;
            }
        }
        (best, best_start, best_end)
    }

    /// Maximum subarray product, returns `(product, start, end)` (1-based
    /// inclusive).
    ///
    /// On ties, the earliest-starting subarray is preferred (by extending an
    /// existing run rather than starting fresh at the current index).
    ///
    /// ```rust
    /// use one_indexed_vec::vec1;
    /// let v = vec1![2, -5, -2, 4, -1];
    /// let (p, a, b) = v.max_subarray_product();
    /// assert_eq!(p, 80);
    /// assert_eq!(a, 1);
    /// assert_eq!(b, 4);
    /// ```
    pub fn max_subarray_product(&self) -> (T, usize, usize)
    where
        T: core::ops::Mul<Output = T>,
    {
        if self.is_empty() {
            return (T::default(), 0, 0);
        }

        let mut max_p = self[1];
        let mut min_p = self[1];
        let mut max_start = 1;
        let mut min_start = 1;

        let mut best = self[1];
        let mut best_start = 1;
        let mut best_end = 1;

        for i in 2..=self.len() {
            let v = self[i];

            let c1 = v;
            let c2 = max_p * v;
            let c3 = min_p * v;

            // Compute new max and its start. On ties, prefer extending an
            // existing run (max_start / min_start) over starting at i.
            let (new_max, new_max_start) = {
                let mut val = c1;
                let mut start = i;
                if c2 >= val {
                    val = c2;
                    start = max_start;
                }
                if c3 >= val {
                    val = c3;
                    start = min_start;
                }
                (val, start)
            };

            // Compute new min and its start (same tie-breaking).
            let (new_min, new_min_start) = {
                let mut val = c1;
                let mut start = i;
                if c2 <= val {
                    val = c2;
                    start = max_start;
                }
                if c3 <= val {
                    val = c3;
                    start = min_start;
                }
                (val, start)
            };

            max_p = new_max;
            max_start = new_max_start;
            min_p = new_min;
            min_start = new_min_start;

            if max_p > best {
                best = max_p;
                best_start = max_start;
                best_end = i;
            }
        }

        (best, best_start, best_end)
    }
}

// ============================================================================
// Boyer-Moore majority vote
// ============================================================================

impl<T> Vec1<T>
where
    T: Copy + PartialEq,
{
    /// Majority element (> n/2 occurrences).
    ///
    /// ```rust
    /// use one_indexed_vec::vec1;
    /// let v = vec1![1, 2, 1, 1, 3, 1, 1];
    /// assert_eq!(v.majority_element(), Some(1));
    /// ```
    pub fn majority_element(&self) -> Option<T> {
        if self.is_empty() {
            return None;
        }
        let mut cand = self[1];
        let mut count = 0i64;
        for &x in self.iter() {
            if count == 0 {
                cand = x;
                count = 1;
            } else if x == cand {
                count += 1;
            } else {
                count -= 1;
            }
        }
        let cnt = self.iter().filter(|&&x| x == cand).count();
        if cnt > self.len() / 2 { Some(cand) } else { None }
    }

    /// Elements appearing more than n/3 times.
    ///
    /// ```rust
    /// use one_indexed_vec::vec1;
    /// let v = vec1![1, 2, 1, 3, 1, 2, 2];
    /// let mut r = v.majority_elements_n3();
    /// r.as_mut_slice().sort();
    /// assert_eq!(r.as_slice(), &[1, 2]);
    /// ```
    pub fn majority_elements_n3(&self) -> Vec1<T> {
        if self.is_empty() {
            return Vec1::new();
        }
        let mut c1: Option<T> = None;
        let mut c2: Option<T> = None;
        let mut n1 = 0usize;
        let mut n2 = 0usize;
        for &x in self.iter() {
            if Some(x) == c1 {
                n1 += 1;
            } else if Some(x) == c2 {
                n2 += 1;
            } else if n1 == 0 {
                c1 = Some(x);
                n1 = 1;
            } else if n2 == 0 {
                c2 = Some(x);
                n2 = 1;
            } else {
                n1 -= 1;
                n2 -= 1;
            }
        }
        let mut result = Vec1::new();
        let thr = self.len() / 3;
        if let Some(c) = c1 {
            if self.iter().filter(|&&x| x == c).count() > thr {
                result.push(c);
            }
        }
        if let Some(c) = c2 {
            if c1 != Some(c) && self.iter().filter(|&&x| x == c).count() > thr {
                result.push(c);
            }
        }
        result
    }
}

// ============================================================================
// Reservoir sampling
// ============================================================================

impl<T> Vec1<T>
where
    T: Copy,
{
    /// Reservoir sampling of `k` elements.
    ///
    /// ```rust
    /// use one_indexed_vec::vec1;
    /// let v = vec1![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
    /// assert_eq!(v.reservoir_sample(3).len(), 3);
    /// ```
    pub fn reservoir_sample(&self, k: usize) -> Vec1<T> {
        if k == 0 || self.is_empty() {
            return Vec1::new();
        }
        let k = k.min(self.len());
        let mut res = Vec1::with_capacity(k);
        for i in 1..=k {
            res.push(self[i]);
        }
        let mut state: u64 = 0x9E37_79B9_7F4A_7C15;
        let mut next = |max: u64| -> u64 {
            state = state.wrapping_mul(6364136223846793005).wrapping_add(1442695040888963407);
            (state >> 33) % max
        };
        for i in (k + 1)..=self.len() {
            let j = next(i as u64) as usize + 1;
            if j <= k {
                res[j] = self[i];
            }
        }
        res
    }
}

// ============================================================================
// Tests
// ============================================================================

#[cfg(test)]
mod tests {
    use crate::{Vec1, vec1};

    #[test]
    fn max_subarray_sum_basic() {
        let v = vec1![-2, 1, -3, 4, -1, 2, 1, -5, 4];
        let (s, a, b) = v.max_subarray_sum();
        assert_eq!(s, 6);
        assert_eq!(a, 4);
        assert_eq!(b, 7);
    }

    #[test]
    fn max_subarray_sum_single_negative() {
        let v = vec1![-5];
        let (s, a, b) = v.max_subarray_sum();
        assert_eq!(s, -5);
        assert_eq!(a, 1);
        assert_eq!(b, 1);
    }

    #[test]
    fn max_subarray_product_basic() {
        let v: Vec1<i32> = vec1![2, -5, -2, 4, -1];
        let (p, a, b) = v.max_subarray_product();
        assert_eq!(p, 80);
        assert_eq!(a, 1);
        assert_eq!(b, 4);
    }

    #[test]
    fn max_subarray_product_simple() {
        let v: Vec1<i32> = vec1![1, 2, 3, 4];
        let (p, a, b) = v.max_subarray_product();
        assert_eq!(p, 24);
        assert_eq!(a, 1);
        assert_eq!(b, 4);
    }

    #[test]
    fn max_subarray_product_with_zero() {
        let v: Vec1<i32> = vec1![-2, 0, -3];
        let (p, a, b) = v.max_subarray_product();
        assert_eq!(p, 0);
        // Maximum product 0 can come from any subarray containing 0;
        // our tie-breaking prefers the longest run.
        assert_eq!(a, 1);
        assert_eq!(b, 2);
    }

    #[test]
    fn max_subarray_product_single() {
        let v: Vec1<i32> = vec1![5];
        let (p, a, b) = v.max_subarray_product();
        assert_eq!(p, 5);
        assert_eq!(a, 1);
        assert_eq!(b, 1);
    }

    #[test]
    fn max_subarray_product_all_negative() {
        let v: Vec1<i32> = vec1![-1, -2, -3];
        let (p, _a, _b) = v.max_subarray_product();
        // Best is single largest (least negative): 6 from [-2, -3]
        assert_eq!(p, 6);
    }

    #[test]
    fn majority_element_basic() {
        let v = vec1![1, 2, 1, 1, 3, 1, 1];
        assert_eq!(v.majority_element(), Some(1));
    }

    #[test]
    fn majority_element_none() {
        let v = vec1![1, 2, 3, 4];
        assert_eq!(v.majority_element(), None);
    }

    #[test]
    fn majority_elements_n3_basic() {
        let v = vec1![1, 2, 1, 3, 1, 2, 2];
        let mut r = v.majority_elements_n3();
        r.as_mut_slice().sort();
        assert_eq!(r.as_slice(), &[1, 2]);
    }

    #[test]
    fn majority_elements_n3_none() {
        let v = vec1![1, 2, 3];
        assert!(v.majority_elements_n3().is_empty());
    }

    #[test]
    fn reservoir_sample_len() {
        let v = vec1![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
        assert_eq!(v.reservoir_sample(3).len(), 3);
    }

    #[test]
    fn reservoir_sample_k_larger_than_len() {
        let v = vec1![1, 2, 3];
        assert_eq!(v.reservoir_sample(10).len(), 3);
    }

    #[test]
    fn reservoir_sample_zero() {
        let v = vec1![1, 2, 3];
        assert!(v.reservoir_sample(0).is_empty());
    }
}