set_theory 1.0.0

//! # MultiSet Unit Tests
//!
//! Comprehensive test suite for the `MultiSet` data structure.
//!
//! This module tests all functionality of the `MultiSet` (bag) implementation,
//! including multiplicity tracking, multiset operations, and conversions.
//!
//! ## Test Coverage
//!
//! - **Creation**: Empty multisets, from iterators
//! - **Multiplicity**: Count tracking for each element
//! - **Cardinality**: Total count including duplicates
//! - **Operations**: Union, intersection, difference, sum
//! - **Conversion**: MultiSet to CustomSet
//! - **Edge Cases**: Zero multiplicity, negative operations
//!
//! ## Running Tests
//!
//! ```bash
//! # Run all MultiSet tests
//! cargo test multiset_tests
//!
//! # Run specific test
//! cargo test multiset_tests::test_multiset_create
//! ```
//!
//! ## Theory Reference
//!
//! Based on multiset theory from:
//! - Multiset operations: max/min multiplicity rules

use set_theory::models::MultiSet;

/// Tests creating a multiset from an iterable.
///
/// ## Summary
///
/// Verifies that a multiset correctly tracks element multiplicity.
///
/// ## Description
///
/// Tests the `MultiSet::from()` constructor with duplicate elements,
/// ensuring proper multiplicity counting.
///
/// ## Input
///
/// - Iterable: `['a', 'a', 'a', 'b', 'c']`
///
/// ## Expected Output
///
/// - Cardinality: 5 (total count)
/// - Unique count: 3
/// - Multiplicity of 'a': 3
///
/// ## Examples
///
/// ```rust
/// let ms = MultiSet::from(vec!['a', 'a', 'a', 'b', 'c']);
/// assert_eq!(ms.multiplicity(&'a'), 3);
/// ```
#[test]
fn test_multiset_create() {
    let ms = MultiSet::from(vec!['a', 'a', 'a', 'b', 'c']);

    assert_eq!(ms.cardinality(), 5, "Total cardinality should be 5");
    assert_eq!(ms.unique_count(), 3, "Unique count should be 3");
    assert_eq!(ms.multiplicity(&'a'), 3, "Multiplicity of 'a' should be 3");
    assert_eq!(ms.multiplicity(&'b'), 1, "Multiplicity of 'b' should be 1");
    assert_eq!(ms.multiplicity(&'c'), 1, "Multiplicity of 'c' should be 1");
    assert_eq!(ms.multiplicity(&'d'), 0, "Multiplicity of 'd' should be 0");
}

/// Tests empty multiset creation.
///
/// ## Summary
///
/// Verifies that an empty multiset has zero cardinality.
///
/// ## Expected Output
///
/// - Cardinality: 0
/// - Unique count: 0
/// - Is empty: `true`
///
/// ## Examples
///
/// ```rust
/// let empty = MultiSet::<i32>::empty();
/// assert!(empty.is_empty());
/// ```
#[test]
fn test_multiset_empty() {
    let empty = MultiSet::<i32>::empty();

    assert_eq!(
        empty.cardinality(),
        0,
        "Empty multiset should have cardinality 0"
    );
    assert_eq!(
        empty.unique_count(),
        0,
        "Empty multiset should have 0 unique elements"
    );
    assert!(
        empty.is_empty(),
        "Empty multiset should return true for is_empty()"
    );
}

/// Tests multiset union operation (max multiplicity).
///
/// ## Summary
///
/// Verifies union returns maximum multiplicity for each element.
///
/// ## Description
///
/// Tests P ∪ Q where multiplicity = max(P, Q) for each element.
///
/// ## Notation
///
/// P ∪ Q
///
/// ## Input
///
/// - P = `{'a': 3, 'c': 1, 'd': 2}`
/// - Q = `{'a': 2, 'b': 1, 'c': 2}`
///
/// ## Expected Output
///
/// - Result = `{'a': 3, 'b': 1, 'c': 2, 'd': 2}`
///
/// ## Theory Reference
///
/// Multiset union: multiplicity = max(multiplicity in P, multiplicity in Q)
///
/// ## Examples
///
/// ```rust
/// let p = MultiSet::from(vec!['a', 'a', 'a', 'c']);
/// let q = MultiSet::from(vec!['a', 'a', 'b', 'c', 'c']);
/// let result = p.union(&q);
/// assert_eq!(result.multiplicity(&'a'), 3);
/// ```
#[test]
fn test_multiset_union() {
    let p = MultiSet::from(vec!['a', 'a', 'a', 'c', 'd', 'd']);
    let q = MultiSet::from(vec!['a', 'a', 'b', 'c', 'c']);
    let result = p.union(&q);

    assert_eq!(result.multiplicity(&'a'), 3, "Max(3, 2) = 3");
    assert_eq!(result.multiplicity(&'b'), 1, "Max(0, 1) = 1");
    assert_eq!(result.multiplicity(&'c'), 2, "Max(1, 2) = 2");
    assert_eq!(result.multiplicity(&'d'), 2, "Max(2, 0) = 2");
}

