#include <iostream>
#include <list>
#include <string>
#include <algorithm> // for std::find etc

// Helper function: print list contents
template<typename T>
void print_list(const std::list<T>& lst, const std::string& msg = "") {
    if (!msg.empty())
        std::cout << msg << ": ";
    std::cout << "[ ";
    for (const auto& elem : lst) {
        std::cout << elem << " ";
    }
    std::cout << "]" << std::endl;
}

int main() {
    // ==================== 1. Construction and assignment ====================
    std::cout << "========== 1. Construction and assignment ==========" << std::endl;

    // Default construct
    std::list<int> list1;
    // Construct with initial size and value
    std::list<int> list2(5, 100);           // 5 elements of 100
    // Initializer list constructor (C++11)
    std::list<int> list3 = {1, 2, 3, 4, 5};
    // Copy construct
    std::list<int> list4(list3);
    // Range construct
    int arr[] = {10, 20, 30};
    std::list<int> list5(std::begin(arr), std::end(arr));

    print_list(list2, "list2 (5 elements of 100)");
    print_list(list3, "list3");
    print_list(list4, "list4 (copy of list3)");
    print_list(list5, "list5 (constructed from array)");

    // assign
    list1.assign(3, 42);
    print_list(list1, "list1 assign(3,42)");
    list1.assign({7, 8, 9});   // initializer list assign
    print_list(list1, "list1 assign({7,8,9})");
    list1.assign(list5.begin(), list5.end());
    print_list(list1, "list1 assign(iterator range)");

    // ==================== 2. Element access ====================
    std::cout << "\n========== 2. Element access ==========" << std::endl;
    std::list<std::string> str_list = {"apple", "banana", "cherry"};
    print_list(str_list, "str_list");
    std::cout << "front(): " << str_list.front() << std::endl;
    std::cout << "back(): " << str_list.back() << std::endl;
    // Note: list doesn't support operator[] or at(), because it's not a random access iterator

    // ==================== 3. Iterators ====================
    std::cout << "\n========== 3. Iterators ==========" << std::endl;
    std::list<int> iter_list = {10, 20, 30, 40, 50};
    std::cout << "Forward iterator: ";
    for (auto it = iter_list.begin(); it != iter_list.end(); ++it)
        std::cout << *it << " ";
    std::cout << std::endl;

    std::cout << "Reverse iterator: ";
    for (auto rit = iter_list.rbegin(); rit != iter_list.rend(); ++rit)
        std::cout << *rit << " ";
    std::cout << std::endl;

    // Const iterator (cbegin/cend)
    std::cout << "Const iterator (read-only): ";
    for (auto cit = iter_list.cbegin(); cit != iter_list.cend(); ++cit)
        std::cout << *cit << " ";
    std::cout << std::endl;

    // ==================== 4. Capacity ====================
    std::cout << "\n========== 4. Capacity ==========" << std::endl;
    std::list<double> cap_list = {1.1, 2.2, 3.3};
    print_list(cap_list, "cap_list");
    std::cout << "empty(): " << std::boolalpha << cap_list.empty() << std::endl;
    std::cout << "size(): " << cap_list.size() << std::endl;
    std::cout << "max_size(): " << cap_list.max_size() << std::endl;
    cap_list.resize(5, 0.0);   // resize, new elements filled with 0.0
    print_list(cap_list, "resize(5, 0.0)");
    cap_list.resize(2);         // shrink, remove extra elements
    print_list(cap_list, "resize(2)");

    // ==================== 5. Insertion and deletion ====================
    std::cout << "\n========== 5. Insertion and deletion ==========" << std::endl;
    std::list<int> mod_list;
    // push back
    mod_list.push_back(10);
    mod_list.push_back(20);
    // push front
    mod_list.push_front(5);
    mod_list.push_front(1);
    print_list(mod_list, "after push_back/push_front");

    // pop back
    mod_list.pop_back();
    // pop front
    mod_list.pop_front();
    print_list(mod_list, "after pop_back/pop_front");

    // insert before specified position
    auto it = mod_list.begin();
    ++it; // point to second element (20)
    mod_list.insert(it, 15);   // insert 15 before 20
    print_list(mod_list, "insert 15 before 20");

    mod_list.insert(mod_list.end(), {25, 30});   // insert multiple elements at end
    print_list(mod_list, "insert multiple elements at end");

    // erase remove element at position or range
    it = mod_list.begin();
    ++it; // point to 15
    it = mod_list.erase(it);   // remove 15, return iterator to next element (20)
    print_list(mod_list, "erase second element(15)");

    auto first = mod_list.begin();
    auto last = mod_list.begin();
    std::advance(last, 2);     // point to third element (30)
    mod_list.erase(first, last); // erase first two elements (10 20)
    print_list(mod_list, "erase first two elements");

    // remove / remove_if
    mod_list.push_back(20);
    mod_list.push_back(20);
    mod_list.push_back(40);
    print_list(mod_list, "after adding duplicate elements");
    mod_list.remove(20);       // remove all elements equal to 20
    print_list(mod_list, "after remove(20)");

    mod_list.remove_if([](int n) { return n > 30; }); // remove elements greater than 30
    print_list(mod_list, "after remove_if(>30)");

    // clear
    mod_list.clear();
    std::cout << "after clear size = " << mod_list.size() << std::endl;

    // emplace (C++11 direct construction, avoid copies)
    std::list<std::pair<int, char>> emp_list;
    emp_list.emplace_back(1, 'a');  // emplace back
    emp_list.emplace_front(0, 'z'); // emplace front
    auto eit = emp_list.begin();
    ++eit;
    emp_list.emplace(eit, 2, 'b');  // emplace at second position
    std::cout << "emplace example (pair): ";
    for (const auto& p : emp_list)
        std::cout << "(" << p.first << "," << p.second << ") ";
    std::cout << std::endl;

    // ==================== 6. Special operations (splice, merge, sort, reverse, unique) ====================
    std::cout << "\n========== 6. Special operations (splice, merge, sort, reverse, unique) ==========" << std::endl;
    std::list<int> listA = {1, 2, 3, 4, 5};
    std::list<int> listB = {10, 20, 30};

    // splice: move all elements from listB to the end of listA
    listA.splice(listA.end(), listB);
    print_list(listA, "listA after splice");
    print_list(listB, "listB (now empty)");

    // refill listB for demonstration
    listB = {15, 25, 35};
    auto pos = listA.begin();
    std::advance(pos, 2);  // point to third element
    // move a single element from listB to listA at pos
    listA.splice(pos, listB, listB.begin());  // move the first element from listB (15)
    print_list(listA, "listA after splice single element");
    print_list(listB, "listB (remaining 25,35)");

    // move range
    auto firstB = listB.begin();
    auto lastB = listB.end();
    listA.splice(listA.end(), listB, firstB, lastB); // move all remaining elements from listB
    print_list(listA, "listA after splice range");
    print_list(listB, "listB (now empty)");

    // sort (list has its own sort, cannot use std::sort)
    std::list<int> unsorted = {5, 2, 8, 1, 9, 3};
    print_list(unsorted, "before sort");
    unsorted.sort();  // default ascending
    print_list(unsorted, "after sort() ascending");
    unsorted.sort(std::greater<int>()); // descending
    print_list(unsorted, "after sort(greater) descending");

    // reverse
    unsorted.reverse();
    print_list(unsorted, "after reverse (back to ascending)");

    // unique: remove adjacent duplicates (usually sort first)
    std::list<int> dup_list = {1, 1, 2, 3, 3, 3, 4, 2, 2};
    print_list(dup_list, "before unique");
    dup_list.unique();  // only removes adjacent duplicates, later 2s remain
    print_list(dup_list, "after direct unique (adjacent only)");
    dup_list.sort();    // sort first
    dup_list.unique();  // then unique for full duplicate removal
    print_list(dup_list, "after sort then unique");

    // merge: merge two sorted lists, result remains sorted
    std::list<int> merge1 = {1, 3, 5, 7};
    std::list<int> merge2 = {2, 4, 6, 8};
    merge1.merge(merge2);  // both must be sorted, merge2 becomes empty
    print_list(merge1, "merge result merge1");
    print_list(merge2, "merge2 (now empty)");

    // custom compare merge (descending)
    std::list<int> desc1 = {7, 5, 3, 1};
    std::list<int> desc2 = {8, 6, 4, 2};
    desc1.merge(desc2, std::greater<int>()); // merge in descending order
    print_list(desc1, "merge(greater) descending merge");

    // ==================== 7. Swap and compare ====================
    std::cout << "\n========== 7. Swap and compare ==========" << std::endl;
    std::list<int> swap1 = {1, 2, 3};
    std::list<int> swap2 = {4, 5, 6, 7};
    print_list(swap1, "swap1 before");
    print_list(swap2, "swap2 before");
    swap1.swap(swap2);
    print_list(swap1, "swap1 after");
    print_list(swap2, "swap2 after");
    // std::swap(swap1, swap2) is also valid

    // comparison operators (==, !=, <, >, <=, >=)
    std::list<int> cmp1 = {1, 2, 3};
    std::list<int> cmp2 = {1, 2, 3};
    std::list<int> cmp3 = {1, 2, 4};
    std::cout << std::boolalpha;
    std::cout << "cmp1 == cmp2: " << (cmp1 == cmp2) << std::endl;
    std::cout << "cmp1 == cmp3: " << (cmp1 == cmp3) << std::endl;
    std::cout << "cmp1 < cmp3: " << (cmp1 < cmp3) << std::endl;

    // ==================== 8. Get allocator ====================
    std::cout << "\n========== 8. Get allocator ==========" << std::endl;
    std::list<int> alloc_list = {10, 20};
    auto alloc = alloc_list.get_allocator();
    int* p = alloc.allocate(3); // allocate uninitialized memory
    // rarely used manually, but available
    alloc.deallocate(p, 3);
    std::cout << "get_allocator example completed" << std::endl;

    // ==================== 9. Using non-member functions ====================
    // std::begin, std::end and other generic functions also work with list
    std::cout << "\n========== 9. Using non-member functions ==========" << std::endl;
    const std::list<int> const_list = {100, 200};
    auto it_begin = std::begin(const_list); // returns const_iterator
    std::cout << "std::begin value: " << *it_begin << std::endl;

    return 0;
}