Header

#pragma once
#include <iostream>
#include <fstream>
#include <string>
#include <cassert>
#include <cmath>
#include <array>
using namespace std;

template <typename T>
class List {
public:
    struct Node {
        T value;
        Node *next;
        Node *previous;
    };
    Node *head;
    int size = 0;
    List() : head(NULL) {}
    List(const List &b) {
        Node *nodeb; Node *nodea;
        nodeb = b.head;
        nodea = new Node;
        nodea->previous = NULL;
        if (nodeb != NULL)
        {
            head = nodea;
            nodea->value = nodeb->value;
            size++;
            nodeb = nodeb->next;
        }
        while (nodeb != NULL)
        {
            size++;
            Node *node = new Node;
            nodea->next = node;
            nodea->next->previous = nodea;
            nodea = nodea->next;
            nodea->value = nodeb->value;
            nodeb = nodeb->next;
        }
    }
    ~List()
    {
        clear();
    }
    unsigned int getSize() const
    {
        return this->size;
    }
    bool deleteElement(int n);
    bool incert(T &x, int n);
    void print();
    void print2();
    void clear();
    void push_front(T &x);
    T& operator[] (const unsigned int n);
    void operator=(const List &b);
};
template <typename T>
void List<T>::operator=(const List &b)
{
    clear();
    Node *nodeb; Node *nodea;
    nodeb = b.head;
    nodea = new Node;
    nodea->previous = NULL;
    if (nodeb != NULL)
    {
        head = nodea;
        nodea->value = nodeb->value;
        size++;
        nodeb = nodeb->next;
    }
    while (nodeb != NULL)
    {
        size++;
        Node *node = new Node;
        nodea->next = node;
        nodea->next->previous = nodea;
        nodea = nodea->next;
        nodea->value = nodeb->value;
        nodeb = nodeb->next;
    }
}
template <typename T>
void List<T>::clear()
{
    Node *a;
    size = 0;
    while (head != NULL)
    {
        a = head->next;
        delete[] head;
        head = a;
    }
}
template <typename T>
T& List<T>::operator[] (unsigned int n)
{
    Node *p = head;
    while (p != NULL && n != 0)
    {
        n--;
        p = p->next;
    }
    assert(p != NULL);
    return p->value;
}
template <typename T>
bool List<T>::deleteElement(int n)
{
    Node **p = &head;
    if (n < 0 || *p == NULL)
        return true;
    while (*p != NULL && n != 0)
    {
        p = &((*p)->next);
        n--;
        if (*p == NULL)
            return false;
    }
    Node *b;
    b = (*p)->next;
    delete *p;
    *p = b;
    size--;
    return true;
}
template <typename T>
bool List<T>::incert(T &x, int n)
{
    if (n < 0)
        return false;
    Node **p = &head;
    while (*p != NULL && n != 0)
    {
        p = &((*p)->next);
        n--;
        if (*p == NULL)
            return false;
    }
    Node *node = new Node;
    node->value = x;
    node->next = *p;
    node->previous = (*p)->previous;
    (*p)->previous = node;
    *p = node;
    size++;
    return true;
}
template <typename T>
void List<T>::print()
{
    Node *p = head;
    while (p != NULL)
    {
        cout << p->value << endl; // -> == (*p).
        p = p->next;
    }
}
template <typename T>
void List<T>::print2()
{
    Node *p = head;
    while (p->next != NULL)
        p = p->next;
    while (p->previous != NULL)
    {
        cout << p->value << endl;
        p = p->previous;
    }
    cout << p->value << endl;
}
template <typename T>
void List<T>::push_front(T &x)
{
    Node *p = new Node;
    p->value = x;
    p->next = head;
    p->previous = NULL;
    if (head != NULL)
        head->previous = p;
    head = p;
    size++;
}

struct base_points {
    float lat;
    float lon;
    string id;
};
struct base_ways {
    string id;
    List<string> points;
    };
class map {
public:
    List<base_points> points;
    List<base_ways> ways;
};

class data_processing {
public:
    map currentMap;
    List<string> a;
    base_points temporaryPoint;
    base_ways temporaryWay;
    int stage = 0;
    void on_element_start(string &name);
    bool on_element_end(string &name);
    void on_attribute(string &name, string &value);
    void on_character_data(string &text);
};
void data_processing::on_element_start(string &name)
{
    //cout << "begining: " << name << endl;
    a.push_front(name);
}
bool data_processing::on_element_end(string &name) {
    if (a.head->value == name) {
        //cout << "ending: " << name << endl;
        if (name == "way")
        {
            currentMap.ways.push_front(temporaryWay);
        }
        a.deleteElement(0);
        name = "";
        return true;
    }
    else {
        return false;
    }
}
void data_processing::on_attribute(string &name, string &value) {
    //cout << "attribute: " << name << ", value: " << value << endl;
    if (a.head->value == "node")
    {
        if (name == "lat") {
            stage++;
            temporaryPoint.lat = stof(value);
        }
        else if (name == "lon") {
            stage++;
            temporaryPoint.lon = stof(value);
        }
        else if (name == "id") {
            stage++;
            temporaryPoint.id = value;
        }
        if (stage == 3) {
            stage = 0;
            currentMap.points.push_front(temporaryPoint);
        }
    }
    if (a.head->value == "way") {
        if (name == "id")
            temporaryWay.id = value;
    }
    if (a.head->value == "nd") {
        if (name == "ref")
        {
            temporaryWay.points.push_front(value);
        }
    }

    name = ""; value = "";
}
void data_processing::on_character_data(string &text) {
    //cout << "text: " << text << endl;
    text = "";
}

