Algorithms

/**
 * ============================================================
 * C++ STL ALGORITHMS
 * ============================================================
 * 
 * This file covers:
 * - Non-modifying algorithms (find, count, search)
 * - Modifying algorithms (copy, transform, replace)
 * - Sorting algorithms (sort, stable_sort, partial_sort)
 * - Numeric algorithms (accumulate, inner_product)
 * - Set algorithms (union, intersection, difference)
 * - Using lambdas with algorithms
 * 
 * Compile: g++ -std=c++17 -Wall 01_algorithms.cpp -o algorithms
 * Run: ./algorithms
 * 
 * ============================================================
 */

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <numeric>
#include <functional>
#include <random>
#include <iterator>

using namespace std;

// Helper to print containers
template <typename Container>
void print(const string& label, const Container& c) {
    cout << label << ": ";
    for (const auto& elem : c) cout << elem << " ";
    cout << endl;
}

// ============================================================
// MAIN FUNCTION
// ============================================================

int main() {
    cout << "============================================" << endl;
    cout << "     C++ STL ALGORITHMS" << endl;
    cout << "============================================" << endl << endl;

    // ========================================================
    // PART 1: NON-MODIFYING ALGORITHMS
    // ========================================================
    
    cout << "--- PART 1: NON-MODIFYING ALGORITHMS ---" << endl << endl;
    
    vector<int> data = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    print("data", data);
    
    // find
    auto it = find(data.begin(), data.end(), 5);
    if (it != data.end()) {
        cout << "find(5): found at index " << distance(data.begin(), it) << endl;
    }
    
    // find_if
    auto evenIt = find_if(data.begin(), data.end(), [](int x) { return x % 2 == 0; });
    cout << "find_if(even): " << *evenIt << endl;
    
    // find_if_not
    auto notSmall = find_if_not(data.begin(), data.end(), [](int x) { return x < 5; });
    cout << "find_if_not(< 5): " << *notSmall << endl;
    
    // count / count_if
    cout << "count(5): " << count(data.begin(), data.end(), 5) << endl;
    cout << "count_if(> 3): " << count_if(data.begin(), data.end(), 
                                          [](int x) { return x > 3; }) << endl;
    
    // all_of / any_of / none_of
    cout << "all_of(> 0): " << all_of(data.begin(), data.end(), 
                                      [](int x) { return x > 0; }) << endl;
    cout << "any_of(> 8): " << any_of(data.begin(), data.end(),
                                      [](int x) { return x > 8; }) << endl;
    cout << "none_of(< 0): " << none_of(data.begin(), data.end(),
                                        [](int x) { return x < 0; }) << endl;
    
    // search - find subsequence
    vector<int> pattern = {1, 5};
    auto searchIt = search(data.begin(), data.end(), pattern.begin(), pattern.end());
    if (searchIt != data.end()) {
        cout << "search({1,5}): found at index " << distance(data.begin(), searchIt) << endl;
    }
    
    // adjacent_find
    vector<int> adj = {1, 2, 3, 3, 4, 5};
    auto adjIt = adjacent_find(adj.begin(), adj.end());
    if (adjIt != adj.end()) {
        cout << "adjacent_find: " << *adjIt << " at index " 
             << distance(adj.begin(), adjIt) << endl;
    }
    
    // mismatch
    vector<int> v1 = {1, 2, 3, 4, 5};
    vector<int> v2 = {1, 2, 4, 4, 5};
    auto [mis1, mis2] = mismatch(v1.begin(), v1.end(), v2.begin());
    cout << "mismatch: v1=" << *mis1 << ", v2=" << *mis2 << endl;
    
    cout << endl;

    // ========================================================
    // PART 2: MODIFYING ALGORITHMS
    // ========================================================
    
    cout << "--- PART 2: MODIFYING ALGORITHMS ---" << endl << endl;
    
    // copy
    vector<int> src = {1, 2, 3, 4, 5};
    vector<int> dest(5);
    copy(src.begin(), src.end(), dest.begin());
    print("copy", dest);
    
    // copy_if
    vector<int> evens;
    copy_if(src.begin(), src.end(), back_inserter(evens),
            [](int x) { return x % 2 == 0; });
    print("copy_if(even)", evens);
    
    // copy_n
    vector<int> first3(3);
    copy_n(src.begin(), 3, first3.begin());
    print("copy_n(3)", first3);
    
    // transform
    vector<int> doubled(src.size());
    transform(src.begin(), src.end(), doubled.begin(),
              [](int x) { return x * 2; });
    print("transform(*2)", doubled);
    
    // transform with two inputs
    vector<int> added(src.size());
    transform(src.begin(), src.end(), doubled.begin(), added.begin(),
              [](int a, int b) { return a + b; });
    print("transform(src+doubled)", added);
    
    // fill
    vector<int> filled(5);
    fill(filled.begin(), filled.end(), 42);
    print("fill(42)", filled);
    
    // generate
    vector<int> generated(5);
    int n = 0;
    generate(generated.begin(), generated.end(), [&n]() { return n++; });
    print("generate(counter)", generated);
    
    // replace / replace_if
    vector<int> rep = {1, 2, 3, 2, 4, 2, 5};
    replace(rep.begin(), rep.end(), 2, 99);
    print("replace(2->99)", rep);
    
    vector<int> rep2 = {1, 2, 3, 4, 5, 6};
    replace_if(rep2.begin(), rep2.end(), [](int x) { return x > 3; }, 0);
    print("replace_if(>3->0)", rep2);
    
    // remove (doesn't actually remove - moves to end)
    vector<int> rem = {1, 2, 3, 2, 4, 2, 5};
    auto newEnd = remove(rem.begin(), rem.end(), 2);
    print("remove(2) before erase", rem);
    rem.erase(newEnd, rem.end());  // Actually remove
    print("after erase", rem);
    
    // unique
    vector<int> dup = {1, 1, 2, 2, 2, 3, 3, 4};
    auto uniqueEnd = unique(dup.begin(), dup.end());
    dup.erase(uniqueEnd, dup.end());
    print("unique", dup);
    
    // reverse
    vector<int> toRev = {1, 2, 3, 4, 5};
    reverse(toRev.begin(), toRev.end());
    print("reverse", toRev);
    
    // rotate
    vector<int> toRot = {1, 2, 3, 4, 5};
    rotate(toRot.begin(), toRot.begin() + 2, toRot.end());
    print("rotate(+2)", toRot);
    
    cout << endl;

    // ========================================================
    // PART 3: SORTING ALGORITHMS
    // ========================================================
    
    cout << "--- PART 3: SORTING ALGORITHMS ---" << endl << endl;
    
    // sort
    vector<int> toSort = {5, 2, 8, 1, 9, 3, 7};
    sort(toSort.begin(), toSort.end());
    print("sort", toSort);
    
    // sort descending
    sort(toSort.begin(), toSort.end(), greater<int>());
    print("sort(desc)", toSort);
    
    // sort with custom comparator
    vector<string> words = {"banana", "apple", "cherry", "date"};
    sort(words.begin(), words.end(), [](const string& a, const string& b) {
        return a.length() < b.length();  // By length
    });
    print("sort(by length)", words);
    
    // stable_sort (preserves order of equal elements)
    vector<pair<int, string>> items = {{2, "b"}, {1, "a"}, {2, "c"}, {1, "d"}};
    stable_sort(items.begin(), items.end(), 
                [](const auto& a, const auto& b) { return a.first < b.first; });
    cout << "stable_sort: ";
    for (const auto& [num, str] : items) cout << "(" << num << "," << str << ") ";
    cout << endl;
    
    // partial_sort
    vector<int> partial = {5, 2, 8, 1, 9, 3, 7};
    partial_sort(partial.begin(), partial.begin() + 3, partial.end());
    print("partial_sort(3)", partial);  // First 3 are smallest, rest unsorted
    
    // nth_element
    vector<int> nth = {5, 2, 8, 1, 9, 3, 7};
    nth_element(nth.begin(), nth.begin() + 3, nth.end());
    print("nth_element(3)", nth);
    cout << "4th smallest: " << nth[3] << endl;
    
    // is_sorted
    vector<int> sorted = {1, 2, 3, 4, 5};
    cout << "is_sorted({1,2,3,4,5}): " << is_sorted(sorted.begin(), sorted.end()) << endl;
    
    cout << endl;

    // ========================================================
    // PART 4: BINARY SEARCH ALGORITHMS
    // ========================================================
    
    cout << "--- PART 4: BINARY SEARCH ---" << endl << endl;
    
    vector<int> sorted2 = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    print("sorted", sorted2);
    
    // binary_search
    cout << "binary_search(5): " << binary_search(sorted2.begin(), sorted2.end(), 5) << endl;
    cout << "binary_search(10): " << binary_search(sorted2.begin(), sorted2.end(), 10) << endl;
    
    // lower_bound (first element >= value)
    auto lb = lower_bound(sorted2.begin(), sorted2.end(), 5);
    cout << "lower_bound(5): index " << distance(sorted2.begin(), lb) << endl;
    
    // upper_bound (first element > value)
    auto ub = upper_bound(sorted2.begin(), sorted2.end(), 5);
    cout << "upper_bound(5): index " << distance(sorted2.begin(), ub) << endl;
    
    // equal_range (both bounds)
    vector<int> withDups = {1, 2, 2, 2, 3, 4, 5};
    auto [lo, hi] = equal_range(withDups.begin(), withDups.end(), 2);
    cout << "equal_range(2): [" << distance(withDups.begin(), lo) 
         << ", " << distance(withDups.begin(), hi) << ")" << endl;
    
    cout << endl;

    // ========================================================
    // PART 5: NUMERIC ALGORITHMS
    // ========================================================
    
    cout << "--- PART 5: NUMERIC ALGORITHMS ---" << endl << endl;
    
    vector<int> nums = {1, 2, 3, 4, 5};
    print("nums", nums);
    
    // accumulate
    int sum = accumulate(nums.begin(), nums.end(), 0);
    cout << "sum: " << sum << endl;
    
    // accumulate with custom operation
    int product = accumulate(nums.begin(), nums.end(), 1, multiplies<int>());
    cout << "product: " << product << endl;
    
    // inner_product (dot product)
    vector<int> a = {1, 2, 3};
    vector<int> b = {4, 5, 6};
    int dot = inner_product(a.begin(), a.end(), b.begin(), 0);
    cout << "dot product: " << dot << " (1*4 + 2*5 + 3*6 = 32)" << endl;
    
    // partial_sum
    vector<int> partial_sums(nums.size());
    partial_sum(nums.begin(), nums.end(), partial_sums.begin());
    print("partial_sum", partial_sums);
    
    // adjacent_difference
    vector<int> diffs(nums.size());
    adjacent_difference(nums.begin(), nums.end(), diffs.begin());
    print("adjacent_diff", diffs);
    
    // iota
    vector<int> seq(10);
    iota(seq.begin(), seq.end(), 1);  // 1, 2, 3, ...
    print("iota(1)", seq);
    
    cout << endl;

    // ========================================================
    // PART 6: SET ALGORITHMS
    // ========================================================
    
    cout << "--- PART 6: SET ALGORITHMS ---" << endl << endl;
    
    vector<int> s1 = {1, 2, 3, 4, 5};
    vector<int> s2 = {3, 4, 5, 6, 7};
    print("s1", s1);
    print("s2", s2);
    
    // set_union
    vector<int> unionResult;
    set_union(s1.begin(), s1.end(), s2.begin(), s2.end(), back_inserter(unionResult));
    print("union", unionResult);
    
    // set_intersection
    vector<int> intersectResult;
    set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), 
                     back_inserter(intersectResult));
    print("intersection", intersectResult);
    
    // set_difference
    vector<int> diffResult;
    set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), 
                   back_inserter(diffResult));
    print("difference(s1-s2)", diffResult);
    
    // set_symmetric_difference
    vector<int> symDiff;
    set_symmetric_difference(s1.begin(), s1.end(), s2.begin(), s2.end(),
                             back_inserter(symDiff));
    print("symmetric_diff", symDiff);
    
    // includes
    vector<int> subset = {3, 4};
    cout << "s1 includes {3,4}: " << includes(s1.begin(), s1.end(),
                                              subset.begin(), subset.end()) << endl;
    
    cout << endl;

    // ========================================================
    // PART 7: MIN/MAX AND PERMUTATIONS
    // ========================================================
    
    cout << "--- PART 7: MIN/MAX & PERMUTATIONS ---" << endl << endl;
    
    vector<int> vals = {3, 1, 4, 1, 5, 9, 2, 6};
    
    // min_element / max_element
    auto minIt = min_element(vals.begin(), vals.end());
    auto maxIt = max_element(vals.begin(), vals.end());
    cout << "min: " << *minIt << " at index " << distance(vals.begin(), minIt) << endl;
    cout << "max: " << *maxIt << " at index " << distance(vals.begin(), maxIt) << endl;
    
    // minmax_element
    auto [minElem, maxElem] = minmax_element(vals.begin(), vals.end());
    cout << "minmax: " << *minElem << ", " << *maxElem << endl;
    
    // clamp (C++17)
    cout << "clamp(7, 1, 5): " << clamp(7, 1, 5) << endl;
    cout << "clamp(3, 1, 5): " << clamp(3, 1, 5) << endl;
    cout << "clamp(-2, 1, 5): " << clamp(-2, 1, 5) << endl;
    
    // next_permutation
    vector<int> perm = {1, 2, 3};
    cout << "\nPermutations of {1,2,3}:" << endl;
    do {
        for (int x : perm) cout << x << " ";
        cout << endl;
    } while (next_permutation(perm.begin(), perm.end()));
    
    // shuffle
    vector<int> toShuffle = {1, 2, 3, 4, 5};
    random_device rd;
    mt19937 gen(rd());
    shuffle(toShuffle.begin(), toShuffle.end(), gen);
    print("\nshuffled", toShuffle);
    
    cout << endl;

    // ========================================================
    // ALGORITHM SUMMARY
    // ========================================================
    
    cout << "--- ALGORITHM CATEGORIES ---" << endl << endl;
    
    cout << "Non-modifying:" << endl;
    cout << "─────────────────────────────────────────" << endl;
    cout << "find, find_if, count, count_if" << endl;
    cout << "all_of, any_of, none_of" << endl;
    cout << "search, mismatch, equal" << endl;
    
    cout << "\nModifying:" << endl;
    cout << "─────────────────────────────────────────" << endl;
    cout << "copy, copy_if, transform" << endl;
    cout << "fill, generate, replace" << endl;
    cout << "remove, unique, reverse, rotate" << endl;
    
    cout << "\nSorting:" << endl;
    cout << "─────────────────────────────────────────" << endl;
    cout << "sort, stable_sort, partial_sort" << endl;
    cout << "nth_element, is_sorted" << endl;
    
    cout << "\nBinary Search:" << endl;
    cout << "─────────────────────────────────────────" << endl;
    cout << "binary_search, lower_bound, upper_bound" << endl;
    cout << "equal_range" << endl;
    
    cout << "\nNumeric:" << endl;
    cout << "─────────────────────────────────────────" << endl;
    cout << "accumulate, inner_product" << endl;
    cout << "partial_sum, adjacent_difference, iota" << endl;
    
    cout << endl;

    cout << "============================================" << endl;
    cout << "STL ALGORITHMS COMPLETE!" << endl;
    cout << "============================================" << endl;

    return 0;
}

// ============================================================
// EXERCISES:
// ============================================================
/*
 * 1. Word processor:
 *    - Read text, count word frequency
 *    - Find longest word, most common word
 *    - Remove duplicates, sort by frequency
 * 
 * 2. Statistics calculator:
 *    - Calculate mean, median, mode, std deviation
 *    - Use accumulate, sort, nth_element
 *    - Handle edge cases (empty input)
 * 
 * 3. Set operations puzzle:
 *    - Given multiple sets, find elements in:
 *      - All sets (multi-set intersection)
 *      - Exactly one set (symmetric diff)
 *      - At least N sets
 * 
 * 4. Custom sort:
 *    - Sort students by GPA, then by name
 *    - Use stable_sort with multiple criteria
 *    - Partition into pass/fail groups
 */