// list.h
#include<iostream>
using namespace std;
#include<cstddef>
#include "node.h"

enum Error_code {success, fail, overflow, range_error};  // The possible error conditions

template <class List_entry>
class List {
public:
    List();      // constructor
    /* Post: The List is initialized to be empty.*/
    
    int size() const;
    /* Post: Return the size of the List. */
    
    bool empty() const;
    /* Post: If the List is empty, true is returned. Otherwise false is returned. */
    
    void clear();
    /* Post: All List  entries have been removed; the List is empty*/
    
    void traverse(void (*visit)(List_entry &));
    /* Post: The action specified by function(*visit) has been performed on every entry of theList ,
             beginning at position 0 and doing each in turn. */
    
    Error_code retrieve(int position, List_entry &x) const;
    /* Post: The entry at the indicated position has been retrieved to the
             output parameter x. If position is out of bounds an Error_code
             of range_error is returned. */

    Error_code replace(int position, const List_entry &x);
    /* Post: If 0 <= position < n, where n is the number of entries in the List,
             the function succeeds: The entry at position is replaced by x;
             all other entries remain unchanged.
             Else: The function fails with a diagnostic error code.*/
            
    Error_code remove(int position, List_entry &x);
    /* Post: If 0<= position < n, where n is the number of entries in the List, the function succeeds:
             The entry at position is removed from the List, and all later entries have their position numbers decreased by 1.
             The parameter x records a copy of the entry formerly at position.
             Else: The function fails with a diagnostic error code.*/

    Error_code insert(int position, const List_entry &x);
    /* Post: If the List is not full and 0 <= position <= count the function succeeds.
             Any entry formerly at position and all later entries have their position
             increased by 1 and x is inserted at position of the List.
             Else: the function fails with a diagnostic error code. */
                             
    ~List();     // destructor
    /* Post: The List has been destroyed and its memory freed. */
    
    const List<List_entry>& operator = (const List<List_entry> &original); // Overload assignment operator
    /* Stub */


    List(const List<List_entry> &original);    // copy constructor
    /* Post: The List is initialized as a copy of List original. */

protected:
    int count;
    mutable int current_position;
    mutable Node <List_entry> *current;
    Node<List_entry> *head;
    void set_position(int position) const;
    /* Pre:  Position is a valid position in the List: 0 <= position < count.
       Post: The current Node pointer references the Node at position. */
};

template <class List_entry>
Error_code List<List_entry>::insert(int position, const List_entry &x)
/* Post: If the List is not full and 0 <= position <= count the function succeeds.
         Any entry formerly at position and all later entries have their position
         increased by 1 and x is inserted at position of the List.
         Else: the function fails with a diagnostic error code. */
{
    Node<List_entry> *new_node, *following, *preceding;
    if (position < 0 || position > count) return range_error;
    if (position == 0) {
        if (count == 0) following = NULL;
        else {
            set_position(0);
            following = current;
        }
        preceding = NULL;
    }
    else {
        set_position(position - 1);
        preceding = current;
        following = preceding->next;
    }
    new_node = new(nothrow) Node<List_entry>(x, preceding, following);
    if (new_node == NULL) return overflow;
    if (preceding != NULL) preceding->next = new_node;
    if (following != NULL) following->back = new_node;
    current = new_node;
    current_position = position;
    count++;
    return success;
}

template <class List_entry>
Error_code List<List_entry>::remove(int position, List_entry &x)
/* Post: If 0<= position < n, where n is the number of entries in the List, the function succeeds:
         The entry at position is removed from the List, and all later entries have their position numbers decreased by 1.
         The parameter x records a copy of the entry formerly at position.
         Else: The function fails with a diagnostic error code.*/
{    
    Node<List_entry> *previous, *following;
    if (position < 0 || position >= count) return range_error;
    if (position > 0) {
        set_position(position-1);
        previous = current;
        following = previous->next;
        previous->next = following->next;
        if(following->next) following->next->back = previous;
    }
    else{
        following = head;
        head = head->next;
        if(head)head->back = NULL;
    }
    delete following;
    count--;
    return success;
}
    
