Num4

#include <iostream>
#include <map>
#include <set>
#include <map>
#include <exception>
#include <regex>
#include <stack>
#include <queue>
#include <unordered_set>
#include <list>

class ParseExceptions : public std::exception {
private:
    std::string _error;
public:
    ParseExceptions() = default;

    explicit ParseExceptions(std::string error) : _error(std::move(error)) {}

    ~ParseExceptions() override = default;

    [[nodiscard]] const char *what() const noexcept override {
        return _error.c_str();
    }
};

class Graph {

public:

    Graph() = default;

    Graph(std::string typeId) {
        if (typeId == "d")
            _directedGraph = true;
        else if (typeId == "u")
            _directedGraph = false;
        else
            throw ParseExceptions("ERROR: Incorrect type of graph");

    }

    void graphCreation(const std::string firstVertexId, const std::string secondVertexId) {
//        _graphData.insert(firstVertexId,secondVertexId);
        _graphData = new std::map<std::string, std::set<std::string>>;
        auto finded = _graphData->find(firstVertexId);

        if (finded == _graphData->end()) {
            _graphData->insert(std::make_pair(firstVertexId, std::set({secondVertexId})));
        } else {
            std::set<std::string> *neighbours = &_graphData->at(firstVertexId);
            neighbours->insert(secondVertexId);
            /*       if(!_directedGraph) {
                       auto neighbour = _graphData.find(secondVertexId);
                       if(neighbour == _graphData.end()) {
                           _graphData.insert(std::make_pair(secondVertexId, std::set({firstVertexId})));
                       }
                       else {
                           std::set<std::string>* neighbours = &_graphData.at(secondVertexId);
                           neighbours->insert(firstVertexId);
                       }
                   }*/
        }
        if (!_directedGraph) {
            auto neighbour = _graphData->find(secondVertexId);
            if (neighbour == _graphData->end()) {
                _graphData->insert(std::make_pair(secondVertexId, std::set({firstVertexId})));
            } else {
                std::set<std::string> *neighbours = &_graphData->at(secondVertexId);
                neighbours->insert(firstVertexId);
            }
        }
//        dispEdges();
        std::cout << "\n*********************************\n";
    }

    /*
u 1 d
1 3
1 2
1 5
2 3
2 4
5 4
     */

    void startSearch(std::string firstVertex, std::string searchType) {
        if (searchType == "d")
            DFS(firstVertex);
        if (searchType == "b")
            BFS(firstVertex);
    }

    ~Graph() {
        /*for (auto pair : *_graphData) {
            pair.first.
            for (auto neighb : set)

            std::cout << "\n";
        }*/
        delete _graphData;
        _graphData = nullptr;
    }

private:
//    enum class TYPE {DIRECTED, UNDIRECTED};
    Graph(Graph &copied) = delete;

    Graph(Graph &&moved) = delete;

    Graph operator=(Graph &copied) = delete;

    Graph operator=(Graph &&moved) = delete;

    std::set<std::string> _usedVertices;

    std::map<std::string, std::set<std::string>> *_graphData = nullptr; // {vertex, {{vertex,visited}...}}
    bool _directedGraph;
    //    TYPE _graphType = TYPE::UNDIRECTED;

    void dispEdges() {
        std::cout << "GRAPH " << (_directedGraph ? "DIRECTED\n" : "UNDIRECTED\n");
        for (auto[vtx, set] : *_graphData) {
            std::cout << "VTX: <" << vtx << "> ~: ";
            for (auto neighb : set)
                std::cout << neighb << "  ";
            std::cout << "\n";
        }
    }

    /*void dispEdges () {
        for(auto vertex = _graphData.begin(); vertex != _graphData.end(); vertex++) {
            std::cout << "VTX: <" << vertex->first << "> ~: "; // name
            for (auto neighb = vertex->second.begin(); neighb != vertex->second.end(); neighb++)
                std::cout << *neighb << "  ";
            std::cout << "\n";
        }
    }*/


    void BFS(std::string startVertex) {
//        dispEdges();

        std::queue<std::string> queue;
        std::unordered_set<std::string> queued;
        std::set<std::string> visited;
        queue.push(startVertex);
        std::string &curVertex = queue.front(); //just for Initialization TODO: Check FRONT or BACK
        while (!queue.empty()) {
            curVertex = queue.front();
            queue.pop();
            visited.insert(curVertex);
            const auto &neighbours = _graphData->find(startVertex)->second;
            std::set<std::string>::const_reverse_iterator revIt;
            /*auto* ss = new std::string("ddd") ;
            std::string **sss = &ss ;*/
            for (revIt = neighbours.rbegin(); revIt != neighbours.rend(); revIt++) {
                if (queued.find(*revIt) == queued.end() && visited.find(*revIt) == visited.end()) {        // TODO Check
                    queue.push(*revIt);
                    visited.insert(*revIt); //TODO Check!
                    queued.insert(*revIt);
                }
            }
        }
        std::cout << "Result:\n"; //TODO : DEbug -> delete
        for (const auto &vertex : visited) {
            std::cout << vertex << std::endl;
        }

    }

