relmath/

temporal.rs

//! Deterministic temporal interval and valid-time foundations.
//!
//! This first G5 slice introduces half-open intervals `[start, end)` over
//! endpoint domains with total ordering. Intervals use deterministic
//! lexicographic `(start, end)` ordering when stored in ordered collections,
//! which makes later coalescing behavior easy to audit.
//!
//! Half-open semantics mean:
//!
//! - `start` is included;
//! - `end` is excluded;
//! - directly adjacent intervals such as `[1, 3)` and `[3, 5)` do not
//!   overlap, but they can be coalesced;
//! - invalid intervals with `start >= end` are rejected explicitly.
//!
//! On top of the interval substrate, this module also provides a first
//! deterministic valid-time relation foundation:
//!
//! - `ValidTimeSupport<T>` stores the canonical interval support for one fact;
//! - `ValidTimeRelation<F, T>` maps exact facts to deterministic valid-time
//!   support and materializes exact support back into the published unary,
//!   binary, and n-ary relation surface.
//! - `ValidTimeRelation::snapshot_at` and `ValidTimeRelation::restrict_to`
//!   provide the first narrow temporal operations over stored facts.
//!
//! This module remains intentionally narrower than a full temporal algebra.
//! Temporal joins, temporal composition, transaction time, and bitemporal APIs
//! are later work.

use std::{collections::BTreeMap, fmt};

use crate::{
    BinaryRelation, NaryRelation, NaryRelationError, UnaryRelation, traits::FiniteRelation,
};

/// Validation errors for deterministic half-open intervals.
///
/// # Examples
///
/// ```rust
/// use relmath::temporal::{Interval, IntervalError};
///
/// assert_eq!(
///     Interval::new(4, 4),
///     Err(IntervalError::InvalidBounds { start: 4, end: 4 })
/// );
/// ```
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum IntervalError<T> {
    /// The interval is invalid because `start >= end`.
    InvalidBounds {
        /// The requested inclusive lower bound.
        start: T,
        /// The requested exclusive upper bound.
        end: T,
    },
}

impl<T: fmt::Debug> fmt::Display for IntervalError<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::InvalidBounds { start, end } => {
                write!(
                    f,
                    "invalid half-open interval: expected start < end, got start={start:?}, end={end:?}"
                )
            }
        }
    }
}

impl<T: fmt::Debug> std::error::Error for IntervalError<T> {}

/// Deterministic half-open interval over an ordered endpoint domain.
///
/// `Interval<T>` represents `[start, end)`: `start` is included and `end` is
/// excluded. The interval is valid only when `start < end`.
///
/// Intervals derive `Ord`, so ordered collections such as `BTreeSet` keep
/// them in lexicographic `(start, end)` order. That is the deterministic order
/// later temporal coalescing code should use.
///
/// # Examples
///
/// ```rust
/// use std::collections::BTreeSet;
///
/// use relmath::temporal::Interval;
///
/// let windows = BTreeSet::from([
///     Interval::new(3, 5).expect("expected valid interval"),
///     Interval::new(1, 4).expect("expected valid interval"),
///     Interval::new(1, 3).expect("expected valid interval"),
/// ]);
///
/// assert_eq!(
///     windows.into_iter().collect::<Vec<_>>(),
///     vec![
///         Interval::new(1, 3).expect("expected valid interval"),
///         Interval::new(1, 4).expect("expected valid interval"),
///         Interval::new(3, 5).expect("expected valid interval"),
///     ]
/// );
/// ```
#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub struct Interval<T: Ord> {
    start: T,
    end: T,
}

impl<T: Ord> Interval<T> {
    /// Creates one valid half-open interval `[start, end)`.
    ///
    /// Returns an explicit error when `start >= end`.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::temporal::{Interval, IntervalError};
    ///
    /// let valid = Interval::new(2, 5).expect("expected valid interval");
    /// assert_eq!(valid.start(), &2);
    /// assert_eq!(valid.end(), &5);
    ///
    /// assert_eq!(
    ///     Interval::new(5, 2),
    ///     Err(IntervalError::InvalidBounds { start: 5, end: 2 })
    /// );
    /// ```
    pub fn new(start: T, end: T) -> Result<Self, IntervalError<T>> {
        if start < end {
            Ok(Self { start, end })
        } else {
            Err(IntervalError::InvalidBounds { start, end })
        }
    }

