#include <iostream>
#include <vector>
#include <memory>
#include <algorithm> // Used to demonstrate std::sort as a standard library strategy

// ==================== Strategy Interface ====================
// Abstract strategy: defines the interface all concrete sorting strategies must implement
class SortStrategy {
public:
    virtual ~SortStrategy() = default;
    virtual void sort(std::vector<int>& data) const = 0;
    virtual std::string name() const = 0; // Used to print strategy name
};

// ==================== Concrete Strategies ====================

// Bubble Sort Strategy
class BubbleSort : public SortStrategy {
public:
    void sort(std::vector<int>& data) const override {
        size_t n = data.size();
        for (size_t i = 0; i < n - 1; ++i) {
            for (size_t j = 0; j < n - i - 1; ++j) {
                if (data[j] > data[j + 1]) {
                    std::swap(data[j], data[j + 1]);
                }
            }
        }
    }

    std::string name() const override {
        return "Bubble Sort";
    }
};

// Quick Sort Strategy (simulated using std::sort from STL)
class QuickSort : public SortStrategy {
public:
    void sort(std::vector<int>& data) const override {
        // The C++ standard library sort is typically implemented as an introsort (quick sort + heap sort mix)
        std::sort(data.begin(), data.end());
    }

    std::string name() const override {
        return "Quick Sort (std::sort)";
    }
};

// Merge Sort Strategy (simple custom implementation)
class MergeSort : public SortStrategy {
private:
    void merge(std::vector<int>& data, size_t left, size_t mid, size_t right) const {
        std::vector<int> temp(right - left + 1);
        size_t i = left, j = mid + 1, k = 0;
        while (i <= mid && j <= right) {
            temp[k++] = (data[i] <= data[j]) ? data[i++] : data[j++];
        }
        while (i <= mid) temp[k++] = data[i++];
        while (j <= right) temp[k++] = data[j++];
        for (size_t p = 0; p < temp.size(); ++p) {
            data[left + p] = temp[p];
        }
    }

    void mergeSort(std::vector<int>& data, size_t left, size_t right) const {
        if (left >= right) return;
        size_t mid = left + (right - left) / 2;
        mergeSort(data, left, mid);
        mergeSort(data, mid + 1, right);
        merge(data, left, mid, right);
    }

public:
    void sort(std::vector<int>& data) const override {
        if (!data.empty())
            mergeSort(data, 0, data.size() - 1);
    }

    std::string name() const override {
        return "Merge Sort";
    }
};

// ==================== Context Class ====================
// Sorter uses a sorting strategy and can switch it at runtime
class Sorter {
private:
    // Manage strategy object lifetime with smart pointers
    std::unique_ptr<SortStrategy> strategy_;

public:
    // Constructor: inject initial strategy (default null)
    explicit Sorter(std::unique_ptr<SortStrategy> initialStrategy = nullptr)
        : strategy_(std::move(initialStrategy)) {}

    // Set a new strategy
    void setStrategy(std::unique_ptr<SortStrategy> newStrategy) {
        strategy_ = std::move(newStrategy);
    }

    // Execute sort (delegate to current strategy)
    void sort(std::vector<int>& data) const {
        if (!strategy_) {
            throw std::runtime_error("No sorting strategy set!");
        }
        std::cout << "Using strategy: " << strategy_->name() << std::endl;
        strategy_->sort(data);
    }
};

// ==================== Helper Functions ====================
void printVector(const std::vector<int>& data) {
    std::cout << "[ ";
    for (int num : data) {
        std::cout << num << " ";
    }
    std::cout << "]\n";
}

// ==================== Main Demonstration Function ====================
int main() {
    // Original unsorted data
    std::vector<int> original = { 42, 23, 74, 11, 65, 58, 94, 36, 99, 7 };

    std::cout << "Original data: ";
    printVector(original);

    // Create Sorter context (no strategy set yet)
    Sorter sorter;

    // -------------------- Using Bubble Sort --------------------
    std::vector<int> data1 = original;
    sorter.setStrategy(std::make_unique<BubbleSort>());
    sorter.sort(data1);
    std::cout << "Sorted result: ";
    printVector(data1);
    std::cout << "----------------------------\n";

    // -------------------- Using Quick Sort (std::sort) --------------------
    std::vector<int> data2 = original;
    sorter.setStrategy(std::make_unique<QuickSort>());
    sorter.sort(data2);
    std::cout << "Sorted result: ";
    printVector(data2);
    std::cout << "----------------------------\n";

    // -------------------- Using Merge Sort --------------------
    std::vector<int> data3 = original;
    sorter.setStrategy(std::make_unique<MergeSort>());
    sorter.sort(data3);
    std::cout << "Sorted result: ";
    printVector(data3);
    std::cout << "----------------------------\n";

    // Demonstrate dynamic switching: bubble sort then merge sort on the same data
    std::cout << "Demonstrating dynamic strategy switching:\n";
    std::vector<int> data4 = original;
    sorter.setStrategy(std::make_unique<BubbleSort>());
    sorter.sort(data4);
    std::cout << "First sorted result: ";
    printVector(data4);

    // Shuffle data and then use merge sort
    data4 = { 88, 3, 67, 24, 59, 41, 73, 18, 90, 55 };
    std::cout << "New unsorted data: ";
    printVector(data4);
    sorter.setStrategy(std::make_unique<MergeSort>());
    sorter.sort(data4);
    std::cout << "Merge sort result: ";
    printVector(data4);

    return 0;
}