#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>

using namespace std;

struct LinearList {
public:
    double value;
    LinearList *next;

    bool inputElement() {
        bool notCorrect = true;
        bool isSuccess = true;
        while(notCorrect && isSuccess) {
            string input;
            getline(cin, input);
            if(input == "стоп") {
                isSuccess = false;
                next = nullptr;
            } else {
                try {
                    value = stod(input);
                    notCorrect = false;
                } catch (...) {
                    cout << "Вводимый элемент должен быть вещественным числом, повторите ввод" << endl;
                }
            }
        }
        return isSuccess;
    }

    void inputExactElement(double el) {
        value = el;
    }

    vector<double> toVector() {
        vector<double> arr;
        LinearList *currList = this;
        while(currList != nullptr) {
            arr.push_back(currList->value);
            currList = currList->next;
        }
        return arr;
    }

    void sort() {
        vector<double> arr = this->toVector();
        for(int i = 0; i < arr.size(); i++) {
            int minIdx = i;
            for(int j = i; j < arr.size(); j++) {
                double el = arr[j];
                double min = arr[minIdx];
                if(el < min)
                    minIdx = j;
            }
            if(arr[minIdx] != arr[i]) {
                double tmp = arr[minIdx];
                arr[minIdx] = arr[i];
                arr[i] = tmp;
            }
        }
        LinearList *currList = this;
        int i = 0;
        while(currList != nullptr) {
            currList->value = arr[i];
            currList = currList->next;
            i++;
        }
    }
};

LinearList* createLinearList(int i) {
    LinearList *list = new LinearList();
    cout << "Чтобы прекратить ввод элементов списка, введите [стоп]" << endl;
    cout << "Введите " << i << "-й элемент списка" << endl;
    if(list->inputElement()) {
        list->next = createLinearList(i+1);
    } else {
        if(i > 2)
            list = nullptr;
        else {
            cout << "Добавьте хотя бы 2 элемента в список" << endl;
            return createLinearList(i);
        }
    }
    return list;
}

LinearList* createLinearListFromArray(vector<double> &arr) {
    LinearList *list = new LinearList();
    LinearList *currList = list;
    for(int i = 0; i < arr.size(); i++) {
        double el = arr[i];
        currList->inputExactElement(el);
        if(i == arr.size()-1)
            currList->next = nullptr;
        else
            currList->next = new LinearList();
        currList = currList->next;
    }
    return list;
}

string vectorToStr(vector<double> &arr) {
    string str;
    for(double el : arr)
        str += to_string(el) + " ";
    return str;
}

void showResult(vector<double> &arr) {
    if(arr.size() > 0) {
        cout << "Количество элементов, которые содержатся в обоих списках в указанном порядке = " << arr.size() << endl;
        cout << "Совпадающие элементы:" << endl;
        cout << vectorToStr(arr) << endl;
    } else {
        cout << "Повторяющихся по порядку элементов в данных списках нет" << endl;
    }
}

void showList(LinearList *list) {
    LinearList *currList = list;
    while(currList != nullptr) {
        cout << currList->value << " ";
        currList = currList->next;
    }
    cout << endl;
}

vector<double> findMatchingEls(LinearList &list1, LinearList &list2) {
    vector<double> arr1 = list1.toVector();
    vector<double> arr2 = list2.toVector();
    vector<double> matchingEls;
    int size = arr1.size();
    if(arr2.size() < arr1.size())
        size = arr2.size();
    for(int i = 0; i < size; i++) {
        double el1 = arr1[i];
        double el2 = arr2[i];
        if(el1 == el2)
            matchingEls.push_back(el1);
    }
    return matchingEls;
}

void sortLists(LinearList &list1, LinearList &list2) {
    cout << "Отсортированный по неубыванию 1-й список:" << endl;
    list1.sort();
    showList(&list1);
    cout << "Отсортированный по неубыванию 2-й список:" << endl;
    list2.sort();
    showList(&list2);
}