    /// Returns the inclusive lower bound of the interval.
    #[must_use]
    pub fn start(&self) -> &T {
        &self.start
    }

    /// Returns the exclusive upper bound of the interval.
    #[must_use]
    pub fn end(&self) -> &T {
        &self.end
    }

    /// Returns `true` when `point` lies inside `[start, end)`.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::temporal::Interval;
    ///
    /// let window = Interval::new(10, 12).expect("expected valid interval");
    ///
    /// assert!(window.contains(&10));
    /// assert!(window.contains(&11));
    /// assert!(!window.contains(&12));
    /// ```
    #[must_use]
    pub fn contains(&self, point: &T) -> bool {
        &self.start <= point && point < &self.end
    }

    /// Returns `true` when the intervals overlap with non-empty intersection.
    ///
    /// Directly adjacent intervals do not overlap under half-open semantics.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::temporal::Interval;
    ///
    /// let left = Interval::new(1, 3).expect("expected valid interval");
    /// let overlap = Interval::new(2, 4).expect("expected valid interval");
    /// let adjacent = Interval::new(3, 5).expect("expected valid interval");
    ///
    /// assert!(left.overlaps(&overlap));
    /// assert!(!left.overlaps(&adjacent));
    /// ```
    #[must_use]
    pub fn overlaps(&self, other: &Self) -> bool {
        self.start < other.end && other.start < self.end
    }

    /// Returns `true` when the intervals touch at exactly one boundary.
    ///
    /// Adjacent intervals are not overlapping, but later valid-time layers may
    /// still coalesce them into one canonical support fragment.
    #[must_use]
    pub fn is_adjacent_to(&self, other: &Self) -> bool {
        self.end == other.start || other.end == self.start
    }

    /// Returns `true` when the intervals can be coalesced.
    ///
    /// This is true for overlapping or directly adjacent intervals.
    #[must_use]
    pub fn can_coalesce_with(&self, other: &Self) -> bool {
        self.overlaps(other) || self.is_adjacent_to(other)
    }
}

impl<T: Ord + Clone> Interval<T> {
    /// Returns the non-empty intersection of two intervals.
    ///
    /// When the intervals are disjoint or only touch at one boundary, this
    /// returns `None`.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::temporal::Interval;
    ///
    /// let left = Interval::new(1, 4).expect("expected valid interval");
    /// let right = Interval::new(3, 6).expect("expected valid interval");
    ///
    /// assert_eq!(
    ///     left.intersection(&right),
    ///     Some(Interval::new(3, 4).expect("expected valid interval"))
    /// );
    /// ```
    #[must_use]
    pub fn intersection(&self, other: &Self) -> Option<Self> {
        let start = if self.start >= other.start {
            self.start.clone()
        } else {
            other.start.clone()
        };
        let end = if self.end <= other.end {
            self.end.clone()
        } else {
            other.end.clone()
        };

        Self::new(start, end).ok()
    }

    /// Restricts this interval to the overlap with `constraint`.
    ///
    /// This is an interval-level helper for later temporal `restrict_to`
    /// behavior on valid-time relations.
    #[must_use]
    pub fn restrict_to(&self, constraint: &Self) -> Option<Self> {
        self.intersection(constraint)
    }

