CircularLinkedList.h

00001 
00002 /*  A circular double linked list
00003   *  
00004   * Copyright (c) 2012 Bart Janssens
00005   *
00006   * Permission is hereby granted, free of charge, to any person obtaining a copy
00007   * of this software and associated documentation files (the "Software"), to deal
00008   * in the Software without restriction, including without limitation the rights
00009   * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
00010   * copies of the Software, and to permit persons to whom the Software is
00011   * furnished to do so, subject to the following conditions:
00012   *
00013   * The above copyright notice and this permission notice shall be included in
00014   * all copies or substantial portions of the Software.
00015   *
00016   * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
00017   * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
00018   * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
00019   * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
00020   * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
00021   * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
00022   * THE SOFTWARE.
00023   */
00024 template <typename T>
00025 class Node
00026 {
00027 public:  
00028   Node(T data) : data(data), next(NULL) {}
00029 //private:
00030   Node *next;
00031   Node *prev;
00032   T data;  
00033 };
00034 
00035 template <typename T>
00036 class CircularLinkedList
00037 {
00038 public:
00039   CircularLinkedList() : head(NULL),size(0) {}  //constructor
00040   ~CircularLinkedList(); // decunstructor
00041   bool isEmpty() { return (head == NULL);}  // is list Empty ?
00042   void moveForward(); // move cursor forward
00043   void moveBackward(); // move cursor backward
00044   void toHead(); // move cursor to head
00045   T * getNode();
00046   void addNode(T data);
00047   void deleteNode(T data);
00048   int getSize();
00049 private:
00050   Node<T> *head;
00051   Node<T> *cursor;
00052   int size;
00053 };
00054 
00055 template <typename T>
00056 CircularLinkedList<T>::~CircularLinkedList()
00057 {
00058   if (!isEmpty()) {
00059       Node<T> *tmp = head;
00060       while (tmp->next != head) {
00061           Node<T> *t = tmp;
00062           tmp = tmp->next;
00063           delete(t);
00064       }
00065       delete tmp;
00066       head = NULL;
00067   }
00068 }
00069 
00070 
00071 
00072 template <typename T>
00073 T * CircularLinkedList<T>::getNode()
00074 {
00075   return &(cursor->data);
00076 }
00077 
00078 template <typename T>
00079 void CircularLinkedList<T>::addNode(T data)
00080 {
00081   Node<T> * t = new Node<T>(data);
00082 
00083   if (isEmpty())
00084     {
00085       t->next = t;
00086       t->prev = t;
00087       head = t;
00088       size++;
00089       cursor = head;
00090       return;
00091     }
00092 
00093   Node<T> *tmp = head;
00094   while (tmp->next !=  head)
00095     {
00096       tmp = tmp->next;
00097     }
00098 
00099   tmp->next = t;
00100   t->next = head;
00101   t->prev = tmp;
00102   head->prev = t;
00103   size++;
00104 }
00105 
00106 template <typename T>
00107 void CircularLinkedList<T>::deleteNode(T data)
00108 {
00109   Node<T> *tmp = head;
00110   Node<T> *prev = NULL;
00111   while (tmp->next !=  head)
00112     {
00113       if (tmp->data == data) break;
00114       prev = tmp;
00115       tmp = tmp->next;
00116     }
00117 
00118   if (tmp == head)
00119     {
00120       while (tmp->next != head)
00121         {
00122           tmp = tmp->next;
00123         }
00124       tmp->next = head->next;
00125       head->next->prev = tmp
00126       delete head;
00127       size--;
00128       head = tmp->next;
00129     }
00130   else
00131     {
00132       prev->next = tmp->next;
00133       tmp->next->prev = prev;
00134       delete tmp;
00135       size--;
00136     }
00137 }
00138 
00139 template <typename T>
00140 void CircularLinkedList<T>::moveForward()
00141 {
00142     if (!isEmpty()) cursor = cursor->next;
00143 }
00144 
00145 template <typename T>
00146 void CircularLinkedList<T>::moveBackward()
00147 {
00148     if (!isEmpty()) cursor = cursor->prev;
00149 }
00150 
00151 template <typename T>
00152 void CircularLinkedList<T>::toHead()
00153 {
00154     cursor = head;
00155 }
00156 
00157 template <typename T>
00158 int CircularLinkedList<T>::getSize()
00159 {
00160     return size;
00161 }