use core::ops::{Add, Div, Mul, Sub};
#[cfg(not(feature = "std"))]
use alloc::vec::Vec;
use crate::vec1;
use crate::vec1_core::index1::Index1;
use crate::vec1_core::Vec1;
impl<T> Vec1<T>
where
T: Copy + Add<Output = T> + Default,
{
#[inline]
pub fn prefix_sum(&self) -> Vec1<T> {
self.prefix_sum_with(T::default())
}
#[inline]
pub fn prefix_sum_with(&self, identity: T) -> Vec1<T> {
let mut out = Vec1::with_capacity(self.len());
let mut acc = identity;
for &x in self.iter() {
acc = acc + x;
out.push(acc);
}
out
}
#[inline]
pub fn sum(&self) -> T {
self.sum_with(T::default())
}
#[inline]
pub fn sum_with(&self, identity: T) -> T {
let mut acc = identity;
for &x in self.iter() {
acc = acc + x;
}
acc
}
#[inline]
pub fn cumulative_product(&self) -> Vec1<T>
where
T: Mul<Output = T>,
{
let mut out = Vec1::with_capacity(self.len());
let mut acc = T::default();
let mut first = true;
for &x in self.iter() {
if first {
acc = x;
first = false;
} else {
acc = acc * x;
}
out.push(acc);
}
out
}
}
impl<T> Vec1<T>
where
T: Copy + Mul<Output = T> + From<u8>,
{
#[inline]
pub fn product(&self) -> T {
self.product_with(T::from(1))
}
#[inline]
pub fn product_with(&self, identity: T) -> T {
let mut acc = identity;
for &x in self.iter() {
acc = acc * x;
}
acc
}
}
impl<T> Vec1<T>
where
T: Copy + Add<Output = T> + Mul<Output = T> + Default,
{
#[inline]
pub fn dot_product(&self, other: &Vec1<T>) -> T {
assert_eq!(
self.len(),
other.len(),
"dot_product: length mismatch (self {}, other {})",
self.len(),
other.len()
);
let mut acc = T::default();
for (&x, &y) in self.iter().zip(other.iter()) {
acc = acc + x * y;
}
acc
}
#[inline]
pub fn dot_product_upto(&self, other: &Vec1<T>, i: usize) -> T {
assert!(i >= 1, "dot_product_upto: index i must be >= 1 (got {})", i);
assert!(
i <= self.len(),
"dot_product_upto: index i ({}) exceeds self length ({})",
i,
self.len()
);
assert!(
i <= other.len(),
"dot_product_upto: index i ({}) exceeds other length ({})",
i,
other.len()
);
let mut acc = T::default();
for idx in 1..=i {
acc = acc + self[idx] * other[idx];
}
acc
}
#[inline]
pub fn dot_product_upto_index1(&self, other: &Vec1<T>, i: Index1) -> T {
self.dot_product_upto(other, i.get())
}
#[inline]
pub fn dot_product_range(&self, other: &Vec1<T>, start: usize, end: usize) -> T {
assert!(start >= 1, "dot_product_range: start must be >= 1 (got {})", start);
assert!(end >= 1, "dot_product_range: end must be >= 1 (got {})", end);
assert!(
start <= end,
"dot_product_range: start ({}) must be <= end ({})",
start,
end
);
assert!(
end <= self.len(),
"dot_product_range: end ({}) exceeds self length ({})",
end,
self.len()
);
assert!(
end <= other.len(),
"dot_product_range: end ({}) exceeds other length ({})",
end,
other.len()
);
let mut acc = T::default();
for idx in start..=end {
acc = acc + self[idx] * other[idx];
}
acc
}
#[inline]
pub fn dot_product_range_index1(
&self,
other: &Vec1<T>,
start: Index1,
end: Index1,
) -> T {
self.dot_product_range(other, start.get(), end.get())
}
}
impl<T> Vec1<T>
where
T: Copy + PartialOrd + Default,
{
#[inline]
pub fn any_non_positive(&self) -> bool {
let zero = T::default();
self.iter().any(|&x| x <= zero)
}
#[inline]
pub fn all_non_positive(&self) -> bool {
let zero = T::default();
self.iter().all(|&x| x <= zero)
}
#[inline]
pub fn has_non_positive(&self) -> bool {
self.any_non_positive()
}
}
impl<T> Vec1<T>
where
T: Copy,
{
#[inline]
pub fn window(&self, start: usize, end: usize) -> Vec1<T> {
assert!(start >= 1, "window: start must be >= 1 (got {})", start);
assert!(end >= 1, "window: end must be >= 1 (got {})", end);
assert!(start <= end, "window: start ({}) must be <= end ({})", start, end);
assert!(
end <= self.len(),
"window: end ({}) exceeds length ({})",
end,
self.len()
);
let mut out = Vec1::with_capacity(end - start + 1);
for idx in start..=end {
out.push(self[idx]);
}
out
}
#[inline]
pub fn window_mut(&mut self, start: usize, end: usize) -> WindowMut<'_, T> {
assert!(start >= 1, "window_mut: start must be >= 1 (got {})", start);
assert!(end >= 1, "window_mut: end must be >= 1 (got {})", end);
assert!(start <= end, "window_mut: start ({}) must be <= end ({})", start, end);
assert!(
end <= self.len(),
"window_mut: end ({}) exceeds length ({})",
end,
self.len()
);
WindowMut::new(self, start, end)
}
#[inline]
pub fn window_index1(&self, start: Index1, end: Index1) -> Vec1<T> {
self.window(start.get(), end.get())
}
#[inline]
pub fn window_mut_index1(&mut self, start: Index1, end: Index1) -> WindowMut<'_, T> {
self.window_mut(start.get(), end.get())
}
#[inline]
pub fn window_view(&self, start: usize, end: usize) -> &[T] {
assert!(start >= 1, "window_view: start must be >= 1 (got {})", start);
assert!(end >= 1, "window_view: end must be >= 1 (got {})", end);
assert!(start <= end, "window_view: start ({}) must be <= end ({})", start, end);
assert!(
end <= self.len(),
"window_view: end ({}) exceeds length ({})",
end,
self.len()
);
&self.as_slice()[(start - 1)..end]
}
}
pub struct WindowMut<'a, T> {
inner: &'a mut Vec1<T>,
start: usize,
end: usize,
}
impl<'a, T> WindowMut<'a, T> {
#[inline]
pub(crate) fn new(inner: &'a mut Vec1<T>, start: usize, end: usize) -> Self {
WindowMut { inner, start, end }
}
#[inline]
pub fn len(&self) -> usize {
self.end - self.start + 1
}
#[inline]
pub fn is_empty(&self) -> bool {
self.len() == 0
}
#[inline]
pub fn as_slice(&self) -> &[T] {
&self.inner.as_slice()[(self.start - 1)..self.end]
}
#[inline]
pub fn as_mut_slice(&mut self) -> &mut [T] {
&mut self.inner.as_mut_slice()[(self.start - 1)..self.end]
}
}
impl<'a, T> core::ops::Index<usize> for WindowMut<'a, T> {
type Output = T;
#[inline]
fn index(&self, index: usize) -> &Self::Output {
assert!(index >= 1, "WindowMut: index must be >= 1");
assert!(index <= self.len(), "WindowMut: index out of bounds");
&self.inner[self.start + index - 1]
}
}
impl<'a, T> core::ops::IndexMut<usize> for WindowMut<'a, T> {
#[inline]
fn index_mut(&mut self, index: usize) -> &mut Self::Output {
assert!(index >= 1, "WindowMut: index must be >= 1");
assert!(index <= self.len(), "WindowMut: index out of bounds");
&mut self.inner[self.start + index - 1]
}
}
impl<'a, T> AsRef<[T]> for WindowMut<'a, T> {
#[inline]
fn as_ref(&self) -> &[T] {
self.as_slice()
}
}
impl<'a, T> AsMut<[T]> for WindowMut<'a, T> {
#[inline]
fn as_mut(&mut self) -> &mut [T] {
self.as_mut_slice()
}
}
impl<T> Vec1<T>
where
T: Copy + Add<Output = T> + Sub<Output = T> + Default,
{
#[inline]
pub fn finite_difference(&self) -> Vec1<T> {
if self.len() < 2 {
return Vec1::new();
}
let mut out = Vec1::with_capacity(self.len() - 1);
for i in 1..self.len() {
out.push(self[i + 1] - self[i]);
}
out
}
#[inline]
pub fn second_finite_difference(&self) -> Vec1<T> {
if self.len() < 3 {
return Vec1::new();
}
let mut out = Vec1::with_capacity(self.len() - 2);
for i in 1..=self.len() - 2 {
out.push(self[i + 2] - self[i + 1] - self[i + 1] + self[i]);
}
out
}
#[inline]
pub fn moving_average(&self, n: usize) -> Vec1<T>
where
T: Div<Output = T> + From<u8>,
{
assert!(n > 0, "moving_average: window size must be > 0");
if self.len() < n {
return Vec1::new();
}
let factor = T::from(n as u8);
let mut out = Vec1::with_capacity(self.len() - n + 1);
for start in 1..=self.len() - n + 1 {
let sum: T = self
.window(start, start + n - 1)
.iter()
.fold(T::default(), |acc, &x| acc + x);
out.push(sum / factor);
}
out
}
}
impl<T> Vec1<T>
where
T: Copy
+ Add<Output = T>
+ Mul<Output = T>
+ Sub<Output = T>
+ Div<Output = T>
+ Default
+ From<u8>,
{
#[inline]
pub fn central_difference(&self) -> Vec1<T> {
if self.len() < 3 {
return Vec1::new();
}
let two = T::from(2u8);
let mut out = Vec1::with_capacity(self.len() - 2);
for i in 2..self.len() {
out.push((self[i + 1] - self[i - 1]) / two);
}
out
}
}
pub struct Windows<'a, T> {
inner: &'a Vec1<T>,
start: usize,
end: usize,
}
impl<'a, T> Windows<'a, T> {
#[inline]
pub(crate) fn new(inner: &'a Vec1<T>, window_size: usize) -> Self {
Windows {
inner,
start: 1,
end: window_size,
}
}
}
impl<'a, T> Iterator for Windows<'a, T> {
type Item = &'a [T];
#[inline]
fn next(&mut self) -> Option<Self::Item> {
if self.end > self.inner.len() {
return None;
}
let slice = &self.inner.as_slice()[(self.start - 1)..self.end];
self.start += 1;
self.end += 1;
Some(slice)
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
let remaining = self.inner.len().saturating_sub(self.end - 1);
(remaining, Some(remaining))
}
}
impl<'a, T> ExactSizeIterator for Windows<'a, T> {}
pub struct WindowsMut<'a, T> {
inner: *mut Vec1<T>,
start: usize,
end: usize,
_marker: core::marker::PhantomData<&'a mut T>,
}
impl<'a, T> WindowsMut<'a, T> {
#[inline]
pub(crate) fn new(inner: &'a mut Vec1<T>, window_size: usize) -> Self {
WindowsMut {
inner: inner as *mut Vec1<T>,
start: 1,
end: window_size,
_marker: core::marker::PhantomData,
}
}
}
impl<'a, T> Iterator for WindowsMut<'a, T> {
type Item = &'a mut [T];
#[inline]
fn next(&mut self) -> Option<Self::Item> {
let len = unsafe { (*self.inner).len() };
if self.end > len {
return None;
}
let start_idx = self.start - 1;
let end_idx = self.end;
let slice = unsafe {
let ptr = (*self.inner).as_mut_ptr();
core::slice::from_raw_parts_mut(ptr.add(start_idx), end_idx - start_idx)
};
self.start += 1;
self.end += 1;
Some(unsafe { core::mem::transmute(slice) })
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
let len = unsafe { (*self.inner).len() };
let remaining = len.saturating_sub(self.end - 1);
(remaining, Some(remaining))
}
}
impl<'a, T> ExactSizeIterator for WindowsMut<'a, T> {}
impl<T> Vec1<T> {
#[inline]
pub fn windows(&self, window_size: usize) -> Windows<'_, T> {
assert!(window_size > 0, "windows: window_size must be > 0");
Windows::new(self, window_size)
}
#[inline]
pub fn windows_mut(&mut self, window_size: usize) -> WindowsMut<'_, T> {
assert!(window_size > 0, "windows_mut: window_size must be > 0");
WindowsMut::new(self, window_size)
}
}
pub struct PrefixSumView<'a, T> {
inner: &'a Vec1<T>,
cumulative: Vec1<T>,
}
impl<'a, T> PrefixSumView<'a, T>
where
T: Copy + Add<Output = T> + Default,
{
#[inline]
pub(crate) fn new(inner: &'a Vec1<T>) -> Self {
let cumulative = inner.prefix_sum();
PrefixSumView { inner, cumulative }
}
#[inline]
pub fn get(&self, i: usize) -> T {
assert!(i >= 1, "PrefixSumView: index must be >= 1");
assert!(i <= self.inner.len(), "PrefixSumView: index out of bounds");
self.cumulative[i]
}
#[inline]
pub fn range_sum(&self, start: usize, end: usize) -> T
where
T: Sub<Output = T>,
{
assert!(start >= 1, "PrefixSumView: start must be >= 1");
assert!(end >= start, "PrefixSumView: end must be >= start");
assert!(end <= self.inner.len(), "PrefixSumView: end out of bounds");
if start == 1 {
self.get(end)
} else {
self.get(end) - self.get(start - 1)
}
}
#[inline]
pub fn total_sum(&self) -> T {
if self.inner.is_empty() {
T::default()
} else {
self.cumulative[self.inner.len()]
}
}
}
impl<T> Vec1<T>
where
T: Copy + Add<Output = T> + Default,
{
#[inline]
pub fn prefix_sum_view(&self) -> PrefixSumView<'_, T> {
PrefixSumView::new(self)
}
#[inline]
pub fn cumsum_alloc(&self) -> Vec1<T> {
self.prefix_sum()
}
}
impl<T> Vec1<T> {
#[inline]
pub fn shrink_to_fit_if(&mut self, factor: usize) {
if factor == 0 {
self.shrink_to_fit();
return;
}
let len = self.len();
let cap = self.capacity();
if cap > len * factor {
self.shrink_to_fit();
}
}
#[inline]
pub fn shrink_to_fit_if_excess(&mut self, threshold: usize) {
let len = self.len();
let cap = self.capacity();
if cap > len && cap - len > threshold {
self.shrink_to_fit();
}
}
#[inline]
pub fn ensure_capacity(&mut self, min_capacity: usize) -> usize {
if self.capacity() < min_capacity {
self.reserve(min_capacity - self.capacity());
}
self.capacity()
}
}
impl<T> Vec1<T>
where
T: Copy + PartialEq,
{
#[inline]
pub fn find_first(&self, value: &T) -> Option<usize> {
self.iter().position(|x| x == value).map(|p| p + 1)
}
#[inline]
pub fn find_last(&self, value: &T) -> Option<usize> {
self.iter().rposition(|x| x == value).map(|p| p + 1)
}
}
impl<T> Vec1<T>
where
T: Copy + Add<Output = T> + Default,
{
#[inline]
pub fn mean(&self) -> T
where
T: Div<Output = T> + From<u8>,
{
if self.is_empty() {
T::default()
} else {
self.sum() / T::from(self.len() as u8)
}
}
#[inline]
pub fn variance(&self) -> T
where
T: Div<Output = T> + From<u8> + Sub<Output = T> + Mul<Output = T>,
{
if self.len() < 2 {
return T::default();
}
let m = self.mean();
let sq = self.iter().fold(T::default(), |acc, &x| {
let d = x - m;
acc + d * d
});
sq / T::from(self.len() as u8)
}
#[inline]
pub fn std_dev(&self) -> T
where
T: Div<Output = T> + From<u8> + Sub<Output = T> + Mul<Output = T>,
f64: From<T>,
T: From<f64>,
{
if self.len() < 2 {
return T::default();
}
let v = self.variance();
let vf: f64 = v.into();
T::from(vf.sqrt())
}
}
impl<T> Vec1<T>
where
T: Copy + PartialOrd + Default,
{
#[inline]
pub fn sliding_window_max(&self, n: usize) -> Vec1<T> {
assert!(n > 0, "sliding_window_max: window size must be > 0");
if self.len() < n {
return Vec1::new();
}
let mut result = Vec1::with_capacity(self.len() - n + 1);
let mut deque: Vec<usize> = Vec::with_capacity(n);
for i in 1..=self.len() {
if let Some(&front) = deque.first() {
if front + n <= i {
deque.remove(0);
}
}
while let Some(&last) = deque.last() {
if self[last] <= self[i] {
deque.pop();
} else {
break;
}
}
deque.push(i);
if i >= n {
result.push(self[deque[0]]);
}
}
result
}
#[inline]
pub fn sliding_window_min(&self, n: usize) -> Vec1<T> {
assert!(n > 0, "sliding_window_min: window size must be > 0");
if self.len() < n {
return Vec1::new();
}
let mut result = Vec1::with_capacity(self.len() - n + 1);
let mut deque: Vec<usize> = Vec::with_capacity(n);
for i in 1..=self.len() {
if let Some(&front) = deque.first() {
if front + n <= i {
deque.remove(0);
}
}
while let Some(&last) = deque.last() {
if self[last] >= self[i] {
deque.pop();
} else {
break;
}
}
deque.push(i);
if i >= n {
result.push(self[deque[0]]);
}
}
result
}
}
impl<T> Vec1<T>
where
T: Copy + Ord + Default,
{
#[inline]
pub fn sliding_window_median(&self, n: usize) -> Vec1<T> {
assert!(n > 0, "sliding_window_median: window size must be > 0");
if self.len() < n {
return Vec1::new();
}
let mut result = Vec1::with_capacity(self.len() - n + 1);
let mut buf: Vec<T> = Vec::with_capacity(n);
for start in 1..=self.len() - n + 1 {
buf.clear();
for i in start..start + n {
buf.push(self[i]);
}
buf.sort();
result.push(buf[(n - 1) / 2]);
}
result
}
}
impl Vec1<f64> {
#[inline]
pub fn ewma(&self, alpha: f64) -> Vec1<f64> {
assert!(alpha > 0.0 && alpha <= 1.0, "ewma: alpha must be in (0, 1]");
if self.is_empty() {
return Vec1::new();
}
let mut result = Vec1::with_capacity(self.len());
let mut e = self[1];
result.push(e);
for i in 2..=self.len() {
e = alpha * self[i] + (1.0 - alpha) * e;
result.push(e);
}
result
}
#[inline]
pub fn ewma_with_initial(&self, alpha: f64, initial: f64) -> Vec1<f64> {
assert!(
alpha > 0.0 && alpha <= 1.0,
"ewma_with_initial: alpha must be in (0, 1]"
);
if self.is_empty() {
return Vec1::new();
}
let mut result = Vec1::with_capacity(self.len());
let mut e = alpha * self[1] + (1.0 - alpha) * initial;
result.push(e);
for i in 2..=self.len() {
e = alpha * self[i] + (1.0 - alpha) * e;
result.push(e);
}
result
}
}
impl<T> Vec1<T>
where
T: Copy,
{
#[inline]
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
}
}
impl<T> Vec1<T>
where
T: Copy + Add<Output = T> + PartialOrd + Default,
{
#[inline]
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)
}
#[inline]
pub fn max_subarray_product(&self) -> (T, usize, usize)
where
T: 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 best = self[1];
let mut best_start = 1;
let mut best_end = 1;
let mut cur_start = 1;
for i in 2..=self.len() {
let v = self[i];
let c1 = v;
let c2 = max_p * v;
let c3 = min_p * v;
let new_max = *[c1, c2, c3]
.iter()
.max_by(|a, b| a.partial_cmp(b).unwrap())
.unwrap();
let new_min = *[c1, c2, c3]
.iter()
.min_by(|a, b| a.partial_cmp(b).unwrap())
.unwrap();
if new_max == v {
cur_start = i;
}
if new_max > best {
best = new_max;
best_start = cur_start;
best_end = i;
}
max_p = new_max;
min_p = new_min;
}
(best, best_start, best_end)
}
}
impl<T> Vec1<T>
where
T: Copy + PartialEq,
{
#[inline]
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
}
}
#[inline]
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
}
}
impl<T> Vec1<T>
where
T: Copy + Add<Output = T> + Mul<Output = T> + Default,
{
#[inline]
pub fn convolve(&self, other: &Vec1<T>) -> Vec1<T> {
if self.is_empty() || other.is_empty() {
return Vec1::new();
}
let n = self.len();
let m = other.len();
let mut out = Vec1::with_capacity(n + m - 1);
for k in 1..=n + m - 1 {
let mut acc = T::default();
let lo = if k > m { k - m + 1 } else { 1 };
let hi = k.min(n);
for i in lo..=hi {
acc = acc + self[i] * other[k - i + 1];
}
out.push(acc);
}
out
}
#[inline]
pub fn cross_correlate(&self, other: &Vec1<T>) -> Vec1<T> {
if self.is_empty() || other.is_empty() {
return Vec1::new();
}
let mut rev = Vec1::with_capacity(other.len());
for i in (1..=other.len()).rev() {
rev.push(other[i]);
}
self.convolve(&rev)
}
}
impl Vec1<f64> {
#[inline]
pub fn min_max_normalize(&self) -> Vec1<f64> {
if self.is_empty() {
return Vec1::new();
}
let mut min_v = self[1];
let mut max_v = self[1];
for i in 2..=self.len() {
if self[i] < min_v {
min_v = self[i];
}
if self[i] > max_v {
max_v = self[i];
}
}
let range = max_v - min_v;
let mut out = Vec1::with_capacity(self.len());
if range == 0.0 {
for _ in 1..=self.len() {
out.push(0.5);
}
return out;
}
for i in 1..=self.len() {
out.push((self[i] - min_v) / range);
}
out
}
#[inline]
pub fn z_score_normalize(&self) -> Vec1<f64> {
if self.len() < 2 {
let mut out = Vec1::with_capacity(self.len());
for _ in 1..=self.len() {
out.push(0.0);
}
return out;
}
let mean = self.mean();
let sd = self.std_dev();
let mut out = Vec1::with_capacity(self.len());
if sd == 0.0 {
for _ in 1..=self.len() {
out.push(0.0);
}
return out;
}
for i in 1..=self.len() {
out.push((self[i] - mean) / sd);
}
out
}
}
impl<T> Vec1<T>
where
T: Copy + PartialEq + Default,
{
#[inline]
pub fn forward_fill(&self) -> Vec1<T> {
let mut out = Vec1::with_capacity(self.len());
let mut last = T::default();
let mut found = false;
for i in 1..=self.len() {
if self[i] != T::default() {
last = self[i];
found = true;
}
out.push(if found { last } else { self[i] });
}
out
}
#[inline]
pub fn backward_fill(&self) -> Vec1<T> {
if self.is_empty() {
return Vec1::new();
}
let mut out = vec1![T::default(); self.len()];
let mut next = T::default();
let mut found = false;
for i in (1..=self.len()).rev() {
if self[i] != T::default() {
next = self[i];
found = true;
}
out[i] = if found { next } else { self[i] };
}
out
}
#[inline]
pub fn linear_interpolate(&self) -> Vec1<f64>
where
T: Into<f64>,
{
if self.is_empty() {
return Vec1::new();
}
let mut known: Vec<(usize, f64)> = Vec::new();
for i in 1..=self.len() {
if self[i] != T::default() {
known.push((i, self[i].into()));
}
}
if known.is_empty() {
return vec1![0.0; self.len()];
}
let mut out = vec1![0.0; self.len()];
if known.len() == 1 {
let v = known[0].1;
for i in 1..=self.len() {
out[i] = v;
}
return out;
}
let (fi, fv) = known[0];
for i in 1..fi {
out[i] = fv;
}
out[fi] = fv;
for w in known.windows(2) {
let (i1, v1) = w[0];
let (i2, v2) = w[1];
for i in i1..=i2 {
let frac = (i - i1) as f64 / (i2 - i1) as f64;
out[i] = v1 + frac * (v2 - v1);
}
}
let (li, lv) = known[known.len() - 1];
for i in li..=self.len() {
out[i] = lv;
}
out
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::vec1;
#[test]
fn prefix_sum_basic() {
let v = vec1![1, 2, 3, 4];
let ps = v.prefix_sum();
assert_eq!(ps.as_slice(), &[1, 3, 6, 10]);
}
#[test]
fn prefix_sum_empty() {
let v: Vec1<i32> = Vec1::new();
assert!(v.prefix_sum().is_empty());
}
#[test]
fn prefix_sum_with_identity() {
let v = vec1![1, 2, 3];
assert_eq!(v.prefix_sum_with(100).as_slice(), &[101, 103, 106]);
}
#[test]
fn cumulative_product_basic() {
let v = vec1![2, 3, 4];
assert_eq!(v.cumulative_product().as_slice(), &[2, 6, 24]);
}
#[test]
fn sum_product() {
let v = vec1![1, 2, 3, 4];
assert_eq!(v.sum(), 10);
assert_eq!(v.sum_with(100), 110);
let v = vec1![2, 3, 4];
assert_eq!(v.product(), 24);
assert_eq!(v.product_with(0), 0);
}
#[test]
fn dot_product_basic() {
let a = vec1![1, 2, 3];
let b = vec1![4, 5, 6];
assert_eq!(a.dot_product(&b), 32);
}
#[test]
#[should_panic(expected = "length mismatch")]
fn dot_product_length_mismatch() {
let a = vec1![1, 2];
let b = vec1![1, 2, 3];
let _ = a.dot_product(&b);
}
#[test]
fn dot_product_upto_basic() {
let a = vec1![1, 2, 3, 4];
let b = vec1![5, 6, 7, 8];
assert_eq!(a.dot_product_upto(&b, 3), 38);
assert_eq!(a.dot_product_upto(&b, 1), 5);
assert_eq!(a.dot_product_upto(&b, a.len()), a.dot_product(&b));
}
#[test]
#[should_panic(expected = "index i must be >= 1")]
fn dot_product_upto_zero_panics() {
let a = vec1![1, 2, 3];
let b = vec1![4, 5, 6];
let _ = a.dot_product_upto(&b, 0);
}
#[test]
fn dot_product_range_basic() {
let a = vec1![1, 2, 3, 4, 5];
let b = vec1![6, 7, 8, 9, 10];
assert_eq!(a.dot_product_range(&b, 2, 4), 74);
}
#[test]
fn window_basic() {
let v = vec1![1, 2, 3, 4, 5];
let w = v.window(2, 4);
assert_eq!(w.as_slice(), &[2, 3, 4]);
assert_eq!(w[1], 2);
assert_eq!(w[3], 4);
}
#[test]
#[should_panic(expected = "window: start must be >= 1")]
fn window_start_zero_panics() {
let v = vec1![1, 2, 3];
let _ = v.window(0, 2);
}
#[test]
#[should_panic(expected = "window: end (4) exceeds length (3)")]
fn window_oob_panics() {
let v = vec1![1, 2, 3];
let _ = v.window(1, 4);
}
#[test]
fn window_mut_modifies_original() {
let mut v = vec1![1, 2, 3, 4, 5];
{
let mut w = v.window_mut(2, 4);
for i in 1..=w.len() {
w[i] *= 2;
}
}
assert_eq!(v.as_slice(), &[1, 4, 6, 8, 5]);
}
#[test]
fn window_view_basic() {
let v = vec1![1, 2, 3, 4, 5];
assert_eq!(v.window_view(2, 4), &[2, 3, 4]);
}
#[test]
fn windows_iterator_basic() {
let v = vec1![1, 2, 3, 4, 5];
let mut w = v.windows(3);
assert_eq!(w.next().unwrap(), &[1, 2, 3]);
assert_eq!(w.next().unwrap(), &[2, 3, 4]);
assert_eq!(w.next().unwrap(), &[3, 4, 5]);
assert!(w.next().is_none());
}
#[test]
fn windows_iterator_len() {
let v = vec1![1, 2, 3, 4];
assert_eq!(v.windows(2).len(), 3);
}
#[test]
fn windows_mut_basic() {
let mut v = vec1![1, 2, 3, 4, 5];
for w in v.windows_mut(1) {
w[0] *= 2;
}
assert_eq!(v.as_slice(), &[2, 4, 6, 8, 10]);
}
#[test]
fn finite_difference_basic() {
let v = vec1![1, 3, 6, 10];
assert_eq!(v.finite_difference().as_slice(), &[2, 3, 4]);
}
#[test]
fn second_finite_difference_basic() {
let v = vec1![1, 4, 9, 16, 25];
assert_eq!(v.second_finite_difference().as_slice(), &[2, 2, 2]);
}
#[test]
fn central_difference_basic() {
let v: Vec1<f64> = vec1![1.0, 4.0, 9.0, 16.0, 25.0];
assert_eq!(v.central_difference().as_slice(), &[4.0, 6.0, 8.0]);
}
#[test]
fn moving_average_basic() {
let v: Vec1<f64> = vec1![1.0, 2.0, 3.0, 4.0, 5.0];
assert_eq!(v.moving_average(3).as_slice(), &[2.0, 3.0, 4.0]);
}
#[test]
fn prefix_sum_view_basic() {
let v = vec1![1, 2, 3, 4, 5];
let p = v.prefix_sum_view();
assert_eq!(p.get(3), 6);
assert_eq!(p.range_sum(2, 4), 9);
assert_eq!(p.total_sum(), 15);
}
#[test]
fn prefix_sum_view_empty() {
let e: Vec1<i32> = Vec1::new();
assert_eq!(e.prefix_sum_view().total_sum(), 0);
}
#[test]
fn shrink_to_fit_if_basic() {
let mut v = Vec1::with_capacity(1000);
v.extend(vec1![1, 2, 3, 4, 5].iter().copied());
v.shrink_to_fit_if(4);
assert!(v.capacity() < 20);
}
#[test]
fn ensure_capacity_grows() {
let mut v = Vec1::new();
for i in 1..=3 {
v.push(i);
}
let old = v.capacity();
let new = v.ensure_capacity(old + 50);
assert!(new > old);
}
#[test]
fn find_first_and_last() {
let v = vec1![10, 20, 30, 20, 40];
assert_eq!(v.find_first(&20), Some(2));
assert_eq!(v.find_last(&20), Some(4));
assert_eq!(v.find_first(&50), None);
}
#[test]
fn mean_variance_std() {
let v: Vec1<f64> = vec1![1.0, 2.0, 3.0, 4.0, 5.0];
assert!((v.mean() - 3.0).abs() < 1e-10);
assert!((v.variance() - 2.0).abs() < 1e-10);
assert!((v.std_dev() - 1.41421356).abs() < 1e-6);
}
#[test]
fn non_positive_checks() {
assert!(vec1![-1, -2].all_non_positive());
assert!(vec1![-1, 5].any_non_positive());
assert!(!vec1![1, 2].any_non_positive());
}
#[test]
fn sliding_window_max_basic() {
let v = vec1![1, 3, -1, -3, 5, 3, 6, 7];
assert_eq!(v.sliding_window_max(3).as_slice(), &[3, 3, 5, 5, 6, 7]);
}
#[test]
fn sliding_window_min_basic() {
let v = vec1![1, 3, -1, -3, 5, 3, 6, 7];
assert_eq!(v.sliding_window_min(3).as_slice(), &[-1, -3, -3, -3, 3, 3]);
}
#[test]
fn sliding_window_median_basic() {
let v = vec1![1, 3, 2, 4, 5, 6, 7, 8];
assert_eq!(v.sliding_window_median(3).as_slice(), &[2, 3, 4, 5, 6, 7]);
}
#[test]
fn ewma_basic() {
let v: Vec1<f64> = vec1![1.0, 2.0, 3.0, 4.0, 5.0];
let e = v.ewma(0.3);
assert!((e[1] - 1.0).abs() < 1e-10);
assert!((e[2] - 1.3).abs() < 1e-10);
assert!((e[3] - 1.81).abs() < 1e-10);
}
#[test]
fn ewma_with_initial_basic() {
let v: Vec1<f64> = vec1![1.0, 2.0, 3.0];
let e = v.ewma_with_initial(0.5, 10.0);
assert!((e[1] - 5.5).abs() < 1e-10);
}
#[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 max_subarray_sum_basic() {
let v: Vec1<i32> = 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_product_basic() {
let v: Vec1<i32> = vec1![2, -5, -2, 4, -1];
let (p, a, b) = v.max_subarray_product();
assert_eq!(p, 40);
assert_eq!(a, 1);
assert_eq!(b, 4);
}
#[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_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 convolve_basic() {
let a = vec1![1, 2, 3];
let b = vec1![4, 5];
assert_eq!(a.convolve(&b).as_slice(), &[4, 13, 22, 15]);
}
#[test]
fn min_max_normalize_basic() {
let v: Vec1<f64> = vec1![1.0, 2.0, 3.0, 4.0, 5.0];
assert_eq!(v.min_max_normalize().as_slice(), &[0.0, 0.25, 0.5, 0.75, 1.0]);
}
#[test]
fn z_score_normalize_basic() {
let v: Vec1<f64> = vec1![1.0, 2.0, 3.0, 4.0, 5.0];
let z = v.z_score_normalize();
assert!((z[1] - (-1.41421356)).abs() < 1e-6);
assert!((z[5] - 1.41421356).abs() < 1e-6);
}
#[test]
fn forward_fill_basic() {
let v = vec1![1, 0, 0, 2, 0, 3];
assert_eq!(v.forward_fill().as_slice(), &[1, 1, 1, 2, 2, 3]);
}
#[test]
fn backward_fill_basic() {
let v = vec1![1, 0, 0, 2, 0, 3];
assert_eq!(v.backward_fill().as_slice(), &[1, 2, 2, 2, 3, 3]);
}
#[test]
fn linear_interpolate_basic() {
let v: Vec1<f64> = vec1![1.0, 0.0, 0.0, 4.0];
let r = v.linear_interpolate();
assert!((r[1] - 1.0).abs() < 1e-10);
assert!((r[2] - 2.0).abs() < 1e-10);
assert!((r[3] - 3.0).abs() < 1e-10);
assert!((r[4] - 4.0).abs() < 1e-10);
}
#[test]
fn empty_operations() {
let v: Vec1<i32> = Vec1::new();
assert_eq!(v.sum(), 0);
assert_eq!(v.product(), 1);
assert!(v.prefix_sum().is_empty());
}
}