template <class List_entry>
Error_code List<List_entry>::retrieve(int position, List_entry &x) const
/* Post: The entry at the indicated position has been retrieved to the
         output parameter x. If position is out of bounds an Error_code
         of range_error is returned. */
{
    if (position < 0 || position >= count || empty()) return range_error;
    set_position(position);
    x = current->entry;
    return success;
}

template <class List_entry>
Error_code List<List_entry>::replace(int position, const List_entry &x)
/* Post: If 0 <= position < n, where n is the number of entries in the List,
         the function succeeds: The entry at position is replaced by x;
         all other entries remain unchanged.
         Else: The function fails with a diagnostic error code.*/            
{
    if (position < 0 || position >= count) return range_error;
    set_position(position);
    current->entry=x;
    return success;
}


template <class List_entry>
bool List<List_entry>::empty() const
/* Post: If the List is empty, true is returned. Otherwise false is returned. */
{
    return (count == 0);
}

template <class List_entry>
int List<List_entry>::size() const
/* Post: Return the size of the List. */
{
    return count;
}

template <class List_entry>
List<List_entry>::List()    // Constructor
/* Post: The List is initialized to be empty.*/
{
    count = 0;
}

template <class List_entry>
void List<List_entry>::clear()
/* Post: All List entries have been removed; the List is empty*/
{
    List_entry x;
    while(!empty())remove(0,x);
}

template <class List_entry>
void List<List_entry>::traverse(void (*visit)(List_entry &))
/* Post: The action specified by function(*visit) has been performed on every entry of the List,
         beginning at position 0 and doing each in turn. */
{
    Node<List_entry> *new_node = head;
    while(new_node){
        (*visit)(new_node->entry);
        new_node = new_node -> next;
    }
}

template <class List_entry>
List<List_entry>::~List()     // Destructor
/* Post: The List has been destroyed and its memory freed. */
{
    clear();
}

template <class List_entry>
const List<List_entry>& List<List_entry>::operator = (const List<List_entry> &original) // Overload assignment operator
/* Stub */
{
}

template <class List_entry>
List<List_entry>::List(const List<List_entry> &original) // copy constructor
/* Post: The List is initialized as a copy of List original. */
{
    List_entry x;
    count = 0;
    for (int i = 0; i < original.count; i++){
        original.retrieve(i, x);
        insert(i, x);
    }
}

template <class List_entry>
void List<List_entry>::set_position(int position) const
/* Pre:  Position is a valid position in the List: 0 <= position < count.
   Post: The current Node pointer references the Node at position. */
{
    if (current_position <= position)
        for (; current_position != position; current_position++)
            current = current->next;
    else
        for(; current_position != position; current_position--)
            current = current->back;
}

// node.h
#include<cstddef>

template <class Node_entry>
struct Node{
// data members
    Node_entry entry;
    Node<Node_entry> *next;
    Node<Node_entry> *back;
// constructors
    Node();
    /* Post: an empty node is created that has no next or previous nodes. */
    
    Node(Node_entry item, Node<Node_entry> *link_back = NULL,
                          Node<Node_entry> *link_next = NULL);
    /* Post: a node is created that contains the entry item and has the node at link_back
             as the back node and link_next as the next node. */
};

template <class Node_entry>
Node<Node_entry>::Node()
/* Post: an empty node is created that has no next node. */
{
    next = NULL;
    back = NULL;
}

template <class Node_entry>
Node<Node_entry>::Node(Node_entry item, Node<Node_entry> *link_back, Node<Node_entry> *link_next)
/* Post: a node is created that contains the entry item and has the node at link_back as the
         back node and link_next as the next node. */
{
    entry = item;
    next = link_next;
    back = link_back;
}

// main.cpp
#include<iostream>
using namespace std;

#include "list.h"

typedef char List_entry;

void print(List_entry &x);
/* Post: Print a character. */

void help();
/* Post: A help screen for the program is printed, giving the meaning of each
         command that the user may enter.*/

void introduction();
// An introduction of the program.

