Tuesday 9 April 2013

Complete Double Linked List with class Template


Convert to template DLL from int DLL.

Source Files:

dll_template.h.
#ifndef __DLL_H__
#define __DLL_H__
template <class T>
class DLL;
template <class T>
class Node {
 T _data;
 Node<T>* _prev;
 Node<T>* _next;
 Node(T data, Node<T>* prev = (Node<T>*)0, Node<T>* next = (Node<T>*)0);
 friend class DLL<T>;
};
template <class T>
class DLL {
 Node<T>* _head;
 Node<T>* _curr;
 Node<T>* _tail;
 DLL(DLL<T>& D); // prevent copying
 DLL<T>& operator=(DLL<T>& D);
public:
 DLL();
 virtual ~DLL();
 void append(T data); // add after tail
 T remove();   // remove the current goes next if possible
 void insert(T data); // insert data before current
 T visit();   // returns data of current
 bool goHead();
 bool goTail();
 bool goNext();
 bool goPrev();
 bool isEmpty();
};
#endif

dll_template.cpp
#include "dll.h"

template <class T>
Node<T>::Node(T data, Node<T>* prev, Node<T>* next) {
 _data = data;
 _prev = prev;
 _next = next;
}
template <class T>
DLL<T>::DLL() {
 _head = (Node<T>*)0;
 _curr = (Node<T>*)0;
 _tail = (Node<T>*)0;
}
template <class T>
DLL<T>::~DLL() {
 while(!isEmpty()) {
  remove();
 }
}
template <class T>
void DLL<T>::append(T data) {
 if(isEmpty()) {
  Node<T>* newNode = new Node<T>(data);
  _head = newNode;
  _curr = newNode;
  _tail = newNode;
 }
 else {
  Node<T>* newNode = new Node<T>(data);
  newNode->_prev = _curr;
  _curr->_next = newNode;
  _tail = newNode;
  _curr = newNode;
 }
}
template <class T>
T DLL<T>::remove() {
 T data = 0;
 if(!isEmpty()) {
  Node<T>* ToDel = _curr;
  data = _curr->_data;
  if(_curr == _head && _curr == _tail) {
   _head = (Node<T>*)0;
   _curr = (Node<T>*)0;
   _tail = (Node<T>*)0;
   delete ToDel;
  }
  else if(_curr == _head) {
   _curr->_next->_prev = _curr->_prev;
   _head = _curr->_next;
   _curr = _head;
   delete ToDel;
  }
  else if(_curr == _tail) {
   _curr->_prev->_next = _curr->_next;
   _tail = _curr->_prev;
   _curr = _tail;
   delete ToDel;
  }
  else {
   _curr->_next->_prev = _curr->_prev;
   _curr->_prev->_next = _curr->_next;
   _curr = _curr->_next;
   delete ToDel;
  }
 }
 return data;
}
template <class T>
void DLL<T>::insert(T data) {
 Node<T>* newNode = new Node<T>(data);
 if(isEmpty()) {
  _head = newNode;
  _curr = newNode;
  _tail = newNode;
 }
 else if(_curr == _head) {
  newNode->_next = _head;
  _head->_prev = newNode;
  _head = newNode;
  _curr = newNode;
 }
 else {
  newNode->_prev = _curr->_prev;
  newNode->_next = _curr;
  _curr->_prev->_next = newNode;
  _curr->_prev = newNode;
  _curr = newNode;
 }
}
template <class T>
T DLL<T>::visit() {
 return _curr->_data;
}
template <class T>
bool DLL<T>::goHead() {
 _curr = _head;
 return true;
}
template <class T>
bool DLL<T>::goTail() {
 _curr = _tail;
 return true;
}
template <class T>
bool DLL<T>::goNext() {
 if(_curr != _tail) {
  _curr = _curr->_next;
  return true;
 }
 else {
  return false;
 }
}
template <class T>
bool DLL<T>::goPrev() {
 if(_curr != _head) {
  _curr = _curr->_prev;
  return true;
 }
 else {
  return false;
 }
}
template <class T>
bool DLL<T>::isEmpty() {
 return !_head && !_curr && !_tail;
}

