// Author: mikedebo@gmail.com (Michael DiBernardo)
// Copyright Michael DiBernardo 2006
//
// Exercise 3 from Column 1 of Bentley's Programming Pearls: How does bitmap
// sort compare to the system sort? The actual comparison was done with the
// 'time' utility.
#include <stdlib.h>
#include <algorithm>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#include "BitVector.h"
using namespace std; // No one is going to include this file, so this is OK.

void BitVectorSort(int max_value, vector<int>* numbers_to_sort) {
  BitVector sorter(max_value);

  for (vector<int>::iterator next_int = numbers_to_sort->begin();
       next_int != numbers_to_sort->end();
       ++next_int) {
    sorter.Set(*next_int);
  }

  int destIndex = 0;
  for (int bitIndex = 0; bitIndex < sorter.Size(); ++bitIndex) {
    if (sorter.Get(bitIndex)) {
      (*numbers_to_sort)[destIndex] = bitIndex;
      ++destIndex;
    }
  }
}

void SystemSort(vector<int>* numbers_to_sort) {
  sort(numbers_to_sort->begin(), numbers_to_sort->end());
}

void ReadNumbersFromFile(const char* filename, vector<int>* return_numbers) { 
  ifstream number_stream(filename);
  if (!number_stream) {
    cout << "Could not open file " << filename << endl;
    exit(-1);
  }
  while (!number_stream.eof()) {
    int next_number_from_file;
    number_stream >> next_number_from_file;
    return_numbers->push_back(next_number_from_file);
  }
  number_stream.close();
}

int main(int argc, char** argv) {
  // Validate arguments.
  if (argc != 4) {
    cout << "Usage: sort_compare <filename> <mode> <max_value>, where mode = [s]ystem or [b]itmap"
         << endl;
    exit(-1);
  }

  // Read numbers from specified file.
  const char* filename = argv[1];
  vector<int> numbers_to_sort;
  ReadNumbersFromFile(filename, &numbers_to_sort);

  // Figure out what the largest int we're handling is.
  // I use atoi here even though it's bad style to mix C and C++. I find sstream 
  // is so damned clumsy...
  const int kMaxValue = atoi(argv[3]);

  // Determine the sort mode and execute the sort.
  const string sort_mode(argv[2]);
  if (sort_mode == "s") {
    SystemSort(&numbers_to_sort);
  } else if (sort_mode == "b") {
    BitVectorSort(kMaxValue, &numbers_to_sort);
  } else {
    cout << "Invalid sort mode specified: Please select [s]ystem or [b]itmap."
         << endl;
    exit(-1);
  }

  // Print the sorted list.
  for (vector<int>::iterator next_sorted_number = numbers_to_sort.begin();
       next_sorted_number != numbers_to_sort.end();
       ++next_sorted_number) {
    cout << *next_sorted_number << endl;
  }
}