#include <iostream>
#include <set>
#include <unordered_set>
#include <algorithm>   // for set_intersection etc.
#include <iterator>    // for inserter
#include <string>
#include <vector>

// Custom struct used to demonstrate storing custom types in set and specifying ordering
struct Person {
    std::string name;
    int age;

    // Default constructor (optional)
    Person() = default;
    // Parameterized constructor for convenience
    Person(const std::string& n, int a) : name(n), age(a) {}

    // Comparison operator used for set ordering
    bool operator<(const Person& other) const {
        if (age != other.age) return age < other.age;
        return name < other.name;   // Sort by name when ages are equal to ensure uniqueness
    }
};

// Custom comparator functor (descending order)
struct Descending {
    bool operator()(int a, int b) const {
        return a > b;
    }
};

int main() {
    // ====================== 1. std::set basic operations ======================
    std::cout << "========== std::set basic operations ==========\n";

    // 1.1 Different ways to create set
    std::set<int> s1;                          // Empty set, ascending order (default less<int>)
    std::set<int, Descending> s2;              // Descending set
    std::set<int> s3 = {5, 2, 8, 2, 1, 9};     // Initializer list, duplicates removed and sorted
    std::set<int> s4(s3.begin(), s3.end());    // Iterator range construction
    std::set<int> s5(s3);                      // Copy construction

    // 1.2 Insert elements
    s1.insert(10);
    s1.insert(5);
    s1.insert(20);
    s1.insert(5);   // Duplicate insert ignored, set contains only one 5
    auto [pos, inserted] = s1.insert(15);      // pos is iterator, inserted indicates whether insertion succeeded
    std::cout << "Insert 15 " << (inserted ? "succeeded" : "failed") << '\n';

    // Bulk insert (iterator range)
    std::vector<int> vec = {30, 25, 30};
    s1.insert(vec.begin(), vec.end());

    // Insert initializer list
    s1.insert({40, 35, 40});

    // emplace: construct element directly, avoid temporaries
    s1.emplace(45);

    // emplace_hint: provide a hint position (usually end()), may improve performance
    s1.emplace_hint(s1.end(), 50);

    std::cout << "s1 contents (ascending): ";
    for (int x : s1) std::cout << x << " ";
    std::cout << '\n';

    // 1.3 Erase elements
    // Erase by value
    size_t n = s1.erase(30);   // Returns number of erased elements (0 or 1)
    std::cout << "Erase 30: " << (n ? "succeeded" : "failed") << '\n';

    // Erase by iterator
    auto it = s1.find(40);
    if (it != s1.end()) {
        s1.erase(it);
        std::cout << "Erased 40\n";
    }

    // Erase a range [first, last)
    auto first = s1.lower_bound(20);
    auto last  = s1.upper_bound(35);
    s1.erase(first, last);
    std::cout << "After erasing elements in [20,35), s1: ";
    for (int x : s1) std::cout << x << " ";
    std::cout << '\n';

    // Clear all elements
    s1.clear();
    std::cout << "After clearing s1 size: " << s1.size() << '\n';

    // 1.4 Find and count
    std::set<int> ss = {1, 2, 3, 4, 5};
    // find: returns iterator if found, otherwise end()
    auto it_find = ss.find(3);
    if (it_find != ss.end()) std::cout << "Found " << *it_find << '\n';
    // count: returns 0 or 1 because set has unique elements
    std::cout << "count of element 3: " << ss.count(3) << '\n';
    // contains (C++20)
    #if __cplusplus >= 202002L
    if (ss.contains(4)) std::cout << "contains(4) is true\n";
    #endif

    // 1.5 Boundary queries (lower_bound, upper_bound, equal_range)
    std::set<int> bounds = {10, 20, 30, 40, 50};
    auto low = bounds.lower_bound(25);   // first element >= 25 => 30
    auto up = bounds.upper_bound(35);    // first element > 35 => 40
    std::cout << "lower_bound(25): " << *low << '\n';
    std::cout << "upper_bound(35): " << *up << '\n';

    auto eq = bounds.equal_range(30);    // returns pair<lower_bound, upper_bound>
    std::cout << "equal_range(30): [" << *eq.first << ", " << *eq.second << "]\n";

    // 1.6 Size and capacity
    std::set<int> sz = {1,2,3};
    std::cout << "size: " << sz.size() << '\n';
    std::cout << "empty: " << std::boolalpha << sz.empty() << '\n';
    std::cout << "max_size: " << sz.max_size() << " (platform-dependent)\n";

    // 1.7 Iterators (forward, reverse, const)
    std::set<int> iter_set = {10,20,30,40};
    std::cout << "Forward iteration: ";
    for (auto it = iter_set.begin(); it != iter_set.end(); ++it) std::cout << *it << " ";
    std::cout << "\nReverse iteration: ";
    for (auto rit = iter_set.rbegin(); rit != iter_set.rend(); ++rit) std::cout << *rit << " ";
    std::cout << "\nRange for: ";
    for (int x : iter_set) std::cout << x << " ";
    std::cout << '\n';

    // 1.8 Comparator functions (key_comp and value_comp)
    std::set<int, Descending> comp_set = {5,2,8,1};
    auto key_comp = comp_set.key_comp();   // comparator object for keys
    std::cout << "In descending set, is first element less than second? " << key_comp(5,2) << " (5>2 returns false)\n";
    auto val_comp = comp_set.value_comp(); // same as key_comp
    (void)val_comp; // avoid unused warning

    // 1.9 swap contents of two sets
    std::set<int> a = {1,2,3}, b = {4,5,6};
    a.swap(b);
    std::cout << "After swap a: "; for(int x:a) std::cout << x << " ";
    std::cout << ", b: "; for(int x:b) std::cout << x << " ";
    std::cout << '\n';

    // 1.10 Custom type as set element
    std::set<Person> people;
    people.insert(Person("Alice", 25));      // use constructor
    people.insert(Person("Bob", 30));
    people.insert(Person("Charlie", 22));
    people.emplace("David", 25);             // emplace directly calls constructor
    std::cout << "Person set (sorted by age): ";
    for (const auto& p : people) std::cout << p.name << "(" << p.age << ") ";
    std::cout << '\n';

    // ====================== 2. std::multiset ======================
    std::cout << "\n========== std::multiset (allows duplicates) ==========\n";
    std::multiset<int> ms = {1, 2, 2, 3, 3, 3};
    ms.insert(2);
    ms.insert(4);
    std::cout << "multiset contents: ";
    for (int x : ms) std::cout << x << " ";  // 1 2 2 2 3 3 3 4
    std::cout << '\n';
    std::cout << "count of 2: " << ms.count(2) << '\n';  // 3
    // erase all elements equal to a certain value
    ms.erase(3);
    std::cout << "After erasing all 3: ";
    for (int x : ms) std::cout << x << " ";
    std::cout << '\n';
    // find returns first iterator equal to that value
    auto it_ms = ms.find(2);
    if (it_ms != ms.end()) std::cout << "find found: " << *it_ms << '\n';
    // Boundary queries: lower_bound/upper_bound are meaningful in multiset
    ms = {1,2,2,2,3,4,5};
    auto lo = ms.lower_bound(2);      // first 2
    auto up_ms = ms.upper_bound(2);   // first element >2 (i.e. 3)
    std::cout << "lower_bound(2): " << *lo << ", upper_bound(2): " << *up_ms << '\n';
    // equal_range returns a pair of iterators, the range contains all 2s
    auto eq_ms = ms.equal_range(2);
    std::cout << "equal_range(2) range length: " << std::distance(eq_ms.first, eq_ms.second) << '\n';

    // ====================== 3. std::unordered_set ======================
    std::cout << "\n========== std::unordered_set (hash, unordered) ==========\n";
    std::unordered_set<int> us = {5, 2, 8, 2, 1, 9, 5};
    us.insert(10);
    us.emplace(7);
    std::cout << "unordered_set contents (unordered): ";
    for (int x : us) std::cout << x << " ";
    std::cout << '\n';
    std::cout << "bucket_count: " << us.bucket_count() << '\n';
    std::cout << "load_factor: " << us.load_factor() << '\n';
    auto it_us = us.find(8);
    if (it_us != us.end()) std::cout << "Found 8\n";
    us.erase(2);
    std::cout << "After erasing 2: ";
    for (int x : us) std::cout << x << " ";
    std::cout << '\n';

    // For custom types, need to provide hash and equality comparison
    struct PersonHash {
        std::size_t operator()(const Person& p) const {
            return std::hash<std::string>()(p.name) ^ (std::hash<int>()(p.age) << 1);
        }
    };
    struct PersonEqual {
        bool operator()(const Person& a, const Person& b) const {
            return a.name == b.name && a.age == b.age;
        }
    };
    std::unordered_set<Person, PersonHash, PersonEqual> us_person;
    us_person.insert(Person("Alice", 25));   // use constructor
    us_person.insert(Person("Bob", 30));
    us_person.insert(Person("Alice", 25));   // duplicate, not inserted
    std::cout << "unordered_set<Person> size: " << us_person.size() << '\n';

    // ====================== 4. Set operations ======================
    std::cout << "\n========== Set operations (union, intersection, difference) ==========\n";
    std::set<int> A = {1, 2, 3, 4, 5};
    std::set<int> B = {4, 5, 6, 7, 8};
    std::set<int> result;

    // Union
    std::set_union(A.begin(), A.end(), B.begin(), B.end(),
                   std::inserter(result, result.begin()));
    std::cout << "A ∪ B: ";
    for (int x : result) std::cout << x << " ";
    std::cout << '\n';

    // Intersection
    result.clear();
    std::set_intersection(A.begin(), A.end(), B.begin(), B.end(),
                          std::inserter(result, result.begin()));
    std::cout << "A ∩ B: ";
    for (int x : result) std::cout << x << " ";
    std::cout << '\n';

    // Difference (A - B)
    result.clear();
    std::set_difference(A.begin(), A.end(), B.begin(), B.end(),
                        std::inserter(result, result.begin()));
    std::cout << "A - B: ";
    for (int x : result) std::cout << x << " ";
    std::cout << '\n';

    // Symmetric difference (A △ B)
    result.clear();
    std::set_symmetric_difference(A.begin(), A.end(), B.begin(), B.end(),
                                  std::inserter(result, result.begin()));
    std::cout << "A △ B: ";
    for (int x : result) std::cout << x << " ";
    std::cout << '\n';

    // ====================== 5. Other advanced operations ======================
    std::cout << "\n========== Other advanced operations ==========\n";
    // Get allocator
    std::set<int>::allocator_type alloc = s3.get_allocator();
    int* p = alloc.allocate(1);
    alloc.construct(p, 42);
    std::cout << "Value constructed by allocator: " << *p << '\n';
    alloc.destroy(p);
    alloc.deallocate(p, 1);

    // Extract node (C++17)
    std::set<int> source = {100, 200};
    std::set<int> target = {300};
    auto node = source.extract(100);  // extract node without copying element
    if (node) {
        target.insert(std::move(node));
        std::cout << "After extracting and inserting, target contains 100: " << (target.find(100) != target.end()) << '\n';
    }
    // Merge
    source = {400, 500};
    target.merge(source);  // moves elements from source into target, duplicates remain in source
    std::cout << "After merge target size: " << target.size() << ", source size: " << source.size() << '\n';

    return 0;
}