git.mutantstargoat.com Git - summerhack/blob - tools/curve_draw/linkedlist.h

   1 /*
   2 Copyright 2004 John Tsiombikas <nuclear@siggraph.org>
   3
   4 This file is part of the eternal demo.
   5
   6 The eternal library is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2 of the License, or
   9 (at your option) any later version.
  10
  11 The eternal demo is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with the eternal demo; if not, write to the Free Software
  18 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  19 */
  20 #ifndef _LINKEDLIST_H_
  21 #define _LINKEDLIST_H_
  22
  23 template <class T>
  24 struct ListNode {
  25         T data;
  26         ListNode<T> *next, *prev;
  27 };
  28
  29
  30 template <class T>
  31 class LinkedList {
  32 private:
  33         ListNode<T> *head, *tail;
  34         int sz;
  35
  36 public:
  37
  38         LinkedList();
  39         ~LinkedList();
  40
  41         inline ListNode<T> *begin();
  42         inline const ListNode<T> *begin() const;
  43         inline ListNode<T> *end();
  44         inline const ListNode<T> *end() const;
  45
  46         void push_back(ListNode<T> *node);
  47         void push_back(T data);
  48
  49         void insert(ListNode<T> *pos, ListNode<T> *node);
  50         void insert(ListNode<T> *pos, T data);
  51
  52         void remove(ListNode<T> *node);
  53         ListNode<T> *erase(ListNode<T> *node);
  54
  55         ListNode<T> *find(T key);
  56
  57         int count_nodes();
  58         inline int size() const;
  59
  60         void operator =(LinkedList &rhs);
  61 };
  62
  63
  64 /////////// implementation //////////
  65 template <class T>
  66 LinkedList<T>::LinkedList() {
  67         head = tail = 0;
  68         sz = 0;
  69 }
  70
  71
  72 template <class T>
  73 LinkedList<T>::~LinkedList() {
  74
  75         while(head) {
  76                 erase(head);
  77         }
  78 }
  79
  80 template <class T>
  81 ListNode<T> *LinkedList<T>::begin() {
  82         return head;
  83 }
  84
  85 template <class T>
  86 const ListNode<T> *LinkedList<T>::begin() const {
  87         return head;
  88 }
  89
  90 template <class T>
  91 ListNode<T> *LinkedList<T>::end() {
  92         return tail;
  93 }
  94
  95 template <class T>
  96 const ListNode<T> *LinkedList<T>::end() const {
  97         return tail;
  98 }
  99
 100 template <class T>
 101 void LinkedList<T>::push_back(ListNode<T> *node) {
 102
 103         if(!head) {             // empty list
 104                 head = tail = node;
 105                 node->next = node->prev = 0;
 106         } else {
 107                 tail->next = node;
 108                 node->prev = tail;
 109                 tail = node;
 110                 node->next = 0;
 111         }
 112
 113         sz++;
 114 }
 115
 116 template <class T>
 117 void LinkedList<T>::push_back(T data) {
 118
 119         ListNode<T> *node = new ListNode<T>;
 120         node->data = data;
 121
 122         if(!head) {             // empty list
 123                 head = tail = node;
 124                 node->next = node->prev = 0;
 125         } else {
 126                 tail->next = node;
 127                 node->prev = tail;
 128                 tail = node;
 129                 node->next = 0;
 130         }
 131
 132         sz++;
 133 }
 134
 135 template <class T>
 136 void LinkedList<T>::insert(ListNode<T> *pos, ListNode<T> *node) {
 137
 138         if(!head) {
 139                 head = tail = node;
 140                 node->next = node->prev = 0;
 141         } else {
 142                 node->prev = pos->prev;
 143                 pos->prev = node;
 144                 node->next = pos;
 145                 if(head == pos) head = node; else node->prev->next = node;
 146         }
 147
 148         sz++;
 149 }
 150
 151 template <class T>
 152 void LinkedList<T>::insert(ListNode<T> *pos, T data) {
 153
 154         ListNode<T> *node = new ListNode<T>;
 155         node->data = data;
 156
 157         if(!head) {
 158                 head = tail = node;
 159                 node->next = node->prev = 0;
 160         } else {
 161                 node->prev = pos->prev;
 162                 pos->prev = node;
 163                 node->next = pos;
 164                 if(head == pos) head = node; else node->prev->next = node;
 165         }
 166
 167         sz++;
 168 }
 169
 170 template <class T>
 171 void LinkedList<T>::remove(ListNode<T> *node) {
 172
 173         if(!node) return;       // e.g. remove(head) on an empty list
 174
 175         if(node->prev) {
 176                 node->prev->next = node->next;
 177         } else {
 178                 head = node->next;
 179         }
 180
 181         if(node->next) {
 182                 node->next->prev = node->prev;
 183         } else {
 184                 tail = node->prev;
 185         }
 186
 187         sz--;
 188 }
 189
 190 template <class T>
 191 ListNode<T> *LinkedList<T>::erase(ListNode<T> *node) {
 192
 193         if(!node) return 0;     // e.g. erase(head) on an empty list
 194
 195         if(node->prev) {
 196                 node->prev->next = node->next;
 197         } else {
 198                 head = node->next;
 199         }
 200
 201         if(node->next) {
 202                 node->next->prev = node->prev;
 203         } else {
 204                 tail = node->prev;
 205         }
 206
 207         ListNode<T> *destr = node;
 208         node = node->next;
 209
 210         delete destr;
 211
 212         sz--;
 213
 214         return node;
 215 }
 216
 217 template <class T>
 218 ListNode<T> *LinkedList<T>::find(T key) {
 219
 220         ListNode<T> *iter = head;
 221         while(iter) {
 222                 if(iter->data == key) return iter;
 223                 iter = iter->next;
 224         }
 225
 226         return 0;       // null pointer if not found
 227 }
 228
 229 template <class T>
 230 int LinkedList<T>::count_nodes() {
 231
 232         sz = 0;
 233
 234         ListNode<T> *iter = head;
 235         while(iter) {
 236                 sz++;
 237                 iter = iter->next;
 238         }
 239
 240         return sz;
 241 }
 242
 243 template <class T>
 244 int LinkedList<T>::size() const {
 245         return sz;
 246 }
 247
 248
 249 template <class T>
 250 void LinkedList<T>::operator =(LinkedList<T> &rhs) {
 251
 252         ListNode<T> *src = rhs.begin();
 253         while(src) {
 254                 push_back(src->data);
 255                 src = src->next;
 256         }
 257 }
 258
 259
 260 #endif  // _LINKEDLIST_H_