use crate::field::{Fp, PrimeField};
use crate::profile::{Site, hit};
pub struct RowReducer {
cols: usize,
rows: Vec<Vec<Fp>>,
pivots: Vec<usize>,
}
impl RowReducer {
pub fn new(cols: usize) -> RowReducer {
RowReducer {
cols,
rows: Vec::new(),
pivots: Vec::new(),
}
}
pub fn push(&mut self, row: &[Fp], f: &PrimeField) -> bool {
hit(Site::RowReducerPush);
assert_eq!(
row.len(),
self.cols,
"push: row length vs {} columns",
self.cols
);
let mut r = row.to_vec();
for (kept, &pc) in self.rows.iter().zip(&self.pivots) {
let factor = r[pc];
if factor.is_zero() {
continue;
}
for (a, &b) in r[pc..].iter_mut().zip(&kept[pc..]) {
*a = f.sub(*a, f.mul(factor, b));
}
}
let Some(pc) = r.iter().position(|v| !v.is_zero()) else {
return false;
};
let inv = f.inv(r[pc]);
for v in &mut r[pc..] {
*v = f.mul(*v, inv);
}
let at = self.pivots.partition_point(|&c| c < pc);
self.rows.insert(at, r);
self.pivots.insert(at, pc);
true
}
accessor_methods! {
pub rank() -> usize = |this| this.pivots.len();
}
}