main.cpp

#include <chrono>
#include <iomanip>
#include <iostream>
#include <limits>
#include <random>
#include <vector>

#include "include/BST.h"
#include "include/LinkedList.h"
#include "include/Queue.h"
#include "include/Sorting.h"
#include "include/Stack.h"

using namespace std;

void testDataStructures() {
  cout << "\n--- Testing Data Structures ---\n";

  // Linked List
  cout << "Testing Linked List: ";
  LinkedList<int> ll;
  ll.append(10);
  ll.append(20);
  ll.prepend(5);
  ll.display(); // 5 -> 10 -> 20 -> NULL

  // Stack
  cout << "Testing Stack (LIFO): ";
  Stack<int> s;
  s.push(1);
  s.push(2);
  s.push(3);
  cout << "Popped: " << s.pop() << ", Top now: " << s.peek() << endl;

  // Queue
  cout << "Testing Queue (FIFO): ";
  Queue<int> q;
  q.enqueue(100);
  q.enqueue(200);
  cout << "Dequeued: " << q.dequeue() << ", Front now: " << q.peek() << endl;

  // BST
  cout << "Testing BST (Inorder): ";
  BST<int> bst;
  bst.insert(50);
  bst.insert(30);
  bst.insert(70);
  bst.insert(20);
  bst.displayInorder(); // 20 30 50 70
}

void analyzeSortingPerformance(int dataSize) {
  cout << "\n--- Big O Analysis (Data Size: " << dataSize << ") ---\n";

  // Prepare random data
  vector<int> original;
  random_device rd;
  mt19937 gen(rd());
  uniform_int_distribution<> dis(1, 10000);
  for (int i = 0; i < dataSize; ++i)
    original.push_back(dis(gen));

  auto measure = [&](string name, auto func) {
    vector<int> arr = original;
    auto start = chrono::high_resolution_clock::now();
    func(arr);
    auto end = chrono::high_resolution_clock::now();
    chrono::duration<double, milli> elapsed = end - start;
    cout << left << setw(15) << name << ": " << fixed << setprecision(3)
         << elapsed.count() << " ms" << endl;
  };

  measure("Bubble Sort", [](vector<int> &v) { Sorting::bubbleSort(v); });
  measure("Merge Sort",
          [](vector<int> &v) { Sorting::mergeSort(v, 0, v.size() - 1); });
  measure("Quick Sort",
          [](vector<int> &v) { Sorting::quickSort(v, 0, v.size() - 1); });
  measure("STL Sort", [](vector<int> &v) { sort(v.begin(), v.end()); });
}

int main() {
  cout << "========================================\n";
  cout << "      Algorithmic Efficiency Lab        \n";
  cout << "========================================\n";

  testDataStructures();

  analyzeSortingPerformance(1000); // Small set
  analyzeSortingPerformance(5000); // Larger set

  cout << "\nLab execution complete. Memory cleaned up via destructors.\n";

  cout << "\nPress Enter to exit...";
  cin.clear();
  cin.ignore(numeric_limits<streamsize>::max(), '\n');
  cin.get();

  return 0;
}