dlltester_template.cpp
#include "dll.h"
#include "dll.cpp"
#include <iostream>
using namespace std;

template <class T>
void printList(DLL<T>& d){
    d.goHead();
}
template <class T>
ostream& operator<<(ostream& os, DLL<T>& d){
  int cur;
  bool done = false;
  for(cur=0;d.goPrev();cur++); // findout where is current
  do{
    os<<d.visit();
    done = !d.goNext();
    if(!done){
      os<<", ";
    }
  }while(!done);
  for(d.goHead();cur;d.goNext(), cur--); // set current to what it was before
  return os;
}
template <class T>
ostream& operator>>(ostream& os, DLL<T>& d){ // printing in reverse!!!!!
  int cur;
  bool done = false;
  for(cur=0;d.goNext();cur++); // findout where is current
  do{
    os<<d.visit();
    done = !d.goPrev();
    if(!done){
      os<<", ";
    }
  }while(!done);
  for(d.goTail();cur;d.goPrev(), cur--); // set current to what it was before
  return os;
}

int main(){
  DLL<int> d;
  for(int i=0;i<10;i++){
    d.append(i+1);
  }
  cout<<d<<endl;
  d.goHead();
  d.insert(1000);
  d.goNext();
  d.insert(2000);
  cout<<d<<endl;
  cout>>d<<endl;
  cout<<d.remove()<<endl;
  cout<<d<<endl;
  return 0;
}

Complete Double Linked List with a test file.

To do:
 - Code DLL.

Source Files:
dll.h file.
#ifndef __DLL_H__
#define __DLL_H__
class DLL;
class Node {
 int _data;
 Node* _prev;
 Node* _next;
 Node(int data, Node* prev = (Node*)0, Node* next = (Node*)0);
 friend class DLL;
};
class DLL {
 Node* _head;
 Node* _curr;
 Node* _tail;
 DLL(DLL& D); // prevent copying
 DLL& operator=(DLL& D);
public:
 DLL();
 virtual ~DLL();
 void append(int data); // add after tail
 int remove();   // remove the current goes next if possible
 void insert(int data); // insert data before current
 int visit();   // returns data of current
 bool goHead();
 bool goTail();
 bool goNext();
 bool goPrev();
 bool isEmpty();
};
#endif

dll.cpp file.
#include "dll.h"

Node::Node(int data, Node* prev, Node* next) {
 _data = data;
 _prev = prev;
 _next = next;
}

DLL::DLL() {
 _head = (Node*)0;
 _curr = (Node*)0;
 _tail = (Node*)0;
}
DLL::~DLL() {
 while(!isEmpty()) {
  remove();
 }
}
void DLL::append(int data) {
 if(isEmpty()) {
  Node* newNode = new Node(data);
  _head = newNode;
  _curr = newNode;
  _tail = newNode;
 }
 else {
  Node* newNode = new Node(data);
  newNode->_prev = _curr;
  _curr->_next = newNode;
  _tail = newNode;
  _curr = newNode;
 }
}
int DLL::remove() {
 int data = 0;
 if(!isEmpty()) {
  Node* ToDel = _curr;
  data = _curr->_data;
  if(_curr == _head && _curr == _tail) {
   _head = (Node*)0;
   _curr = (Node*)0;
   _tail = (Node*)0;
   delete ToDel;
  }
  else if(_curr == _head) {
   _curr->_next->_prev = _curr->_prev;
   _head = _curr->_next;
   _curr = _head;
   delete ToDel;
  }
  else if(_curr == _tail) {
   _curr->_prev->_next = _curr->_next;
   _tail = _curr->_prev;
   _curr = _tail;
   delete ToDel;
  }
  else {
   _curr->_next->_prev = _curr->_prev;
   _curr->_prev->_next = _curr->_next;
   _curr = _curr->_next;
   delete ToDel;
  }
 }
 return data;
}
void DLL::insert(int data) {
 Node* newNode = new Node(data);
 if(isEmpty()) {
  _head = newNode;
  _curr = newNode;
  _tail = newNode;
 }
 else if(_curr == _head) {
  newNode->_next = _head;
  _head->_prev = newNode;
  _head = newNode;
  _curr = newNode;
 }
 else {
  newNode->_prev = _curr->_prev;
  newNode->_next = _curr;
  _curr->_prev->_next = newNode;
  _curr->_prev = newNode;
  _curr = newNode;
 }
}
int DLL::visit() {
 return _curr->_data;
}
bool DLL::goHead() {
 _curr = _head;
 return true;
}
bool DLL::goTail() {
 _curr = _tail;
 return true;
}
bool DLL::goNext() {
 if(_curr != _tail) {
  _curr = _curr->_next;
  return true;
 }
 else {
  return false;
 }
}
bool DLL::goPrev() {
 if(_curr != _head) {
  _curr = _curr->_prev;
  return true;
 }
 else {
  return false;
 }
}
bool DLL::isEmpty() {
 return !_head && !_curr && !_tail;
}

