cocycle 0.1.1

Topological data analysis in pure Rust
Documentation
//! Owned interval multisets and their computation coverage.

use std::cmp::Ordering;

use super::interval::{IntervalEnd, PersistenceInterval, finite_scale};
use crate::{Error, Result};

use super::ComputedDimensions;
use crate::filtration::Coverage;

/// An owned persistence diagram with explicitly recorded dimensions and coverage.
///
/// Computed dimensions are explicitly declared, even if their interval lists are
/// empty. [`Self::new`] declares `0..=max_dimension`; [`Self::with_dimensions`]
/// supports noncontiguous sets. Intervals form a canonical logical sequence ordered
/// by dimension, birth, endpoint kind (finite, essential, censored), then endpoint
/// value. Multiplicities are preserved. No original input, simplex IDs or matrix
/// indices are retained.
///
/// Access returns logical values, without guaranteeing contiguous storage, physical
/// interval rows, stable element addresses, backing-buffer reuse, an AoS/SoA layout,
/// or a particular physical partition by dimension or endpoint kind.
///
/// ```
/// use cocycle::diagram::{Coverage, IntervalEnd, PersistenceDiagram, PersistenceInterval};
///
/// let intervals = vec![PersistenceInterval::new(1, 1.0, IntervalEnd::Finite(2.0))?];
/// let diagram = PersistenceDiagram::new(1, Coverage::Complete, intervals)?;
/// assert!(diagram.dimension(0)?.is_empty());
/// let h1 = diagram.dimension(1)?;
/// assert_eq!(h1.len(), 1);
/// assert_eq!(diagram.interval(0), h1.iter().next());
/// assert!(diagram.dimension(2).is_err());
/// # Ok::<(), cocycle::Error>(())
/// ```
#[derive(Clone, Debug, PartialEq)]
pub struct PersistenceDiagram {
    dimensions: ComputedDimensions,
    coverage: Coverage,
    intervals: Vec<PersistenceInterval>,
}

impl PersistenceDiagram {
    /// Take ownership of intervals and validate them against the declared range.
    ///
    /// Complete diagrams may contain finite and essential intervals. For a
    /// truncated diagram, all births and finite deaths must be at or before its
    /// cutoff, all censoring cutoffs must equal it, and essential intervals are
    /// rejected. This conservative convention does not infer eventual survival.
    ///
    /// Sorting is by dimension, birth, endpoint kind (finite, essential, censored),
    /// and then endpoint value. Equal intervals are retained. Validation and
    /// sorting take O(m log m) time for m intervals. The input buffer's allocation
    /// and element addresses are not part of the diagram's contract.
    ///
    /// # Errors
    /// Returns an error for a non-finite cutoff, an interval outside the computed
    /// dimensions, or an interval inconsistent with coverage. Errors referring to
    /// an interval index refer to its position before sorting.
    pub fn new(
        max_dimension: usize,
        coverage: Coverage,
        intervals: Vec<PersistenceInterval>,
    ) -> Result<Self> {
        Self::with_dimensions(
            ComputedDimensions::through(max_dimension),
            coverage,
            intervals,
        )
    }

    /// Own intervals with an explicit, possibly noncontiguous computation domain.
    ///
    /// Applies the coverage and sorting rules of [`Self::new`]. The declared
    /// dimensions describe computation, not just dimensions with nonempty bars.
    ///
    /// ```
    /// use cocycle::diagram::{ComputedDimensions, Coverage, PersistenceDiagram};
    /// let diagram = PersistenceDiagram::with_dimensions(
    ///     ComputedDimensions::new(vec![1, 3])?, Coverage::Complete, vec![],
    /// )?;
    /// assert!(diagram.dimension(3)?.is_empty());
    /// assert!(diagram.dimension(2).is_err());
    /// # Ok::<(), cocycle::Error>(())
    /// ```
    ///
    /// # Errors
    /// Rejects intervals outside `dimensions` and inconsistent or invalid coverage.
    pub fn with_dimensions(
        dimensions: ComputedDimensions,
        coverage: Coverage,
        mut intervals: Vec<PersistenceInterval>,
    ) -> Result<Self> {
        let coverage = match coverage {
            Coverage::Complete => Coverage::Complete,
            Coverage::Through(value) => Coverage::Through(finite_scale(value, "coverage")?),
        };
        for (index, interval) in intervals.iter().enumerate() {
            if !dimensions.contains(interval.dimension()) {
                return Err(Error::DimensionNotComputed {
                    requested: interval.dimension(),
                    computed_max: dimensions.max(),
                });
            }
            validate_coverage(interval, coverage, index)?;
        }
        intervals.sort_unstable_by(compare_intervals);
        Ok(Self {
            dimensions,
            coverage,
            intervals,
        })
    }

    /// Largest computed dimension. This does not imply lower dimensions were computed.
    pub fn max_dimension(&self) -> usize {
        self.dimensions.max()
    }

    /// Exact computation domain, including computed dimensions with no intervals.
    pub fn computed_dimensions(&self) -> &ComputedDimensions {
        &self.dimensions
    }

    /// Complete or inclusive finite computation range.
    pub fn coverage(&self) -> Coverage {
        self.coverage
    }

    /// Number of logical intervals, counting repeated intervals separately.
    pub fn len(&self) -> usize {
        self.intervals.len()
    }