/// Tests multiset intersection operation (min multiplicity).
///
/// ## Summary
///
/// Verifies intersection returns minimum multiplicity for each element.
///
/// ## Description
///
/// Tests P ∩ Q where multiplicity = min(P, Q) for each element.
///
/// ## Notation
///
/// P ∩ Q
///
/// ## Input
///
/// - P = `{'a': 3, 'c': 1, 'd': 2}`
/// - Q = `{'a': 2, 'b': 1, 'c': 2}`
///
/// ## Expected Output
///
/// - Result = `{'a': 2, 'c': 1}`
///
/// ## Theory Reference
///
/// Multiset intersection: multiplicity = min(multiplicity in P, multiplicity in Q)
///
/// ## Examples
///
/// ```rust
/// let p = MultiSet::from(vec!['a', 'a', 'a', 'c']);
/// let q = MultiSet::from(vec!['a', 'a', 'b', 'c', 'c']);
/// let result = p.intersection(&q);
/// assert_eq!(result.multiplicity(&'a'), 2);
/// ```
#[test]
fn test_multiset_intersection() {
    let p = MultiSet::from(vec!['a', 'a', 'a', 'c', 'd', 'd']);
    let q = MultiSet::from(vec!['a', 'a', 'b', 'c', 'c']);
    let result = p.intersection(&q);

    assert_eq!(result.multiplicity(&'a'), 2, "Min(3, 2) = 2");
    assert_eq!(result.multiplicity(&'b'), 0, "Min(0, 1) = 0");
    assert_eq!(result.multiplicity(&'c'), 1, "Min(1, 2) = 1");
    assert_eq!(result.multiplicity(&'d'), 0, "Min(2, 0) = 0");
}

/// Tests multiset difference operation.
///
/// ## Summary
///
/// Verifies difference returns multiplicity P - Q (minimum 0).
///
/// ## Description
///
/// Tests P - Q where multiplicity = max(0, P - Q) for each element.
///
/// ## Notation
///
/// P - Q
///
/// ## Input
///
/// - P = `{'a': 3, 'b': 2, 'c': 1, 'd': 2, 'e': 1}`
/// - Q = `{'a': 2, 'b': 3, 'c': 1, 'd': 2, 'f': 1}`
///
/// ## Expected Output
///
/// - Result = `{'a': 1, 'e': 1}`
///
/// ## Theory Reference
///
/// Multiset difference: multiplicity = max(0, multiplicity in P - multiplicity in Q)
///
/// ## Examples
///
/// ```rust
/// let p = MultiSet::from(vec!['a', 'a', 'a', 'b']);
/// let q = MultiSet::from(vec!['a', 'a', 'b', 'b']);
/// let result = p.difference(&q);
/// assert_eq!(result.multiplicity(&'a'), 1);
/// ```
#[test]
fn test_multiset_difference() {
    let p = MultiSet::from(vec!['a', 'a', 'a', 'b', 'b', 'c', 'd', 'd', 'e']);
    let q = MultiSet::from(vec!['a', 'a', 'b', 'b', 'b', 'c', 'c', 'd', 'd', 'f']);
    let result = p.difference(&q);

    assert_eq!(result.multiplicity(&'a'), 1, "3 - 2 = 1");
    assert_eq!(result.multiplicity(&'b'), 0, "2 - 3 = 0 (not negative)");
    assert_eq!(result.multiplicity(&'c'), 0, "1 - 1 = 0");
    assert_eq!(result.multiplicity(&'d'), 0, "2 - 2 = 0");
    assert_eq!(result.multiplicity(&'e'), 1, "1 - 0 = 1");
    assert_eq!(result.multiplicity(&'f'), 0, "0 - 1 = 0 (not negative)");
}

