/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/*
 * File:   Listenbearbeitung.cpp
 * Author: Thorsten
 *
 * Created on 16. März 2018, 12:19
 */

#include <cstdlib>
#include <algorithm>
#include <list>
#include <iostream>
#include <limits>
#include <vector>
#include <numeric>

using namespace std;

/*
 *
 */

int validInputInt() {
    int eingabe;

    cin >> eingabe;
    while (cin.fail()) //Solange die Eingabe nicht eindeutig von Typ int ist (Sonderzeichen, etc.)
    {
        cin.clear(); //Fehlerstatus wird auf goodbit gesetzt, um weiterhin mit der Eingabe zu arbeiten
        cin.ignore(numeric_limits<streamsize>::max(), '\n'); //Eingabe wird bis zum newline character gelöscht
        cout << "Fehlerhafte Eingabe. Bitte eine gueltige Zahl eingeben: ";
        cin >> eingabe;
    }
    cin.ignore(numeric_limits<streamsize>::max(), '\n');
    return eingabe;
}

list<int> gemeinsameElemente (list<int>& liste_1, list<int>& liste_2)
{
    list<int> liste_output;

    liste_1.sort();
    liste_2.sort();

    set_intersection(liste_1.begin(), liste_1.end(), liste_2.begin(), liste_2.end(), back_inserter(liste_output));

    liste_output.unique();

    return liste_output;
}

bool keineGemeinsamenWerte (list<int>& liste_1, list<int>& liste_2)
{
    list<int> liste_output = gemeinsameElemente (liste_1, liste_2);

    return liste_output.size() == 0;
}

bool hatGleicheAnzahl (list<int>& liste_1, list<int>& liste_2)
{
    list<int> liste_1_unique = liste_1;
    liste_1_unique.unique();
    list<int> liste_2_unique = liste_2;
    liste_2_unique.unique();
    //Annahme: Es sei wahr. Widerlegung folgt ggf.
    bool hatGleicheAnzahl = true;

    list<int>::iterator it;
    for (it=liste_1_unique.begin(); it != liste_1_unique.end(); ++it)
    {
        //cout << "*it_1: " << *it << endl;
        //If count (die Zahl bei liste 1) != count (bei liste 2)
        if( count(liste_1.begin(), liste_1.end(), *it) != count(liste_2.begin(), liste_2.end(), *it) )
        {
            hatGleicheAnzahl = false;
        }
    }
    for (it=liste_2_unique.begin(); it != liste_2_unique.end(); ++it)
    {
        //cout << "*it_2: " << *it << endl;
        //If count (die Zahl bei liste 2) != count (bei liste 1)
        if( count(liste_2.begin(), liste_2.end(), *it) != count(liste_1.begin(), liste_1.end(), *it) )
        {
            hatGleicheAnzahl = false;
        }
    }

    return hatGleicheAnzahl;
}

void fillWithUniques (list<int>& liste_1, list<int> liste_2)
{
    liste_2.unique();

    list<int>::iterator it;
    for (it=liste_2.begin(); it != liste_2.end(); ++it)
    {
        if (*find(liste_1.begin(), liste_1.end(), *it) != *it)
        {
            cout << "Zahl " << *it << " in Liste 1 nicht gefunden." << endl;
            liste_1.push_back(*it);
        }
    }
    liste_1.sort();
}

int n_kleinstes_Element (list<int>& liste)
{
    //In Vektor konvertieren wegen Random Access Iterator
    vector<int> zahlen{liste.begin(), liste.end()};
    cout << "Bitte n eingeben, um das n-kleinste Element zu erhalten: " << endl;
    int n = validInputInt()-1;

    while (n >= zahlen.size())
    {
        cout << "n ist out of bounds. Bitte ein n zwischen 1 und " << zahlen.size() << " eingeben: " << endl;
        n = validInputInt()-1;
    }

    nth_element(zahlen.begin(), zahlen.begin()+n, zahlen.end());

    return zahlen[n];
}

int rekursiv_vektor_fuellen (vector<int>& zahlen, int n)
{
    if (n <= 0)
    {
        return(n);
    }

    zahlen[n] = accumulate(zahlen.begin(), zahlen.begin()+n+1, 0);

    return rekursiv_vektor_fuellen(zahlen, n-1);
}

list<int> n_tes_Element_Summe (list<int>& liste)
{
    //In Vektor konvertieren wegen Random Access Iterator
    vector<int> zahlen{liste.begin(), liste.end()};
    cout << "Bitte n eingeben, um die Summe der ersten n Elemente zu erhalten: " << endl;
    int n = validInputInt()-1;

    while (n >= zahlen.size())
    {
        cout << "n ist out of bounds. Bitte ein n zwischen 1 und " << zahlen.size() << " eingeben: " << endl;
        n = validInputInt()-1;
    }

    rekursiv_vektor_fuellen(zahlen, n);

    list<int> output;
    copy(zahlen.begin(), zahlen.begin()+n+1, back_inserter(output));

    return output;
}

void outputList (list<int>& liste)
{
    //Liste ausgeben
    list<int>::iterator it;
    for (it=liste.begin(); it != liste.end(); ++it)
    {
        cout << *it << '\t';
    }
    cout << endl << endl;
}

int main() {

    list<int> liste_1 = {2, 5, 5, 3, 8, 8, 10};
    list<int> liste_2 = {5, 5, 10, 8, 8, 3, 2, 12};

    list<int> liste_3 = {10, 5, 7, 2, 8, 4};
    list<int> liste_output = gemeinsameElemente (liste_1, liste_2);

    cout << "Gemeinsame Elemente von Liste 1 und Liste 2: " << endl << endl;
    outputList(liste_output);

    cout << boolalpha << "Liste 1 & Liste 2 haben keine gemeinsamen Werte -> " << keineGemeinsamenWerte (liste_1, liste_2) << endl << endl;

    cout << boolalpha << "Gleiche Anzahl aller Werte der ersten Liste in der zweiten Liste und umgekehrt? " << hatGleicheAnzahl(liste_1, liste_2) << endl << endl;

    fillWithUniques (liste_1, liste_2);
    cout << "Neue Liste 1: " << endl << endl;
    outputList(liste_1);

    cout << "n-kleinstes Element: " << n_kleinstes_Element(liste_3) << endl;

    list<int> liste_summe = n_tes_Element_Summe (liste_3);

    outputList(liste_summe);

    return 0;
}