#include<iostream>
#include<string.h>
#include<iomanip>

using namespace std;

class DNode{                                                     // Establish DNode Class
private:
    DNode *next;                                                // Node to use in list
    DNode *prev;
    
    string fname;                                               // Node element values
    string lname;
    string addre;
    string phone;
    friend class DLinkedList;                                   // Give access to DLinkedList
};

class DLinkedList{
private:
    DNode *header;                                              // List Sentinels
    DNode *trailer;
public:
    DLinkedList();                                              // Constructor
    ~DLinkedList();                                             // Destructor
    bool empty() const;                                         // Bool - is the list empty
    const string& front() const;                                // Get Front Element
    const string& back() const;                                 // Get Back Element
    void addFront(const string& l, const string& f, const string& a, const string& p); // Add Node to Front
    void addNode(const string& l, const string& f, const string& a, const string& p);  // Add Node
    void remove();
    void displayBackward();                                     // Display from Trailer
    void displayForward();                                      // Display from Header
    void search(const string& l);
    void sortAtoz();                                            // Sort by last name
    void sortZtoa();
};

bool DLinkedList::empty() const{
    return (header-> next == trailer);}

int main (){
    DLinkedList list = DLinkedList();                           // create variabl
    string lastName;
    string firstName;
    string address;
    string phoneNum;
    char again;
    
    cout << "Please enter the following information." << endl;  // get input
    cout << endl;
    cout << "Last Name: ";
    getline(cin, lastName);
    cout << endl;
    cout << "First Name:  ";
    getline(cin, firstName);
    cout << endl;
    cout << "Home address:  ";
    getline(cin, address);
    cout << endl;
    cout << "Phone Number:  ";
    cin >> phoneNum;
    cout << endl;
    list.addFront(lastName, firstName, address, phoneNum);
    
    cout << "Do you want to add another individual (Y/N): ";    // adds as many as needed
    cin >> again;
    while (again == 'Y' || again == 'y'){
        cout << endl;
        cin.ignore();
        cout << "Last Name: ";
        getline(cin, lastName);
        cout << endl;
        cout << "First Name:  ";
        getline(cin, firstName);
        cout << endl;
        cout << "Home address:  ";
        getline(cin, address);
        cout << endl;
        cout << "Phone Number:  ";
        cin >> phoneNum;
        cout << endl;
        list.addNode(lastName, firstName, address, phoneNum);
        cout << "Do you want to add another individual: ";
        cin >> again;
        cout << endl;
    }
    
    int choice;                                                     // variable for do-while loop
    
    do{                                                              // user input menu option
        cout << "The following are your choices.\n";
        cout << "Please enter the number for the selection you want: \n";
        cout << endl;
        cout << "1. Print the list forward.\n";
        cout << "2. Print the list backward.\n";
        cout << "3. Sort the list by last name in A-Z order.\n";
        cout << "4. Sort the list by last name in Z-A order.\n";
        cout << "5. Search for a last name.\n";
        cout << "6. Quit Program\n";
        cout << endl;
        cout << "Enter your selection: ";
        cin >> choice;
        
        while (choice < 1 || choice > 6){                            // input validation
            cout << "The valid choices are 1 through 6.  Please\n"
            << "select one of those." << endl;
            cout << "Enter your selection: ";
            cin >> choice;
        }
        
        switch (choice){
            case 1:                                                 // display function described below
                list.displayForward();
                cout << endl;
                break;
            case 2:                                                 // search function described below
                list.displayBackward();
                cout << endl;
                break;
            case 3:
                list.sortAtoz();                                    // sort function described below
                list.displayForward();
                cout << endl;
                break;
            case 4:
                list.sortZtoa();
                list.displayForward();
                cout << endl;
                break;
            case 5:{                                                 // search function described below
                string searchValue;
                cout << "Which last name are you looking for: ";
                cin >> searchValue;
                cout << endl;
                list.search(searchValue);
                cout << endl;
                break;}
            case 6:                                                 // ends program
                cout << "Thank you for using this program.\n";
                cout << "Have a nice Day.\n";
                cout << endl;
        }
    }while (choice != 6);
    
    return 0;
}

