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

No comments:

Post a Comment