// ================================================================
// Author:  Yee Hsu
// Date:    6/1/2005
// File:    Vector.cpp
//
// Description:
//      Implementation of class Vector. Vector performs all
//      necessary task to maintain the list structure. The list
//      is a bi-directional doubly linked list containing nodes
//      of records. ADT member functions performs the
//      restructuring and reattaching the link list.
// ================================================================

#include <iostream.h>
#include "Node.h"
#include "Vector.h"

// ================================================================
// Vector default constructor
// ================================================================

Vector::Vector()
{
    this->head = NULL;
    this->curr = NULL;
    this->tail = NULL;
}

// ================================================================
// Vector default copy constructor
// Performs a deep copy of a vector.
// ================================================================

Vector::Vector(const Vector &v)
{
    if (v.head == NULL)
        head = curr = tail = NULL;
    else
    {
        // copy the head node
        head = new Node(*(v.head));

        pNode newptr = head;
        pNode oldptr = v.head->next;

        // copy the rest of the list
        while (oldptr != NULL)
        {
            newptr->next = new Node;
            newptr = newptr->next;
            *newptr = *oldptr;
            oldptr = oldptr->next;
        }
        newptr->next = NULL;
    }
}

// ================================================================
// Vector default destructor
// Deletes all nodes to prevent memory leak
// ================================================================

Vector::~Vector()
{
    pNode temp = head;

    while (head != NULL)
    {
        head = head->next;
        delete temp;
        temp = head;
    }
    head = curr = tail = NULL;
}

// ================================================================
// Vector overloaded = operator
// Allows a vector object to be assigned to another vector
// ================================================================

Vector& Vector::operator =(const Vector &v)
{
    if (this != &v)
    {
        // deletes old vector
        this->~Vector();

        if (v.head == NULL)
            head = curr = tail = NULL;
        else
        {
            // copy the head node
            head = new Node(*(v.head));

            pNode newptr = head;
            pNode oldptr = v.head->next;

            // copy the rest of the list
            while (oldptr != NULL)
            {
                newptr->next = new Node;
                newptr = newptr->next;
                *newptr = *oldptr;
                oldptr = oldptr->next;
            }
            newptr->next = NULL;
        }
    }
    return *this;
}

// ================================================================
// Vector overloaded == operator
// Allows vector objects to compare each other for equality
// ================================================================

bool Vector::operator ==(const Vector &v)
{
    bool VEqual = false;
    pNode v1 = head;
    pNode v2 = v.head;

    if (this->Length() == v.Length())
    {
        while (v1 != NULL)
        {
            VEqual = false;

            if (*v1 == *v2)
            {
                VEqual = true;
                v1 = v1->next;
                v2 = v2->next;
            }
            else
                break;
        }
    }
    return VEqual;
}

// ================================================================
// Vector overloaded == operator
// Allows vector objects to compare each other for inequality
// ================================================================

bool Vector::operator !=(const Vector &v)
{
    return !(*this == v);
}

// ================================================================
// IDENTIFIER:  InsertAtFront(const Data data)
//
// PARAM:       data        -- a data of records
//
// RETURNS:     curr->data  -- the data inserted
//
// COMMENTS:    Inserts a data at the beginning of the list.
// ================================================================

Data Vector::InsertAtFront(const Data data)
{
    pNode temp = new Node;
    temp->data = data;
    temp->prev = NULL;

    if (head == NULL)
    {
        // special case when list is empty
        head = temp;
        head->next = NULL;
        tail = head;
    }
    else
    {
        // inserts the node at beginning of list
        head->prev = temp;
        temp->next = head;
        head = temp;
    }
    curr = head;
    return curr->data;
}

// ================================================================
// IDENTIFIER:  InsertAtPlace(const Data data)
//
// PARAM:       data        -- a data of records
//
// RETURNS:     curr->data  -- the data inserted
//
// COMMENTS:    Inserts a data at it's currect sorted place.
//              Neighboring nodes are reattached for list integrity
// ================================================================

Data Vector::InsertAtPlace(const Data data)
{
    pNode temp = new Node;
    temp->data = data;

    do
    {
        if (curr == NULL)
        {
            // special case when list is empty
            curr = temp;
            curr->next = NULL;
            curr->prev = NULL;
            head = tail = curr;
            break;
        }
        else if (data.key < curr->data.key && curr->prev == NULL)
        {
            // special case at the beginning of the list
            curr->prev = temp;
            curr->prev->next = curr;
            curr = curr->prev;
            curr->prev = NULL;
            head = curr;
            break;
        }
        else if (data.key > curr->data.key && curr->next == NULL)
        {
            // special case at the end of the list
            curr->next = temp;
            curr->next->prev = curr;
            curr = curr->next;
            curr->next = NULL;
            tail = curr;
            break;
        }
        else if (data.key < curr->data.key && data.key > curr->prev->data.key)
        {
            // insert between this node and its previous node
            temp->prev = curr->prev;
            temp->next = curr;
            curr->prev->next = temp;
            curr->prev = temp;
            curr = temp;
            break;
        }
        else if (data.key > curr->data.key && data.key < curr->next->data.key)
        {
            // insert between this node and its next node
            temp->prev = curr;
            temp->next = curr->next;
            curr->next->prev = temp;
            curr->next = temp;
            curr = temp;
            break;
        }
        else if (data.key < curr->data.key)
            curr = curr->prev;
        else if (data.key > curr->data.key)
            curr = curr->next;
        else
            break;
    } while (curr != NULL);

    return curr->data;
}

