set_theory 1.0.0

# Set Theory Library

A comprehensive mathematical set theory library for Rust implementing standard set operations, multisets, and set laws verification following discrete mathematics principles.

## Table of Contents

- [Overview](#overview)
- [Features](#features)
- [Installation](#installation)
- [Quick Start](#quick-start)
- [Documentation](#documentation)
- [Module Structure](#module-structure)
- [Usage Examples](#usage-examples)
- [Set Operations](#set-operations)
- [Set Laws](#set-laws)
- [Multiset Operations](#multiset-operations)
- [Testing](#testing)
- [Performance](#performance)
- [Academic References](#academic-references)
- [Contributing](#contributing)
- [License](#license)

---

## Overview

This library provides a complete implementation of **Set Theory** concepts from discrete mathematics, designed for educational purposes and practical applications. It follows the curriculum from **Institut Teknologi Sumatera (ITERA)** and **Institut Teknologi Bandung (ITB)** Discrete Mathematics courses.

The library implements:
- **CustomSet**: Mutable set with unique elements
- **FrozenSet**: Immutable, thread-safe set
- **MultiSet**: Set allowing duplicate elements with multiplicity tracking
- **Set Operations**: Union, intersection, complement, difference, symmetric difference
- **Advanced Operations**: Cartesian product, power set, partition validation
- **Set Laws**: Verification of all standard set theory laws

---

## Features

| Feature | Description |
|---------|-------------|
| **CustomSet** | Mutable set with unique elements |
| **FrozenSet** | Immutable, thread-safe set |
| **MultiSet** | Set with multiplicity tracking |
| **Basic Operations** | Union, intersection, complement, difference |
| **Advanced Operations** | Cartesian product, power set, partition |
| **Set Laws** | All 11 standard set theory laws |
| **Lazy Evaluation** | Memory-efficient power set generation |
| **Type Safety** | Full generic implementations |
| **Test Coverage** | 80+ comprehensive unit tests |
| **Documentation** | Full Rust doc comments |

## Installation

Add this to your `Cargo.toml`:

```toml
[dependencies]
set_theory = "1.0.0"
```

Or install via cargo:

```bash
cargo add set_theory
```

## Quick Start

```rust
use set_theory::models::CustomSet;
use set_theory::operations::SetOperations;

// Create sets
let a = CustomSet::from(vec![1, 2, 3, 4]);
let b = CustomSet::from(vec![3, 4, 5, 6]);

// Perform operations
let union = SetOperations::union(&a, &b);
let intersection = SetOperations::intersection(&a, &b);

println!("A ∪ B = {}", union);           // {1, 2, 3, 4, 5, 6}
println!("A ∩ B = {}", intersection);     // {3, 4}
```

---

## Documentation

Generate local documentation:

```bash
cargo doc --open
```

View online documentation: [https://docs.rs/set_theory](https://docs.rs/set_theory)

---

## Module Structure

```
set_theory/
├── src/
│   ├── lib.rs              # Main library entry point
│   ├── main.rs             # Demo application
│   ├── traits/
│   │   ├── mod.rs
│   │   └── math_set.rs     # Core MathSet trait
│   ├── models/
│   │   ├── mod.rs
│   │   ├── custom_set.rs   # Mutable set implementation
│   │   ├── frozen_set.rs   # Immutable set implementation
│   │   └── multiset.rs     # Multiset implementation
│   ├── operations/
│   │   ├── mod.rs
│   │   ├── basic_ops.rs    # Basic set operations
│   │   ├── advanced_ops.rs # Advanced operations
│   │   └── lazy_ops.rs     # Lazy evaluation
│   ├── laws/
│   │   ├── mod.rs
│   │   └── set_laws.rs     # Set law verification
│   └── utils/
│       ├── mod.rs
│       ├── equality.rs     # Equality utilities
│       └── pretty_print.rs # Formatting utilities
├── tests/
│   ├── mod.rs
│   ├── custom_set_tests.rs
│   ├── multiset_tests.rs
│   ├── operations_tests.rs
│   └── laws_tests.rs
├── Cargo.toml
├── README.md
└── LICENSE
```

---

## Usage Examples

### Creating Sets

```rust
use set_theory::models::CustomSet;

// Empty set
let empty = CustomSet::<i32>::empty();

// From vector
let numbers = CustomSet::from(vec![1, 2, 3, 4]);

// From predicate
let evens = CustomSet::from_predicate(0..100, |x| x % 2 == 0);

// From iterator
let set: CustomSet<i32> = (1..=10).collect();
```

### Basic Set Operations

```rust
use set_theory::models::CustomSet;
use set_theory::operations::SetOperations;

let a = CustomSet::from(vec![1, 2, 3, 4, 5]);
let b = CustomSet::from(vec![4, 5, 6, 7, 8]);

// Intersection: A ∩ B
let intersection = SetOperations::intersection(&a, &b);
println!("A ∩ B = {}", intersection);  // {4, 5}

// Union: A ∪ B
let union = SetOperations::union(&a, &b);
println!("A ∪ B = {}", union);  // {1, 2, 3, 4, 5, 6, 7, 8}

// Difference: A - B
let difference = SetOperations::difference(&a, &b);
println!("A - B = {}", difference);  // {1, 2, 3}

// Symmetric Difference: A ⊕ B
let sym_diff = SetOperations::symmetric_difference(&a, &b);
println!("A ⊕ B = {}", sym_diff);  // {1, 2, 3, 6, 7, 8}

// Complement: A' (with respect to universal set)
let universal = CustomSet::from((1..=10).collect::<Vec<_>>());
let complement = SetOperations::complement(&a, &universal);
println!("A' = {}", complement);  // {6, 7, 8, 9, 10}
```

### Subset Operations

```rust
use set_theory::models::CustomSet;

let a = CustomSet::from(vec![1, 2, 3]);
let b = CustomSet::from(vec![1, 2, 3, 4, 5]);

println!("A ⊆ B: {}", a.is_subset_of(&b));           // true
println!("A ⊂ B: {}", a.is_proper_subset_of(&b));    // true
println!("A ⊇ B: {}", a.is_superset_of(&b));         // false
println!("A ⊃ B: {}", a.is_proper_superset_of(&b));  // false
println!("A = B: {}", a.equals(&b));                 // false
println!("A // B: {}", a.is_disjoint_from(&b));      // false
```

### Power Set (Lazy Evaluation)

```rust
use set_theory::models::CustomSet;

let a = CustomSet::from(vec![1, 2, 3]);
let power_set: Vec<_> = a.power_set().collect();

println!("|P(A)| = {}", power_set.len());  // 8 (2^3)
for subset in &power_set {
    println!("  {}", subset);
}
// Output:
//   ∅
//   {1}
//   {2}
//   {3}
//   {1, 2}
//   {1, 3}
//   {2, 3}
//   {1, 2, 3}
```

### Cartesian Product

```rust
use set_theory::models::CustomSet;
use set_theory::operations::AdvancedSetOperations;

let x = CustomSet::from(vec![1, 2]);
let y = CustomSet::from(vec!['a', 'b']);

let cartesian = AdvancedSetOperations::cartesian_product(&x, &y);
println!("X × Y = {:?}", cartesian);
// {(1, 'a'), (1, 'b'), (2, 'a'), (2, 'b')}
println!("|X × Y| = {}", cartesian.cardinality());  // 4
```

### Multiset Operations

```rust
use set_theory::models::MultiSet;

let p = MultiSet::from(vec!['a', 'a', 'a', 'b', 'c']);
let q = MultiSet::from(vec!['a', 'b', 'b', 'd']);

println!("P = {}", p);  // {a:3, b:1, c:1}
println!("Q = {}", q);  // {a:1, b:2, d:1}

// Union (max multiplicity)
println!("P ∪ Q = {}", p.union(&q));  // {a:3, b:2, c:1, d:1}

// Intersection (min multiplicity)
println!("P ∩ Q = {}", p.intersection(&q));  // {a:1, b:1}

// Difference
println!("P - Q = {}", p.difference(&q));  // {a:2, c:1}

// Sum
println!("P + Q = {}", p.sum(&q));  // {a:4, b:3, c:1, d:1}
```

---

## Set Operations Reference

| Operation | Notation | Method | Description |
|-----------|----------|--------|-------------|
| **Intersection** | A ∩ B | `intersection()` | Elements in both sets |
| **Union** | A ∪ B | `union()` | Elements in either set |
| **Complement** | A' | `complement()` | Elements not in A (w.r.t universal) |
| **Difference** | A - B | `difference()` | Elements in A but not B |
| **Symmetric Difference** | A ⊕ B | `symmetric_difference()` | Elements in either but not both |
| **Subset** | A ⊆ B | `is_subset_of()` | A is contained in B |
| **Proper Subset** | A ⊂ B | `is_proper_subset_of()` | A ⊆ B and A ≠ B |
| **Superset** | A ⊇ B | `is_superset_of()` | B is contained in A |
| **Power Set** | P(A) | `power_set()` | All subsets of A |
| **Cartesian Product** | A × B | `cartesian_product()` | All ordered pairs |

---

## Set Laws

This library verifies all 11 standard set theory laws:

| # | Law | Formula | Method |
|---|-----|---------|--------|
| 1 | **Identity** | A ∪ ∅ = A, A ∩ U = A | `identity_union()`, `identity_intersection()` |
| 2 | **Null/Domination** | A ∩ ∅ = ∅, A ∪ U = U | `null_intersection()`, `null_union()` |
| 3 | **Complement** | A ∪ A' = U, A ∩ A' = ∅ | `complement_union()`, `complement_intersection()` |
| 4 | **Idempotent** | A ∪ A = A, A ∩ A = A | `idempotent_union()`, `idempotent_intersection()` |
| 5 | **Involution** | (A')' = A | `involution()` |
| 6 | **Absorption** | A ∪ (A ∩ B) = A, A ∩ (A ∪ B) = A | `absorption_union()`, `absorption_intersection()` |
| 7 | **Commutative** | A ∪ B = B ∪ A, A ∩ B = B ∩ A | `commutative_union()`, `commutative_intersection()` |
| 8 | **Associative** | A ∪ (B ∪ C) = (A ∪ B) ∪ C | `associative_union()`, `associative_intersection()` |
| 9 | **Distributive** | A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) | `distributive_union()`, `distributive_intersection()` |
| 10 | **De Morgan's** | (A ∪ B)' = A' ∩ B' | `de_morgan_union()`, `de_morgan_intersection()` |
| 11 | **0/1** | ∅' = U, U' = ∅ | `law_zero()`, `law_one()` |

### Example: Verifying Set Laws

```rust
use set_theory::models::CustomSet;
use set_theory::laws::SetLaws;

let a = CustomSet::from(vec![1, 2, 3]);
let b = CustomSet::from(vec![3, 4, 5]);
let universal = CustomSet::from((1..=9).collect::<Vec<_>>());

// Verify laws
assert!(SetLaws::commutative_union(&a, &b));
assert!(SetLaws::distributive_union(&a, &b, &universal));
assert!(SetLaws::de_morgan_union(&a, &b, &universal));
assert!(SetLaws::absorption_union(&a, &b));
```

---

## Testing

Run all tests:

```bash
cargo test
```

Run specific test modules:

```bash
# CustomSet tests
cargo test custom_set_tests

# MultiSet tests
cargo test multiset_tests

# Operations tests
cargo test operations_tests

# Set Laws tests
cargo test laws_tests
```

Run with verbose output:

```bash
cargo test -- --nocapture
```

### Test Coverage Summary

| Module | Tests | Coverage |
|--------|-------|----------|
| `custom_set_tests` | 25+ | Core functionality |
| `multiset_tests` | 15+ | Multiset operations |
| `operations_tests` | 20+ | Set operations |
| `laws_tests` | 20+ | Law verification |
| **Total** | **80+** | **Comprehensive** |

---

## Performance

| Operation | Time Complexity | Space Complexity |
|-----------|-----------------|------------------|
| `contains()` | O(1) average | O(1) |
| `add()` | O(1) average | O(1) |
| `remove()` | O(1) average | O(1) |
| `union()` | O(n + m) | O(n + m) |
| `intersection()` | O(min(n, m)) | O(min(n, m)) |
| `difference()` | O(n) | O(n) |
| `complement()` | O(|U|) | O(|U|) |
| `power_set()` | O(2^n) lazy | O(n) |
| `cartesian_product()` | O(n × m) | O(n × m) |

## Academic References

This library is based on the following academic materials:

1. **ITERA Discrete Mathematics Course** (IF2120)
   - Institut Teknologi Sumatera
   - Lecture slides: "02 - Himpunan.pdf"
   - Topics: Set theory, operations, laws, multisets

2. **ITB Discrete Mathematics** (Adapted)
   - Institut Teknologi Bandung
   - Original slides by Dr. Rinaldi
   - Standard set theory curriculum

3. **Textbooks**
   - Rosen, K. H. "Discrete Mathematics and Its Applications"
   - Standard set theory principles and notation

### Key Concepts from Course Material

| Concept | Slide Reference | Implementation |
|---------|-----------------|----------------|
| Set Definition | Slide 2-4 | `CustomSet` |
| Multiset | Slide 82-86 | `MultiSet` |
| Set Operations | Slide 28-35 | `SetOperations` |
| Cartesian Product | Slide 38-39 | `AdvancedSetOperations` |
| Power Set | Slide 27 | `power_set()` |
| Set Laws | Slide 48-49 | `SetLaws` |
| Inclusion-Exclusion | Slide 67-73 | `inclusion_exclusion_*()` |
| Partition | Slide 81 | `is_partition()` |

## Contributing

Contributions are welcome! Please follow these guidelines:

1. **Fork** the repository
2. **Create** a feature branch (`git checkout -b feature/amazing-feature`)
3. **Commit** your changes (`git commit -m 'Add amazing feature'`)
4. **Push** to the branch (`git push origin feature/amazing-feature`)
5. **Open** a Pull Request

### Code Style

- Follow Rust standard formatting (`cargo fmt`)
- All code must pass Clippy lints (`cargo clippy`)
- All tests must pass (`cargo test`)
- Document all public items with Rust doc comments

### Documentation Standards

All public items must include:
- `## Summary` - Brief description
- `## Description` - Detailed explanation
- `## Arguments` - Parameter descriptions
- `## Returns` - Return value description
- `## Examples` - Usage examples
- `## Theory Reference` - Academic reference (if applicable)

## License

This project is licensed under the **MIT License** - see the [LICENSE](LICENSE) file for details.