set_theory 1.0.0

//! # CustomSet Implementation
//!
//! A mutable mathematical set implementation with unique elements.
//!
//! This is the primary set type in the library, providing full support
//! for all standard set operations with mutable access.

use crate::operations::lazy_ops::PowerSet;
use crate::traits::MathSet;
use std::collections::HashSet;
use std::collections::hash_set;
use std::hash::Hash;
use std::iter::FromIterator;

/// A mathematical set containing unique elements.
///
/// `CustomSet` is the primary mutable set implementation in this library.
/// It follows standard set theory principles where order does not matter
/// and duplicate elements are automatically removed.
///
/// # Type Parameters
///
/// * `T` - The type of elements. Must implement `Eq + Hash + Clone`
///
/// # Examples
///
/// ```rust
/// use set_theory::models::CustomSet;
///
/// // Create from Vec
/// let numbers = CustomSet::from(vec![1, 2, 3, 4]);
///
/// // Create empty set
/// let empty = CustomSet::<i32>::empty();
///
/// // Create from predicate
/// let evens = CustomSet::from_predicate(0..100, |x| x % 2 == 0);
/// ```
///
/// # Performance Characteristics
///
/// | Operation | Complexity |
/// |-----------|------------|
/// | contains | O(1) average |
/// | insert | O(1) average |
/// | remove | O(1) average |
/// | union | O(n + m) |
/// | intersection | O(min(n, m)) |
/// | difference | O(n) |
#[derive(Clone)]
pub struct CustomSet<T: Eq + Hash + Clone> {
    /// Internal storage using HashSet for O(1) lookups
    elements: HashSet<T>,
}

impl<T: Eq + Hash + Clone> CustomSet<T> {
    /// Creates an empty set.
    ///
    /// # Returns
    ///
    /// A new `CustomSet` with no elements.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use set_theory::models::CustomSet;
    ///
    /// let empty = CustomSet::<i32>::empty();
    /// assert_eq!(empty.cardinality(), 0);
    /// ```
    pub fn empty() -> Self {
        Self {
            elements: HashSet::new(),
        }
    }

    /// Creates a set from an iterable of elements.
    ///
    /// Duplicate elements are automatically removed.
    ///
    /// # Arguments
    ///
    /// * `iter` - Any iterable collection of elements
    ///
    /// # Returns
    ///
    /// A new `CustomSet` containing unique elements from the iterable.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use set_theory::models::CustomSet;
    ///
    /// let set = CustomSet::from(vec![1, 2, 2, 3, 3, 3]);
    /// assert_eq!(set.cardinality(), 3);
    /// ```
    pub fn new<I: IntoIterator<Item = T>>(iter: I) -> Self {
        Self {
            elements: HashSet::from_iter(iter),
        }
    }

    /// Creates a set from a predicate function applied to a universe.
    ///
    /// Only elements from the universe that satisfy the predicate are included.
    ///
    /// # Arguments
    ///
    /// * `universe` - The universe of elements to filter
    /// * `predicate` - Function that returns true for elements to include
    ///
    /// # Returns
    ///
    /// A new `CustomSet` containing elements that satisfy the predicate.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use set_theory::models::CustomSet;
    ///
    /// let evens = CustomSet::from_predicate(0..10, |x| x % 2 == 0);
    /// assert_eq!(evens.cardinality(), 5);
    /// assert!(evens.contains(&4));
    /// ```
    pub fn from_predicate<I, F>(universe: I, predicate: F) -> Self
    where
        I: IntoIterator<Item = T>,
        F: Fn(&T) -> bool,
    {
        Self {
            elements: universe.into_iter().filter(|x| predicate(x)).collect(),
        }
    }

    /// Returns the cardinality (number of elements) in the set.
    ///
    /// # Notation
    ///
    /// |A| or n(A)
    ///
    /// # Examples
    ///
    /// ```rust
    /// use set_theory::models::CustomSet;
    ///
    /// let set = CustomSet::from(vec![1, 2, 3]);
    /// assert_eq!(set.cardinality(), 3);
    /// ```
    pub fn cardinality(&self) -> usize {
        self.elements.len()
    }

    /// Checks if an element is a member of this set.
    ///
    /// # Notation
    ///
    /// x ∈ A
    ///
    /// # Examples
    ///
    /// ```rust
    /// use set_theory::models::CustomSet;
    ///
    /// let set = CustomSet::from(vec![1, 2, 3]);
    /// assert!(set.contains(&2));
    /// assert!(!set.contains(&5));
    /// ```
    pub fn contains(&self, element: &T) -> bool {
        self.elements.contains(element)
    }

