Labels

doubly linked list implementation of complete system

input.txt:


5
8
2
3
4
5



main.cpp:

#include <iostream>
#include"my_Doubly.h"
#include <string>
#include <fstream>
using namespace std;

void takeAction()
{
cout<<"------>WELCOME TO DOUBLY LINK LIST SYSTEM<--------\n";
cout<<"------>PRESS 1 TO INSERT ELEMENTS FROM CONSOLE_INPUT<---\n";
cout<<"------>PRESS 2 TO DELETE AN ELEMENT<-----------------\n";
cout<<"------>PRESS 3 TO DELETE ALL ELEMENTS<---------------\n";
cout<<"------>PRESS 4 TO RETREIVE(Index-Wise) AN ELEMENT<---\n";
cout<<"------>PRESS 5 TO REVERSE LLIST<---------------------\n";
cout<<"------>PRESS 6 TO MERGE TWO LINK LISTS<--------------\n";
cout<<"------>PRESS 0 TO QUIT FROM THE MENU<----------------\n";
cout<<" NOTE:-->AT BEGINING PROGRAM TAKES INPUT FROM TXT FILE...\n";
}



int main()
{
int menu=-1;
my_Doubly<int>obj1;
my_Doubly<int>obj2;
int size=10;
ifstream file;
file.open( "input.txt" );


if(!file) {
cout << "the input file could not be opened" << endl;
}
else 
{
cout << "Opening file 1" << endl;

int s;
while (file >> s)
{

obj1.push_front(s); //attempting to create new node and use data read 
//from file
obj1.sort(true);
}
}

obj1.print();

do{
takeAction();
cout<<"\n PLEASE PROCEED FROM MENU \n";
cin>>menu;
if(menu==1)
{
obj1.push_front(1);
obj1.push_front(2);
obj1.push_front(3);
obj1.push_front(4);
obj1.push_front(5);
obj1.print();


}
if(menu==2)
{
int element=0;
cout<<" please enter an element to delete \n";
cin>>element;
obj1.Del_element(element);
obj1.print();
}
if(menu==3)
{

obj1.clearList();
obj1.print();

}
if(menu==4)
{

int index=0;
cout<<"please enter an index from where you want to retrieve back element \n";
cin>>index;
int Vaue=obj1.getValue(index);
cout<<"Value: "<<Vaue<<endl; 

}

if(menu==5)
{
obj1.reverse();
obj1.print();

}
if(menu==6)
{

obj2.push_front(6);
obj2.push_front(7);
obj2.push_front(8);
obj2.push_front(9);
obj2.push_front(10);
my_Doubly<int>obj3;
obj3=obj1+obj2;
obj3.sort(true);
obj3.print();
}


}while(menu!=0);

system("Pause");
return 0;
}



my_Doubly.h:


#include <iostream>

template <typename T>
class Node {
private:
T value;
public:
Node(T value);
T getValue();
void setValue(T value);
Node<T> *next;
Node<T> *prev;
};

template <typename T>
class my_Doubly {
private:
Node<T> *head, *tail;
int size;
void quickSort(my_Doubly<T> *list, size_t left, size_t right, bool type);

public:
my_Doubly();
my_Doubly(const my_Doubly & object);
my_Doubly(int quantity, T value);
~my_Doubly();
bool isEmpty();
int getSize();
T getValue(int id);
my_Doubly<T>& setValue(int id, T value);
my_Doubly<T>& clearList();
my_Doubly<T>& print();
my_Doubly<T>& push_back(T value);
my_Doubly<T>& push_front(T value);
T pop_back();
T pop_front();
my_Doubly<T>& insert(int id, T value);
my_Doubly<T>& reverse();
my_Doubly<T>& remove(int id);
my_Doubly<T>& Del_element(T value);
my_Doubly<T>& swap(int fid, int sid);
my_Doubly<T>& sort(bool type = true);
/* operators overload */
my_Doubly<T> operator+(const my_Doubly<T> & object);
my_Doubly<T> operator+(T value);
my_Doubly<T>& operator=(const my_Doubly<T> & object);
// friend ostream& operator << (ostream &fout, const my_Doubly<T> &list);

};




/*
================================= Definitions of class Node =================================
*/



template <typename T>
Node<T>::Node(T value) {
this->value = value;
next = NULL;
prev = NULL;
}

template <typename T>
T Node<T>::getValue() {
if (this) {
return value;
}
else {
cout<<"Can not get value of the Node";
}
}