char get_command();
/* Post: The user enters a command (I, D, R, G, P, H, Q, i, d, r, g, p, h, or q). The function returns
         the command entered. */
        
bool do_command(char c, List<List_entry> &test_list);
/* Pre:  c represents a valid command.
   Post: Performs the given command c on the List test_List.
         Returns false if c == 'q', otherwise returns true.
   Uses: The class List. */

int main()
/* Post: Accepts commands from user as a menu-driven demonstration program
         for the class List.
   Uses: The class List and the funcitons introduction, get_command, and do_command. */
{
    List<List_entry> test_list;
    introduction();
    while (do_command(get_command(), test_list));    
}

void introduction()
// stub
{
    cout << "The Doubly Linked List." << endl;
}

void help()
/* Post: A help screen for the program is printed, giving the meaning of each
         command that the user may enter.*/
{
    cout << endl
         << "This program allows the user to enter one command" << endl
         << "(but only one) on each input line." << endl
         << "For example, if the command G is entered, then" << endl
         << "the program will retreive an entry from the list." << endl
         << endl
         << "The valid commands are:" << endl
         << "I - Insert a entry into the list" << endl
         << "D - Delete an entry from the list" << endl
         << "R - Replace an entry in the list" << endl
         << "G - Get an entry from the list" << endl
         << "P - Print the list" << endl
         << "H - This help screen" << endl
         << "Q - Quit" << endl
         << "Press < Enter > to continue." << flush;
    
    char c;
    cin.get(c);   // flush out an extra newline
    do {
         cin.get(c);
    } while (c != '\n');
}

char get_command()
/* Post: The user enters a command (I, D, R, G, P, H, Q, i, d, r, g, p, h, or q). The function returns
         the command entered. */
{
    char command;
    bool waiting = true;
    cout << "Select command and press < Enter > :";
    while (waiting){
        cin >> command;
        command = tolower(command);
        if (command == 'i' || command == 'd' || command == 'r' ||
            command == 'g' || command == 'p' || command == 'h' || command == 'q')
            waiting = false;
        else {
            cout << "Please enter a valid command:" << endl
                 << "[I]insert [D]delete [R]replace" << endl
                 << "[G]get [P]print [H]Help" << endl
                 << "[Q]uit." << endl;
        }
    }
    return command;
}

bool do_command(char c, List<List_entry> &test_list)
/* Pre:  c represents a valid command.
   Post: Performs the given command c on the List test_list.
         Returns false if c == 'q', otherwise returns true.
   Uses: The class List. */
{
    bool continue_input = true;
    int position;
    List_entry x;
    Error_code err;
    switch (c) {
    case 'i':
        cout << "Please enter a position to insert the new entry: " << flush;
        cin >> position;
        cout << "Please enter a new character to insert into the List: " << flush;
        cin >> x;
        err = test_list.insert(position, x);
        if (err == overflow)
            cout << "List is full." << endl;
        if (err == range_error)
            cout << "Position is not valid." << endl;
        break;
    case 'd':
        cout << "Please enter a position to delete: " << flush;
        cin >> position;
        err = test_list.remove(position, x);
        if (err == range_error)
            cout << "Position is not valid." << endl;
        else
            cout << "The removed entry was " << x << "." << endl;
        break;
    case 'r':
        cout << "Please enter a position to replace: " << flush;
        cin >> position;
        cout << "Please enter a new character to put in this position: " << flush;
        cin >> x;
        err = test_list.replace(position, x);
        if (err == range_error)
            cout << "Position is not valid." << endl;
        break;
    case 'g':
        cout << "Please enter a position to get: " << flush;
        cin >> position;
        err = test_list.retrieve(position, x);
        if (err == range_error)
            cout << "Position is not valid." << endl;
        else
            cout << "The entry is " << x << "." << endl;
        break;
    case 'p':
        test_list.traverse(print);
        cout << endl;
        break;
    case 'h':
        help();
        break;
    case 'q':
        cout << "List demonstration finished." << endl;
        continue_input = false;
        break;
    }
    return continue_input;
}

void print(List_entry &x)
{
    cout << x << " ";
}