#pragma once
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
using std::ofstream;
using std::ifstream;
using std::ios;
//predefine crossroad class
class CrossRoad;
//neighbor class - has a reference to a crossroad, as well as a cost to reach it
class Neighbor {
public:
    CrossRoad *key1;
    int cost;
    Neighbor(CrossRoad *_key1 = nullptr, int _cost = 0) :key1(_key1), cost(_cost) {}
};
//same as the neighbor class, but contains both crossroads
class CameFromTrio :public Neighbor {
public:
    CrossRoad *key2;
    CameFromTrio(CrossRoad *_key1 = nullptr, CrossRoad *_key2 = nullptr, int _cost = 0) :Neighbor(_key1, _cost), key2(_key2) {}
};
//generic class for a list with a typename class
template <typename T>
class List
{
protected:
    //array of items
    T *items;
    //size of array
    int size;
public:
    //constructor
    List() :items(nullptr) {}
    //add item function
    void AddItem(T *_item)
    {
        //creates temporary array, 1 element more than the current item array
        T *temp = new T[size + 1];
        //adds current items to temp array
        for (int i = 0; i < size; i++)
        {
            temp[i] = items[i];
        }
        //last item is the new item
        temp[size] = *_item;
        //increase size
        size++;
        //set items array
        items = temp;
    }
    //remove item from item array
    void RemoveItem(T *_item)
    {
        //check if item is in items array
        if (Contains(_item))
        {
            //index of item
            int index = 0;
            //get index of item
            for (int i = 0; i < size; i++)
            {
                if (GetItem(i) == _item)
                {
                    index = i;
                    break;
                }
            }
            //temp array
            T *_temp = new T[size - 1];
            //copy items from items array to temp array, excluding the item
            for (int i = 0; i < index; i++)
            {
                _temp[i] = items[i];
            }
            for (int i = index; i < size - 1; i++)
            {
                _temp[i] = items[i + 1];
            }
            //set items array
            items = _temp;
            //decrease items size
            size--;
        }
    }
    //get item from items array by index
    T *GetItem(int i)
    {
        return &items[i];
    }
    //return size of items array
    int Count()
    {
        return size;
    }
    //check if item is contained in items array
    bool Contains(T *item)
    {
        for (int i = 0; i < Count(); i++)
        {
            T *_t = GetItem(i);
            if (_t == item)
            {
                return true;
            }
        }
        return false;
    }
    //reverse the order of the list
    void Reverse()
    {
        //make temporary array of the same size
        T *_temp = new T[size];
        for (int i = size - 1; i >= 0; i--)
        {//add the elements backwards
            _temp[size - i - 1] = items[i];
        }
        //set items array
        items = _temp;

    }
};
//crossroad class
class CrossRoad
{
protected:
    //name of crossroad
    string name;
    //neighbors of crossroad, and distance to reach them
    List<Neighbor> neighbors;
public:
    //constructor
    CrossRoad(string _name = "") :name(_name) {}
    string Name()
    {
        return name;
    }
    //check if neighbor is contained.
    //can't use default list function for Contained, since we're using a list of CrossRoadNeighbor, not CrossRoad.
    //i wanted to store the distance in something, so i had to do it like this
    bool ContainsNeighbor(CrossRoad *_neighbor)
    {
        for (int i = 0; i < neighbors.Count(); i++)
        {
            if (neighbors.GetItem(i)->key1 == _neighbor)
            {
                return true;
            }
        }
        return false;
    }
    //add new neighbor + distance
    void AddNeighbor(CrossRoad *_neighbor, int _distance, bool DoubleSided)
    {
        if (!ContainsNeighbor(_neighbor)) {
            Neighbor temp;//(_neighbor, _distance);
            temp.key1 = _neighbor;
            temp.cost = _distance;
            neighbors.AddItem(&temp);
            //function calls itself, won't end in infinite loop since we check if the crossroad is contained in neighbors
            if (DoubleSided) {
                _neighbor->AddNeighbor(this, _distance,false);
            }
        }
    }
    //return neighbors
    List<Neighbor> *Neighbors()
    {
        return &neighbors;
    }
};
//used for the CameFrom list
//key1 is the key
//key2 is the parent of key1
//key3 is the cost so far