/// Tests multiset sum operation.
///
/// ## Summary
///
/// Verifies sum returns multiplicity P + Q for each element.
///
/// ## Description
///
/// Tests P + Q where multiplicity = P + Q for each element.
///
/// ## Notation
///
/// P + Q
///
/// ## Input
///
/// - P = `{'a': 2, 'b': 1, 'c': 2}`
/// - Q = `{'a': 1, 'b': 2, 'd': 1}`
///
/// ## Expected Output
///
/// - Result = `{'a': 3, 'b': 3, 'c': 2, 'd': 1}`
///
/// ## Theory Reference
///
/// Multiset sum: multiplicity = multiplicity in P + multiplicity in Q
///
/// ## Examples
///
/// ```rust
/// let p = MultiSet::from(vec!['a', 'a', 'b', 'c', 'c']);
/// let q = MultiSet::from(vec!['a', 'b', 'b', 'd']);
/// let result = p.sum(&q);
/// assert_eq!(result.multiplicity(&'a'), 3);
/// ```
#[test]
fn test_multiset_sum() {
    let p = MultiSet::from(vec!['a', 'a', 'b', 'c', 'c']);
    let q = MultiSet::from(vec!['a', 'b', 'b', 'd']);
    let result = p.sum(&q);

    assert_eq!(result.multiplicity(&'a'), 3, "2 + 1 = 3");
    assert_eq!(result.multiplicity(&'b'), 3, "1 + 2 = 3");
    assert_eq!(result.multiplicity(&'c'), 2, "2 + 0 = 2");
    assert_eq!(result.multiplicity(&'d'), 1, "0 + 1 = 1");
}

/// Tests multiset to set conversion.
///
/// ## Summary
///
/// Verifies conversion from MultiSet to CustomSet removes duplicates.
///
/// ## Description
///
/// Tests `to_set()` which converts a multiset to a standard set
/// by removing all duplicate elements.
///
/// ## Input
///
/// - MultiSet: `{1: 3, 2: 2, 3: 1}`
///
/// ## Expected Output
///
/// - Set: `{1, 2, 3}`
/// - Cardinality: 3
///
/// ## Examples
///
/// ```rust
/// let ms = MultiSet::from(vec![1, 1, 1, 2, 2, 3]);
/// let set = ms.to_set();
/// assert_eq!(set.cardinality(), 3);
/// ```
#[test]
fn test_multiset_to_set() {
    let ms = MultiSet::from(vec![1, 1, 1, 2, 2, 3]);
    let set = ms.to_set();

    assert_eq!(set.cardinality(), 3, "Set should have 3 unique elements");
    assert!(set.contains(&1), "Set should contain 1");
    assert!(set.contains(&2), "Set should contain 2");
    assert!(set.contains(&3), "Set should contain 3");
}

/// Tests multiset add operation with count.
///
/// ## Summary
///
/// Verifies adding elements with specified multiplicity.
///
/// ## Examples
///
/// ```rust
/// let mut ms = MultiSet::<char>::empty();
/// ms.add('a', 3);
/// assert_eq!(ms.multiplicity(&'a'), 3);
/// ```
#[test]
fn test_multiset_add_with_count() {
    let mut ms = MultiSet::<char>::empty();

    ms.add('a', 3);
    assert_eq!(ms.multiplicity(&'a'), 3, "Should add 3 'a' elements");

    ms.add('a', 2);
    assert_eq!(ms.multiplicity(&'a'), 5, "Should add 2 more 'a' elements");

    ms.add('b', 1);
    assert_eq!(ms.multiplicity(&'b'), 1, "Should add 1 'b' element");
}

