/*The original author is Isaac Sarver. He releases this software is released under International Components for Unicode license version 1.8.1. http://source.icu-project.org/repos/icu/icu/trunk/license.html
Started 9/16/10
Converted to char on 9/19/10.
This is the class for a linked list of chars. It will be unsorted, indexed, and doublely linked.*/
#include
using namespace std;
#include"List.h"
Type List::DeleteIndex(int i) //Delete Node at index [i], placed here for dignostic conveiance
{
nodeptr n; //Node pointer to node to delete
nodeptr loc = head; //Location node pointer
Type deleted; //Value to be returned
if(i < count-1 && i > 0) //Execute only if the given an index that is less than tail position, will otherwise execute DeleteTail as this would be the appearent attempt. This algorithm will error if the element is to be removed at the head or tail, will call the correct function if so.
{
if(head == NULL) //If empty list
{ //Do nothing, this arrangement is to due copy and paste from adding node at index
}
else
{
count--; //Decreament size
while(loc->index != i && loc->next != NULL) //while loc is not at the index i and loc is not looking at the cliff. Second condition should not be needed
{
loc = loc->next; //advance location
}
n = loc; //point n at location
loc = loc->next; //Get loc off the sinking ship
loc->prev = n->prev; //Point loc->prev at new prev
n->prev->next = loc; //Point prev node->next at loc
n->next = NULL; //Point n links into the void
n->prev = NULL;
deleted = n->value; //Stores deleted value
delete n; //Delete n
while(loc != NULL) //While n has not fallen off the cliff, will not execute if was empty because head-next = NULL
{
loc->index--; //Increament index of all nodes after at and after loc
loc = loc->next; //Advance loc
}
}
}
else if(i <= 0)
{
deleted = DeleteHead();
}
else //Only range greater than count has not been covered, no need to check
{
deleted = DeleteTail();
}
return(deleted);
}
void List::AddHead(Type x) //Add Node to Head
{
nodeptr n = new node; //General node pointer
n->value = x; //Store new value in n
n->index = 0; //Going to index 0
n->prev = NULL; //Point previous to NULL
n->next = NULL; //Point next to NULL, there may not be a next node if empty list
count++; //Increament size
if(head == NULL) //If empty list
{
head = n; //Point head and tail to n
tail = n;
}
else
{
n->next = head; //point next at present head
head->prev = n; //point prev of next node, which is head, to n
head = n; //point head at new head node
if(count == 0)
{
n = n->next; //Advance n, needs to be done before the index is increamented or this list will not function as a normal array
}
else
{
while(n != NULL) //While n has not fallen off the cliff, will not execute if was empty because head-next = NULL
{
n->index++; //Increament index of all nodes after head
n = n->next; //Advance n
}
}
}
return;
}
void List::AddTail(Type x) //Add Node to Tail
{
nodeptr n = new node; //General node pointer
n->value = x; //Store new value in n
n->index = count; //Going to index count, count happens to be the value of the index at the back before increamentation
n->prev = NULL; //Point previous to NULL, there may not be a previous node if empty list
n->next = NULL; //Point next to NULL
count++; //Increament size
if(head == NULL) //If empty list
{
head = n; //Point head and tail to n
tail = n;
}
else
{
n->prev = tail; //point prev at present tail
tail->next = n; //point next of prev node, which is tail, to n
tail = n; //point tail at new head node
} //Increamenting indices is not needed as this is going at the tail
return;
}
void List::AddIndex(Type x, int i) //Add Node at index [i]
{
nodeptr n = new node; //New node pointer
nodeptr loc = head; //Location node pointer
if(i < count-1 && i > 0) //Execute only if the given an index that is less than tail position, will otherwise execute AddTail as this would be the appearent attempt. This algorithm will error if the element is to be inserted at the head or tail, will call the correct function if so.
{
n->value = x; //Store new value in n
n->index = i; //Going to index i
n->prev = NULL; //Point previous to NULL
n->next = NULL; //Point next to NULL, there may not be a next node if empty list
count++; //Increament size
if(head == NULL) //If empty list
{
head = n; //Point head and tail to n
tail = n;
}
else
{
while(loc->index != i) //while loc is not at the index i
{
loc = loc->next; //advance location
}
n->next = loc; //point next at location
n->prev = loc->prev; //point prev of n to what will be previous of loc
loc->prev->next = n; //point node prev to loc at n
loc->prev = n; //point loc prev at n
while(loc != NULL) //While loc has not fallen off the cliff, will not execute if was empty because head-next = NULL
{
loc->index++; //Increament index of all nodes after at and after loc
loc = loc->next; //Advance loc
}
}
}
else if(i <= 0)
{
AddHead(x);
}
else //Only range greater than count has not been covered, no need to check
{
AddTail(x);
}
return;
}
Type List::DeleteHead() //Delete first Node
{
nodeptr n = head; //General n point and point it at the node to go away
Type deleted = '0'; //Value to be returned, default of 0 will be error for Unpaired in In2Post
if(n != NULL) //If the list isn't already empty
{
deleted = head->value; //Inside the conditional or it will trigger segfault
count--; //Decreament the counter
if(head->next != NULL) //I think this next line will cause a Seg Fault if executed with only 1 in the list. Not an issue with DeleteIndex as this function will be called to do that.
{
head = head->next; //Advance head
}
head->prev = NULL; //Point the new head's previous into the void
n->next = NULL; //Disconnect n from list
delete n; //Delete n
if(count == 0) //To return the list to the orginal state to accept new nodes without ill effect
{//Placeing this if statement here will prevent a seg fault involving n=head, n!=NULL in lines 198 and 199
head = NULL;
tail = NULL;
}
n = head; //Advance n, needs to be done before the index is decreamented or this list will not function correctly
while(n != NULL) //While n has not fallen off the cliff, will not execute if was empty because head-next = NULL
{
n->index--; //Decreament index of all nodes after head
n = n->next; //Advance n
}
}
return(deleted);
}
Type List::DeleteTail() //Delete last Node
{
nodeptr n = tail; //General n point and point it at the node to go away
Type deleted = tail->value; //Value to be returned
if(n != NULL) //If the list isn't already empty
{
count--; //Decreament the counter
if(tail->prev != NULL) //I think this line will cause a Seg Fault if list of 1
{
tail = tail->prev; //Advance tail
}
tail->next = NULL; //Point the new tail's next into the void
n->prev = NULL; //Disconnect n from list
delete n; //Delete n
}//Decreamenting indices is not needed as it was the last one that went away
if(count == 0) //To return the list to the orginal state to accept new nodes without ill effect
{
head = NULL;
tail = NULL;
}
return(deleted);
}
void List::ChangeValue(Type x, int i) //Changes value to x at index [i], "reassignment operator"
{
nodeptr n = head; //General node pointer and start at the head
while(n->next != NULL && n->index < i) //While the index is not found and n has not found the end of the list
{
n = n->next; //Advance n
}
n->value = x; //Store new value at the index
return;
}
Type List::WhatValue(int i) //Returns value at index [i], "subscript operator"
{
nodeptr n = head; //General node pointer and start at the head
while(n->next != NULL && n->index < i) //While the index is not found and n has not found the end of the list
{
n = n->next; //Advance n
}
return(n->value);
}
int List::WhereIs(Type x) //Returns first index of value if value is in list, -1 if not
{
nodeptr n = head; //General node pointer and start at the head
int loc = -1; //The first location of the value to be found
while(n != NULL && n->value != x) //While the index is not found and n has not fallen off the end of the list
{
n = n->next; //Advance n
}
if(n->value == x) //If the present position has the value
{
loc = n->index; //Store and return that location
}
return(loc);
}
int List::Size() //Returns the length of the list
{
return(count);
}
void List::Switch(int i, int j) //Switches the location of two values at indices [i] and [j]
{
nodeptr ni = head; //Location of node with index i
nodeptr nj = head; //Location of node with index j
Type holder; //Holder while values switch
int iholder; //Holder for index value to switch and improve efficentcy
if(j < i) //If j is less than i, switch the values
{
iholder = i;
i = j;
j = iholder;
}
while(ni != NULL && ni->index < i) //While the index is not found and ni has not fallen off the end of the list
{
ni = ni->next; //Advance ni
}
nj = ni; // Start nj at ni as j is greater than i, no need to transvese that part of list
while(nj != NULL && nj->index < j) //While the index is not found and nj has not fallen off the end of the list
{
nj = nj->next; //Advance nj
}
if(ni != NULL && nj != NULL) //If both indices exist in the list
{
holder = ni->value; //Store ni to holder
ni->value = nj->value; //Store nj to ni
nj->value = holder; //Store holder to nj
}
return;
}
int List::HowMany(Type x) //Returns number of times value is in the list
{
nodeptr n = head; //General node pointer and start at the head
int number = 0; //Number of times x appears in list
while(n != NULL) //While n has not fallen off the end of the list
{
if(n->value == x) //If value is found
{
number++; //Increament number
}
n = n->next; //Advance n
}
return(number);
}
void List::Print() //Returns first index of value if value is in list, -1 if not
{
nodeptr n = head; //General node pointer and start at the head
while(n != NULL) //While the index is not found and n has not fallen off the end of the list
{
cout << "List[" << n->index << "] = " << n->value << ", "; //Print value
n = n->next; //Advance n
}
cout << endl;
return;
}
bool List::operator==(List & other)
{
bool truth = true; //Assume true
nodeptr n = head;
nodeptr m = other.head;
if(count == other.count) //If both are same length
{
if(count == 0) //If size is zero
{
if(head != other.head) //check to see if both heads are pointing at same place, only happening if NULL
{
truth = false;
}
else if(tail != other.tail) //check to see if both tails are point at same place, only happening if NULL
{
truth = false;
}
}
else //If non-zero size
{
while(n != NULL) //While the pointer hasn't fallen off of the cliff
{
if(n->value != m->value) //If current position is not equal
{
truth = false;
break; //break
}
n = n->next; //Advance pointers
m = m->next;
}
}
}
else //Not same size
{
truth = false;
}
return(truth);
}
void List::operator=(List other)
{
nodeptr n = head;
nodeptr m = other.head;
while(count != 0)
{
DeleteTail();
}
while(m != NULL)
{
AddTail(m->value);
m = m->next;
}
/*while(n != NULL) //Assumes equal length
{
n->value = m->value;
n = n->next;
m = m->next;
}*/
return;
}