class word_processing {
public:
    string elementName = "", attributeName = "", attributeValue = "", text = "";
    char c = 0;
    data_processing* data;
    string input;
    int line = 1, column = 0;
    word_processing(string in, data_processing* input_data) : input(in), data(input_data) {}
    void start();
    void error();
    void check_char(char c);
};
void word_processing::check_char(char c)
{
    if (c == '\n' || c == '\r')
    {
        line++;
        column = 0;
    }
    else if (c == '\t')
        column += 4;
    else
        column++;
}
void word_processing::start() {
    ifstream in(input);
    if (!in.is_open())
    {
        cout << "FILE HAD NOT BEEN  READ!\n";
        return;
    }
    int state(-1);
    bool closedTag = false;
    while (c != EOF)
    {
        switch (state) {
        case -1:
            c = in.get();
            check_char(c);
            if (c == '<')
                state = 0;
            break;
        case 0://ищем имя элемета
            c = in.get();
            if (c == '?')
            {
                state = -1;
                break;
            }
            check_char(c);
            if (c == ' ' || c == '\n')
            {
                state = 1;
                data->on_element_start(elementName);
            }
            else if (c == '/')
            {
                if (elementName != "")
                {
                    data->on_element_start(elementName);
                    if (!data->on_element_end(elementName))
                    {
                        //cout << "error on line " << line << " column " << column - data->name.length() << "! founded </" << name << ">, expected </" << a.tail->value << ">" << endl;
                        error();
                        return;
                    }
                }
                else
                    closedTag = true;
            }
            else if (c == '>')
            {
                if (elementName != "" && !closedTag) {
                    data->on_element_start(elementName);
                    elementName = "";
                }
                else if (closedTag)
                {
                    closedTag = false;
                    if (!data->on_element_end(elementName)) {
                        error();
                        return;
                    }
                }
                state = 2;
            }
            else if (elementName == "" && !((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || c == ':' || c == '_' || c == '?'))
            {
                cout << "syntax error!" << endl;
                return;
            }
            else if (!((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c <= '9' && c >= '0') || c == '?' || c == ':' || c == '_' || c == '-' || c == '.'))
            {
                cout << "syntax error!" << endl;
                return;
            }
            else
                elementName += c;
            break;
        case 1://имена атрибутов
            c = in.get();
            check_char(c);
            if (c == '/')
            {
                state = 0;
                if (!data->on_element_end(elementName))
                {
                    error();
                    return;
                }
            }
            else if (c == '>')
            {
                elementName = "";
                state = 2;
            }
            else if (c == '"')
                state = 3;
            else if (c == '=' || c == ' ' || c == '\n' || c == '\r')
                attributeName = attributeName;
            else if (attributeName == "" && !((c >= 'a' && c <= 'z') || c == '?' || (c >= 'A' && c <= 'Z') || c == ':' || c == '_'))
            {
                cout << "syntax error!" << endl;
                return;
            }
            else if (!((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c <= '9' && c >= '0') || c == '?' || c == ':' || c == '_' || c == '-' || c == '.'))
            {
                cout << "syntax error!" << endl;
                return;
            }
            else
                attributeName += c;
            break;
        case 2://текст
            c = in.get();
            check_char(c);
            if (c == '<')
            {
                state = 0;
                data->on_character_data(text);
            }
            else
                text += c;
            break;
        case 3://значение атрибутов
            c = in.get();
            check_char(c);
            if (c == '"')
            {
                state = 1;
                data->on_attribute(attributeName, attributeValue);
            }
            else
                attributeValue += c;
            break;
        }
    }
    in.close();
}
void word_processing::error()
{
    cout << "error on line " << line << " column " << column << "!" << endl;
}
double cosDegrees(double x)
{
    return cos(x * 3.141592653 / 180);
}

double sinDegrees(double x)
{
    return sin(x *3.141592653 / 180);
}

double distanceDegrees(const pair<double, double> &latLon1, const pair<double, double> &latLon2)
{
    const unsigned int earthRadius = 6371000;
    return earthRadius * std::acos(sinDegrees(latLon1.first) * sinDegrees(latLon2.first) + cosDegrees(latLon1.first) * cosDegrees(latLon2.first) * cosDegrees(latLon2.second - latLon1.second));
}