#include <iostream>
#include <map>
#include <string>
#include <utility>
#include <functional>   // std::greater

// Example class used as a key with custom type
struct Person {
    int id;
    std::string name;

    // Must provide operator<, or use a custom comparator
    bool operator<(const Person& other) const {
        return id < other.id;   // sort by id
    }
};

// Helper template to print map contents
template<typename K, typename V>
void printMap(const std::map<K, V>& m, const std::string& title) {
    std::cout << title << ":\n";
    for (const auto& [key, value] : m) {
        std::cout << "  " << key << " -> " << value << '\n';
    }
    std::cout << "  size = " << m.size() << "\n\n";
}

int main() {
    // ========== 1. Construction and initialization ==========
    std::cout << "=== 1. Construction and initialization ===\n";
    // Default construct
    std::map<int, std::string> m1;
    // initializer_list construction
    std::map<int, std::string> m2 = {
        {1, "one"},
        {2, "two"},
        {3, "three"}
    };
    // Copy construct
    std::map<int, std::string> m3(m2);
    // Range construct
    std::map<int, std::string> m4(m2.begin(), m2.end());

    printMap(m2, "m2");

    // ========== 2. Inserting elements ==========
    std::cout << "=== 2. Inserting elements ===\n";
    std::map<int, std::string> mp;

    // 2.1 Using operator[] (inserts with default value if key missing)
    mp[10] = "ten";
    mp[20] = "twenty";

    // 2.2 Using insert
    mp.insert(std::pair<int, std::string>(30, "thirty"));      // old style
    mp.insert(std::make_pair(40, "forty"));                    // recommended: make_pair
    mp.insert({50, "fifty"});                                  // C++11: initializer_list

    // 2.3 insert return value: pair<iterator, bool>, bool indicates success
    auto [it, inserted] = mp.insert({20, "TWENTY"});
    if (!inserted) {
        std::cout << "Key 20 already exists, value is " << it->second << ", insertion failed\n";
    }

    // 2.4 emplace (construct in-place, avoid temporaries)
    mp.emplace(60, "sixty");

    // 2.5 try_emplace (C++17, like emplace but does not modify value if key exists)
    mp.try_emplace(70, "seventy");
    mp.try_emplace(10, "TEN");   // key=10 already exists, no overwrite

    // 2.6 insert_or_assign (C++17, assign if key exists, insert otherwise)
    mp.insert_or_assign(10, "TEN");       // overwrite existing value
    mp.insert_or_assign(80, "eighty");

    printMap(mp, "map after insertions");

    // ========== 3. Accessing elements ==========
    std::cout << "=== 3. Accessing elements ===\n";
    // operator[] will insert missing key (use with caution)
    std::cout << "mp[10] = " << mp[10] << '\n';
    std::cout << "mp[100] (not existing) = " << mp[100] << " (automatically inserted empty string)\n";
    // at() method: safe access, throws std::out_of_range if key missing
    try {
        std::cout << "mp.at(20) = " << mp.at(20) << '\n';
        // std::cout << mp.at(999) << '\n';  // would throw
    } catch (const std::out_of_range& e) {
        std::cout << "Exception: " << e.what() << '\n';
    }
    std::cout << '\n';

    // ========== 4. Iterators and traversal ==========
    std::cout << "=== 4. Iterators and traversal ===\n";
    std::cout << "Forward traversal: ";
    for (auto it = mp.begin(); it != mp.end(); ++it) {
        std::cout << it->first << ":" << it->second << " ";
    }
    std::cout << '\n';

    std::cout << "Reverse traversal: ";
    for (auto rit = mp.rbegin(); rit != mp.rend(); ++rit) {
        std::cout << rit->first << ":" << rit->second << " ";
    }
    std::cout << '\n';

    std::cout << "Range-based for loop: ";
    for (const auto& [k, v] : mp) {
        std::cout << k << ":" << v << " ";
    }
    std::cout << "\n\n";

    // ========== 5. Finding elements ==========
    std::cout << "=== 5. Finding elements ===\n";
    int key = 50;
    auto it_find = mp.find(key);
    if (it_find != mp.end()) {
        std::cout << "find(" << key << ") -> " << it_find->first << ":" << it_find->second << '\n';
    } else {
        std::cout << "find(" << key << ") not found\n";
    }

    // count: returns the number of occurrences of key (0 or 1 because map keys are unique)
    std::cout << "count(30) = " << mp.count(30) << '\n';
    std::cout << "count(99) = " << mp.count(99) << '\n';

    // contains (C++20)
#if __cplusplus >= 202002L
    std::cout << "contains(40): " << mp.contains(40) << '\n';
#endif

    // lower_bound / upper_bound / equal_range
    auto lb = mp.lower_bound(30);   // first element >= 30
    auto ub = mp.upper_bound(30);   // first element > 30
    std::cout << "lower_bound(30): " << lb->first << ":" << lb->second << '\n';
    std::cout << "upper_bound(30): " << ub->first << ":" << ub->second << '\n';

    auto eq = mp.equal_range(30);
    std::cout << "equal_range(30): ["
              << eq.first->first << ":" << eq.first->second << ", "
              << eq.second->first << ":" << eq.second->second << "]\n\n";

    // ========== 6. Erasing elements ==========
    std::cout << "=== 6. Erasing elements ===\n";
    // Erase by key
    mp.erase(100);          // no effect if key doesn't exist
    mp.erase(80);           // erase key=80
    // Erase by iterator
    auto it_del = mp.find(60);
    if (it_del != mp.end()) {
        mp.erase(it_del);
    }
    // Erase by range (remove first two elements)
    auto first = mp.begin();
    auto last = mp.begin();
    std::advance(last, 2);   // first two elements
    mp.erase(first, last);

    printMap(mp, "map after erasing some elements");

    // ========== 7. Size and capacity ==========
    std::cout << "=== 7. Size and capacity ===\n";
    std::cout << "size() = " << mp.size() << '\n';
    std::cout << "empty() = " << (mp.empty() ? "true" : "false") << '\n';
    std::cout << "max_size() = " << mp.max_size() << " (platform-dependent)\n\n";

    // ========== 8. Modifiers ==========
    std::cout << "=== 8. Modifiers ===\n";
    std::map<int, std::string> other = {{999, "nine-nine-nine"}};
    mp.swap(other);
    std::cout << "after swap mp: ";
    for (const auto& [k, v] : mp) std::cout << k << ":" << v << " ";
    std::cout << "\nafter swap other: ";
    for (const auto& [k, v] : other) std::cout << k << ":" << v << " ";
    std::cout << '\n';

    mp.clear();
    std::cout << "after clear mp.size() = " << mp.size() << "\n\n";

    // ========== 9. Custom comparison (descending) ==========
    std::cout << "=== 9. Custom comparison (descending) ===\n";
    std::map<int, std::string, std::greater<int>> descMap = {
        {1, "a"}, {3, "c"}, {2, "b"}
    };
    for (const auto& [k, v] : descMap) {
        std::cout << k << " -> " << v << '\n';
    }

    // Use lambda as comparator (C++11)
    auto cmp = [](const Person& p1, const Person& p2) { return p1.id > p2.id; };
    std::map<Person, std::string, decltype(cmp)> personMap(cmp);
    personMap[{101, "Alice"}] = "Manager";
    personMap[{102, "Bob"}]   = "Engineer";
    personMap[{100, "Carol"}] = "Director";
    std::cout << "\nPerson map (sorted by id descending):\n";
    for (const auto& [p, role] : personMap) {
        std::cout << "  id:" << p.id << " name:" << p.name << " -> " << role << '\n';
    }
    std::cout << '\n';

    // ========== 10. Merge and extract ==========
    std::cout << "=== 10. Merge and extract ===\n";
    std::map<int, std::string> src = {{1, "one"}, {2, "two"}, {3, "three"}};
    std::map<int, std::string> dst = {{2, "TWO"}, {4, "four"}};

    // extract node (no value copy)
    auto node = src.extract(1);       // extract node with key=1
    node.key() = 10;                  // modify key (C++17)
    dst.insert(std::move(node));      // insert into destination map

    // merge: move all nodes from src into dst (conflicting ones remain in src)
    dst.merge(src);
    std::cout << "after merge dst: ";
    for (const auto& [k, v] : dst) std::cout << k << ":" << v << " ";
    std::cout << "\nafter merge src: ";
    for (const auto& [k, v] : src) std::cout << k << ":" << v << " ";
    std::cout << "\n";

    // ========== 11. Other utilities ==========
    std::cout << "\n=== 11. Other utilities ===\n";
    // Swap two maps contents using non-member std::swap
    std::map<int, std::string> a = {{1, "a"}};
    std::map<int, std::string> b = {{2, "b"}};
    std::swap(a, b);
    std::cout << "after std::swap a: ";
    for (const auto& [k, v] : a) std::cout << k << ":" << v << " ";
    std::cout << "\n";

    // Comparison operators (==, !=, <, <=, >, >=) compare lexicographically
    std::map<int, int> m_a = {{1,10}, {2,20}};
    std::map<int, int> m_b = {{1,10}, {2,20}};
    std::map<int, int> m_c = {{1,10}, {3,30}};
    std::cout << "m_a == m_b: " << (m_a == m_b) << '\n';
    std::cout << "m_a <  m_c: " << (m_a < m_c) << '\n';

    return 0;
}