#include <iostream>
#include <cstdlib>
#include <cmath>
#include <string>

using namespace std;

class Snode                                      //create node class
{
private:
    Snode *next;                                 //next item on list
    Snode *prior;                                //previous item on list
    string code;                                 //initialize variable for airport codes
    int dist;                                    //initialize variable for miles
public:
    
    friend class SLinkedList;                    //give SLinkedList access to Snode
};

class SLinkedList                                //create Linked List class
{
private:
    Snode *head;                                 //pointer to head node
    Snode *priorloc;                             //pointer to prior node
    Snode *nextloc;                              //pointer to next note
public:
    SLinkedList();                               //constructor
    ~SLinkedList();                              //destructor
    bool empty()const;                           //empty test
    void addNode(const string& c, const int& m); //create node function
    void removeNode();                           //remove node function
    void display();                              //display/traverse function
    void recurSearch(const string &);            //search and sum recursively
    void forSearch(const string &);              //search and sum loop
    int recurSum(Snode * thisnode, const string &c);                       //recursive sum function
};

SLinkedList::SLinkedList()                       //constructor, initialize nodes
{
    head = NULL;
    priorloc = NULL;
    nextloc = NULL;
}

SLinkedList::~SLinkedList()                      //destructor,
{
    while(!empty()) removeNode();
}

bool SLinkedList::empty() const                  //empty test
{
    return head == NULL;
}

int main()
{
    SLinkedList list = SLinkedList();
    string airport;
    int miles;
    char again;
    
    list.addNode("LGA", 0);
    
    do{
        cout << "Enter 3 letter code for airport: ";
        cin >> airport;
        cout << "Enter distance in miles: ";
        cin >> miles;
        list.addNode(airport, miles);
        cout << "Do you want to enter another airport (y or Y): ";
        cin >> again;
        cout << endl;
    }while(again == 'y' || again == 'Y');
    
    int choice;
    do{
        cout << "The following are your choices:\n";
        cout << "1. Print the list of all airports.\n";
        cout << "2. Search for airport recursively.\n";
        cout << "3. Search for airport.\n";
        cout << "4. Quit.\n";
        cout << endl;
        cin >> choice;
        while(choice < 1 || choice > 4){
            cout << "Invalid choice.\n";
            cout << "Please choose again.\n";
            cin >> choice;
        }
        string search;
        switch(choice){
            case 1:
                list.display();
                break;
            case 2:
                cout << "Which airport are you looking for: ";
                cin >> search;
                cout << endl;
                list.recurSearch(search);
                break;
            case 3:
                cout << "Which airport are you looking for: ";
                cin >> search;
                cout << endl;
                list.forSearch(search);
                break;
            case 4:
                cout << "Thank you for using this program.\n";
                cout << endl;
        }
    }while(choice != 4);
    
    return 0;
}

/*Create nodes*/
void SLinkedList::addNode(const string &c, const int &m)
{
    Snode *v = new Snode;
    v-> code = c;
    v-> dist = m;
    v-> next = NULL;
    if(priorloc == NULL)
        head = v;
    else
        priorloc-> next = v;
    priorloc = v;
}

/*Remove nodes*/
void SLinkedList::removeNode()
{
    Snode *old = head;
    head = old-> next;
    delete(old);
}

/*Displays complete linked list plus provide traversing verification*/
void SLinkedList::display()
{
    Snode *current = head;
    while(current != NULL){
        cout << current-> code << " " << current-> dist << " miles" << endl;
        current = current-> next;
    }
    cout << endl;
}

/*searches for airport code and computes cumulative miles from LGA to search airport code recursively*/
void SLinkedList::recurSearch(const string &c)
{
    Snode *temp = head;
    while(temp-> code != c)
    {
        temp = temp-> next;
    }
    cout << temp-> code << " airport is " << recurSum(head,c) << " cumulative miles to La Guardia airport." << endl;
    cout << endl;
}

/*calculates cumulative miles via loop from LGA to searched airport*/
void SLinkedList::forSearch(const string &c)
{
    Snode *temp = head;
    int sum = 0;
    while(temp-> code != c)
    {
        sum += temp-> dist;
        temp = temp-> next;
    }
    cout << temp-> code << " airport is " << sum + temp-> dist << " cumulative miles from LGA." << endl;
    cout << endl;
    if (temp-> code != c)                                       // if search value is found
        cout << "There is no airport code that matches what you entered." << endl;
}

/*recursively sums linked list*/
int SLinkedList::recurSum(Snode * thisnode, const string &c)
{
    int sum = 0;
    if(thisnode->code == c) //reach the end of search
    {
        return thisnode->dist; //return the distance to search
    }
    else
    {
        sum+= thisnode->dist; //add this distance to the sum
        return sum + recurSum(thisnode->next,c); //return the sum and the recursive sum of the next node
    }
}