// Übung zu Templates, STL vector & forward_list, File-I/O, Exceptions:
// File per Merge-Sort sortieren, mit forward_list und vordefiniertem merge
//
// Aufruf: merge-sort-list
//
// Klaus Kusche, 2020

#include <iostream>
#include <fstream>
#include <vector>
#include <forward_list>
#include <string>
#include <cstdlib>

using namespace std;

// Speichert in result eine sortierte Liste der Elementen von input
// zwischen den Positionen from und to (jeweils einschließlich)
template <typename T>
void merge_sort(forward_list<T> &result,
                const vector<T> &input, int from, int to)
{
  if (from == to) {
    // der zu sortierende Bereich umfasst nur 1 Element:
    // dieses Element ins Ergebnis speichern
    result.push_front(input[from]);
  } else if (from < to) {
    // zwei zu sortierende Teile
    forward_list<T> second;
    int mid = (from + to) / 2;
    merge_sort(result, input, from, mid);
    merge_sort(second, input, mid + 1, to);
    // zweiten Teil sortiert in den resten Teil einfügen
    result.merge(second);
  }
}

// kopiere die Datei in_name zeilenweise sortiert in die Datei out_name
void copy_sorted(string in_name, string out_name)
{
  ifstream in_file(in_name);
  if (!in_file) {
    // C++ string-Objekte kann man mit + aneinanderhängen,
    // funktioniert auch mit C String-Konstanten
    throw "Opening " + in_name + " for reading failed";
  }
  ofstream out_file(out_name);
  if (!out_file) {
    throw "Opening " + out_name + " for writing failed";
  }
  string line;
  // Der STL-Container vector ist wie ein "selbstwachsendes" Array
  // wir wissen die Anzahl der Elemente ja vorher nicht
  // Jedes Element ist eine Zeile unseres Inputs, also Elementtyp string
  vector<string> input;
  // getline liest genau eine Zeile
  // (>> kann ja nur wortweise lesen, nicht zeilenweise)
  while (getline(in_file, line)) {
    // push_back: Hänge einen Wert hinten an den Vektor an
    input.push_back(line);
  }
  // für das Ergebnis verwenden wir eine einfach verkettete Liste,
  // am Anfang leer
  forward_list<string> result;
  merge_sort(result, input, 0, input.size() - 1);
  // C++-11 Container-Schleife:
  // elem wird der Reihe nach auf die einzelnen Elemente von result gesetzt
  for (const string &elem : result) {
    out_file << elem << endl;
  }
}

int main(int argc, const char *argv[])
{
  if (argc != 3) {
    cerr << "Usage: " << argv[0] << " infilename outfilename" << endl;
    exit(EXIT_FAILURE);
  }

  try {
    copy_sorted(argv[1], argv[2]);
  }
  catch (const string &err) {
    cerr << err << endl;
    exit(EXIT_FAILURE);
  }
  
  exit(EXIT_SUCCESS);
}