use std::collections::HashSet;
use indexmap::IndexSet;
 
fn basic_usage() {
    // HashSet - order not guaranteed
    let mut hash_set: HashSet<&str> = HashSet::new();
    hash_set.insert("apple");
    hash_set.insert("banana");
    hash_set.insert("cherry");
    
    // Iteration order is unpredictable
    for item in &hash_set {
        println!("{}", item);  // Order varies between runs/versions
    }
    
    // IndexSet - preserves insertion order
    let mut index_set: IndexSet<&str> = IndexSet::new();
    index_set.insert("apple");
    index_set.insert("banana");
    index_set.insert("cherry");
    
    // Iteration order is guaranteed: apple, banana, cherry
    for item in &index_set {
        println!("{}", item);  // Always in insertion order
    }
}

use std::collections::HashSet;
use indexmap::IndexSet;
 
fn iteration_order() {
    // HashSet iteration order depends on hash values and internal state
    let mut set1: HashSet<i32> = HashSet::new();
    set1.insert(1);
    set1.insert(2);
    set1.insert(3);
    
    let mut set2: HashSet<i32> = HashSet::new();
    set2.insert(3);
    set2.insert(2);
    set2.insert(1);
    
    // set1 and set2 may iterate in the same order despite different insertion order!
    // The order depends on hash values, not insertion order
    
    // IndexSet iteration order reflects insertion order
    let mut idx1: IndexSet<i32> = IndexSet::new();
    idx1.insert(1);
    idx1.insert(2);
    idx1.insert(3);
    
    let mut idx2: IndexSet<i32> = IndexSet::new();
    idx2.insert(3);
    idx2.insert(2);
    idx2.insert(1);
    
    // idx1 iterates: 1, 2, 3
    // idx2 iterates: 3, 2, 1
    // Order is deterministic and matches insertion order
}

use indexmap::IndexSet;
 
fn index_access() {
    let mut set: IndexSet<&str> = IndexSet::new();
    set.insert("first");
    set.insert("second");
    set.insert("third");
    
    // Access by index - HashSet cannot do this
    let first = set[0];       // "first"
    let second = set[1];      // "second"
    let third = set[2];       // "third"
    
    // get() returns reference with index
    let (index, value) = set.get_full("second").unwrap();
    println!("'second' is at index {}: {:?}", index, value);
    
    // get_index returns element at position
    let at_one = set.get_index(1);  // Some(&"second")
    
    // Iterate with indices
    for (index, value) in set.iter().enumerate() {
        println!("{}: {}", index, value);
    }
}

use indexmap::IndexSet;
 
fn position_operations() {
    let mut set: IndexSet<&str> = IndexSet::new();
    set.insert("a");
    set.insert("b");
    set.insert("c");
    
    // Get the index of an element
    let pos = set.get_index_of("b");  // Some(1)
    let not_found = set.get_index_of("z");  // None
    
    // Get element and its index together
    if let Some((idx, value)) = set.get_full("c") {
        println!("Found '{}' at index {}", value, idx);  // Found 'c' at index 2
    }
    
    // Get mutable reference with index
    if let Some((idx, value)) = set.get_full_mut("a") {
        println!("Modifying element at index {}", idx);
        // Note: cannot modify in a way that would change hash
    }
}

use indexmap::IndexSet;
 
fn reinsertion() {
    let mut set: IndexSet<&str> = IndexSet::new();
    
    set.insert("first");
    set.insert("second");
    set.insert("third");
    
    // Reinserting doesn't change position
    set.insert("second");  // Returns false (already present)
    
    // Order is still: first, second, third
    // "second" stays at index 1
    
    // Check iteration order
    for (i, item) in set.iter().enumerate() {
        println!("{}: {}", i, item);
    }
    // Output:
    // 0: first
    // 1: second
    // 2: third
}

use indexmap::IndexSet;
 
fn removal_behavior() {
    let mut set: IndexSet<&str> = IndexSet::new();
    set.insert("a");
    set.insert("b");
    set.insert("c");
    set.insert("d");
    
    // swap_remove - swaps with last element (fast, changes order)
    set.swap_remove("b");
    // Order now: a, d, c (d swapped into b's position)
    
    set.clear();
    set.insert("a");
    set.insert("b");
    set.insert("c");
    set.insert("d");
    
    // shift_remove - shifts elements to fill gap (slower, preserves order)
    set.shift_remove("b");
    // Order now: a, c, d (c and d shifted left)
    
    // remove is alias for swap_remove by default
    set.remove("c");  // Uses swap_remove semantics
}

use std::collections::HashSet;
use indexmap::IndexSet;
 
// Operation complexity comparison:
//
// Operation          | HashSet      | IndexSet
// --------------------|--------------|-----------------
// Insert              | O(1) avg     | O(1) avg
// Lookup (contains)   | O(1) avg     | O(1) avg
// Remove              | O(1) avg     | O(1) avg (swap_remove)
//                     |              | O(n) avg (shift_remove)
// Index access        | N/A          | O(1)
// Iteration           | O(n)         | O(n)
// Get index of elem   | N/A          | O(1) avg
 
