Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on Sep 24th, 2011  |  syntax: C++  |  size: 2.82 KB  |  views: 54  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #ifndef DEQUE_H_
  2. #define DEQUE_H_
  3.  
  4. #include <string>
  5. #include <iostream>
  6. #include <sstream>
  7.  
  8. using namespace std;
  9.  
  10. template <class T>
  11. struct Node {
  12.   T value;
  13.   Node<T> *next, *prev;
  14. };
  15.  
  16. template <class T>
  17. class Deque {
  18.   public:
  19.   Deque();
  20.   void PushBack(const T& item);
  21.   void PushFront(const T& item);
  22.   Node<T>* PopBack();
  23.   Node<T>* PopFront();
  24.   bool IsEmpty() { return head_ == NULL; }
  25.   string ToString();  
  26.  
  27.   private:
  28.   Node<T> *head_;
  29.   Node<T>* MakeNewNode(const T& item, Node<T>* next = 0, Node<T>* prev = 0);
  30. };
  31.  
  32. // From the point of view of the compiler, templates are not normal functions
  33. // or classes. They are compiled on demand, meaning that the code of a template
  34. // function is not compiled until an instantiation with specific template
  35. // arguments is required.
  36. //
  37. // Because templates are compiled when required, the implementation of a
  38. // template class or function must be in the same file as its declaration.
  39. template <class T>
  40. Deque<T>::Deque() {
  41.   head_ = NULL;
  42. }
  43.  
  44. template <class T>
  45. void Deque<T>::PushFront(const T& item) {
  46.   Node<T>* new_node;  
  47.   if (head_ == NULL) {
  48.     new_node = MakeNewNode(item);
  49.     new_node->next = new_node;
  50.     new_node->prev = new_node;
  51.   } else {
  52.     new_node = MakeNewNode(item, head_, head_->prev);
  53.     head_->prev->next = new_node;
  54.     head_->prev = new_node;
  55.   }
  56.   head_ = new_node;
  57. }
  58.  
  59. template <class T>
  60. void Deque<T>::PushBack(const T& item) {
  61.   Node<T>* new_node;  
  62.   if (head_ == NULL) {
  63.     new_node = MakeNewNode(item);
  64.     new_node->next = new_node;
  65.     new_node->prev = new_node;
  66.     head_ = new_node;
  67.   } else {
  68.     new_node = MakeNewNode(item, head_, head_->prev);
  69.     head_->prev->next = new_node;
  70.     head_->prev = new_node;
  71.   }
  72. }
  73.  
  74. template <class T>
  75. Node<T>* Deque<T>::PopFront() {  
  76.   if (head_ == NULL)
  77.     return NULL;
  78.  
  79.   Node<T>* node = head_;
  80.   if (head_ == head_->next) {
  81.     head_ = NULL;
  82.     return node;
  83.   }    
  84.   head_ = head_->next;
  85.   head_->prev = node->prev;
  86.   node->prev->next = head_;
  87.   return node;
  88. }
  89.  
  90. template <class T>
  91. Node<T>* Deque<T>::PopBack() {  
  92.   if (head_ == NULL)
  93.     return NULL;
  94.  
  95.   Node<T>* node = head_->prev;
  96.   if (head_ == head_->prev) {
  97.     head_ = NULL;
  98.     return node;
  99.   }    
  100.   head_->prev = node->prev;
  101.   node->prev->next = head_;
  102.   return node;
  103. }
  104.  
  105. template <class T>
  106. string Deque<T>::ToString() {
  107.   ostringstream oss;
  108.   if (IsEmpty())
  109.     return oss.str();
  110.   Node<T>* cursor = head_;
  111.   do {
  112.     oss << cursor->value << " ";
  113.     cursor = cursor->next;  
  114.   } while (cursor != head_);
  115.   return oss.str();
  116. }
  117.  
  118. template <class T>
  119. Node<T>* Deque<T>::MakeNewNode(const T& item, Node<T>* next, Node<T>* prev) {
  120.   Node<T> *node = new Node<T>;
  121.   node->value = item;
  122.   node->next = next;
  123.   node->prev = prev;
  124.   return node;
  125. }
  126. #endif // DEQUE_H_