//list of trio
//has multiple functions to get values based on keys
class TrioList :public List<CameFromTrio>
{
public:
    CrossRoad *GetKey(CrossRoad *item)
    {
        for (int i = 0; i < size; i++)
        {
            if (items[i].key1->Name() == item->Name())
            {
                return items[i].key2;
            }
        }
        return nullptr;
    }
    CrossRoad *GetKeyValue(CrossRoad *item)
    {
        for (int i = 0; i < size; i++)
        {
            if (items[i].key2->Name() == item->Name())
            {
                return items[i].key1;
            }
        }
        return nullptr;
    }
    int GetCostSoFar(CrossRoad *item)
    {
        for (int i = 0; i < size; i++)
        {
            if (items[i].key1 == item)
            {
                return items[i].cost;
            }
        }
        return 0;
    }
    bool Contains(CrossRoad *item)
    {
        for (int i = 0; i < size; i++)
        {
            if (items[i].key1 == item)
                return true;
        }
        return false;
    }
};
//get path
List<CrossRoad> * Path(CrossRoad *_start, CrossRoad *_end) {
    List<CrossRoad> storeIn;
    //start at the starting node
    CrossRoad *cur = _start;
    //list of trios
    TrioList CameFrom;
    //add the starting node, it comes from itself, 0 cost
    CameFrom.AddItem(new CameFromTrio(_start, _start, 0));
    //frontier, contains all the nodes we're about to check
    List<CrossRoad> frontier;
    //add starting node
    frontier.AddItem(cur);
    //do cycle until frontier is empty
    while (frontier.Count() > 0)
    {
        //remove cur item
        //if we had coordinates, we could use a priority que to remove the item closest to the goal, would make the process a lot faster
        cur = frontier.GetItem(0);
        frontier.RemoveItem(cur);
        //if we've reached the end, reconstruct the path
        if (cur->Name() == _end->Name())
        {
            //add end
            storeIn.AddItem(cur);
            //get number of connections;
            //we're not necessarily going to check everyone, but we need a limit
            int cost = CameFrom.Count();
            for (int i = 0; i < cost; i++)
            {
                //next is the element that cur came from
                CrossRoad *next = CameFrom.GetKey(cur);
                //add next to the path
                storeIn.AddItem(next);
                //if we've reached the start, reverse the path
                //now start is at the begining of the path, end is at the end
                if (next->Name() == _start->Name())
                {
                    storeIn.Reverse();
                    return &storeIn;
                }
                cur = next;
            }
        }
        //get neighbors
        List<Neighbor> *neighbors = cur->Neighbors();
        for (int i = 0; i < neighbors->Count(); i++)
        {
            Neighbor *_next = neighbors->GetItem(i);
            CrossRoad *next = _next->key1;
            int newCost = CameFrom.GetCostSoFar(cur) + _next->cost;
            if (!CameFrom.Contains(next) || CameFrom.GetCostSoFar(cur) < newCost)
            {
                //add next to frontier
                frontier.AddItem(next);
                //get distance to next crossroad
                //add next to camefrom
                CameFrom.AddItem(new CameFromTrio(next, cur, newCost));
            }
        }
    }
    return &storeIn;
}

bool PathExists(CrossRoad *_start, CrossRoad *_end)
{
    List<CrossRoad> _path = *Path(_start, _end);
    return _path.Count() > 1;
}
/*
void testTextFileOutput() {
    ofstream text_file("test.txt");

    text_file << "This is my text file\n";
    text_file << 10 << ' ' << 5.6;

    text_file.close();
}

void testBinaryFileOutput() {
    ofstream binary_file("test.bin", ios::binary);

    for (int i = 0; i <= 20; ++i) {
        binary_file.put((char)i);
    }

    int numbers[] = { 1.2, 3.4, 5.6, 7.8 };
    binary_file.write((const char*)numbers, sizeof(numbers));

    binary_file.close();
}

void testTextFileInput() {
    ifstream text_file("test.txt");

    char line[100];
    text_file.getline(line, 100);

    int first_number;
    int second_number;
    text_file >> first_number >> second_number;

    cout << "line = " << line << '\n';
    cout << "first_number = " << first_number << '\n';
    cout << "second_number = " << second_number << '\n';

    text_file.close();
}

void testBinaryFileInput() {
    ifstream binary_file("test.bin", ios::binary);

    for (int i = 0; i <= 20; ++i) {
        cout << binary_file.get() << '\n';
    }

    int numbers[4];
    binary_file.read((char*)numbers, 4 * sizeof(int));

    for (int i = 0; i < 4; ++i) {
        cout << numbers[i] << '\n';
    }

    binary_file.seekg(-2 * sizeof(int), ios::cur);
    cout << binary_file.tellg() << '\n';

    int number;
    binary_file.read((char*)&number, sizeof(int));
    cout << "number = " << number << '\n';

    binary_file.close();
}
*/