    /// Coalesces two overlapping or directly adjacent intervals.
    ///
    /// Returns `None` when the intervals are strictly disjoint.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::temporal::Interval;
    ///
    /// let morning = Interval::new(9, 12).expect("expected valid interval");
    /// let afternoon = Interval::new(12, 15).expect("expected valid interval");
    ///
    /// assert_eq!(
    ///     morning.coalesce(&afternoon),
    ///     Some(Interval::new(9, 15).expect("expected valid interval"))
    /// );
    /// ```
    #[must_use]
    pub fn coalesce(&self, other: &Self) -> Option<Self> {
        if !self.can_coalesce_with(other) {
            return None;
        }

        let start = if self.start <= other.start {
            self.start.clone()
        } else {
            other.start.clone()
        };
        let end = if self.end >= other.end {
            self.end.clone()
        } else {
            other.end.clone()
        };

        Some(Self { start, end })
    }
}

fn canonicalize_intervals<T: Ord + Clone>(mut intervals: Vec<Interval<T>>) -> Vec<Interval<T>> {
    intervals.sort();

    let mut canonical: Vec<Interval<T>> = Vec::with_capacity(intervals.len());
    for interval in intervals {
        if let Some(last) = canonical.last_mut() {
            if let Some(coalesced) = last.coalesce(&interval) {
                *last = coalesced;
                continue;
            }
        }

        canonical.push(interval);
    }

    canonical
}

/// Deterministic canonical valid-time support for one fact.
///
/// `ValidTimeSupport<T>` stores half-open intervals in canonical
/// lexicographic order. Overlapping or directly adjacent intervals are
/// coalesced, so user-visible support never contains redundant fragments.
/// Support can then be queried for overlap with one interval or restricted to
/// one interval window without losing deterministic canonical order.
///
/// This is the interval support attached to one stored fact. It is distinct
/// from the exact support of a relation, which forgets time and keeps only
/// which facts are present.
///
/// # Examples
///
/// ```rust
/// use relmath::temporal::{Interval, ValidTimeSupport};
///
/// let support = ValidTimeSupport::from_intervals([
///     Interval::new(3, 5).expect("expected valid interval"),
///     Interval::new(1, 3).expect("expected valid interval"),
///     Interval::new(6, 7).expect("expected valid interval"),
///     Interval::new(4, 6).expect("expected valid interval"),
/// ]);
///
/// assert_eq!(
///     support.to_vec(),
///     vec![Interval::new(1, 7).expect("expected valid interval")]
/// );
/// assert!(support.contains(&4));
/// assert!(!support.contains(&7));
/// ```
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct ValidTimeSupport<T: Ord + Clone> {
    intervals: Vec<Interval<T>>,
}

impl<T: Ord + Clone> ValidTimeSupport<T> {
    /// Creates empty valid-time support.
    ///
    /// A `ValidTimeRelation` does not store empty support for a fact, so
    /// absent facts return `None` rather than an empty support value. This
    /// constructor is still useful for standalone inspection and testing.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::temporal::ValidTimeSupport;
    ///
    /// let empty = ValidTimeSupport::<i32>::new();
    ///
    /// assert!(empty.is_empty());
    /// assert_eq!(empty.len(), 0);
    /// ```
    #[must_use]
    pub fn new() -> Self {
        Self {
            intervals: Vec::new(),
        }
    }

    /// Creates canonical valid-time support from intervals.
    ///
    /// The resulting support is sorted and coalesced deterministically.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::temporal::{Interval, ValidTimeSupport};
    ///
    /// let support = ValidTimeSupport::from_intervals([
    ///     Interval::new(2, 4).expect("expected valid interval"),
    ///     Interval::new(1, 2).expect("expected valid interval"),
    /// ]);
    ///
    /// assert_eq!(
    ///     support.to_vec(),
    ///     vec![Interval::new(1, 4).expect("expected valid interval")]
    /// );
    /// ```
    #[must_use]
    pub fn from_intervals<I>(intervals: I) -> Self
    where
        I: IntoIterator<Item = Interval<T>>,
    {
        intervals.into_iter().collect()
    }

    /// Returns the number of canonical support intervals.
    ///
    /// For one stored fact, this counts canonical support fragments rather than
    /// time points or inserted raw intervals.
    #[must_use]
    pub fn len(&self) -> usize {
        self.intervals.len()
    }

