set_theory 1.0.0

//! # Advanced Set Operations
//!
//! Provides advanced set operations beyond basic operations.
//!
//! This includes Cartesian product, partition validation, and
//! inclusion-exclusion principle calculations.

use crate::models::CustomSet;
use crate::operations::basic_ops::SetOperations;
use std::hash::Hash;

/// Provides advanced set operations beyond the basic operations.
///
/// This struct includes operations such as Cartesian product, power set,
/// partition validation, and the inclusion-exclusion principle.
///
/// # Examples
///
/// ```rust
/// use set_theory::models::CustomSet;
/// use set_theory::operations::AdvancedSetOperations;
///
/// let c = CustomSet::from(vec![1, 2, 3]);
/// let d = CustomSet::from(vec!['a', 'b']);
/// let cartesian = AdvancedSetOperations::cartesian_product(&c, &d);
/// assert_eq!(cartesian.cardinality(), 6); // 3 × 2 = 6
/// ```
pub struct AdvancedSetOperations;

impl AdvancedSetOperations {
    /// Returns the Cartesian product of two sets.
    ///
    /// # Notation
    ///
    /// A × B = {(a, b) | a ∈ A and b ∈ B}
    ///
    /// # Arguments
    ///
    /// * `a` - First set
    /// * `b` - Second set
    ///
    /// # Returns
    ///
    /// A new `CustomSet` containing all ordered pairs (a, b).
    ///
    /// # Complexity
    ///
    /// O(|A| × |B|) - generates all pairs
    ///
    /// # Examples
    ///
    /// ```rust
    /// use set_theory::models::CustomSet;
    /// use set_theory::operations::AdvancedSetOperations;
    ///
    /// let c = CustomSet::from(vec![1, 2, 3]);
    /// let d = CustomSet::from(vec!['a', 'b']);
    /// let result = AdvancedSetOperations::cartesian_product(&c, &d);
    /// assert_eq!(result.cardinality(), 6);
    /// ```
    pub fn cartesian_product<T: Eq + Hash + Clone, U: Eq + Hash + Clone>(
        a: &CustomSet<T>,
        b: &CustomSet<U>,
    ) -> CustomSet<(T, U)> {
        if a.is_empty() || b.is_empty() {
            return CustomSet::empty();
        }

        let mut pairs = Vec::new();
        for element_a in a.iter() {
            for element_b in b.iter() {
                pairs.push((element_a.clone(), element_b.clone()));
            }
        }
        CustomSet::new(pairs)
    }

    /// Returns the Cartesian product of n sets.
    ///
    /// # Notation
    ///
    /// A₁ × A₂ × ... × Aₙ = {(a₁, a₂, ..., aₙ) | aᵢ ∈ Aᵢ}
    ///
    /// # Arguments
    ///
    /// * `sets` - Vector of sets to compute Cartesian product
    ///
    /// # Returns
    ///
    /// A new `CustomSet` containing all possible n-tuples.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use set_theory::models::CustomSet;
    /// use set_theory::operations::AdvancedSetOperations;
    ///
    /// let sets = vec![
    ///     CustomSet::from(vec![1, 2]),
    ///     CustomSet::from(vec![3, 4]),
    /// ];
    /// let result = AdvancedSetOperations::cartesian_product_n(sets);
    /// assert_eq!(result.cardinality(), 4); // 2 × 2 = 4
    /// ```
    pub fn cartesian_product_n<T: Eq + Hash + Clone>(sets: Vec<CustomSet<T>>) -> CustomSet<Vec<T>> {
        if sets.is_empty() || sets.iter().any(|s| s.is_empty()) {
            return CustomSet::empty();
        }

        let mut result: Vec<Vec<T>> = vec![vec![]];
        for set in sets {
            let mut new_result = Vec::new();
            for prefix in &result {
                for element in set.iter() {
                    let mut new_tuple = prefix.clone();
                    new_tuple.push(element.clone());
                    new_result.push(new_tuple);
                }
            }
            result = new_result;
        }
        CustomSet::new(result)
    }

