#ifndef AdjList_H_
#define AdjList_H_

#include <iostream>
#include <cstdlib>
#include <string>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

class Edge;

struct Vertex
{
public:
    string id;
    vector<Edge> adj;
    Vertex(string name){
        this->id = name;
    }
    ~Vertex(){};
    void addEdge(Vertex* n, int weight){
        Edge edge(n, weight);
        adj.push_back(edge);
    }
};

class Edge{
public:
    Edge(Vertex* next, int weight);
    ~Edge();
private:
    Vertex* next; //next node
    int weight;
};

Edge::Edge(Vertex* next, int weight){
    next = next;
    weight = weight;
}

Edge::~Edge(){}

class Graph{
public:
    Graph();
    ~Graph();
    const int returnEdges();
    void addName(string name);
    void fillGraph(char* filename);

    int editDist(const string &s1, const string & s2);


private:
    vector <Vertex*> vertices;
};

Graph::Graph(){
}

const int Graph::getNumOfNodes(){
    return vertices.size();
}

const int Graph::returnEdges(){
    return edges.size();
}
Graph::~Graph()
{
}

void Graph::addName(string name){
    Vertex newVertex(name);
    vertices.push_back(newVertex);

}

void Graph::fillGraph(char* filename){
    ifstream openFile;
    string input = "";
    vector <string> names;
    openFile.open(filename);

    while (getline(openFile, input)){
        names.push_back(input);
    } openFile.close();


}


//Uses levenshtein's distance to calculate the edit distance
int Graph::editDist(const string &s1, const string & s2) {
    const std::size_t len1 = s1.size(), len2 = s2.size();

    vector<int> col(len2 + 1), prevCol(len2 + 1);

    for (int i = 0; i < prevCol.size(); i++)
        prevCol[i] = i;
    for (int i = 0; i < len1; i++) {
        col[0] = i + 1;
        for (int j = 0; j < len2; j++)
            col[j + 1] = std::min(std::min(prevCol[1 + j] + 1, col[j] + 1),
            prevCol[j] + (s1[i] == s2[j] ? 0 : 1));
        col.swap(prevCol);
    }
    return prevCol[len2];
}


#endif