    /// Adds an element to the set.
    ///
    /// If the element already exists, the set remains unchanged.
    ///
    /// # Arguments
    ///
    /// * `element` - The element to add
    ///
    /// # Returns
    ///
    /// `true` if the element was added, `false` if it already existed.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use set_theory::models::CustomSet;
    ///
    /// let mut set = CustomSet::from(vec![1, 2]);
    /// assert!(set.add(3));
    /// assert!(!set.add(3)); // Already exists
    /// ```
    pub fn add(&mut self, element: T) -> bool {
        self.elements.insert(element)
    }

    /// Removes an element from the set.
    ///
    /// # Arguments
    ///
    /// * `element` - The element to remove
    ///
    /// # Returns
    ///
    /// `true` if the element was removed, `false` if it was not found.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use set_theory::models::CustomSet;
    ///
    /// let mut set = CustomSet::from(vec![1, 2, 3]);
    /// assert!(set.remove(&2));
    /// assert!(!set.remove(&2)); // Already removed
    /// ```
    pub fn remove(&mut self, element: &T) -> bool {
        self.elements.remove(element)
    }

    /// Removes all elements from the set.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use set_theory::models::CustomSet;
    ///
    /// let mut set = CustomSet::from(vec![1, 2, 3]);
    /// set.clear();
    /// assert!(set.is_empty());
    /// ```
    pub fn clear(&mut self) {
        self.elements.clear()
    }

    /// Checks if this set is a subset of another set.
    ///
    /// # Notation
    ///
    /// A ⊆ B
    ///
    /// # Examples
    ///
    /// ```rust
    /// use set_theory::models::CustomSet;
    ///
    /// let a = CustomSet::from(vec![1, 2, 3]);
    /// let b = CustomSet::from(vec![1, 2, 3, 4, 5]);
    /// assert!(a.is_subset_of(&b));
    /// ```
    pub fn is_subset_of(&self, other: &Self) -> bool {
        self.elements.iter().all(|e| other.elements.contains(e))
    }

    /// Checks if this set is a proper subset of another set.
    ///
    /// # Notation
    ///
    /// A ⊂ B
    ///
    /// # Examples
    ///
    /// ```rust
    /// use set_theory::models::CustomSet;
    ///
    /// let a = CustomSet::from(vec![1, 2, 3]);
    /// let b = CustomSet::from(vec![1, 2, 3]);
    /// let c = CustomSet::from(vec![1, 2, 3, 4]);
    /// assert!(!a.is_proper_subset_of(&b));
    /// assert!(a.is_proper_subset_of(&c));
    /// ```
    pub fn is_proper_subset_of(&self, other: &Self) -> bool {
        self.is_subset_of(other) && self.cardinality() < other.cardinality()
    }

    /// Checks if this set is a superset of another set.
    ///
    /// # Notation
    ///
    /// A ⊇ B
    ///
    /// # Examples
    ///
    /// ```rust
    /// use set_theory::models::CustomSet;
    ///
    /// let a = CustomSet::from(vec![1, 2, 3, 4, 5]);
    /// let b = CustomSet::from(vec![1, 2, 3]);
    /// assert!(a.is_superset_of(&b));
    /// ```
    pub fn is_superset_of(&self, other: &Self) -> bool {
        other.is_subset_of(self)
    }

    /// Checks if this set is a proper superset of another set.
    ///
    /// # Notation
    ///
    /// A ⊃ B
    ///
    /// # Examples
    ///
    /// ```rust
    /// use set_theory::models::CustomSet;
    ///
    /// let a = CustomSet::from(vec![1, 2, 3, 4]);
    /// let b = CustomSet::from(vec![1, 2, 3]);
    /// assert!(a.is_proper_superset_of(&b));
    /// ```
    pub fn is_proper_superset_of(&self, other: &Self) -> bool {
        other.is_proper_subset_of(self)
    }

    /// Checks if this set is equal to another set.
    ///
    /// # Notation
    ///
    /// A = B
    ///
    /// # Examples
    ///
    /// ```rust
    /// use set_theory::models::CustomSet;
    ///
    /// let a = CustomSet::from(vec![1, 2, 3]);
    /// let b = CustomSet::from(vec![3, 2, 1]);
    /// assert!(a.equals(&b));
    /// ```
    pub fn equals(&self, other: &Self) -> bool {
        self.cardinality() == other.cardinality() && self.is_subset_of(other)
    }

    /// Checks if this set is equivalent to another set (same cardinality).
    ///
    /// # Notation
    ///
    /// A ~ B
    ///
    /// # Examples
    ///
    /// ```rust
    /// use set_theory::models::CustomSet;
    ///
    /// let a = CustomSet::from(vec![1, 2, 3, 4]);
    /// let b = CustomSet::from(vec!['a', 'b', 'c', 'd']);
    /// assert!(a.is_equivalent_to(&b));
    /// ```
    pub fn is_equivalent_to<U: Eq + Hash + Clone>(&self, other: &CustomSet<U>) -> bool {
        self.cardinality() == other.cardinality()
    }