template <typename T>
void Node<T>::setValue(T value) {
if (this) {
this->value = value;
}
else {
cout<<"Can not set value of the Node";
}
}

/*
============================== Definitions of class my_Doubly ==============================
*/
//constructors
template <typename T>
my_Doubly<T>::my_Doubly() : head(NULL), tail(NULL), size(0) {}

template <typename T>
my_Doubly<T>::my_Doubly(const my_Doubly & object) : head(NULL), tail(NULL), size(0) {
Node<T> *node = object.head;
while (node != NULL) {
push_back(node->getValue());
node = node->next;
}
}

template <typename T>
my_Doubly<T>::my_Doubly(int quantity, T value) : head(NULL), tail(NULL), size(0) {
for (int i = 0; i < quantity; i++) {
push_back(value);
}
}

//Destructor
template <typename T>
my_Doubly<T>::~my_Doubly() {
clearList();
delete head;
delete tail;
head = tail = NULL;
}

template <typename T>
int my_Doubly<T>::getSize() {
return size;
}

template <typename T>
bool my_Doubly<T>::isEmpty() {
if (head == NULL && tail == NULL && size == 0) {
return true;
}
return false;
}

template <typename T>
T my_Doubly<T>::getValue(int id) { // make better n/2
if (id >= 0 && id < size) {
Node<T> *item = head;
for (int i = 0; i < id; i++) {
item = item->next;
}
return item->getValue();
}
else {
cout<<"ID is out of range";
}
}

template <typename T>
my_Doubly<T>& my_Doubly<T>::setValue(int id, T value) { // make better n/2
if (id >= 0 && id < size) {
Node<T> *item = head;
for (int i = 0; i < id; i++) {
item = item->next;
}
item->setValue(value);
return *this;
}
else {
cout<<"ID is out of range";
}
}


template <typename T>
my_Doubly<T>& my_Doubly<T>::clearList() {
if (!isEmpty()) {
Node<T> *item = tail;
while (item != NULL) {
Node<T> *tmp = item;
item = item->prev;
delete tmp;
tmp = NULL;
}
head = tail = NULL;
size = 0;
}
return *this;
}

template <typename T>
my_Doubly<T>& my_Doubly<T>::print() {
if (!isEmpty()) {
Node<T> *node = head;
std::cout << "LIST" << std::endl;
while (node != NULL) {
if (node != tail) {
std::cout << " " << char(0xC3) << char(0xC4) << char(0xC4) << " " << node->getValue() << std::endl;
}
else {
std::cout << " " << char(0xC0) << char(0xC4) << char(0xC4) << " " << node->getValue() << std::endl;
}
node = node->next;
}
std::cout << std::endl;
return *this;
}
else {
cout<<"List is empty and can not be printed";
}
}

template <typename T>
my_Doubly<T>& my_Doubly<T>::push_back(T value) {
Node<T> *newnode = new Node<T>(value);
if (isEmpty()) {
head = tail = newnode;
size++;
}
else {
newnode->prev = tail;
tail->next = newnode;
tail = newnode;
size++;
}
return *this;
}

template <typename T>
my_Doubly<T>& my_Doubly<T>::push_front(T value) {
Node<T> *newnode = new Node<T>(value);
if (isEmpty()) {
head = tail = newnode;
size++;
}
else {
newnode->next = head;
head->prev = newnode;
head = newnode;
size++;
}
return *this;
}

template <typename T>
T my_Doubly<T>::pop_back() {
T tmp;
if (!isEmpty()) {
if (head == tail) {
tmp = tail->getValue();
head = tail = NULL;
size--;
return tmp;
}
else {
tmp = tail->getValue();
tail->prev->next = NULL;
tail = tail->prev;
size--;
return tmp;
}
}
else {
cout<<"List is empty and element can not be poped";
}
}

template <typename T>
T my_Doubly<T>::pop_front() {
T tmp;
if (!isEmpty()) {
if (head == tail) {
tmp = head->getValue();
head = tail = NULL;
size--;
return tmp;
}
else {
tmp = head->getValue();
head->next->prev = NULL;
head = head->next;
size--;
return tmp;
}
}
else {
cout<<"List is empty and element can not be poped";
}
}

