/* qsort.cpp
 * Date: 2024-06-22
 * Author: Aryadev Chavali
 * Commentary: The inplace O(nlog(n)) sortitng algorithm.  Originally designed
 * in C, hence the lack of iostream.
 */
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <stack>
#include <vector>

using u64 = uint64_t;

#define ARR_SIZE(XS) (sizeof(XS) / sizeof((XS)[0]))
#define SWAP(A, B) \
  do               \
  {                \
    (A) ^= (B);    \
    (B) ^= (A);    \
    (A) ^= (B);    \
  } while (0)

void print_arr(u64 *arr, u64 size)
{
  printf("{\n");
  for (u64 i = 0; i < size; ++i)
    printf("  %lu,\n", arr[i]);
  printf("}\n");
}

struct Partition
{
  u64 *arr;
  u64 arr_size;
};

void quicksort(u64 *arr, u64 arr_size)
{
  std::stack<Partition> partitions;
  partitions.push({arr, arr_size});

  while (!partitions.empty())
  {
    const auto partition = partitions.top();
    arr                  = partition.arr;
    arr_size             = partition.arr_size;
    partitions.pop();

    // TODO: Use a different sort for small enough sizes?
    if (arr_size > 1)
    {
      // TODO: Choose a better pivot maybe?
      u64 pivot       = arr[arr_size - 1]; // Choose the last element as pivot
      u64 pivot_index = -1;

      for (u64 j = 0; j < arr_size; ++j)
      {
        if (arr[j] < pivot)
        {
          ++pivot_index;
          std::swap(arr[pivot_index], arr[j]);
        }
      }

      std::swap(arr[pivot_index + 1], arr[arr_size - 1]);

      partitions.push({arr, pivot_index + 1});
      partitions.push({arr + pivot_index + 1, arr_size - pivot_index - 1});
    }
  }
}

int main(int argc, char *argv[])
{
  (void)argc;
  (void)argv;

#define TEST_SIZE 10
  // randomly generate some numbers
  // u64 *arr     = new u64[TEST_SIZE];
  // u64 arr_size = TEST_SIZE;

  // for (size_t i = 0; i < TEST_SIZE; ++i)
  //   arr[i] = rand() % (2L << 30);

  // Use nums.txt
  std::ifstream input(argc > 1 ? argv[1] : "nums.txt");
  std::vector<u64> num_vec;

  for (std::string line; std::getline(input, line);
       num_vec.push_back(std::stoi(line)))
    continue;
  u64 *arr     = &num_vec[0];
  u64 arr_size = num_vec.size();

  printf("Before: ");
  print_arr(arr, arr_size);
  printf("\n");

  quicksort(arr, arr_size);

  printf("After: ");
  print_arr(arr, arr_size);
  printf("\n");

  // delete[] arr;

  return 0;
}