    /// Returns `true` when the support contains no intervals.
    #[must_use]
    pub fn is_empty(&self) -> bool {
        self.intervals.is_empty()
    }

    /// Returns `true` when `point` is covered by some support interval.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::temporal::{Interval, ValidTimeSupport};
    ///
    /// let support =
    ///     ValidTimeSupport::from_intervals([Interval::new(2, 4).expect("expected valid interval")]);
    ///
    /// assert!(support.contains(&2));
    /// assert!(support.contains(&3));
    /// assert!(!support.contains(&4));
    /// ```
    #[must_use]
    pub fn contains(&self, point: &T) -> bool {
        self.intervals
            .iter()
            .any(|interval| interval.contains(point))
    }

    /// Returns `true` when some support interval overlaps `constraint`.
    ///
    /// Direct boundary-only contact does not count as overlap under half-open
    /// semantics.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::temporal::{Interval, ValidTimeSupport};
    ///
    /// let support = ValidTimeSupport::from_intervals([
    ///     Interval::new(1, 3).expect("expected valid interval"),
    ///     Interval::new(5, 7).expect("expected valid interval"),
    /// ]);
    ///
    /// assert!(support.overlaps(&Interval::new(2, 6).expect("expected valid interval")));
    /// assert!(!support.overlaps(&Interval::new(3, 5).expect("expected valid interval")));
    /// ```
    #[must_use]
    pub fn overlaps(&self, constraint: &Interval<T>) -> bool {
        self.intervals
            .iter()
            .any(|interval| interval.overlaps(constraint))
    }

    /// Restricts this support to the overlap with `constraint`.
    ///
    /// The returned support remains canonical: overlapping or directly adjacent
    /// fragments are coalesced deterministically. When no interval overlaps the
    /// constraint, this returns empty support.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::temporal::{Interval, ValidTimeSupport};
    ///
    /// let support = ValidTimeSupport::from_intervals([
    ///     Interval::new(1, 3).expect("expected valid interval"),
    ///     Interval::new(5, 7).expect("expected valid interval"),
    /// ]);
    ///
    /// assert_eq!(
    ///     support
    ///         .restrict_to(&Interval::new(2, 6).expect("expected valid interval"))
    ///         .to_vec(),
    ///     vec![
    ///         Interval::new(2, 3).expect("expected valid interval"),
    ///         Interval::new(5, 6).expect("expected valid interval"),
    ///     ]
    /// );
    /// assert!(
    ///     support
    ///         .restrict_to(&Interval::new(3, 5).expect("expected valid interval"))
    ///         .is_empty()
    /// );
    /// ```
    #[must_use]
    pub fn restrict_to(&self, constraint: &Interval<T>) -> Self {
        self.intervals
            .iter()
            .filter_map(|interval| interval.restrict_to(constraint))
            .collect()
    }

    /// Returns an iterator over canonical support intervals.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::temporal::{Interval, ValidTimeSupport};
    ///
    /// let support = ValidTimeSupport::from_intervals([
    ///     Interval::new(4, 6).expect("expected valid interval"),
    ///     Interval::new(1, 3).expect("expected valid interval"),
    /// ]);
    ///
    /// assert_eq!(
    ///     support.iter().cloned().collect::<Vec<_>>(),
    ///     vec![
    ///         Interval::new(1, 3).expect("expected valid interval"),
    ///         Interval::new(4, 6).expect("expected valid interval"),
    ///     ]
    /// );
    /// ```
    pub fn iter(&self) -> impl Iterator<Item = &Interval<T>> {
        self.intervals.iter()
    }

    /// Returns the canonical interval list as a vector.
    #[must_use]
    pub fn to_vec(&self) -> Vec<Interval<T>> {
        self.intervals.clone()
    }

    fn insert_interval(&mut self, interval: Interval<T>) -> bool {
        let mut updated = self.intervals.clone();
        updated.push(interval);
        updated = canonicalize_intervals(updated);

        if updated == self.intervals {
            false
        } else {
            self.intervals = updated;
            true
        }
    }
}