    /// Checks if this set is disjoint from another set.
    ///
    /// # Notation
    ///
    /// A // B
    ///
    /// # Examples
    ///
    /// ```rust
    /// use set_theory::models::CustomSet;
    ///
    /// let a = CustomSet::from(vec![1, 2, 3]);
    /// let b = CustomSet::from(vec![4, 5, 6]);
    /// assert!(a.is_disjoint_from(&b));
    /// ```
    pub fn is_disjoint_from(&self, other: &Self) -> bool {
        self.elements.iter().all(|e| !other.contains(e))
    }

    /// Returns true if the set contains no elements.
    ///
    /// # Notation
    ///
    /// A = ∅
    ///
    /// # Examples
    ///
    /// ```rust
    /// use set_theory::models::CustomSet;
    ///
    /// let empty = CustomSet::<i32>::empty();
    /// assert!(empty.is_empty());
    /// ```
    pub fn is_empty(&self) -> bool {
        self.elements.is_empty()
    }

    /// Returns an iterator over the elements.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use set_theory::models::CustomSet;
    ///
    /// let set = CustomSet::from(vec![1, 2, 3]);
    /// for element in set.iter() {
    ///     println!("{}", element);
    /// }
    /// ```
    pub fn iter(&self) -> impl Iterator<Item = &T> {
        self.elements.iter()
    }

    /// Returns the intersection of this set with another.
    ///
    /// # Notation
    ///
    /// A ∩ B = {x | x ∈ A and x ∈ B}
    ///
    /// # Arguments
    ///
    /// * `other` - Reference to the other set
    ///
    /// # Returns
    ///
    /// A new `CustomSet` containing elements present in both sets.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use set_theory::models::CustomSet;
    ///
    /// let a = CustomSet::from(vec![2, 4, 6, 8, 10]);
    /// let b = CustomSet::from(vec![4, 10, 14, 18]);
    /// let result = a.intersection(&b);
    /// assert_eq!(result.cardinality(), 2);
    /// ```
    pub fn intersection(&self, other: &Self) -> Self {
        Self {
            elements: self
                .elements
                .intersection(&other.elements)
                .cloned()
                .collect(),
        }
    }

    /// Returns the union of this set with another.
    ///
    /// # Notation
    ///
    /// A ∪ B = {x | x ∈ A or x ∈ B}
    ///
    /// # Arguments
    ///
    /// * `other` - Reference to the other set
    ///
    /// # Returns
    ///
    /// A new `CustomSet` containing all elements from both sets.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use set_theory::models::CustomSet;
    ///
    /// let a = CustomSet::from(vec![2, 5, 8]);
    /// let b = CustomSet::from(vec![7, 5, 22]);
    /// let result = a.union(&b);
    /// assert_eq!(result.cardinality(), 5);
    /// ```
    pub fn union(&self, other: &Self) -> Self {
        CustomSet {
            elements: self.elements.union(&other.elements).cloned().collect(),
        }
    }

    /// Returns the complement of this set with respect to a universal set.
    ///
    /// # Notation
    ///
    /// A' = {x | x ∈ U and x ∉ A}
    ///
    /// # Arguments
    ///
    /// * `universal` - Reference to the universal set
    ///
    /// # Returns
    ///
    /// A new `CustomSet` containing elements in universal but not in this set.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use set_theory::models::CustomSet;
    ///
    /// let universal = CustomSet::from(vec![1, 2, 3, 4, 5, 6, 7, 8, 9]);
    /// let a = CustomSet::from(vec![1, 3, 7, 9]);
    /// let result = a.complement(&universal);
    /// assert_eq!(result.cardinality(), 5);
    /// ```
    pub fn complement(&self, universal: &Self) -> Self {
        Self {
            elements: universal
                .elements
                .iter()
                .filter(|e| !self.elements.contains(*e))
                .cloned()
                .collect(),
        }
    }

    ///
    /// # Notation
    ///
    /// A - B = {x | x ∈ A and x ∉ B}
    ///
    /// # Arguments
    ///
    /// * `other` - Reference to the other set
    ///
    /// # Returns
    ///
    /// A new `CustomSet` containing elements in this set but not in other.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use set_theory::models::CustomSet;
    ///
    /// let a = CustomSet::from(vec![1, 2, 3, 4, 5]);
    /// let b = CustomSet::from(vec![2, 4]);
    /// let result = a.difference(&b);
    /// assert_eq!(result.cardinality(), 3);
    /// ```
    pub fn difference(&self, other: &Self) -> Self {
        Self {
            elements: self
                .elements
                .iter()
                .filter(|e| !other.elements.contains(*e))
                .cloned()
                .collect(),
        }
    }