    /// Checks if a collection of sets forms a valid partition.
    ///
    /// A partition of set A is a collection of non-empty subsets where:
    /// 1. Union of all subsets equals the original set
    /// 2. All subsets are pairwise disjoint
    ///
    /// # Arguments
    ///
    /// * `partitions` - Collection of potential partition sets
    /// * `original` - The original set to partition
    ///
    /// # Returns
    ///
    /// `true` if the collection forms a valid partition.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use set_theory::models::CustomSet;
    /// use set_theory::operations::AdvancedSetOperations;
    ///
    /// let original = CustomSet::from(vec![1, 2, 3, 4, 5, 6, 7, 8]);
    /// let partitions = CustomSet::from(vec![
    ///     CustomSet::from(vec![1]),
    ///     CustomSet::from(vec![2, 3, 4]),
    ///     CustomSet::from(vec![5, 6]),
    ///     CustomSet::from(vec![7, 8]),
    /// ]);
    /// assert!(AdvancedSetOperations::is_partition(&partitions, &original));
    /// ```
    pub fn is_partition<T: Eq + Hash + Clone + std::fmt::Debug>(
        partitions: &CustomSet<CustomSet<T>>,
        original: &CustomSet<T>,
    ) -> bool {
        // Check all partitions are non-empty
        // Criterion: ∀i, Aᵢ ≠ ∅
        for partition in partitions.iter() {
            if partition.is_empty() {
                return false;
            }
        }

        // Check union of all partitions equals original
        // Criterion: A₁ ∪ A₂ ∪ ... ∪ Aₙ = A
        let mut union_set = CustomSet::<T>::empty();
        for partition in partitions.iter() {
            union_set = SetOperations::union(&union_set, partition);
        }
        if !union_set.equals(original) {
            return false;
        }

        // Check all partitions are pairwise disjoint
        // Criterion: ∀i≠j, Aᵢ ∩ Aⱼ = ∅
        let partition_list: Vec<_> = partitions.iter().collect();
        for i in 0..partition_list.len() {
            for j in (i + 1)..partition_list.len() {
                if !partition_list[i].is_disjoint_from(partition_list[j]) {
                    return false;
                }
            }
        }

        true
    }

    /// Applies the inclusion-exclusion principle for two sets.
    ///
    /// # Formula
    ///
    /// |A ∪ B| = |A| + |B| - |A ∩ B|
    ///
    /// # Arguments
    ///
    /// * `a` - First set
    /// * `b` - Second set
    ///
    /// # Returns
    ///
    /// The cardinality of the union without computing it.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use set_theory::models::CustomSet;
    /// use set_theory::operations::AdvancedSetOperations;
    ///
    /// let a = CustomSet::from(vec![1, 2, 3, 4, 5]);
    /// let b = CustomSet::from(vec![4, 5, 6, 7, 8]);
    /// let count = AdvancedSetOperations::inclusion_exclusion_2(&a, &b);
    /// assert_eq!(count, 8);
    /// ```
    pub fn inclusion_exclusion_2<T: Eq + Hash + Clone>(
        a: &CustomSet<T>,
        b: &CustomSet<T>,
    ) -> usize {
        a.cardinality() + b.cardinality() - SetOperations::intersection(a, b).cardinality()
    }