template <typename T>
my_Doubly<T>& my_Doubly<T>::insert(int id, T value) { // make better n/2 as described in class
if (id >= 0 && id < size) {
if (id == 0) {
push_front(value);
}
else if (id == size - 1) {
push_back(value);
}
else {
Node<T> *newnode = new Node<T>(value);
Node<T> *node = head;
for (int i = 0; i < id; i++) {
node = node->next;
}
newnode->prev = node->prev;
newnode->next = node;
node->prev->next = newnode;
node->prev = newnode;
size++;
}
return *this;
}
else {
cout<<"ID is out of range";
}
}
//swap function for reversal of D.L.L
template <typename T>
my_Doubly<T>& my_Doubly<T>::swap(int fid, int sid) {
if (fid != sid && fid >= 0 && sid >= 0 && fid < size && sid < size) {
T tmp = getValue(fid);
setValue(fid, getValue(sid));
setValue(sid, tmp);
return *this;
}
else {
cout<<"ID is out of range";
}
}

//reversal functiom D.L.L
template <typename T>
my_Doubly<T>& my_Doubly<T>::reverse() {
if (size > 1) {
for (int i = 0; i < (size / 2); i++) {
swap(i, size - i - 1);
}
return *this;
}
else {
cout<<"The List is too small";
}
}

//removing an element function
template <typename T>
my_Doubly<T>& my_Doubly<T>::Del_element(T value) {
if (!isEmpty()) {
Node<T> *node = head;
int id = 0;
while (node != NULL) {
if (node->getValue() == value) {
Node<T> *tmp = node->next;
if (id == 0) {
pop_front();
}
else if (id == size - 1) {
pop_back();
}
else {
if (node->prev) node->prev->next = node->next;
if (node->next) node->next->prev = node->prev;
node->next = node->prev = NULL;
delete node;
node = NULL;
size--;
}
node = tmp;
}
else {
node = node->next;
id++;
}
}
return *this;
}
else {
cout<<"List is empty";
}
}


//quick sort algorithmic function for sort function
template <typename T>
void my_Doubly<T>::quickSort(my_Doubly<T> *list, size_t left, size_t right, bool type) {
size_t l = left;
size_t r = right - 1;
size_t size = right - left;

if (size > 1) {
T pivot = list->getValue(rand() % size + l);

if (type == true) {
while (l < r) {
while (list->getValue(r) > pivot && r > l) {
r--;
}

while (list->getValue(l) < pivot && l <= r) {
l++;
}

if (l < r) {
T tmp = list->getValue(l);
list->setValue(l, list->getValue(r));
list->setValue(r, tmp);
l++;
}
}
}
else {
while (l < r) {
while (list->getValue(r) < pivot && r > l) {
r--;
}

while (list->getValue(l) > pivot && l <= r) {
l++;
}

if (l < r) {
T tmp = list->getValue(l);
list->setValue(l, list->getValue(r));
list->setValue(r, tmp);
l++;
}
}
}

quickSort(list, left, l, type);
quickSort(list, r, right, type);
}
}
//sorting function
template <typename T>
my_Doubly<T>& my_Doubly<T>::sort(bool type = true) { // improve sort
if (!isEmpty() && size > 1) {
quickSort(this, 0, size, type);
return *this;
}
else {
cout<<"List is empty or too small";
}
}
//overloaded operator for merging
template <typename T>
my_Doubly<T> my_Doubly<T>::operator+(const my_Doubly<T> & object) {
my_Doubly<T> newlist;
Node<T> *node = this->head;
while (node != NULL) {
newlist.push_back(node->getValue());
node = node->next;
}
delete node;
node = object.head;
while (node != NULL) {
newlist.push_back(node->getValue());
node = node->next;
}
return newlist;
}
//overloaded operator for self merging
template <typename T>
my_Doubly<T> my_Doubly<T>::operator+(T value) {
my_Doubly<T> newlist;
Node<T> *node = this->head;
while (node != NULL) {
newlist.push_back(node->getValue());
node = node->next;
}
delete node;
node = NULL;
newlist.push_back(value);
return newlist;
}
//assignment overloaded operator
template <typename T>
my_Doubly<T>& my_Doubly<T>::operator=(const my_Doubly<T> & object) {
this->clearList();
Node<T> *node = object.head;
while (node != NULL) {
this->push_back(node->getValue());
node = node->next;
}
return *this;
}

//template <typename T>
//ostream& operator << (ostream &fout, const my_Doubly<T> &list)
//{
// list.print();
// return fout;
//}

Labels:

Comments

Post a Comment

Popular Posts