Tuesday, 9 April 2013

DLL Template


#ifndef __DLLTemp_H__
#define __DLLTemp_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);// just incase, review later
  friend class DLL<T>;
};

template <class T>
class DLL{
  Node<T>* _head;
  Node<T>* _curr;
  Node<T>* _tail;
  void copy(DLL<T>& D);
public:
  DLL();
  DLL(DLL<T>& D);
  virtual ~DLL();
  bool isEmpty();
  void append(T data);
  DLL<T>& operator=(DLL<T>& D);
  T remove();   // removes the current node and returns the data
  bool del();     // removes the current node returns false if is empty
  void insert(T data); // insterts before current
  bool goHead();
  bool goTail();
  bool goNext();
  bool goPrev();
  T visit();    // returns the current data
};

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 = _tail = _curr = 0;
}

template <class T>
DLL<T>::~DLL(){
  while(del());
}

template <class T>
void DLL<T>::copy(DLL<T>& D){
  int curpos;
  for(curpos=0;D.goPrev();curpos++); // findout where is current
  if(!D.isEmpty()){
    do{
      this->append(D.visit());
    }while(D.goNext());
  }
  for(D.goHead(), this->goHead();curpos;D.goNext(), this->goNext(),curpos--);
}

template <class T>
DLL<T>::DLL(DLL<T>& D){
  _head = _tail = _curr = 0;
  copy(D);
}

template <class T>
DLL<T>& DLL<T>::operator=(DLL<T>& D){
  while(del());
  copy(D);
  return *this;
}

template <class T>
void DLL<T>::append(T data){
  Node<T>* newnode = new Node<T>(data);
  if(_tail){  // ! empty
    _tail->_next = newnode;
    newnode->_prev = _tail;
    _tail = _curr = newnode;
  }
  else{
    _tail = _curr = _head = newnode;
  }
}

template <class T>
T DLL<T>::remove(){
  T data = visit();
  del();
  return data;
}

template <class T>
bool DLL<T>::del(){
  bool ok = false;
  if(_curr){
    ok = true;
    Node<T>* todel = _curr;
    if(_curr->_next){
      _curr->_next->_prev = _curr->_prev;
    }
    else{
      _tail = _tail->_prev;
    }
    if(_curr->_prev){
      _curr->_prev->_next = _curr->_next;
    }
    else{
      _head = _head->_next;
    }
    _curr = _curr->_next;
    delete todel;
  }
  return ok;
}

template <class T>
void DLL<T>::insert(T data){
  if(_head == _curr){
    _head = new Node<T>(data, (Node<T>*)0, _head);
    _curr->_prev = _head;
  }
  else {
    _curr->_prev = new Node<T>(data, _curr->_prev, _curr);
    _curr->_prev->_prev->_next = _curr->_prev;
  }
}

template <class T>
T DLL<T>::visit(){               // retruns data of current
return _curr->_data;
}

template <class T>
bool DLL<T>::goHead(){
  _curr = _head;
  return (_curr != 0);
}

template <class T>
bool DLL<T>::goTail(){
  _curr = _tail;
  return (_curr != 0);
}

template <class T>
bool DLL<T>::goNext(){
  bool rt = false;
  if(_curr->_next){
    rt = true;
    _curr = _curr->_next;
  }
  return rt;
}

template <class T>
bool DLL<T>::goPrev(){
bool rt = false;
  if(_curr->_prev){
    rt = true;
    _curr = _curr->_prev;
  }
  return rt;
}

template <class T>
bool DLL<T>::isEmpty(){
return !_head;
}



#endif

No comments:

Post a comment