fn performance_comparison() {
    let n = 100_000;
    
    // Both have similar lookup performance
    let mut hash_set: HashSet<i32> = (0..n).collect();
    let mut index_set: IndexSet<i32> = (0..n).collect();
    
    // Lookup is O(1) for both
    assert!(hash_set.contains(&50_000));
    assert!(index_set.contains(&50_000));
    
    // IndexSet has additional capabilities
    let elem = index_set[50_000];  // O(1) index access
    let idx = index_set.get_index_of(&50_000);  // O(1) position lookup
}

use std::collections::HashSet;
use indexmap::IndexSet;
 
fn memory_comparison() {
    // HashSet stores elements in hash buckets
    // Memory: hash table with buckets + elements
    // Layout depends on hash function and load factor
    
    // IndexSet stores:
    // 1. Hash table for O(1) lookup
    // 2. Sequential array for order preservation
    // Memory: hash table + elements array + indices mapping
    
    // IndexSet uses more memory to maintain order
    let hash_set: HashSet<i32> = (0..1000).collect();
    let index_set: IndexSet<i32> = (0..1000).collect();
    
    // IndexSet has higher memory overhead
    // But provides both hash lookup AND ordered access
}

use std::collections::HashSet;
 
fn hashset_appropriate() {
    // When you only need uniqueness
    let mut seen: HashSet<String> = HashSet::new();
    for word in ["apple", "banana", "apple", "cherry"] {
        if seen.insert(word.to_string()) {
            println!("New word: {}", word);
        }
    }
    
    // When order doesn't matter
    let set1: HashSet<i32> = [1, 2, 3].iter().cloned().collect();
    let set2: HashSet<i32> = [3, 2, 1].iter().cloned().collect();
    assert_eq!(set1, set2);  // Equal regardless of insertion order
    
    // When memory matters
    // HashSet has lower overhead
    
    // When maximum performance is critical
    // HashSet may have slightly better cache behavior
}

use indexmap::IndexSet;
 
fn indexset_appropriate() {
    // When you need deterministic iteration order
    let mut ordered: IndexSet<String> = IndexSet::new();
    ordered.insert("first".to_string());
    ordered.insert("second".to_string());
    ordered.insert("third".to_string());
    
    // Order is guaranteed for serialization, display, etc.
    let output: Vec<_> = ordered.iter().collect();
    // output is always ["first", "second", "third"]
    
    // When you need index-based access
    let item = ordered[1];  // "second"
    
    // When order affects equality
    let mut a: IndexSet<i32> = IndexSet::new();
    a.insert(1);
    a.insert(2);
    
    let mut b: IndexSet<i32> = IndexSet::new();
    b.insert(2);
    b.insert(1);
    
    // Different insertion order = different sets (unlike HashSet)
    // Though as sets, they contain the same elements
    
    // When implementing ordered unique lists
    // Like a playlist with no duplicates
}

use std::collections::HashSet;
use indexmap::IndexSet;
 
fn set_operations() {
    // Both support standard set operations
    
    // HashSet
    let mut a: HashSet<i32> = [1, 2, 3].iter().cloned().collect();
    let b: HashSet<i32> = [2, 3, 4].iter().cloned().collect();
    
    a.union(&b);       // {1, 2, 3, 4} - order not guaranteed
    a.intersection(&b); // {2, 3}
    a.difference(&b);   // {1}
    a.symmetric_difference(&b); // {1, 4}
    
    // IndexSet - preserves order from left operand
    let mut x: IndexSet<i32> = [1, 2, 3].iter().cloned().collect();
    let y: IndexSet<i32> = [2, 3, 4].iter().cloned().collect();
    
    // Union preserves order: 1, 2, 3, 4
    let union: IndexSet<i32> = x.union(&y).copied().collect();
    
    // Intersection preserves order from first set: 2, 3
    let inter: IndexSet<i32> = x.intersection(&y).copied().collect();
}

use indexmap::IndexSet;
use serde::{Serialize, Deserialize};
 
#[derive(Serialize, Deserialize)]
struct Config {
    // Order matters for display/serialization
    allowed_users: IndexSet<String>,
}
 
fn serialization() {
    let mut config = Config {
        allowed_users: IndexSet::new(),
    };
    
    config.allowed_users.insert("alice".to_string());
    config.allowed_users.insert("bob".to_string());
    config.allowed_users.insert("charlie".to_string());
    
    // JSON will have users in insertion order
    let json = serde_json::to_string(&config).unwrap();
    // {"allowed_users":["alice","bob","charlie"]}
    
    // With HashSet, order would be unpredictable
    // This matters for:
    // - Configuration files (human readability)
    // - API responses (stable output for testing)
    // - Reproducible builds
}

use indexmap::IndexSet;
 
fn command_processing() {
    // Process commands in order, skip duplicates
    let commands = vec!["init", "load", "process", "load", "save", "init"];
    
    let mut seen = IndexSet::new();
    for cmd in commands {
        if seen.insert(cmd) {
            println!("Executing: {}", cmd);
        } else {
            println!("Skipping duplicate: {}", cmd);
        }
    }
    
    // Output:
    // Executing: init
    // Executing: load
    // Executing: process
    // Skipping duplicate: load
    // Executing: save
    // Skipping duplicate: init
    
    // Order preserved, duplicates removed
    let unique_commands: Vec<_> = seen.iter().collect();
    // ["init", "load", "process", "save"]
}