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

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

using namespace std;

// füge alle Elemente der sortierten Liste "second"
// an den richtigen Stellen in die sortierte Liste "first" ein
template <typename T>
void merge(forward_list<T> &first, forward_list<T> &second)
{
  // prev_elem zeigt auf das Element von first *vor* der Stelle,
  // an der wir einfügen
  // am Anfang zeigt prev_elem auf das "nichts" vor dem ersten Element
  // (falls wir vor dem ersten Element einfügen)
  auto prev_elem = first.before_begin();
  // next_elem zeigt auf das Element von first *nach* der Stelle,
  // an der wir einfügen
  // am Anfang zeigt next_elem auf das erste Element 
  auto next_elem = first.begin();

  // wiederhole, bis alle Elemente aus second entnommen sind
  while (!second.empty()) {
    // merk dir den Wert des vordersten Elementes von second
    T val = second.front();
    // .. und entferne das vorderste Element aus second
    second.pop_front();

    // verschiebe prev_elem und next_elem nach hinten, 
    // bis entweder prev_elem auf das letzte Element von first zeigt
    //   (es daher kein next_elem mehr gibt)
    //   und val ganz hinten an first angehängt gehört
    // oder bis der Wert des Elementes next_elem
    //   größer als der einzufügende Wert ist
    //   und val zwischen prev_elem und next_elem eingefügt gehört
    while ((next_elem != first.end()) && (*next_elem <= val)) {
      ++prev_elem;
      ++next_elem;
    }

    // füge den Wert aus second hinter prev_elem in first ein
    // und lass prev_elem dann auf das neu eingefügte Element zeigen
    prev_elem = first.insert_after(prev_elem, val);
  }
}

// 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);
    merge(result, 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);
}