// ================================================================
// 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;
}