impl<T: Ord + Clone> Default for ValidTimeSupport<T> {
    fn default() -> Self {
        Self::new()
    }
}

impl<T: Ord + Clone> FromIterator<Interval<T>> for ValidTimeSupport<T> {
    fn from_iter<I: IntoIterator<Item = Interval<T>>>(iter: I) -> Self {
        let intervals = canonicalize_intervals(iter.into_iter().collect());
        Self { intervals }
    }
}

impl<T: Ord + Clone> Extend<Interval<T>> for ValidTimeSupport<T> {
    fn extend<I: IntoIterator<Item = Interval<T>>>(&mut self, iter: I) {
        let mut updated = self.intervals.clone();
        updated.extend(iter);
        self.intervals = canonicalize_intervals(updated);
    }
}

/// Deterministic valid-time support attached to exact facts.
///
/// `ValidTimeRelation<F, T>` keeps exact facts in deterministic fact order and
/// stores canonical valid-time support for each fact. Repeated insertion of a
/// fact with overlapping or directly adjacent intervals coalesces that fact's
/// support. The first temporal operations on top of this surface are
/// [`Self::snapshot_at`] and [`Self::restrict_to`].
///
/// In this first G5 slice, only facts with non-empty valid-time support are
/// stored. Exact support materialization forgets time and keeps only which
/// facts are present at all.
///
/// # Examples
///
/// ```rust
/// use relmath::temporal::{Interval, ValidTimeRelation};
///
/// let assignments = ValidTimeRelation::from_facts([
///     (("alice", "review"), Interval::new(1, 3).expect("expected valid interval")),
///     (("alice", "review"), Interval::new(3, 5).expect("expected valid interval")),
///     (("bob", "approve"), Interval::new(2, 4).expect("expected valid interval")),
/// ]);
///
/// assert_eq!(
///     assignments
///         .valid_time_of(&("alice", "review"))
///         .expect("expected support")
///         .to_vec(),
///     vec![Interval::new(1, 5).expect("expected valid interval")]
/// );
/// assert!(assignments.is_active_at(&("alice", "review"), &4));
/// assert!(!assignments.is_active_at(&("alice", "review"), &5));
/// ```
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct ValidTimeRelation<F: Ord, T: Ord + Clone> {
    facts: BTreeMap<F, ValidTimeSupport<T>>,
}

impl<F: Ord, T: Ord + Clone> ValidTimeRelation<F, T> {
    /// Creates an empty valid-time relation.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::{FiniteRelation, temporal::ValidTimeRelation};
    ///
    /// let relation = ValidTimeRelation::<(&str, &str), i32>::new();
    ///
    /// assert!(relation.is_empty());
    /// assert!(relation.snapshot_at(&0).is_empty());
    /// ```
    #[must_use]
    pub fn new() -> Self {
        Self {
            facts: BTreeMap::new(),
        }
    }

    /// Creates a valid-time relation from `(fact, interval)` entries.
    ///
    /// Repeated facts combine by deterministic canonical coalescing of valid
    /// time support.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::temporal::{Interval, ValidTimeRelation};
    ///
    /// let relation = ValidTimeRelation::from_facts([
    ///     ("alice", Interval::new(1, 3).expect("expected valid interval")),
    ///     ("alice", Interval::new(3, 5).expect("expected valid interval")),
    /// ]);
    ///
    /// assert_eq!(
    ///     relation
    ///         .valid_time_of(&"alice")
    ///         .expect("expected support")
    ///         .to_vec(),
    ///     vec![Interval::new(1, 5).expect("expected valid interval")]
    /// );
    /// ```
    #[must_use]
    pub fn from_facts<I>(facts: I) -> Self
    where
        I: IntoIterator<Item = (F, Interval<T>)>,
    {
        facts.into_iter().collect()
    }

