use std::sync::Arc;
use crate::algebra::Algebra;
use crate::context::VerificationContext;
use crate::decompose::{inverse_morphism, mutually_inverse};
use crate::hom::{HomError, Morphism, hom_dim};
use crate::indec::IndecomposableModule;
use crate::iso::indecomposable_iso;
use crate::module::{Module, summand_sum};
use crate::profile::{Site, hit};
use crate::radical::{loewy_length, socle, top};
use super::decomposition::{BasicDecomposition, BasicError, defect_non_invertible};
pub struct ProjectiveSupport {
algebra: Arc<Algebra>,
vertices: Vec<u32>,
}
debug_fields!(ProjectiveSupport |this| {
"vertices" => this.vertices;
});
impl PartialEq for ProjectiveSupport {
fn eq(&self, other: &ProjectiveSupport) -> bool {
self.vertices == other.vertices
}
}
impl Eq for ProjectiveSupport {}
impl ProjectiveSupport {
pub fn new(algebra: &Arc<Algebra>, vertices: &[u32]) -> Result<ProjectiveSupport, BasicError> {
let num_vertices = algebra.quiver().num_vertices();
for &vertex in vertices {
if vertex >= num_vertices {
return Err(BasicError::VertexOutOfRange {
vertex,
num_vertices,
});
}
}
let mut sorted = vertices.to_vec();
sorted.sort_unstable();
sorted.dedup();
Ok(ProjectiveSupport {
algebra: algebra.clone(),
vertices: sorted,
})
}
accessor_methods! {
pub algebra() -> &Arc<Algebra> = |this| &this.algebra;
pub vertices() -> &[u32] = |this| &this.vertices;
pub len() -> usize = |this| this.vertices.len();
pub is_empty() -> bool = |this| this.vertices.is_empty();
pub contains(v: u32) -> bool = |this| this.vertices.binary_search(&v).is_ok();
pub is_compatible(other: &ProjectiveSupport) -> bool = |this|
Arc::ptr_eq(&this.algebra, &other.algebra);
pub module() -> Module = |this|
summand_sum(&this.algebra, &this.vertices, Module::projective);
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum SupportPairObstruction {
ProjectiveSupport {
first: Vec<u32>,
second: Vec<u32>,
},
SummandCount {
first: usize,
second: usize,
},
UnmatchedSummand {
index: usize,
dim_vector: Vec<usize>,
},
}
#[derive(Clone)]
pub struct SupportPairIsoWitness {
pub(super) bijection: Vec<usize>,
pub(super) forward: Vec<Morphism>,
pub(super) backward: Vec<Morphism>,
}
debug_fields!(SupportPairIsoWitness |this| {
"bijection" => this.bijection;
});
impl SupportPairIsoWitness {
accessor_methods! {
pub bijection() -> &[usize] = |this| &this.bijection;
pub forward() -> &[Morphism] = |this| &this.forward;
pub backward() -> &[Morphism] = |this| &this.backward;
}
pub fn verify(&self) -> bool {
hit(Site::SupportPairIsoWitnessVerify);
verify_guard!(
self.forward.len() == self.bijection.len()
&& self.backward.len() == self.bijection.len()
);
let mut seen = vec![false; self.bijection.len()];
for &j in &self.bijection {
verify_guard!(j < seen.len() && !seen[j]);
seen[j] = true;
}
for (f, g) in self.forward.iter().zip(&self.backward) {
verify_guard!(mutually_inverse(f, g));
}
true
}
}
#[derive(Clone, Debug)]
pub enum SupportPairIsoOutcome {
Isomorphic(SupportPairIsoWitness),
NotIsomorphic(SupportPairObstruction),
}
pub fn pair_iso(
a_mod: &BasicDecomposition,
a_proj: &ProjectiveSupport,
b_mod: &BasicDecomposition,
b_proj: &ProjectiveSupport,
) -> Result<SupportPairIsoOutcome, BasicError> {
hit(Site::PairIso);
if !a_proj.is_compatible(b_proj)
|| !Arc::ptr_eq(a_mod.module().algebra(), a_proj.algebra())
|| !Arc::ptr_eq(b_mod.module().algebra(), b_proj.algebra())
{
return Err(BasicError::DifferentAlgebras);
}
if a_proj.vertices() != b_proj.vertices() {
return Ok(SupportPairIsoOutcome::NotIsomorphic(
SupportPairObstruction::ProjectiveSupport {
first: a_proj.vertices().to_vec(),
second: b_proj.vertices().to_vec(),
},
));
}
if a_mod.len() != b_mod.len() {
return Ok(SupportPairIsoOutcome::NotIsomorphic(
SupportPairObstruction::SummandCount {
first: a_mod.len(),
second: b_mod.len(),
},
));
}
let mut bijection = Vec::with_capacity(a_mod.len());
let mut forward = Vec::with_capacity(a_mod.len());
let mut backward = Vec::with_capacity(a_mod.len());
let mut used = vec![false; b_mod.len()];
for (i, x) in a_mod.summands().iter().enumerate() {
let Some(matched) = certified_match(
x,
b_mod
.summands()
.iter()
.enumerate()
.filter(|(j, _)| !used[*j]),
)?
else {
return Ok(SupportPairIsoOutcome::NotIsomorphic(
SupportPairObstruction::UnmatchedSummand {
index: i,
dim_vector: x.module().dim_vector().to_vec(),
},
));
};
used[matched.target_index] = true;
bijection.push(matched.target_index);
forward.push(matched.forward);
backward.push(matched.backward);
}
Ok(SupportPairIsoOutcome::Isomorphic(SupportPairIsoWitness {
bijection,
forward,
backward,
}))
}
#[derive(Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct SummandFingerprint {
dim_vector: Vec<usize>,
loewy_length: usize,
top_dim_vector: Vec<usize>,
socle_dim_vector: Vec<usize>,
end_dim: usize,
residue_degree: usize,
hom_from_simples: Vec<usize>,
hom_to_simples: Vec<usize>,
}
impl SummandFingerprint {
accessor_methods! {
pub dim_vector() -> &[usize] = |this| &this.dim_vector;
pub loewy_length() -> usize = |this| this.loewy_length;
pub top_dim_vector() -> &[usize] = |this| &this.top_dim_vector;
pub socle_dim_vector() -> &[usize] = |this| &this.socle_dim_vector;
pub end_dim() -> usize = |this| this.end_dim;
pub residue_degree() -> usize = |this| this.residue_degree;
pub hom_from_simples() -> &[usize] = |this| &this.hom_from_simples;
pub hom_to_simples() -> &[usize] = |this| &this.hom_to_simples;
}
}
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub struct PairFingerprint {
projective_support: Vec<u32>,
summands: Vec<SummandFingerprint>,
}
impl PairFingerprint {
pub fn new(
module: &BasicDecomposition,
projective: &ProjectiveSupport,
) -> Result<PairFingerprint, BasicError> {
Self::new_with_hom(module, projective, hom_dim)
}
pub(crate) fn new_with_context(
module: &BasicDecomposition,
projective: &ProjectiveSupport,
context: &VerificationContext,
) -> Result<PairFingerprint, BasicError> {
Self::new_with_hom(module, projective, |source, target| {
context.hom_dim_for(source, target)
})
}
fn new_with_hom(
module: &BasicDecomposition,
projective: &ProjectiveSupport,
hom: impl Fn(&Module, &Module) -> Result<usize, HomError>,
) -> Result<PairFingerprint, BasicError> {
hit(Site::PairFingerprintNew);
let algebra = module.module().algebra();
if !Arc::ptr_eq(algebra, projective.algebra()) {
return Err(BasicError::DifferentAlgebras);
}
let simples: Vec<Module> = (0..algebra.quiver().num_vertices())
.map(|v| Module::simple(algebra, v))
.collect();
let mut summands = Vec::with_capacity(module.len());
for x in module.summands() {
let m = x.module();
let (top_module, _) = top(m);
let (socle_module, _) = socle(m);
let mut hom_from_simples = Vec::with_capacity(simples.len());
let mut hom_to_simples = Vec::with_capacity(simples.len());
for simple in &simples {
hom_from_simples.push(hom(simple, m)?);
hom_to_simples.push(hom(m, simple)?);
}
summands.push(SummandFingerprint {
dim_vector: m.dim_vector().to_vec(),
loewy_length: loewy_length(m),
top_dim_vector: top_module.dim_vector().to_vec(),
socle_dim_vector: socle_module.dim_vector().to_vec(),
end_dim: x.endo().dim(),
residue_degree: x.residue_degree(),
hom_from_simples,
hom_to_simples,
});
}
summands.sort();
Ok(PairFingerprint {
projective_support: projective.vertices().to_vec(),
summands,
})
}
accessor_methods! {
pub projective_support() -> &[u32] = |this| &this.projective_support;
pub summands() -> &[SummandFingerprint] = |this| &this.summands;
}
}
pub(crate) fn pairwise_distinct_by<T, F>(
items: &[T],
mut fingerprint: impl FnMut(&T) -> Option<F>,
mut distinct: impl FnMut(&T, &T) -> bool,
) -> bool
where
F: PartialEq,
{
let_or_false!(
Some(fingerprints) = items
.iter()
.map(&mut fingerprint)
.collect::<Option<Vec<F>>>()
);
(0..items.len()).all(|i| {
(i + 1..items.len())
.all(|j| fingerprints[i] != fingerprints[j] || distinct(&items[i], &items[j]))
})
}
#[derive(Clone)]
pub struct AddMatch {
pub(super) target_index: usize,
pub(super) forward: Morphism,
pub(super) backward: Morphism,
}
debug_fields!(AddMatch |this| {
"target_index" => this.target_index;
});
impl AddMatch {
accessor_methods! {
pub target_index() -> usize = |this| this.target_index;
pub forward() -> &Morphism = |this| &this.forward;
pub backward() -> &Morphism = |this| &this.backward;
}
}
pub(super) fn certified_match<'a>(
x: &IndecomposableModule,
candidates: impl IntoIterator<Item = (usize, &'a IndecomposableModule)>,
) -> Result<Option<AddMatch>, BasicError> {
for (target_index, y) in candidates {
if let Some(forward) = indecomposable_iso(x.module(), y.module(), x.endo()) {
let backward = inverse_morphism(&forward).ok_or_else(defect_non_invertible)?;
return Ok(Some(AddMatch {
target_index,
forward,
backward,
}));
}
}
Ok(None)
}