    /// Whether the diagram contains no intervals, independently of computed dimensions.
    pub fn is_empty(&self) -> bool {
        self.intervals.is_empty()
    }

    /// Iterate over interval values in canonical logical order, preserving multiplicity.
    ///
    /// Creates an iterator in O(1) time; traversal takes O(n) time for n intervals,
    /// with O(1) auxiliary space and no heap allocation or intermediate interval buffer.
    pub fn intervals(&self) -> impl Iterator<Item = PersistenceInterval> + '_ {
        self.intervals.iter().copied()
    }

    /// Resolve a zero-based ordinal in the canonical logical interval sequence.
    ///
    /// Repeated intervals occupy distinct ordinals. Returns `None` when `index`
    /// is out of bounds; the ordinal is not a physical storage address.
    pub fn interval(&self, index: usize) -> Option<PersistenceInterval> {
        self.intervals.get(index).copied()
    }

    /// Borrow a logical view of a computed dimension, which may have no intervals.
    ///
    /// After checking dimension membership, locating the view takes O(log(n + 1))
    /// time for n diagram intervals. Creation uses O(1) auxiliary space and no
    /// heap allocation. The view iterates only its selected intervals.
    ///
    /// # Errors
    /// Returns [`Error::DimensionNotComputed`] for a dimension absent from the
    /// declared set, including gaps below the maximum. Empty does not mean uncomputed.
    pub fn dimension(&self, dimension: usize) -> Result<DiagramDimension<'_>> {
        if !self.dimensions.contains(dimension) {
            return Err(Error::DimensionNotComputed {
                requested: dimension,
                computed_max: self.dimensions.max(),
            });
        }
        let start = self
            .intervals
            .partition_point(|interval| interval.dimension() < dimension);
        let end = self
            .intervals
            .partition_point(|interval| interval.dimension() <= dimension);
        Ok(DiagramDimension {
            dimension,
            intervals: &self.intervals[start..end],
        })
    }
}

/// A borrowed logical view of one computed homology dimension.
///
/// Obtained through [`PersistenceDiagram::dimension`]. An empty view still records
/// a computed dimension. Iteration yields values in the diagram's canonical order,
/// preserving multiplicity; it does not expose a slice or guarantee physical rows,
/// addresses, allocation identity, or a storage layout.
#[derive(Debug)]
pub struct DiagramDimension<'a> {
    dimension: usize,
    intervals: &'a [PersistenceInterval],
}

impl DiagramDimension<'_> {
    /// Homology dimension recorded by this view, including when it is empty.
    pub fn dimension(&self) -> usize {
        self.dimension
    }

    /// Number of logical intervals in this dimension, including repetitions.
    pub fn len(&self) -> usize {
        self.intervals.len()
    }

    /// Whether this computed dimension contains no intervals.
    pub fn is_empty(&self) -> bool {
        self.intervals.is_empty()
    }

    /// Iterate over interval values in canonical logical order.
    ///
    /// Creates an iterator in O(1) time; traversal takes O(k) time for k selected
    /// intervals, with O(1) auxiliary space and no heap allocation.
    pub fn iter(&self) -> impl Iterator<Item = PersistenceInterval> + '_ {
        self.intervals.iter().copied()
    }
}

fn validate_coverage(
    interval: &PersistenceInterval,
    coverage: Coverage,
    index: usize,
) -> Result<()> {
    let reason = match coverage {
        Coverage::Complete => match interval.end() {
            IntervalEnd::RightCensored { .. } => {
                Some("complete coverage cannot contain censored intervals")
            }
            _ => None,
        },
        Coverage::Through(cutoff) => {
            if interval.birth() > cutoff {
                Some("birth exceeds the computation cutoff")
            } else {
                match interval.end() {
                    IntervalEnd::Essential => {
                        Some("truncated coverage cannot certify an essential interval")
                    }
                    IntervalEnd::Finite(death) if death > cutoff => {
                        Some("death exceeds the computation cutoff")
                    }
                    IntervalEnd::RightCensored { through } if through != cutoff => {
                        Some("interval and diagram censoring cutoffs differ")
                    }
                    _ => None,
                }
            }
        }
    };
    match reason {
        Some(reason) => Err(Error::InconsistentDiagram {
            interval: index,
            reason,
        }),
        None => Ok(()),
    }
}

fn compare_intervals(a: &PersistenceInterval, b: &PersistenceInterval) -> Ordering {
    a.dimension()
        .cmp(&b.dimension())
        .then_with(|| a.birth().total_cmp(&b.birth()))
        .then_with(|| compare_ends(a.end(), b.end()))
}

fn compare_ends(a: IntervalEnd, b: IntervalEnd) -> Ordering {
    match (a, b) {
        (IntervalEnd::Finite(a), IntervalEnd::Finite(b)) => a.total_cmp(&b),
        (IntervalEnd::Essential, IntervalEnd::Essential) => Ordering::Equal,
        (IntervalEnd::RightCensored { through: a }, IntervalEnd::RightCensored { through: b }) => {
            a.total_cmp(&b)
        }
        (IntervalEnd::Finite(_), _)
        | (IntervalEnd::Essential, IntervalEnd::RightCensored { .. }) => Ordering::Less,
        _ => Ordering::Greater,
    }
}