    /// Inserts one valid interval for a fact.
    ///
    /// Returns `true` when the fact's stored valid-time support changes.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::temporal::{Interval, ValidTimeRelation};
    ///
    /// let mut relation = ValidTimeRelation::new();
    ///
    /// assert!(relation.insert("alice", Interval::new(1, 3).expect("expected valid interval")));
    /// assert!(!relation.insert("alice", Interval::new(2, 3).expect("already covered")));
    /// ```
    pub fn insert(&mut self, fact: F, interval: Interval<T>) -> bool {
        match self.facts.entry(fact) {
            std::collections::btree_map::Entry::Vacant(entry) => {
                entry.insert(ValidTimeSupport::from_intervals([interval]));
                true
            }
            std::collections::btree_map::Entry::Occupied(mut entry) => {
                entry.get_mut().insert_interval(interval)
            }
        }
    }

    /// Inserts one interval for a fact from raw bounds.
    ///
    /// Returns an explicit error when `start >= end`.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::temporal::{IntervalError, ValidTimeRelation};
    ///
    /// let mut relation = ValidTimeRelation::new();
    ///
    /// assert!(relation.insert_bounds("alice", 1, 3).expect("expected valid bounds"));
    /// assert_eq!(
    ///     relation.insert_bounds("alice", 3, 3),
    ///     Err(IntervalError::InvalidBounds { start: 3, end: 3 })
    /// );
    /// ```
    pub fn insert_bounds(&mut self, fact: F, start: T, end: T) -> Result<bool, IntervalError<T>> {
        Ok(self.insert(fact, Interval::new(start, end)?))
    }

    /// Returns `true` when the relation contains the given fact with non-empty
    /// valid-time support.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::temporal::{Interval, ValidTimeRelation};
    ///
    /// let relation = ValidTimeRelation::from_facts([(
    ///     "alice",
    ///     Interval::new(1, 3).expect("expected valid interval"),
    /// )]);
    ///
    /// assert!(relation.contains_fact(&"alice"));
    /// assert!(!relation.contains_fact(&"bob"));
    /// ```
    #[must_use]
    pub fn contains_fact(&self, fact: &F) -> bool {
        self.facts.contains_key(fact)
    }

    /// Returns the canonical valid-time support for one fact.
    ///
    /// When a fact is absent, this returns `None`. In this first G5 slice, the
    /// relation does not store empty support as a sentinel value, so `None`
    /// also means the fact has no stored valid-time support.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::temporal::{Interval, ValidTimeRelation};
    ///
    /// let relation = ValidTimeRelation::from_facts([(
    ///     "alice",
    ///     Interval::new(1, 3).expect("expected valid interval"),
    /// )]);
    ///
    /// assert_eq!(
    ///     relation.valid_time_of(&"alice").expect("expected support").to_vec(),
    ///     vec![Interval::new(1, 3).expect("expected valid interval")]
    /// );
    /// assert!(relation.valid_time_of(&"bob").is_none());
    /// ```
    #[must_use]
    pub fn valid_time_of(&self, fact: &F) -> Option<&ValidTimeSupport<T>> {
        self.facts.get(fact)
    }

    /// Returns `true` when `fact` is active at `point`.
    ///
    /// Absent facts are never active.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::temporal::{Interval, ValidTimeRelation};
    ///
    /// let relation = ValidTimeRelation::from_facts([(
    ///     "alice",
    ///     Interval::new(1, 3).expect("expected valid interval"),
    /// )]);
    ///
    /// assert!(relation.is_active_at(&"alice", &1));
    /// assert!(!relation.is_active_at(&"alice", &3));
    /// assert!(!relation.is_active_at(&"bob", &1));
    /// ```
    #[must_use]
    pub fn is_active_at(&self, fact: &F, point: &T) -> bool {
        self.facts
            .get(fact)
            .is_some_and(|support| support.contains(point))
    }