    /// Applies the inclusion-exclusion principle for three sets.
    ///
    /// # Formula
    ///
    /// |A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|
    ///
    /// # Arguments
    ///
    /// * `a` - First set
    /// * `b` - Second set
    /// * `c` - Third set
    ///
    /// # Returns
    ///
    /// The cardinality of the union without computing it.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use set_theory::models::CustomSet;
    /// use set_theory::operations::AdvancedSetOperations;
    ///
    /// let a = CustomSet::from(vec![1, 2, 3, 4]);
    /// let b = CustomSet::from(vec![3, 4, 5, 6]);
    /// let c = CustomSet::from(vec![5, 6, 7, 8]);
    /// let count = AdvancedSetOperations::inclusion_exclusion_3(&a, &b, &c);
    /// assert_eq!(count, 8);
    /// ```
    pub fn inclusion_exclusion_3<T: Eq + Hash + Clone>(
        a: &CustomSet<T>,
        b: &CustomSet<T>,
        c: &CustomSet<T>,
    ) -> usize {
        a.cardinality() + b.cardinality() + c.cardinality()
            - SetOperations::intersection(a, b).cardinality()
            - SetOperations::intersection(a, c).cardinality()
            - SetOperations::intersection(b, c).cardinality()
            + SetOperations::intersection(&SetOperations::intersection(a, b), c).cardinality()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_cartesian_product() {
        let c = CustomSet::from(vec![1, 2, 3]);
        let d = CustomSet::from(vec!['a', 'b']);
        let result = AdvancedSetOperations::cartesian_product(&c, &d);
        assert_eq!(result.cardinality(), 6);
        assert!(result.contains(&(1, 'a')));
        assert!(result.contains(&(3, 'b')));
    }

    #[test]
    fn test_cartesian_product_empty() {
        let a = CustomSet::from(vec![1, 2, 3]);
        let empty = CustomSet::<char>::empty();
        let result = AdvancedSetOperations::cartesian_product(&a, &empty);
        assert!(result.is_empty());
    }

    #[test]
    fn test_cartesian_product_n() {
        let sets: Vec<CustomSet<i32>> =
            vec![CustomSet::from(vec![1, 2]), CustomSet::from(vec![3, 4])];
        let result = AdvancedSetOperations::cartesian_product_n(sets);

        assert_eq!(result.cardinality(), 4, "Should have 2 × 2 = 4 tuples");
    }

    #[test]
    fn test_is_partition_valid() {
        let original = CustomSet::from(vec![1, 2, 3, 4, 5, 6, 7, 8]);
        let partitions = CustomSet::from(vec![
            CustomSet::from(vec![1]),
            CustomSet::from(vec![2, 3, 4]),
            CustomSet::from(vec![5, 6]),
            CustomSet::from(vec![7, 8]),
        ]);
        assert!(AdvancedSetOperations::is_partition(&partitions, &original));
    }

    #[test]
    fn test_is_partition_invalid_overlap() {
        let original = CustomSet::from(vec![1, 2, 3, 4]);
        let partitions = CustomSet::from(vec![
            CustomSet::from(vec![1, 2]),
            CustomSet::from(vec![2, 3]), // Overlap with 2
            CustomSet::from(vec![4]),
        ]);
        assert!(!AdvancedSetOperations::is_partition(&partitions, &original));
    }

    #[test]
    fn test_inclusion_exclusion_2() {
        let a = CustomSet::from(vec![1, 2, 3, 4, 5]);
        let b = CustomSet::from(vec![4, 5, 6, 7, 8]);
        let calculated = AdvancedSetOperations::inclusion_exclusion_2(&a, &b);
        let actual = SetOperations::union(&a, &b).cardinality();
        assert_eq!(calculated, actual);
        assert_eq!(calculated, 8);
    }

    #[test]
    fn test_inclusion_exclusion_3() {
        let a = CustomSet::from(vec![1, 2, 3, 4]);
        let b = CustomSet::from(vec![3, 4, 5, 6]);
        let c = CustomSet::from(vec![5, 6, 7, 8]);
        let calculated = AdvancedSetOperations::inclusion_exclusion_3(&a, &b, &c);
        let actual = SetOperations::union(&SetOperations::union(&a, &b), &c).cardinality();
        assert_eq!(calculated, actual);
    }

    #[test]
    fn test_real_world_inclusion_exclusion() {
        // Numbers 1-100 divisible by 3 or 5
        let universal = CustomSet::from((1..=100).collect::<Vec<_>>());
        let div3 = CustomSet::from_predicate(universal.iter().cloned(), |x| x % 3 == 0);
        let div5 = CustomSet::from_predicate(universal.iter().cloned(), |x| x % 5 == 0);

        let count = AdvancedSetOperations::inclusion_exclusion_2(&div3, &div5);
        assert_eq!(count, 47);
    }
}