Archive for March 21, 2012

#include <iostream>
using namespace std;

#include "tqueue.h"

template <class T>
void print(Tqueue<T>& Q){
  bool done = false;
  Q.goHead();
  cout<<"NULL <- [HEAD] ";
  if(!Q.isEmpty()){
    do{
      cout<<Q.visit();
      if(Q.goNext()) cout<<" <=> ";
      else{
        done = true;
      }
    }while(!done);
  }
  cout<<" [TAIL] -> NULL"<<endl;
  cout<<endl<<endl;
}

int main(){
  Tqueue<int> Q;
  cout<<"Before Data to be Added:"<<endl;
  print(Q);

  for(int i=1;i<=6;i+=1){
    Q.append((rand()%rand())%100+1);
  }
  cout<<"After Data Added Ramndomly:"<<endl;
  print(Q);

  cout<<"After Assending Order:"<<endl;
  Q.sort();
  print(Q);
  cout<<"After Dessending Order:"<<endl;
  Q.sort(0);
  print(Q);

  cout<<"Let's POP some data:"<<endl;
  cout<<Q.pop()<<endl;
  cout<<Q.pop()<<endl;
  cout<<Q.pop()<<endl<<endl;
  cout<<"After Poped some data:"<<endl;
  print(Q);

  cout<<"After Pushed some data:"<<endl;
  Q.push(111);
  Q.push(555);
  Q.push(999);
  print(Q);

  Q.append(55);
  cout<<"AFTER APPENDED A DATA:"<<endl;
  print(Q);


  cout<<"MOVE CURRENT TO SECOND NODE (if exist) AND USE INSERTBEFORE TO ADD 1234:"<<endl;
  Q.goHead();
  Q.goNext();
  Q.insertBefore(1234);
  print(Q);

  cout<<"MOVE CURRENT TO FIFTH NODE (if exist) AND USE INSERTAFTER TO ADD 1000:"<<endl;
  Q.goHead();
  Q.goNext();
  Q.goNext();
  Q.goNext();
  Q.goNext();
  Q.insertAfter(1000);
  print(Q);

  cout<<"MOVE CURRENT TO SECOND NODE (if exist) AND REMOVE:"<<endl;
  Q.goHead();
  Q.goNext();
  Q.removeCurrent();
  print(Q);

  getchar();
  return 0;
}

Double Linked List with Templates

Posted: March 21, 2012 in OOP344
#ifndef __TQUEUE_H__
#define __TQUEUE_H__

template <class T>
class Tqueue;

template <class T>
class Tqnode{
  Tqnode<T>* _next;
  Tqnode<T>* _prev;
  T _data;
  Tqnode(T data, 
    Tqnode<T>* prev = (Tqnode<T>*)0, 
    Tqnode<T>* next = (Tqnode<T>*)0):_data(data){
    _next = next;
    _prev = prev;
  }
  friend class Tqueue<T>;
};

template <class T>
class Tqueue{
  Tqnode<T>* _head;
  Tqnode<T>* _curr;
  Tqnode<T>* _tail;
public:
  Tqueue();
  virtual ~Tqueue();
  bool goNext();
  bool goPrev();
  bool goHead();
  bool goTail();
  bool isEmpty();
  void append(T data);// appends to tail
  T remove(); // removes the data from the head of the list
  void insertBefore(T data);  // before current (prev side)
  void insertAfter(T data);  // after current  (next side)
  T visit(); // returs the data of the current
  T removeCurrent(); // removes curent
  bool sort(bool Ascending = true);  // sorts the nodes
  void push(T data);
  T pop();

};

template <class T>
Tqueue<T>::Tqueue(){
  _head = _tail = _curr = (Tqnode<T>*)0;
}

template <class T>
Tqueue<T>::~Tqueue(){
  goHead();
  while(_curr){
    _head = _curr;
    _curr = _curr->_next;
    delete _head;
  }
}

template <class T>
T Tqueue<T>::visit(){ 
  return _curr->_data;
}

template <class T>
bool Tqueue<T>::sort(bool Ascending){
  Tqnode<T>* tmp = _curr = _head;
  bool done = false;
  goNext();
  while(tmp && tmp->_next){
    if((Ascending && tmp->_data > _curr->_data) || (!Ascending && tmp->_data < _curr->_data)){
      T buff = tmp->_data;
      tmp->_data = _curr->_data;
      _curr->_data = buff;
    }
    if(!goNext()){
      tmp = tmp->_next;
      if(tmp->_next) _curr = tmp->_next;
      else done = true;
    }
  }
  return done;
}

template <class T>
void Tqueue<T>::append(T data){ 
  _tail = new Tqnode<T>(data, _tail);
  if(_curr) _tail->_prev->_next = _tail;
  else _curr = _head = _tail;
}

template <class T>
T Tqueue<T>::remove(){
  T data = _head->_data;
  if(_head == _tail){
    delete _head;
    _head = _tail = _curr = (Tqnode<T>*)0;
  }
  else{
    Tqnode<T>* todel = _head;
    if(!_curr->_prev)_curr = _curr->_next;
    _head = _head->_next;
    _head->_prev = (Tqnode<T>*)0;
    delete todel;
  }
  return data;
}

template <class T>
void Tqueue<T>::insertBefore(T data){
  if(_curr){
    _curr = new Tqnode<T>(data, _curr->_prev, _curr);
    _curr->_next->_prev = _curr; 
    if(_curr->_prev) _curr->_prev->_next = _curr;
    else _head = _curr;
  }
  else _tail = _head = _curr = new Tqnode<T>(data);
}

template <class T>
void Tqueue<T>::insertAfter(T data){
  if(_curr){
    _curr = new Tqnode<T>(data, _curr, _curr->_next);
    _curr->_prev->_next = _curr; 
    if(_curr->_next) _curr->_next->_prev = _curr;
    else _tail = _curr;
  }
  else _tail = _head = _curr = new Tqnode<T>(data);
}

template <class T>
T Tqueue<T>::removeCurrent(){
  T data = _curr->_data;
  if(_curr == _head){
    data = remove();
  }
  else{
    Tqnode<T>* todel = _curr;
    if(_tail == _curr){
      _curr->_prev->_next = (Tqnode<T>*)0;
      _curr = _tail = _curr->_prev;
    }
    else{
      _curr->_prev->_next = _curr->_next;
      _curr->_next->_prev = _curr->_prev;
      _curr = _curr->_next;
    }
    delete todel;
  }
  return data;
}

template <class T>
void Tqueue<T>::push(T data){
  _head = new Tqnode<T>(data, (Tqnode<T>*)0, _head);
  if(_curr) _head->_next->_prev = _head;
  else _curr = _tail = _head;
}

template <class T>
T Tqueue<T>::pop(){
  return remove();
}

template <class T>
bool Tqueue<T>::isEmpty(){
  return !_curr;
}

template <class T>
bool Tqueue<T>::goTail(){
  bool res = false;
  if(_curr){  // is not null
    _curr = _tail;
    res = true;
  }
  return res;
}

template <class T>
bool Tqueue<T>::goHead(){
  bool res = false;
  if(_curr){  // is not null
    _curr = _head;
    res = true;
  }
  return res;
}

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

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

#endif