    /// Returns an iterator over facts and valid-time support in deterministic
    /// fact order.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::temporal::{Interval, ValidTimeRelation};
    ///
    /// let relation = ValidTimeRelation::from_facts([
    ///     ("bob", Interval::new(2, 4).expect("expected valid interval")),
    ///     ("alice", Interval::new(1, 3).expect("expected valid interval")),
    /// ]);
    ///
    /// assert_eq!(
    ///     relation
    ///         .iter()
    ///         .map(|(fact, support)| (*fact, support.to_vec()))
    ///         .collect::<Vec<_>>(),
    ///     vec![
    ///         ("alice", vec![Interval::new(1, 3).expect("expected valid interval")]),
    ///         ("bob", vec![Interval::new(2, 4).expect("expected valid interval")]),
    ///     ]
    /// );
    /// ```
    pub fn iter(&self) -> impl Iterator<Item = (&F, &ValidTimeSupport<T>)> {
        self.facts.iter()
    }

    /// Returns the exact support relation of stored facts as a unary relation.
    ///
    /// This materialization forgets time and keeps only which facts have
    /// non-empty valid-time support.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::temporal::{Interval, ValidTimeRelation};
    ///
    /// let relation = ValidTimeRelation::from_facts([
    ///     ("Closure", Interval::new(1, 4).expect("expected valid interval")),
    ///     ("Relations", Interval::new(2, 5).expect("expected valid interval")),
    /// ]);
    ///
    /// assert_eq!(relation.support().to_vec(), vec!["Closure", "Relations"]);
    /// ```
    #[must_use]
    pub fn support(&self) -> UnaryRelation<F>
    where
        F: Clone,
    {
        self.facts.keys().cloned().collect()
    }

    /// Returns the exact snapshot of facts active at `point`.
    ///
    /// The result is a unary relation over stored facts. Facts are present in
    /// the snapshot exactly when their valid-time support contains `point`.
    /// When no facts are active, this returns an empty unary relation.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::{FiniteRelation, temporal::{Interval, ValidTimeRelation}};
    ///
    /// let assignments = ValidTimeRelation::from_facts([
    ///     (("alice", "review"), Interval::new(1, 3).expect("expected valid interval")),
    ///     (("alice", "review"), Interval::new(3, 5).expect("expected valid interval")),
    ///     (("bob", "approve"), Interval::new(2, 4).expect("expected valid interval")),
    /// ]);
    ///
    /// assert_eq!(
    ///     assignments.snapshot_at(&3).to_vec(),
    ///     vec![("alice", "review"), ("bob", "approve")]
    /// );
    /// assert!(assignments.snapshot_at(&5).is_empty());
    /// ```
    #[must_use]
    pub fn snapshot_at(&self, point: &T) -> UnaryRelation<F>
    where
        F: Clone,
    {
        self.facts
            .iter()
            .filter(|(_, support)| support.contains(point))
            .map(|(fact, _)| fact.clone())
            .collect()
    }

    /// Restricts every fact's valid-time support to `constraint`.
    ///
    /// Facts whose support has no overlap with `constraint` are omitted from
    /// the returned relation. Remaining support fragments stay in deterministic
    /// fact order and canonical interval order.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::temporal::{Interval, ValidTimeRelation};
    ///
    /// let assignments = ValidTimeRelation::from_facts([
    ///     (("alice", "review"), Interval::new(1, 3).expect("expected valid interval")),
    ///     (("alice", "review"), Interval::new(5, 7).expect("expected valid interval")),
    ///     (("bob", "approve"), Interval::new(2, 4).expect("expected valid interval")),
    ///     (("carol", "audit"), Interval::new(7, 9).expect("expected valid interval")),
    /// ]);
    ///
    /// let audit_window = Interval::new(2, 6).expect("expected valid interval");
    /// let restricted = assignments.restrict_to(&audit_window);
    ///
    /// assert_eq!(
    ///     restricted
    ///         .valid_time_of(&("alice", "review"))
    ///         .expect("expected support")
    ///         .to_vec(),
    ///     vec![
    ///         Interval::new(2, 3).expect("expected valid interval"),
    ///         Interval::new(5, 6).expect("expected valid interval"),
    ///     ]
    /// );
    /// assert!(!restricted.contains_fact(&("carol", "audit")));
    /// ```
    #[must_use]
    pub fn restrict_to(&self, constraint: &Interval<T>) -> Self
    where
        F: Clone,
    {
        let facts = self
            .facts
            .iter()
            .filter_map(|(fact, support)| {
                let restricted = support.restrict_to(constraint);

                if restricted.is_empty() {
                    None
                } else {
                    Some((fact.clone(), restricted))
                }
            })
            .collect();

        Self { facts }
    }
}

