use std::sync::Arc;
use crate::TopologyError;
use crate::evidence::EvidenceStore;
use crate::incidence::{
Basis, CanonicalBoundary, CanonicalMaximal, ChainView, DegreeLayout, build_boundaries,
canonical_faces, try_filled, validated_permutation_sign,
};
use crate::{ChainComplex, IntegerRing, IntegralChainComplex};
#[derive(Debug)]
pub struct CandidateInput {
values: Box<[usize]>,
signs: Box<[i8]>,
row_count: usize,
row_width: usize,
vertex_count: Option<usize>,
}
impl CandidateInput {
pub fn signed<T>(
values: impl IntoIterator<Item = T>,
row_count: usize,
row_width: usize,
vertex_count: Option<usize>,
) -> Result<Self, TopologyError>
where
i128: From<T>,
{
Self::checked(
values.into_iter().map(|value| {
let value = i128::from(value);
if value < 0 {
Err(TopologyError::negative_index(value))
} else {
usize::try_from(value)
.map_err(|_| TopologyError::index_overflow(value.cast_unsigned()))
}
}),
row_count,
row_width,
vertex_count,
)
}
pub fn unsigned<T>(
values: impl IntoIterator<Item = T>,
row_count: usize,
row_width: usize,
vertex_count: Option<usize>,
) -> Result<Self, TopologyError>
where
u128: From<T>,
{
Self::checked(
values.into_iter().map(|value| {
let value = u128::from(value);
usize::try_from(value).map_err(|_| TopologyError::index_overflow(value))
}),
row_count,
row_width,
vertex_count,
)
}
fn checked(
values: impl IntoIterator<Item = Result<usize, TopologyError>>,
row_count: usize,
row_width: usize,
vertex_count: Option<usize>,
) -> Result<Self, TopologyError> {
let expected = row_count
.checked_mul(row_width)
.ok_or(TopologyError::CountOverflow)?;
let mut admitted = Vec::new();
let mut signs = Vec::new();
admitted
.try_reserve_exact(expected)
.map_err(|_| TopologyError::Allocation)?;
signs
.try_reserve_exact(row_count)
.map_err(|_| TopologyError::Allocation)?;
for value in values {
if admitted.len() == expected {
return Err(TopologyError::CandidateShape);
}
admitted.push(value?);
if row_width != 0 && admitted.len().is_multiple_of(row_width) {
signs.push(validated_permutation_sign(
&admitted[admitted.len() - row_width..],
)?);
}
}
if admitted.len() != expected {
return Err(TopologyError::CandidateShape);
}
Ok(Self {
values: admitted.into_boxed_slice(),
signs: signs.into_boxed_slice(),
row_count,
row_width,
vertex_count,
})
}
}
#[derive(Debug)]
pub struct ComplexCore {
pub(crate) vertex_count: usize,
pub(crate) dimension: usize,
pub(crate) layout: DegreeLayout,
pub(crate) bases: Box<[Basis]>,
pub(crate) orientations: Box<[Box<[i8]>]>,
pub(crate) boundaries: Box<[CanonicalBoundary]>,
pub(crate) immediate_faces: Box<[Box<[usize]>]>,
pub(crate) evidence: EvidenceStore,
}
impl ComplexCore {
pub fn admit(candidate: CandidateInput) -> Result<Arc<Self>, TopologyError> {
let canonical = canonicalize_maximal(candidate)?;
let vertex_count = canonical.vertex_count;
let dimension = canonical.rows.row_width() - 1;
let mut bases = Vec::new();
bases
.try_reserve_exact(dimension + 1)
.map_err(|_| TopologyError::Allocation)?;
for degree in 0..=dimension {
let degree_basis = if degree == 0 {
Basis::from_flat((0..vertex_count).collect(), vertex_count, 1)?
} else {
canonical_faces(&canonical.rows, degree + 1)?
};
bases.push(degree_basis);
}
let layout = DegreeLayout::from_bases(&bases)?;
let mut orientations = Vec::new();
orientations
.try_reserve_exact(dimension + 1)
.map_err(|_| TopologyError::Allocation)?;
for (degree, basis) in bases.iter().enumerate() {
let signs = if degree == dimension {
if basis.values() != canonical.rows.values() {
return Err(TopologyError::InternalInvariant);
}
canonical.signs.to_vec()
} else {
vec![1_i8; basis.row_count()]
};
orientations.push(signs.into_boxed_slice());
}
let (boundaries, immediate_faces) = build_boundaries(&bases, &orientations)?;
Ok(Arc::new(Self {
vertex_count,
dimension,
layout,
bases: bases.into_boxed_slice(),
orientations: orientations.into_boxed_slice(),
boundaries: boundaries.into_boxed_slice(),
immediate_faces: immediate_faces.into_boxed_slice(),
evidence: EvidenceStore::default(),
}))
}
#[must_use]
pub fn chain_complex(self: &Arc<Self>) -> IntegralChainComplex {
ChainComplex::simplicial(Arc::clone(self), IntegerRing)
}
#[must_use]
pub const fn vertex_count(&self) -> usize {
self.vertex_count
}
#[must_use]
pub const fn dimension(&self) -> usize {
self.dimension
}
#[must_use]
pub const fn chain_view(&self) -> ChainView<'_> {
ChainView::simplicial(self)
}
pub fn basis(&self, degree: usize) -> Result<&Basis, TopologyError> {
self.bases
.get(degree)
.ok_or(TopologyError::degree_outside(degree))
}
pub fn immediate_faces(&self, degree: usize) -> Result<&[usize], TopologyError> {
self.immediate_faces
.get(degree)
.map(AsRef::as_ref)
.ok_or(TopologyError::degree_outside(degree))
}
pub fn orientation(&self, degree: usize) -> Result<&[i8], TopologyError> {
self.orientations
.get(degree)
.map(AsRef::as_ref)
.ok_or(TopologyError::degree_outside(degree))
}
pub fn boundary(&self, degree: usize) -> Result<&CanonicalBoundary, TopologyError> {
self.boundaries
.get(degree)
.ok_or(TopologyError::degree_outside(degree))
}
pub fn immediate_face_rows(&self, degree: usize) -> Result<&[usize], TopologyError> {
self.immediate_faces
.get(degree)
.map(AsRef::as_ref)
.ok_or(TopologyError::degree_outside(degree))
}
}
fn canonicalize_maximal(candidate: CandidateInput) -> Result<CanonicalMaximal, TopologyError> {
let CandidateInput {
values,
signs,
row_count,
row_width,
vertex_count: declared_vertex_count,
} = candidate;
if row_count == 0 || row_width == 0 {
return Err(TopologyError::EmptyMaximalSimplices);
}
let mut rows = values.into_vec();
let mut signs = signs.into_vec();
let mut maximum = 0_usize;
for raw_row in rows.chunks_exact(row_width) {
maximum = maximum.max(raw_row.iter().copied().max().unwrap_or(0));
}
let inferred_vertices = maximum.checked_add(1).ok_or(TopologyError::CountOverflow)?;
let vertex_count = declared_vertex_count.unwrap_or(inferred_vertices);
if vertex_count == 0 || vertex_count <= maximum {
return Err(TopologyError::vertex_extent(
vertex_count,
inferred_vertices,
));
}
for row in rows.chunks_exact_mut(row_width) {
row.sort_unstable();
}
let mut order = (0..row_count).collect::<Vec<_>>();
order.sort_unstable_by(|left, right| {
let left_start = left * row_width;
let right_start = right * row_width;
rows[left_start..left_start + row_width].cmp(&rows[right_start..right_start + row_width])
});
for pair in order.windows(2) {
let left_start = pair[0] * row_width;
let right_start = pair[1] * row_width;
if rows[left_start..left_start + row_width] == rows[right_start..right_start + row_width] {
return Err(TopologyError::DuplicateMaximalSimplex);
}
}
let mut visited = try_filled(row_count, false)?;
let mut saved_row = Vec::new();
saved_row
.try_reserve_exact(row_width)
.map_err(|_| TopologyError::Allocation)?;
for start in 0..row_count {
if visited[start] {
continue;
}
saved_row.extend_from_slice(&rows[start * row_width..(start + 1) * row_width]);
let saved_sign = signs[start];
let mut destination = start;
loop {
visited[destination] = true;
let source = order[destination];
if source == start {
rows[destination * row_width..(destination + 1) * row_width]
.copy_from_slice(&saved_row);
signs[destination] = saved_sign;
break;
}
rows.copy_within(
source * row_width..(source + 1) * row_width,
destination * row_width,
);
signs[destination] = signs[source];
destination = source;
}
saved_row.clear();
}
Ok(CanonicalMaximal {
vertex_count,
rows: Basis::from_flat(rows, row_count, row_width)?,
signs: signs.into_boxed_slice(),
})
}