    void DFS(std::string startVertex) {  // TODO: Try to replace values to references
//        dispEdges();

        std::stack<std::string> stack;
        std::unordered_set<std::string> queued;
        std::list<std::string> visited ;
        stack.push(startVertex);
        std::string curVertex = stack.top(); //just for Initialization
        while (!stack.empty()) {
            curVertex = stack.top();
            stack.pop();
//            if(std::find(visited.begin(), visited.end(), curVertex) != visited.end()) {
//                continue;
//            }

            visited.push_back(curVertex);
            auto neighbours = _graphData->find(curVertex)->second;
            std::set<std::string>::reverse_iterator revIt;
            /*auto* ss = new std::string("ddd") ;
            std::string **sss = &ss ;*/
            /*if(curVertex == "4")
                std::cout << "" ;*/
            if (!neighbours.empty()) {
                for (revIt = neighbours.rbegin(); revIt != neighbours.rend(); revIt++) {
                    std::string neighb = *revIt;
                    if (queued.find(neighb) == queued.end() && std::find(visited.begin(), visited.end(), neighb) == visited.end()) {        // TODO Check
                        stack.push(neighb);
                        queued.insert(neighb);
                    }
                }
            }
        }
//        std::cout << "Result:\n"; //TODO : DEbug -> delete
//        for (const auto &vertex : visited) {
//            std::cout << vertex << std::endl;
//        }

    }
};

class GraphParser {
private:
    std::regex R_StartInfo = std::regex(R"(^[ud]\s\d+\s[db])");
    std::regex R_Edge = std::regex(R"(\S+\s\S+)");

    Graph *_graph = nullptr;
public:

    GraphParser() = default;

    ~GraphParser() {
        delete _graph;
        _graph = nullptr;
    }


    void runParse() {
//        int numOfSetSize = 0; // TO check if setting again many times
        bool setConfig = false;
        std::string inputStr;
        std::string startVertexId, searchType, graphType;
        while (std::getline(std::cin, inputStr)) {
            if (!inputStr.empty()) {
                try {
                    if (std::regex_match(inputStr, R_StartInfo)) {
                        if (!setConfig) {
                            std::smatch match;

                            std::regex_search(inputStr, match, std::regex(R"([du])"));
                            graphType = match.str();
                            std::regex_search(inputStr, match, std::regex(R"(\d+)"));
                            startVertexId = match.str();
                            std::regex_search(inputStr, match, std::regex(R"([db])"));
                            searchType = match.str();
                            _graph = new Graph(graphType);
                            setConfig = true;
                        } else
                            throw ParseExceptions("error"); // Setting more then one time
                    } else if (setConfig) {
                        if (std::regex_match(inputStr, R_Edge)) {
                            std::smatch matchEdges;
                            std::string vertex1, vertex2;
                            auto reg = std::regex(R"(\S+)");
                            std::string::const_iterator ib = inputStr.begin(), ie = inputStr.end();

                            for (int ind = -1; std::regex_search(ib, ie, matchEdges, reg); ib = matchEdges[0].second) {
//                                std::cout << R"(->f )" << matchEdges[0] << std::endl;
                                ind++;
                                if (ind == 0)
                                    vertex1 = matchEdges[0];
                                if (ind == 1)
                                    vertex2 = matchEdges[0];
                                if (ind > 1)
                                    throw ParseExceptions("ERROR: More then two words");
                            }

//                            std::regex_iterator<std::string::iterator> rit (inputStr.begin(), inputStr.end(), REG);
//                            std::regex_iterator<std::string::iterator> rend;
//
//                            while(rit != rend) {
//                                std::cout << R"(->f )" << rit->str();
//                            }
//                            std::cout << "\n";
                            // TODO Check if all vertices were read

//                            std::cout << "new Edge: <" << vertex1 << "> -> <" << vertex2 << ">\n";

                            _graph->graphCreation(vertex1, vertex2);
                        } else
                            throw ParseExceptions("error"); // Unknown command
                    } else
                        throw ParseExceptions("error"); // Setting more then one time
                }
                catch (ParseExceptions &exc) {
                    std::cout << exc.what() << std::endl;
                }
                catch (std::exception &exc) {
                    std::cout << "ERROR: " << exc.what() << std::endl;
                }
                catch (...) {
                    std::cout << "ERROR: " << "Unexpected error!\n";
                }
            }
        }
        /*
         * Next we start search
         * */
        try {
            _graph->startSearch(startVertexId, searchType);
        }
        catch (ParseExceptions &exc) {
            std::cout << exc.what() << std::endl;
        }
        catch (std::exception &exc) {
            std::cout << "ERROR in search: " << exc.what() << std::endl;
        }
        catch (...) {
            std::cout << "ERROR in search: " << "Unexpected error in search!\n";
        }
    }
};


int main() {
    GraphParser parser;
    parser.runParse();
    return 0;
}