impl<F: Ord, T: Ord + Clone> Default for ValidTimeRelation<F, T> {
    fn default() -> Self {
        Self::new()
    }
}

impl<F: Ord, T: Ord + Clone> FiniteRelation for ValidTimeRelation<F, T> {
    fn len(&self) -> usize {
        self.facts.len()
    }
}

impl<F: Ord, T: Ord + Clone> FromIterator<(F, Interval<T>)> for ValidTimeRelation<F, T> {
    fn from_iter<I: IntoIterator<Item = (F, Interval<T>)>>(iter: I) -> Self {
        let mut relation = Self::new();
        relation.extend(iter);
        relation
    }
}

impl<F: Ord, T: Ord + Clone> Extend<(F, Interval<T>)> for ValidTimeRelation<F, T> {
    fn extend<I: IntoIterator<Item = (F, Interval<T>)>>(&mut self, iter: I) {
        for (fact, interval) in iter {
            self.insert(fact, interval);
        }
    }
}

impl<Value: Ord + Clone, Time: Ord + Clone> ValidTimeRelation<Value, Time> {
    /// Converts scalar facts into a unary relation support set.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::temporal::{Interval, ValidTimeRelation};
    ///
    /// let relation = ValidTimeRelation::from_facts([(
    ///     "Closure",
    ///     Interval::new(1, 4).expect("expected valid interval"),
    /// )]);
    ///
    /// assert_eq!(relation.to_unary_relation().to_vec(), vec!["Closure"]);
    /// ```
    #[must_use]
    pub fn to_unary_relation(&self) -> UnaryRelation<Value> {
        self.support()
    }
}

impl<A: Ord + Clone, B: Ord + Clone, Time: Ord + Clone> ValidTimeRelation<(A, B), Time> {
    /// Converts pair facts into a binary relation support set.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::temporal::{Interval, ValidTimeRelation};
    ///
    /// let relation = ValidTimeRelation::from_facts([(
    ///     ("alice", "review"),
    ///     Interval::new(1, 3).expect("expected valid interval"),
    /// )]);
    ///
    /// assert_eq!(relation.to_binary_relation().to_vec(), vec![("alice", "review")]);
    /// ```
    #[must_use]
    pub fn to_binary_relation(&self) -> BinaryRelation<A, B> {
        self.facts.keys().cloned().collect()
    }
}

impl<Value: Ord + Clone, Time: Ord + Clone> ValidTimeRelation<Vec<Value>, Time> {
    /// Converts row facts into an n-ary relation with the given schema.
    ///
    /// This method reuses the current `NaryRelation` validation rules, so
    /// duplicate or blank column names and row-arity mismatches return
    /// `NaryRelationError`.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::temporal::{Interval, ValidTimeRelation};
    ///
    /// let rows = ValidTimeRelation::from_facts([(
    ///     vec!["Alice", "Math", "passed"],
    ///     Interval::new(1, 3).expect("expected valid interval"),
    /// )]);
    ///
    /// let relation = rows
    ///     .to_nary_relation(["student", "course", "status"])
    ///     .expect("expected valid n-ary relation");
    ///
    /// assert_eq!(relation.to_rows(), vec![vec!["Alice", "Math", "passed"]]);
    /// ```
    pub fn to_nary_relation<I, S>(
        &self,
        schema: I,
    ) -> Result<NaryRelation<Value>, NaryRelationError>
    where
        I: IntoIterator<Item = S>,
        S: Into<String>,
    {
        NaryRelation::from_rows(schema, self.facts.keys().cloned())
    }
}