// ================================================================
// IDENTIFIER:  InsertAtEnd(const Data data)
//
// PARAM:       data        -- a data of records
//
// RETURNS:     curr->data  -- the data inserted
//
// COMMENTS:    Inserts a data at the end of the list.
//              Similar to Push() and Enqueue()
// ================================================================

Data Vector::InsertAtEnd(const Data data)
{
    pNode temp = new Node;
    temp->data = data;
    temp->next = NULL;

    if (tail == NULL)
    {
        // special case when list is empty
        tail = temp;
        tail->prev = NULL;
        head = tail;
    }
    else
    {
        // inserts at the end of the list
        tail->next = temp;
        temp->prev = tail;
        tail = temp;
    }
    curr = tail;

    return curr->data;
}

// ================================================================
// Returns the data at the head of the list
// ================================================================

Data Vector::PeekAtFront() const
{
    return head->data;
}

// ================================================================
// Returns the data at the current place of the list
// ================================================================

Data Vector::PeekAtPlace() const
{
    return curr->data;
}

// ================================================================
// Returns the data at the end of the list
// ================================================================

Data Vector::PeekAtEnd() const
{
    return tail->data;
}

// ================================================================
// IDENTIFIER:  DeleteAtFront()
//
// RETURNS:     data    -- the data deleted
//
// COMMENTS:    Deletes the head of of the list
//              Similar to Dequeue()
// ================================================================

Data Vector::DeleteAtFront()
{
    Data data;

    if (head != NULL)
    {
        pNode temp = head;
        data = head->data;
        head = head->next;
        head == NULL ? head = tail = NULL : head->prev = NULL;
        curr = head;
        delete temp;
        temp = NULL;
    }
    return data;
}

// ================================================================
// IDENTIFIER:  DeleteAtPlace()
//
// PARAM:       key     -- the data key to be deleted
//
// RETURNS:     data    -- the data deleted
//
// COMMENTS:    Deletes the node record with the Id key
// ================================================================

Data Vector::DeleteAtPlace(const int key)
{
    Data data;

    while (curr != NULL)
    {
        if (key == curr->data.key)
        {
            pNode temp = curr;
            data = curr->data;

            if (curr->prev == NULL && curr->next == NULL)
            {
                // special case when list is a singal node
                curr = head = tail = NULL;
            }
            else if (curr->prev == NULL)
            {
                // special case at the beginning of the list
                curr = curr->next;
                curr->prev = NULL;
                head = curr;
            }
            else if (curr->next == NULL)
            {
                // special case at the end of the list
                curr = curr->prev;
                curr->next = NULL;
                tail = curr;
            }
            else
            {
                // inserts and reattach nodes
                curr->prev->next = curr->next;
                curr->next->prev = curr->prev;
                curr->prev = NULL;
                curr->next = NULL;
            }
            delete temp;
            temp = NULL;
            break;
        }
        else if (key < curr->data.key)
            curr = curr->prev;
        else if (key > curr->data.key)
            curr = curr->next;
    }
    return data;
}

// ================================================================
// IDENTIFIER:  DeleteAtEnd()
//
// RETURNS:     data    -- the data deleted
//
// COMMENTS:    Deletes the end of of the list
//              Simplar to Pop()
// ================================================================

Data Vector::DeleteAtEnd()
{
    Data data;

    if (tail != NULL)
    {
        pNode temp = tail;
        data = tail->data;
        tail = tail->prev;
        tail == NULL ? tail = head = NULL : tail->next = NULL;
        curr = tail;
        delete temp;
        temp = NULL;
    }
    return data;
}

// ================================================================
// IDENTIFIER:  Length()
//
// RETURNS:     length  -- the length of the list
//
// COMMENTS:    Traverse the list and determines it's length
// ================================================================

int Vector::Length() const
{
    pNode temp = head;
    int length = 0;

    while (temp != NULL)
    {
        length++;
        temp = temp->next;
    }
    return length;
}

// ================================================================
// IDENTIFIER:  IsEmpty()
//
// RETURNS:     true if list is empty, false otherwise
//
// COMMENTS:    Determines if the list is empty
// ================================================================

bool Vector::IsEmpty() const
{
    return (curr == NULL);
}

// ================================================================
// IDENTIFIER:  SortVector()
//
// PRE:         A vector out of order that needs to be sorted
//
// CALLS        IsEmpty()           --  Determine list empty?
//              DeleteAtFront()     --  Dequeue()
//              InsertAtPlace()     --  Inserts at sorted place
//
// POST:        The same vector sorted
//
// COMMENTS:    Sorts the vector into accending order
// ================================================================

void Vector::SortVector()
{
    Vector v;
    while (!IsEmpty()) {v.InsertAtPlace(DeleteAtFront());}
    *this = v;
}

// ================================================================
// IDENTIFIER:  DisplayList()
//
// COMMENTS:    Displays the entire vector array
// ================================================================

void Vector::DisplayList() const
{
    pNode temp = head;

    while (temp != NULL)
    {
        cout << *temp;
        cout << endl;
        temp = temp->next;
    }
}

// ================================================================
// Overloaded << to display Vector (DEQ) objects
// ================================================================

ostream& operator<<(ostream &out, const Vector &v)
{
    pNode temp = v.head;

    while (temp != NULL)
    {
        out << *temp;
        temp = temp->next;
    }
    return out;
}