use std::collections::{BTreeMap, HashMap, HashSet};
use super::{Key, SIGNS, face_edges, face_exists, in_plane_neighbours, index};
use crate::axis::Axis;
use crate::engine::coeffs::Coefficients;
use crate::engine::fields::Fields;
use crate::engine::kernel::flush;
use crate::engine::operator::{Hooks, Operator, StepContext};
use crate::{Error, Result};
#[derive(Debug, Clone, PartialEq)]
pub struct SheetCutEdge {
pub axis: Axis,
pub node: [usize; 3],
pub cuts: Vec<f64>,
}
#[derive(Debug, Clone, PartialEq)]
pub struct SheetRegion {
pub fraction: f64,
pub pieces: Vec<(u8, u8)>,
}
#[derive(Debug, Clone, PartialEq)]
pub struct SheetCutFace {
pub axis: Axis,
pub node: [usize; 3],
pub regions: Vec<SheetRegion>,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
enum Ref {
Main(usize, [usize; 3]),
Piece(usize),
}
#[derive(Debug, Clone)]
struct PieceInfo {
ca: f64,
cb: f64,
}
#[derive(Debug, Clone)]
struct PRegion {
face: usize,
fraction: f64,
terms: Vec<(Ref, f64, Key, usize)>,
}
#[derive(Debug, Clone)]
struct PFace {
axis: Axis,
node: [usize; 3],
l: f64,
r: f64,
regions: Vec<usize>,
}
#[derive(Debug, Clone)]
pub(super) struct Prepared {
pieces: Vec<PieceInfo>,
cut: Vec<(Axis, [usize; 3], Vec<usize>)>,
faces: Vec<PFace>,
regions: Vec<PRegion>,
region_at: HashMap<(Key, Key, usize), usize>,
face_index: HashMap<Key, usize>,
}
fn face_lr(co: &Coefficients, a: Axis, k: usize, dt: f64) -> (f64, f64) {
let (da, db) = (co.da(a)[k] as f64, co.db(a)[k] as f64);
if db > 0.0 {
(dt * (1.0 + da) / (2.0 * db), (1.0 - da) / db)
} else {
(0.0, 0.0)
}
}
pub(super) fn validate(
edges: &[SheetCutEdge],
faces: &[SheetCutFace],
n: [usize; 3],
) -> Result<()> {
let bad = |what: String| Err(Error::Invalid(format!("invalid conformal sheet {what}")));
let mut cuts: HashMap<Key, usize> = HashMap::new();
for e in edges {
let a = e.axis.index();
let ok = (0..3).all(|d| e.node[d] < n[d])
&& e.node[a] + 1 < n[a]
&& !e.cuts.is_empty()
&& e.cuts.len() < 255
&& e.cuts.iter().all(|t| *t > 0.0 && *t < 1.0)
&& e.cuts.windows(2).all(|w| w[0] < w[1]);
if !ok || cuts.insert((a, index(n, e.node)), e.cuts.len()).is_some() {
return bad(format!("edge {e:?}"));
}
}
let mut listed: HashSet<Key> = HashSet::new();
for f in faces {
if !face_exists(f.axis, f.node, n)
|| f.regions.is_empty()
|| !listed.insert((f.axis.index(), index(n, f.node)))
{
return bad(format!("face {f:?}"));
}
let fe = face_edges(f.axis, f.node);
let mut seen: [Vec<bool>; 4] = core::array::from_fn(|q| {
let (a, p) = fe[q];
vec![false; cuts.get(&(a.index(), index(n, p))).map_or(1, |c| c + 1)]
});
for r in &f.regions {
if !(0.0..=1.0).contains(&r.fraction) {
return bad(format!("face {f:?}"));
}
for &(q, k) in &r.pieces {
let s = seen.get_mut(q as usize).and_then(|v| v.get_mut(k as usize));
match s {
Some(s) if !*s => *s = true,
_ => return bad(format!("face {f:?}")),
}
}
}
if seen.iter().flatten().any(|s| !s) {
return bad(format!("face {f:?} (pieces not covered)"));
}
}
for e in edges {
for (fa, q) in faces_of_edge(e.axis, e.node, n) {
if !listed.contains(&(fa.index(), index(n, q))) {
return bad(format!("edge {e:?}: face {fa:?} at {q:?} not listed"));
}
}
}
Ok(())
}
fn faces_of_edge(a: Axis, p: [usize; 3], n: [usize; 3]) -> Vec<(Axis, [usize; 3])> {
let mut v = Vec::with_capacity(4);
for f in Axis::ALL {
if f == a {
continue;
}
let o = 3 - f.index() - a.index();
if face_exists(f, p, n) {
v.push((f, p));
}
if p[o] > 0 {
let mut q = p;
q[o] -= 1;
if face_exists(f, q, n) {
v.push((f, q));
}
}
}
v
}
impl Prepared {
pub(super) fn new(
edges: &[SheetCutEdge],
faces: &[SheetCutFace],
co: &Coefficients,
n: [usize; 3],
dt: f64,
) -> Self {
let idx = |p: [usize; 3]| index(n, p);
let mut pieces = Vec::new();
let mut cut = Vec::new();
let mut cut_of: HashMap<Key, usize> = HashMap::new();
for e in edges {
let k = idx(e.node);
let (ca, cb) = (co.ca(e.axis)[k] as f64, co.cb(e.axis)[k] as f64);
let mut ids = Vec::with_capacity(e.cuts.len() + 1);
let mut last = 0.0;
for t in e.cuts.iter().copied().chain(core::iter::once(1.0)) {
ids.push(pieces.len());
pieces.push(PieceInfo {
ca,
cb: cb * (t - last),
});
last = t;
}
cut_of.insert((e.axis.index(), k), cut.len());
cut.push((e.axis, e.node, ids));
}
let mut out = Self {
pieces,
cut,
faces: Vec::new(),
regions: Vec::new(),
region_at: HashMap::new(),
face_index: HashMap::new(),
};
for f in faces {
let k = idx(f.node);
let (l, r) = face_lr(co, f.axis, k, dt);
let fi = out.faces.len();
let fe = face_edges(f.axis, f.node);
let mut ids = Vec::with_capacity(f.regions.len());
for reg in &f.regions {
let ri = out.regions.len();
let mut terms = Vec::with_capacity(reg.pieces.len());
for &(q, pk) in ®.pieces {
let (ea, ep) = fe[q as usize];
let ek = (ea.index(), idx(ep));
let v = match cut_of.get(&ek) {
Some(&c) => Ref::Piece(out.cut[c].2[pk as usize]),
None => Ref::Main(ea.index(), ep),
};
terms.push((v, SIGNS[q as usize] as f64, ek, pk as usize));
out.region_at
.insert(((f.axis.index(), k), ek, pk as usize), ri);
}
out.regions.push(PRegion {
face: fi,
fraction: reg.fraction,
terms,
});
ids.push(ri);
}
out.face_index.insert((f.axis.index(), k), fi);
out.faces.push(PFace {
axis: f.axis,
node: f.node,
l,
r,
regions: ids,
});
}
out
}
pub(super) fn seeds(&self) -> Vec<(usize, usize)> {
let mut s: Vec<(usize, usize)> = (0..self.pieces.len()).map(|p| (3, p)).collect();
for r in &self.regions {
for &(v, _, ek, _) in &r.terms {
if let Ref::Main(..) = v {
s.push(ek);
}
}
}
s
}
pub(super) fn construct(
&self,
co: &Coefficients,
n: [usize; 3],
dt: f64,
tau: f64,
exclude: &HashSet<Key>,
) -> Build {
let idx = |p: [usize; 3]| index(n, p);
let mut faces = self.faces.clone();
let mut regions = self.regions.clone();
let mut region_at = self.region_at.clone();
let mut face_index = self.face_index.clone();
let open_ref = |v: Ref| match v {
Ref::Main(a, p) => co.cb(Axis::from_index(a).expect("axis"))[idx(p)] > 0.0,
Ref::Piece(j) => self.pieces[j].cb > 0.0,
};
let frac_ref = |v: Ref, ek: Key| match v {
Ref::Main(..) => 1.0,
Ref::Piece(j) => {
let (a, k) = ek;
let full = co.cb(Axis::from_index(a).expect("axis"))[k] as f64;
if full > 0.0 {
self.pieces[j].cb / full
} else {
0.0
}
}
};
let live = |r: &PRegion| r.terms.iter().any(|t| open_ref(t.0));
let mut parent: Vec<usize> = (0..regions.len()).collect();
fn find(parent: &mut [usize], k: usize) -> usize {
let mut r = k;
while parent[r] != r {
r = parent[r];
}
let mut c = k;
while parent[c] != r {
let next = parent[c];
parent[c] = r;
c = next;
}
r
}
let small: Vec<usize> = (0..regions.len())
.filter(|&r| regions[r].fraction < tau && live(®ions[r]))
.collect();
let mut members: BTreeMap<usize, Vec<usize>> = BTreeMap::new();
let mut area: HashMap<usize, f64> = HashMap::new();
for &r in &small {
members.insert(r, vec![r]);
area.insert(r, regions[r].fraction);
}
for _pass in 0..small.len().max(1) {
let mut changed = false;
let mut done: HashSet<usize> = HashSet::new();
for &r0 in &small {
let root = find(&mut parent, r0);
let a = area.get(&root).copied().unwrap_or(1.0);
if a >= tau || !done.insert(root) {
continue;
}
let mut best: Option<((f64, f64), Target)> = None;
let mem = members.get(&root).cloned().unwrap_or_else(|| vec![root]);
for &m in &mem {
let f = &faces[regions[m].face];
let (fa, fnode) = (f.axis, f.node);
for &(v, _, ek, pk) in ®ions[m].terms {
let fp = frac_ref(v, ek);
if fp <= 0.0 || !open_ref(v) {
continue;
}
for (e, q, nb) in in_plane_neighbours(fa, fnode, n) {
if (e.index(), idx(q)) != ek {
continue;
}
let nk = (fa.index(), idx(nb));
let cand = if let Some(&ri) = region_at.get(&(nk, ek, pk)) {
if find(&mut parent, ri) == root || !live(®ions[ri]) {
continue;
}
(regions[ri].fraction, Target::Region(ri))
} else if face_index.contains_key(&nk) || exclude.contains(&nk) {
continue;
} else {
let (l, _) = face_lr(co, fa, idx(nb), dt);
let any_open = face_edges(fa, nb)
.iter()
.any(|&(a, p)| co.cb(a)[idx(p)] > 0.0);
if l <= 0.0 || !any_open {
continue;
}
(1.0, Target::Plain(fa, nb))
};
let score = (fp, cand.0);
if best.as_ref().is_none_or(|b| score > b.0) {
best = Some((score, cand.1));
}
}
}
}
let Some((_, target)) = best else {
continue;
};
let tr = match target {
Target::Region(ri) => ri,
Target::Plain(fa, nb) => {
let k = idx(nb);
let (l, r) = face_lr(co, fa, k, dt);
let fi = faces.len();
let ri = regions.len();
let mut terms = Vec::with_capacity(4);
for (q, (ea, ep)) in face_edges(fa, nb).into_iter().enumerate() {
let ek = (ea.index(), idx(ep));
terms.push((Ref::Main(ea.index(), ep), SIGNS[q] as f64, ek, 0));
region_at.insert(((fa.index(), k), ek, 0), ri);
}
regions.push(PRegion {
face: fi,
fraction: 1.0,
terms,
});
parent.push(ri);
face_index.insert((fa.index(), k), fi);
faces.push(PFace {
axis: fa,
node: nb,
l,
r,
regions: vec![ri],
});
ri
}
};
let rt = find(&mut parent, tr);
let (keep, gone) = if root < rt { (root, rt) } else { (rt, root) };
parent[gone] = keep;
let ag = area.remove(&gone).unwrap_or_else(|| regions[gone].fraction);
let ak = area.remove(&keep).unwrap_or_else(|| regions[keep].fraction);
area.insert(keep, ag + ak);
let mg = members.remove(&gone).unwrap_or_else(|| vec![gone]);
let mut mk = members.remove(&keep).unwrap_or_else(|| vec![keep]);
mk.extend(mg);
mk.sort_unstable();
members.insert(keep, mk);
changed = true;
}
if !changed {
break;
}
}
let nreg = regions.len();
let mut gid: Vec<usize> = vec![usize::MAX; nreg];
let mut classes: Vec<Vec<usize>> = Vec::new();
for r in 0..nreg {
let root = find(&mut parent, r);
if gid[root] == usize::MAX {
gid[root] = classes.len();
classes.push(Vec::new());
}
let g = gid[root];
gid[r] = g;
classes[g].push(r);
}
let mut report = SheetCounts {
edges: self.cut.len(),
faces: self.faces.len(),
..SheetCounts::default()
};
let mut groups = Vec::with_capacity(classes.len());
for members in &classes {
let (mut l, mut r) = (0.0, 0.0);
let mut terms: BTreeMap<Ref, f64> = BTreeMap::new();
for &m in members {
let reg = ®ions[m];
let f = &faces[reg.face];
let mut fr = reg.fraction;
if members.len() == 1 && fr < tau && live(reg) {
fr = tau.max(1e-6);
report.floored += 1;
}
l += fr * f.l;
r += fr * f.r;
for &(v, s, _, _) in ®.terms {
*terms.entry(v).or_insert(0.0) += s;
}
}
if members.len() > 1 {
report.merged += members.len();
}
let terms: Vec<(Ref, f64)> = terms.into_iter().filter(|t| t.1 != 0.0).collect();
let (da, db, dt_over_l) = if l > 0.0 {
let den = l + 0.5 * r * dt;
((l - 0.5 * r * dt) / den, dt / den, dt / l)
} else {
(0.0, 0.0, 0.0)
};
groups.push(SGroup {
terms,
writes: Vec::new(),
da,
db,
l,
dt_over_l,
i: 0.0,
});
}
report.groups = groups.len();
let mut corrections = Vec::new();
let mut owned = HashSet::new();
for f in &faces {
owned.insert((f.axis.index(), idx(f.node)));
let primary = *f
.regions
.iter()
.min_by(|&&a, &&b| {
regions[b]
.fraction
.total_cmp(®ions[a].fraction)
.then(a.cmp(&b))
})
.expect("a region");
let gp = gid[primary];
groups[gp].writes.push((f.axis, f.node));
for &r in &f.regions {
let gr = gid[r];
if gr == gp {
continue;
}
for &(v, s, _, _) in ®ions[r].terms {
if let Ref::Main(a, p) = v {
let axis = Axis::from_index(a).expect("axis");
let cb = co.cb(axis)[idx(p)] as f64;
if cb > 0.0 {
corrections.push(Correction {
axis,
node: p,
cbs: cb * s,
region: gr,
primary: gp,
});
}
}
}
}
}
let mut inc: Vec<BTreeMap<usize, f64>> = vec![BTreeMap::new(); self.pieces.len()];
for (r, reg) in regions.iter().enumerate() {
for &(v, s, _, _) in ®.terms {
if let Ref::Piece(j) = v {
*inc[j].entry(gid[r]).or_insert(0.0) += s;
}
}
}
let pieces = self
.pieces
.iter()
.zip(inc)
.map(|(p, inc)| Piece {
ca: p.ca,
cb: p.cb,
cap: if p.cb > 0.0 {
dt * (1.0 + p.ca) / (2.0 * p.cb)
} else {
0.0
},
u: 0.0,
inc: inc.into_iter().filter(|t| t.1 != 0.0).collect(),
})
.collect();
Build {
op: ConformalSheets {
pieces,
cut: self.cut.clone(),
groups,
corrections,
energy: 0.0,
},
owned,
report,
}
}
}
enum Target {
Region(usize),
Plain(Axis, [usize; 3]),
}
#[derive(Debug, Clone, Copy, Default, PartialEq)]
pub(super) struct SheetCounts {
pub edges: usize,
pub faces: usize,
pub groups: usize,
pub merged: usize,
pub floored: usize,
}
pub(super) struct Build {
pub op: ConformalSheets,
pub owned: HashSet<Key>,
pub report: SheetCounts,
}
impl Build {
pub(super) fn apply_coefficients(&self, co: &mut Coefficients, n: [usize; 3]) {
for (a, p, _) in &self.op.cut {
let (ca, cb) = co.e_mut(*a);
let k = index(n, *p);
ca[k] = 0.0;
cb[k] = 0.0;
}
for &(a, k) in &self.owned {
let (da, db) = co.h_mut(Axis::from_index(a).expect("axis"));
da[k] = 1.0;
db[k] = 0.0;
}
}
pub(super) fn stability_terms(&self, n: [usize; 3]) -> (Vec<super::GroupTerms>, Vec<f64>) {
let g = self
.op
.groups
.iter()
.filter(|g| g.l > 0.0)
.map(|g| {
(
g.dt_over_l,
g.terms
.iter()
.map(|&(v, s)| match v {
Ref::Main(a, p) => (a, index(n, p), s),
Ref::Piece(j) => (3, j, s),
})
.collect(),
)
})
.collect();
let sq = self
.op
.pieces
.iter()
.map(|p| p.cb.max(0.0).sqrt())
.collect();
(g, sq)
}
}
#[derive(Debug, Clone, PartialEq)]
struct Piece {
ca: f64,
cb: f64,
cap: f64,
u: f64,
inc: Vec<(usize, f64)>,
}
#[derive(Debug, Clone, PartialEq)]
struct SGroup {
terms: Vec<(Ref, f64)>,
writes: Vec<(Axis, [usize; 3])>,
da: f64,
db: f64,
l: f64,
dt_over_l: f64,
i: f64,
}
#[derive(Debug, Clone, PartialEq)]
struct Correction {
axis: Axis,
node: [usize; 3],
cbs: f64,
region: usize,
primary: usize,
}
#[derive(Debug, Clone, PartialEq)]
pub struct ConformalSheets {
pieces: Vec<Piece>,
cut: Vec<(Axis, [usize; 3], Vec<usize>)>,
groups: Vec<SGroup>,
corrections: Vec<Correction>,
energy: f64,
}
impl ConformalSheets {
pub fn pieces(&self) -> usize {
self.pieces.len()
}
pub fn currents(&self) -> usize {
self.groups.len()
}
fn voltage(&self, v: Ref, f: &Fields<'_>) -> f64 {
match v {
Ref::Main(a, p) => f.u.get(Axis::from_index(a).expect("axis"), p) as f64,
Ref::Piece(j) => self.pieces[j].u,
}
}
fn circulation(&self, g: &SGroup, f: &Fields<'_>) -> f64 {
g.terms.iter().map(|&(v, s)| s * self.voltage(v, f)).sum()
}
}
impl Operator for ConformalSheets {
fn hooks(&self) -> Hooks {
Hooks::POST_H | Hooks::POST_E
}
fn post_h(&mut self, f: &mut Fields<'_>, _ctx: &StepContext<'_>) {
for q in 0..self.groups.len() {
let c = self.circulation(&self.groups[q], f);
let g = &mut self.groups[q];
g.i = flush((g.da * g.i - g.db * c) as f32) as f64;
for &(a, p) in &g.writes {
f.i.set(a, p, g.i as f32);
}
}
}
fn post_e(&mut self, f: &mut Fields<'_>, _ctx: &StepContext<'_>) {
for c in &self.corrections {
let d = c.cbs * (self.groups[c.region].i - self.groups[c.primary].i);
let u = f.u.get_mut(c.axis, c.node);
*u = flush((*u as f64 + d) as f32);
}
for p in &mut self.pieces {
let s: f64 = p.inc.iter().map(|&(g, s)| s * self.groups[g].i).sum();
p.u = flush((p.ca * p.u + p.cb * s) as f32) as f64;
}
for (a, node, ids) in &self.cut {
let s: f64 = ids.iter().map(|&j| self.pieces[j].u).sum();
f.u.set(*a, *node, s as f32);
}
let mut w: f64 = self.pieces.iter().map(|p| 0.5 * p.cap * p.u * p.u).sum();
for g in &self.groups {
if g.l > 0.0 {
let next = flush((g.da * g.i - g.db * self.circulation(g, f)) as f32) as f64;
w += 0.5 * g.l * g.i * next;
}
}
self.energy = w;
}
fn energy(&self) -> f64 {
self.energy
}
}