#include <iostream>
#include <list>
using namespace std;
typedef int element_type;
typedef element_type& reference;
typedef const element_type& const_reference;

class linkedlist{
public:
    linkedlist();   //done
    explicit linkedlist(unsigned int n);
    ~linkedlist();
    bool empty() const; //done
    void clear();   //done
    reference back();   //done
    const_reference back() const;   //done
    reference front();  //done
    const_reference front() const;  //done
    linkedlist& operator=(const linkedlist& l);
    void pop_back ();   //done
    void pop_front ();  //done
    void push_back ( const element_type& x );   //done
    void push_front ( const element_type& x );  //done
    void sort ();   //did not finish
    void check() const; //done
    void rcheck() const;    //done
    void print();




private:
    struct Node{
    element_type data;
    Node* next;
    Node* prev;
    };
    Node* head;
    Node* tail;
    Node* current;
    element_type list_size;

};

linkedlist::linkedlist()    //default constructor
{
    head = new Node;
    tail = new Node;
    head->next = tail;
    head->prev = NULL;
    tail->next = NULL;
    tail->prev = head;
    current = head;
    list_size = 0;
}

linkedlist::linkedlist(unsigned int n)  //explicit constructor
{
    element_type size = n;
    head = new Node;
    tail = new Node;
    current = head;
    head->prev = NULL;
    tail->next = NULL;

    for(int i = 0; i < size; i++)
    {
        current->next = new Node;
        Node * temp = current;
        current = current->next;
        current->prev = temp;
        current->data = i;
    }
    current->next = tail;
    tail->prev = current;
    list_size = n;
}

linkedlist::~linkedlist()   //ask about this
{
    /*clear();
    delete head;
    delete tail;
    */
}

bool linkedlist:: empty() const     // works
{
    if( head->next == tail )
    {
        return true;
    }
    else
    {
        return false;
    }
}

void linkedlist::push_front ( const element_type& x )   //works
{
    if(list_size == 0)
    {
    head->next = new Node;
    current = head->next;
    current->next = tail;
    current->prev = head;
    tail->prev = current;
    current->data = x;
    list_size++;
    }
    else
    {
        current = head->next;
        head->next = new Node;
        current->prev = head->next;
        head->next->prev = head;
        head->next->next = current;
        current = head->next;
        current->data = x;
        list_size++;
    }


}

void linkedlist:: push_back (const element_type& x) //works
{
    if(list_size == 0)
    {
        tail->prev = new Node;
        current = tail->prev;
        current->next = tail;
        current->prev = head;
        head->next = current;
        current->data = x;
        list_size++;
    }
    else
    {
        current = tail->prev;
        tail->prev = new Node;
        current->next = tail->prev;
        tail->prev->prev = current;
        current = tail->prev;
        current->next = tail;
        current->data = x;
        list_size++;
    }
}

reference linkedlist:: front()  //works
{
    return head->next->data;
}

const_reference linkedlist:: front() const  //works
{
    return head->next->data;
}

reference linkedlist:: back()   //works
{
    return tail->prev->data;
}

const_reference linkedlist:: back() const   //works
{
    return tail->prev->data;
}

void linkedlist:: pop_front()   //works
{
    current = head->next;
    head->next = current->next;
    current->next->prev = head;
    current->next = NULL;
    current->prev = NULL;
    delete current;
    list_size--;
}

void linkedlist:: pop_back()    //works
{
    current = tail->prev;
    current->prev->next = tail;
    tail->prev = current->prev;
    current->next = NULL;
    current->prev = NULL;
    delete current;
    list_size--;
}

void linkedlist:: clear()   //works
{
    Node * tmp;
    Node * traverse = head->next;

    while(traverse != NULL)
    {
        tmp = traverse;
        traverse = traverse->next;
        delete tmp;
    }
    current = head;
    head->next = tail;
    tail->prev = head;
    list_size = 0;

}

void linkedlist::check() const  //works
{
    Node *temp_current;
    temp_current = head->next;

    for(int i = 0; i < list_size; i++)
    {
        cout<< temp_current->data << '\n';
        temp_current = temp_current->next;
    }
    if(list_size > 0)
    {
    cout<< "List size: " << list_size << '\n';
    cout<< "Front element: " << front() << '\n';
    cout<< "Back element: " << back() << '\n';
    cout<< "Front element minus 1: " << front()-1 << '\n';
    cout<< "Back element minus 1: " << back()-1 << '\n';
    cout<< "Empty?: " << empty() << '\n';
    }
    else
    {
        cout<< "List size: " << list_size << '\n';
        cout<< "Empty?: " << empty() << '\n';
    }
}

void linkedlist::rcheck() const //works
{
    Node *temp_current;
    temp_current = tail->prev;

    for(int i = list_size; i > 0; i--)
    {
        cout<< temp_current->data << '\n';
        temp_current = temp_current->prev;
    }
}

linkedlist& linkedlist::operator=(const linkedlist& l)
{

    if(this ==&l)
    {
        return *this;
    }

    clear();
    Node* tmp = l.head;
    Node* temp;
    current = head;
    while(tmp!= l.tail)
    {
        current->next = new Node;
        temp = current;
        current = current->next;
        current->prev = temp;
        tmp = tmp->next;
        current->data = tmp->data;
    }
    list_size = l.list_size;
    current->next = tail;
    tail->prev = current;
    return *this;
}

void linkedlist::sort()
{
    //start iterating at head
    Node* current = head->next;
    //iterate until last node in list
    while (current->next != NULL) {
        //set smallest as current
        Node* smallest = current;
        //iterator starts at the next
        Node* iterator = current->next;
        //iterate through rest of list finding smallest node
        while (iterator->next != NULL) {

            if (iterator->data < smallest->data)
                smallest = iterator;
            iterator = iterator->next;
        }
        //if current isn't smallest swith em


        if (current != smallest) {
            //current->prev is null then its head, swith with smallest
            if (current->prev == NULL) {
                head = smallest;
            }
            //get temp vars to use for current from smallest
            Node *s_next = smallest->next;
            Node *s_prev = smallest->prev;


            Node *c_next = current->next;
            Node *c_prev = current->prev;

            //set smallest links to currents;


            smallest->next = c_next;
            if (smallest->next != NULL)
                smallest->next->prev = smallest;
            smallest->prev = c_prev;
            if (smallest->prev != NULL)
                smallest->prev->next = smallest;

            //set currents links to saved smallests

            current->next = s_next;
            if (current->next != NULL)
                current->next->prev = current;
            current->prev = s_prev;
            if (current->prev != NULL)
                current->prev->next = current;
        }

        //go to next in list
        current = smallest->next;
    }
}

void linkedlist::print()
{
    Node* it = head;
    while (it != NULL){
        cout << it->data << " ";
        it = it->next;
    }
    cout << endl;
}


int main()
{
    linkedlist *L1 = new linkedlist();
    L1->push_back(4);
    L1->push_back(5);
    L1->push_back(2);
    L1->push_back(3);
    L1->print();
    L1->sort();
    L1->print();
    L1->clear();
/*linkedlist L3;
L3.push_front(5);
L3.push_front(6);
L3.push_front(2);
L3.push_front(10);
L3.push_front(99);
L3.push_front(40);
L3.push_front(1);
L3.push_front(8);
L3.push_front(1000);
L3.sort();
*/












}