dlltester.cpp file.
// provided by professor.
#include "dll.h"
#include <iostream>
using namespace std;

void printList(DLL& d){
    d.goHead();
}
ostream& operator<<(ostream& os, DLL& d){
  int cur;
  bool done = false;
  for(cur=0;d.goPrev();cur++); // findout where is current
  do{
    os<<d.visit();
    done = !d.goNext();
    if(!done){
      os<<", ";
    }
  }while(!done);
  for(d.goHead();cur;d.goNext(), cur--); // set current to what it was before
  return os;
}
ostream& operator>>(ostream& os, DLL& d){ // printing in reverse!!!!!
  int cur;
  bool done = false;
  for(cur=0;d.goNext();cur++); // findout where is current
  do{
    os<<d.visit();
    done = !d.goPrev();
    if(!done){
      os<<", ";
    }
  }while(!done);
  for(d.goTail();cur;d.goPrev(), cur--); // set current to what it was before
  return os;
}

int main(){
  DLL d;
  for(int i=0;i<10;i++){
    d.append(i+1);
  }
  cout<<d<<endl;
  d.goHead();
  d.insert(1000);
  d.goNext();
  d.insert(2000);
  cout<<d<<endl;
  cout>>d<<endl;
  cout<<d.remove()<<endl;
  cout<<d<<endl;
  return 0;
}

Queue add method

To do:
 - Do the add method of the Queue as exercise

Source Code:
Queue.h file
#pragma once
#ifndef __QUEUE_H__
#define __QUEUE_H__

class Queue;
class Node{
 int _data;
 Node* _next;
 Node(int data, Node* next= (Node*)0);
 friend class Queue;
};
class Queue{
private:
 Node* _head;
public:
 Queue();
 void add(int data);
 int remove();
 bool isEmpty();
 virtual ~Queue();
};
#endif


Queue.cpp file
#include "queue.h"  

Node::Node(int data, Node* next) {
 _data = data;
 _next = next;
}
Queue::Queue() {
 _head = (Node*)0;
}
void Queue::add(int data) {
 // 1 create node, and 2 point to next node
 Node* toAdd= new Node(data, _head);
 _head = toAdd; // 3 point to new node
}
int Queue::remove() {
 int ret = _head->_data;  // 1
 // int ret = (*_head)._data;  // 1 crazy but ok
 Node* toDel = _head;  // 2
 _head = _head->_next;  // 3 
 //  _head = toDel->_next; //  same as 3
 delete toDel; // 5
 return ret;
}
bool Queue::isEmpty() {
 /*if(_head == (Node*)0) {
  return true;
 }
 else {
  return false;
 }*/
 return _head == (Node*)0 ? true : false;
}
Queue::~Queue() {
 while(!isEmpty()) {
  remove();
 }
}