DLinkedList::DLinkedList(){
    header = new DNode;
    trailer = new DNode;
    header-> next = trailer;
    trailer-> prev = header;
}

DLinkedList::~DLinkedList(){
    while (!empty()) remove();
    delete header;
    delete trailer;
}

void DLinkedList::remove(){
    DNode *delNode = header;
    header = delNode-> next;
    delete delNode;
}

void DLinkedList::addNode(const string& l, const string& f, const string& a, const string& p){
    DNode* v = new DNode;
    v-> lname = l;
    v-> fname = f;
    v-> addre = a;
    v-> phone = p;
    v-> prev = trailer;
    trailer-> next = v;
    trailer = v;
}

void DLinkedList::addFront(const string& l, const string& f, const string& a, const string& p){
    DNode* v = new DNode;
    v-> lname = l;
    v-> fname = f;
    v-> addre = a;
    v-> phone = p;
    if(!empty()){
        v-> next = header;
        header-> prev = v;
        header = v;
    }
    else{
        v-> next = header;
        trailer = v;
        header = v;
    }
    
}

void DLinkedList::displayBackward(){
    DNode* temp = trailer;
    while (temp != NULL){
        cout << temp-> lname << " " << temp-> fname << " " << temp-> addre << " " << temp-> phone << " " << endl;
        temp = temp-> prev;
    }
    delete(temp);
}

void DLinkedList::displayForward(){
    DNode* temp = header;
    while (temp != NULL){
        cout << temp-> lname << " " << temp-> fname << " " << temp-> addre << " " << temp-> phone << " " << endl;
        temp = temp-> next;
    }
    delete(temp);
}

void DLinkedList::search(const string& l){
    DNode *temp = trailer;                                        // create temp node
    bool found = false;
    while (temp != NULL){
        if (temp-> lname == l){
            found = true;
            cout << temp-> lname << " " << temp-> fname << " " << temp-> addre << " " << temp-> phone << " " << endl;
        }
        temp = temp-> prev;                                         // otherwise keep searching
    }
    if (!found){
        cout << "There is no last name that matches what you entered." << endl;
        cout << "Please select again." << endl;
        cout << endl;
    }
}

/*
 Sets temp swap1 to first node and compares to second node.  If first node is greater than second node, it swaps. It continues until the smallest values are at the front.
 */

void DLinkedList::sortAtoz(){
    DNode *trailer = NULL;
    while(trailer != header){
        DNode *temp = NULL, *swap1;
        swap1 = header;
        while( swap1-> next != trailer ){
            if(swap1-> lname > swap1-> next-> lname){
                DNode *swap2 = swap1-> next;
                swap1-> next = swap2-> next;
                swap2-> next = swap1;
                if(swap1 == header){
                    header = swap2;
                    swap1 = swap2;
                }
                else{
                    swap1 = swap2;
                    temp-> next = swap2;
                }
            }
            temp = swap1;
            swap1 = swap1-> next;
        }
        trailer = swap1;
    }
}

/*
 Sets temp swap1 to first node and compares to second node.  If first node is less than second node, it swaps. It continues until the largest values are at the front.
 */

void DLinkedList::sortZtoa(){
    DNode *trailer = NULL;
    while(trailer != header){
        DNode *temp = NULL, *swap1;
        swap1 = header;
        while( swap1-> next != trailer ){
            if(swap1-> lname < swap1-> next-> lname){
                DNode *swap2 = swap1-> next;
                swap1-> next = swap2-> next;
                swap2-> next = swap1;
                if(swap1 == header){
                    header = swap2;
                    swap1 = swap2;
                }
                else{
                    swap1 = swap2;
                    temp-> next = swap2;
                }
            }
            temp = swap1;
            swap1 = swap1-> next;
        }
        trailer = swap1;
    }
}