/// Tests multiset remove operation with count.
///
/// ## Summary
///
/// Verifies removing elements with specified multiplicity.
///
/// ## Examples
///
/// ```rust
/// let mut ms = MultiSet::from(vec!['a', 'a', 'a']);
/// ms.remove(&'a', 2);
/// assert_eq!(ms.multiplicity(&'a'), 1);
/// ```
#[test]
fn test_multiset_remove_with_count() {
    let mut ms = MultiSet::from(vec!['a', 'a', 'a', 'b', 'b']);

    ms.remove(&'a', 2);
    assert_eq!(ms.multiplicity(&'a'), 1, "Should remove 2 'a' elements");

    ms.remove(&'b', 5);
    assert_eq!(
        ms.multiplicity(&'b'),
        0,
        "Should remove all 'b' elements (can't go negative)"
    );

    ms.remove(&'a', 1);
    assert_eq!(
        ms.multiplicity(&'a'),
        0,
        "Should remove remaining 'a' element"
    );
}

/// Tests multiset display formatting.
///
/// ## Summary
///
/// Verifies the `Display` trait implementation for MultiSet.
///
/// ## Expected Output
///
/// - Format: `{element:count, element:count, ...}`
/// - Empty: `∅`
///
/// ## Examples
///
/// ```rust
/// let ms = MultiSet::from(vec!['a', 'a', 'b']);
/// println!("{}", ms); // {a:2, b:1}
/// ```
#[test]
fn test_multiset_display() {
    let ms = MultiSet::from(vec!['a', 'a', 'a', 'b', 'c']);
    let display = format!("{}", ms);

    assert!(display.starts_with("{"), "Display should start with {{");
    assert!(display.ends_with("}"), "Display should end with }}");
    assert!(display.contains("a:3"), "Display should show a:3");

    let empty = MultiSet::<i32>::empty();
    assert_eq!(
        format!("{}", empty),
        "∅",
        "Empty multiset should display as ∅"
    );
}

/// Tests real-world hardware procurement scenario.
///
/// ## Summary
///
/// Verifies multiset operations with a practical example from the course material.
///
/// ## Description
///
/// Based on the UTS 2022 problem from ITERA:
/// - TI needs: 100 PC, 40 router, 5 server
/// - MS needs: 10 PC, 7 router, 2 mainframe
///
/// ## Examples
///
/// ```rust
/// let ti = MultiSet::from(vec![
///     // 100 PC, 40 router, 5 server
/// ]);
/// let ms = MultiSet::from(vec![
///     // 10 PC, 7 router, 2 mainframe
/// ]);
/// ```
#[test]
fn test_hardware_procurement_scenario() {
    // Simulating the hardware procurement problem
    // TI needs: 100 PC, 40 router, 5 server
    // MS needs: 10 PC, 7 router, 2 mainframe

    // Create multisets representing hardware needs
    let mut ti = MultiSet::<String>::empty();
    ti.add("PC".to_string(), 100);
    ti.add("router".to_string(), 40);
    ti.add("server".to_string(), 5);

    let mut ms = MultiSet::<String>::empty();
    ms.add("PC".to_string(), 10);
    ms.add("router".to_string(), 7);
    ms.add("mainframe".to_string(), 2);

    // a) Shareable (Union - max)
    let shareable = ti.union(&ms);
    assert_eq!(
        shareable.multiplicity(&"PC".to_string()),
        100,
        "Max(100, 10) = 100"
    );
    assert_eq!(
        shareable.multiplicity(&"router".to_string()),
        40,
        "Max(40, 7) = 40"
    );
    assert_eq!(
        shareable.multiplicity(&"server".to_string()),
        5,
        "Max(5, 0) = 5"
    );
    assert_eq!(
        shareable.multiplicity(&"mainframe".to_string()),
        2,
        "Max(0, 2) = 2"
    );

    // b) Non-shareable (Sum)
    let non_shareable = ti.sum(&ms);
    assert_eq!(
        non_shareable.multiplicity(&"PC".to_string()),
        110,
        "100 + 10 = 110"
    );
    assert_eq!(
        non_shareable.multiplicity(&"router".to_string()),
        47,
        "40 + 7 = 47"
    );

    // c) Only MS not needed by TI (Difference)
    let ms_only = ms.difference(&ti);
    assert_eq!(
        ms_only.multiplicity(&"mainframe".to_string()),
        2,
        "2 - 0 = 2"
    );
    assert_eq!(ms_only.multiplicity(&"PC".to_string()), 0, "10 - 100 = 0");
    assert_eq!(ms_only.multiplicity(&"router".to_string()), 0, "7 - 40 = 0");
}