void saveResult(vector<double> &arr) {
    cout << "Хотите сохранить результат в файл?" << endl;
    string choice;
    bool notCorrect = true;
    while(notCorrect) {
        cout << "Введите либо [д], либо [н]" << endl;
        getline(cin, choice);
        if(choice == "д" || choice == "н")
            notCorrect = false;
    }
    if(choice == "д") {
        cout << "Введите имя файла" << endl;
        string fileName;
        getline(cin, fileName);
        ofstream file;
        file.open(fileName+".txt");
        if(file.is_open()) {
            if(arr.size() > 0) {
                file << "Количество элементов, которые содержатся в обоих списках в указанном порядке = " << arr.size() << endl;
                file << "Совпадающие элементы:" << endl;
                file << vectorToStr(arr) << endl;
            } else {
                file << "Повторяющихся по порядку элементов в данных списках нет" << endl;
            }
            file.close();
        } else {
            cout << "Произошла ошибка при попытке сохранить файл" << endl;
        }
    }
}

void trim(std::string &src) {
    src.erase(std::find_if_not(src.rbegin(), src.rend(), ::isspace).base(), src.end());
    src.erase(src.begin(), std::find_if_not(src.begin(), src.end(), ::isspace));
}

vector<string> split(string str, string delimiter) {
    vector<string> result;
    int pos = 0;
    while (pos != -1) {
        pos = str.find(delimiter);
        result.push_back(str.substr(0, pos));
        str.erase(0, pos + delimiter.length());
    }
    return result;
}

bool isFileCorrect(ifstream &file, int lines) {
    file.seekg(0);
    for(int i = 0; i < lines; i++) {
        string line;
        getline(file, line);
        vector<string> list = split(line, " ");
        if(list.size() < 2)
            return false;
        try {
            for (string el : list)
                stod(el);
        } catch (...) {
            return false;
        }
    }
    return true;
}

vector<LinearList> inputListsFromFile() {
    const int LINES = 2;
    vector<LinearList> lists(LINES);
    bool notCorrect = true;
    while(notCorrect) {
        cout << "Введите путь к файлу" << endl;
        string filePath;
        getline(cin, filePath);
        ifstream file(filePath);
        if(file.good()) {
            if(isFileCorrect(file, LINES)) {
                file.seekg(0);
                for(int i = 0; i < LINES; i++) {
                    string line;
                    getline(file, line);
                    trim(line);
                    vector<string> list = split(line, " ");
                    vector<double> arr;
                    for(string el : list)
                        arr.push_back(stod(el));
                    lists[i] = *createLinearListFromArray(arr);
                }
                notCorrect = false;
            } else {
                cout << "Убедитесь, что в файле содержатся 2 списка чисел (каждый на своей строке), состоящих только из вещественных чисел, разделенных одиночным пробелом и повторите ввод" << endl;
            }
            file.close();
        } else {
            cout << "Произошла ошибка при попытке открыть файл. Убедитесь, что файл существует и повторите ввод" << endl;
            notCorrect = true;
        }
    }
    return lists;
}

vector<LinearList> inputListsFromConsole() {
    cout << "Введите элементы первого списка" << endl;
    LinearList list1 = *createLinearList(1);
    cout << "Введите элементы второго списка" << endl;
    LinearList list2 = *createLinearList(1);
    return vector<LinearList>{list1, list2};
}

vector<LinearList> inputLists() {
    cout << "Введите [f], если хотите ввести данные из файла или [c], если хотите ввести данные из консоли" << endl;
    string choice;
    bool notCorrect = true;
    while(notCorrect) {
        getline(cin, choice);
        if(choice == "f" || choice == "c")
            notCorrect = false;
        else
            cout << "Вы должны ввести либо [f], либо [c]" << endl;
    }

    if(choice == "c")
        return inputListsFromConsole();
    return inputListsFromFile();
}

int main() {
    cout << "Данная программа проверяет содержатся ли элементы первого линейного односвязного списка во втором по порядку" << endl;
    vector<LinearList> lists = inputLists();
    sortLists(lists[0], lists[1]);
    vector<double> matching = findMatchingEls(lists[0], lists[1]);
    showResult(matching);
    saveResult(matching);
    return 0;
}