    /// Returns the symmetric difference of this set with another.
    ///
    /// # Notation
    ///
    /// A ⊕ B = (A ∪ B) - (A ∩ B)
    ///
    /// # Arguments
    ///
    /// * `other` - Reference to the other set
    ///
    /// # Returns
    ///
    /// A new `CustomSet` containing elements in either set but not both.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use set_theory::models::CustomSet;
    ///
    /// let a = CustomSet::from(vec![2, 4, 6]);
    /// let b = CustomSet::from(vec![2, 3, 5]);
    /// let result = a.symmetric_difference(&b);
    /// assert_eq!(result.cardinality(), 4);
    /// ```
    pub fn symmetric_difference(&self, other: &Self) -> Self {
        self.union(other).difference(&self.intersection(other))
    }

    /// Returns the power set of this set (lazy evaluation).
    ///
    /// # Notation
    ///
    /// P(A) or 2^A
    ///
    /// # Returns
    ///
    /// A `PowerSet` iterator that yields subsets one by one.
    ///
    /// # Performance Note
    ///
    /// For a set with n elements, the power set contains 2^n subsets.
    /// This method uses lazy evaluation to avoid memory explosion.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use set_theory::models::CustomSet;
    ///
    /// let a = CustomSet::from(vec![1, 2]);
    /// let power_set: Vec<_> = a.power_set().collect();
    /// assert_eq!(power_set.len(), 4); // 2^2 = 4
    /// ```
    pub fn power_set(&self) -> PowerSet<T> {
        PowerSet::new(self)
    }
}

// Implement MathSet trait
impl<T: Eq + Hash + Clone> MathSet<T> for CustomSet<T> {
    fn cardinality(&self) -> usize {
        self.cardinality()
    }

    fn contains(&self, element: &T) -> bool {
        self.contains(element)
    }

    fn is_subset_of(&self, other: &Self) -> bool {
        self.is_subset_of(other)
    }

    fn is_proper_subset_of(&self, other: &Self) -> bool {
        self.is_proper_subset_of(other)
    }

    fn equals(&self, other: &Self) -> bool {
        self.equals(other)
    }

    fn is_disjoint_from(&self, other: &Self) -> bool {
        self.is_disjoint_from(other)
    }

    fn is_empty(&self) -> bool {
        self.is_empty()
    }
}

// Implement FromIterator
impl<T: Eq + Hash + Clone> FromIterator<T> for CustomSet<T> {
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        CustomSet::new(iter)
    }
}

// Implement IntoIterator
impl<T: Eq + Hash + Clone> IntoIterator for CustomSet<T> {
    type Item = T;
    type IntoIter = hash_set::IntoIter<T>;

    fn into_iter(self) -> Self::IntoIter {
        self.elements.into_iter()
    }
}

// Implement From<Vec<T>>
impl<T: Eq + Hash + Clone> From<Vec<T>> for CustomSet<T> {
    /// Creates a CustomSet from a Vec.
    ///
    /// # Arguments
    ///
    /// * `vec` - A vector of elements to create the set from
    ///
    /// # Returns
    ///
    /// A new `CustomSet` containing unique elements from the vector.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use set_theory::models::CustomSet;
    ///
    /// let set = CustomSet::from(vec![1, 2, 3]);
    /// assert_eq!(set.cardinality(), 3);
    /// ```
    fn from(vec: Vec<T>) -> Self {
        CustomSet::new(vec)
    }
}

// Implement From<&[T]>
impl<T: Eq + Hash + Clone> From<&[T]> for CustomSet<T> {
    fn from(slice: &[T]) -> Self {
        CustomSet::new(slice.iter().cloned())
    }
}

// Implement Display
impl<T: Eq + Hash + Clone + std::fmt::Display> std::fmt::Display for CustomSet<T> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        if self.is_empty() {
            write!(f, "∅")
        } else {
            let elements: Vec<_> = self.elements.iter().collect();
            write!(
                f,
                "{{{}}}",
                elements
                    .iter()
                    .map(|e| e.to_string())
                    .collect::<Vec<_>>()
                    .join(", ")
            )
        }
    }
}

// Implement Debug
impl<T: Eq + Hash + Clone + std::fmt::Debug> std::fmt::Debug for CustomSet<T> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "CustomSet({:?})", self.elements)
    }
}

// Implement PartialEq
impl<T: Eq + Hash + Clone> PartialEq for CustomSet<T> {
    fn eq(&self, other: &Self) -> bool {
        self.equals(other)
    }
}

// Implement Eq
impl<T: Eq + Hash + Clone> Eq for CustomSet<T> {}

// Implement Hash
impl<T: Eq + Hash + Clone + std::fmt::Debug> std::hash::Hash for CustomSet<T> {
    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
        let mut elements: Vec<_> = self.elements.iter().collect();
        elements.sort_by(|a, b| format!("{:?}", a).cmp(&format!("{:?}", b)));
        for element in elements {
            element.hash(state);
        }
    }
}