/// Tests multiset with zero multiplicity elements.
///
/// ## Summary
///
/// Verifies behavior when elements have zero multiplicity.
///
/// ## Expected Behavior
///
/// - Elements with 0 multiplicity should not appear in the multiset
/// - Adding 0 elements should not change the multiset
///
/// ## Examples
///
/// ```rust
/// let mut ms = MultiSet::from(vec![1, 2, 3]);
/// ms.add(4, 0);
/// assert_eq!(ms.multiplicity(&4), 0);
/// ```
#[test]
fn test_multiset_zero_multiplicity() {
    let mut ms = MultiSet::from(vec![1, 2, 3]);

    // Adding 0 should not change anything
    ms.add(4, 0);
    assert_eq!(
        ms.multiplicity(&4),
        0,
        "Adding 0 elements should not add anything"
    );
    assert_eq!(ms.unique_count(), 3, "Unique count should not change");

    // Removing all should result in 0 multiplicity
    ms.remove(&1, 10);
    assert_eq!(
        ms.multiplicity(&1),
        0,
        "Removing more than exists should result in 0"
    );
}

/// Tests multiset cardinality calculation.
///
/// ## Summary
///
/// Verifies total cardinality includes all duplicates.
///
/// ## Description
///
/// Tests that cardinality returns the sum of all multiplicities,
/// not just the unique count.
///
/// ## Examples
///
/// ```rust
/// let ms = MultiSet::from(vec![1, 1, 1, 2, 2, 3]);
/// assert_eq!(ms.cardinality(), 6);
/// assert_eq!(ms.unique_count(), 3);
/// ```
#[test]
fn test_multiset_cardinality() {
    let ms = MultiSet::from(vec!['a', 'a', 'a', 'b', 'b', 'c', 'd', 'd', 'd', 'd']);

    assert_eq!(ms.cardinality(), 10, "Total cardinality should be 10");
    assert_eq!(ms.unique_count(), 4, "Unique count should be 4");

    // Verify individual multiplicities
    assert_eq!(ms.multiplicity(&'a'), 3);
    assert_eq!(ms.multiplicity(&'b'), 2);
    assert_eq!(ms.multiplicity(&'c'), 1);
    assert_eq!(ms.multiplicity(&'d'), 4);

    // Sum of multiplicities should equal cardinality
    let sum: usize = ['a', 'b', 'c', 'd']
        .iter()
        .map(|c| ms.multiplicity(c))
        .sum();
    assert_eq!(
        sum,
        ms.cardinality(),
        "Sum of multiplicities should equal cardinality"
    );
}

/// Tests multiset iteration.
///
/// ## Summary
///
/// Verifies that multisets can be iterated over unique elements.
///
/// ## Examples
///
/// ```rust
/// let ms = MultiSet::from(vec![1, 1, 2, 2, 3]);
/// for element in ms.iter() {
///     println!("{}: {}", element, ms.multiplicity(&element));
/// }
/// ```
#[test]
fn test_multiset_iteration() {
    let ms = MultiSet::from(vec![1, 1, 1, 2, 2, 3]);
    let mut count = 0;

    for _ in ms.iter() {
        count += 1;
    }

    assert_eq!(count, 3, "Should iterate over 3 unique elements");
}

/// Tests multiset equality.
///
/// ## Summary
///
/// Verifies multiset equality based on multiplicity.
///
/// ## Expected Behavior
///
/// - Two multisets are equal if all elements have same multiplicity
/// - Order does not matter
///
/// ## Examples
///
/// ```rust
/// let ms1 = MultiSet::from(vec![1, 1, 2]);
/// let ms2 = MultiSet::from(vec![2, 1, 1]);
/// assert_eq!(ms1, ms2);
/// ```
#[test]
fn test_multiset_equality() {
    let ms1 = MultiSet::from(vec!['a', 'a', 'b', 'c']);
    let ms2 = MultiSet::from(vec!['c', 'a', 'b', 'a']);
    let ms3 = MultiSet::from(vec!['a', 'b', 'c']);

    assert_eq!(
        ms1, ms2,
        "Multisets with same multiplicities should be equal"
    );
    assert_ne!(
        ms1, ms3,
        "Multisets with different multiplicities should not be equal"
    );
}