absence_thelab

annotate src/common/linkedlist.h @ 0:1cffe3409164

find changesets by author, revision, files, or words in the commit message
initial commit
author John Tsiombikas <nuclear@member.fsf.org>
date Thu, 23 Oct 2014 01:46:07 +0300
parents
children
rev   line source
nuclear@0 1 #ifndef _LINKEDLIST_H_
nuclear@0 2 #define _LINKEDLIST_H_
nuclear@0 3
nuclear@0 4 template <class T>
nuclear@0 5 struct ListNode {
nuclear@0 6 T data;
nuclear@0 7 ListNode<T> *next, *prev;
nuclear@0 8 };
nuclear@0 9
nuclear@0 10
nuclear@0 11 template <class T>
nuclear@0 12 class LinkedList {
nuclear@0 13 private:
nuclear@0 14 ListNode<T> *head, *tail;
nuclear@0 15 int size;
nuclear@0 16
nuclear@0 17 public:
nuclear@0 18
nuclear@0 19 LinkedList();
nuclear@0 20 ~LinkedList();
nuclear@0 21
nuclear@0 22 inline ListNode<T> *Begin();
nuclear@0 23 inline ListNode<T> *End();
nuclear@0 24
nuclear@0 25 void PushBack(ListNode<T> *node);
nuclear@0 26 void PushBack(T data);
nuclear@0 27
nuclear@0 28 void Insert(ListNode<T> *pos, ListNode<T> *node);
nuclear@0 29 void Insert(ListNode<T> *pos, T data);
nuclear@0 30
nuclear@0 31 void Remove(ListNode<T> *node);
nuclear@0 32 ListNode<T> *Erase(ListNode<T> *node);
nuclear@0 33
nuclear@0 34 ListNode<T> *Find(T key);
nuclear@0 35
nuclear@0 36 int CountNodes();
nuclear@0 37 inline int Size() const;
nuclear@0 38
nuclear@0 39 void operator =(LinkedList &rhs);
nuclear@0 40 };
nuclear@0 41
nuclear@0 42
nuclear@0 43 /////////// implementation //////////
nuclear@0 44 template <class T>
nuclear@0 45 LinkedList<T>::LinkedList() {
nuclear@0 46 head = tail = 0;
nuclear@0 47 size = 0;
nuclear@0 48 }
nuclear@0 49
nuclear@0 50
nuclear@0 51 template <class T>
nuclear@0 52 LinkedList<T>::~LinkedList() {
nuclear@0 53
nuclear@0 54 while(head) {
nuclear@0 55 Erase(head);
nuclear@0 56 }
nuclear@0 57 }
nuclear@0 58
nuclear@0 59 template <class T>
nuclear@0 60 ListNode<T> *LinkedList<T>::Begin() {
nuclear@0 61 return head;
nuclear@0 62 }
nuclear@0 63
nuclear@0 64 template <class T>
nuclear@0 65 ListNode<T> *LinkedList<T>::End() {
nuclear@0 66 return tail;
nuclear@0 67 }
nuclear@0 68
nuclear@0 69 template <class T>
nuclear@0 70 void LinkedList<T>::PushBack(ListNode<T> *node) {
nuclear@0 71
nuclear@0 72 if(!head) { // empty list
nuclear@0 73 head = tail = node;
nuclear@0 74 node->next = node->prev = 0;
nuclear@0 75 } else {
nuclear@0 76 tail->next = node;
nuclear@0 77 node->prev = tail;
nuclear@0 78 tail = node;
nuclear@0 79 node->next = 0;
nuclear@0 80 }
nuclear@0 81
nuclear@0 82 size++;
nuclear@0 83 }
nuclear@0 84
nuclear@0 85 template <class T>
nuclear@0 86 void LinkedList<T>::PushBack(T data) {
nuclear@0 87
nuclear@0 88 ListNode<T> *node = new ListNode<T>;
nuclear@0 89 node->data = data;
nuclear@0 90
nuclear@0 91 if(!head) { // empty list
nuclear@0 92 head = tail = node;
nuclear@0 93 node->next = node->prev = 0;
nuclear@0 94 } else {
nuclear@0 95 tail->next = node;
nuclear@0 96 node->prev = tail;
nuclear@0 97 tail = node;
nuclear@0 98 node->next = 0;
nuclear@0 99 }
nuclear@0 100
nuclear@0 101 size++;
nuclear@0 102 }
nuclear@0 103
nuclear@0 104 template <class T>
nuclear@0 105 void LinkedList<T>::Insert(ListNode<T> *pos, ListNode<T> *node) {
nuclear@0 106
nuclear@0 107 if(!head) {
nuclear@0 108 head = tail = node;
nuclear@0 109 node->next = node->prev = 0;
nuclear@0 110 } else {
nuclear@0 111 node->prev = pos->prev;
nuclear@0 112 pos->prev = node;
nuclear@0 113 node->next = pos;
nuclear@0 114 if(head == pos) head = node; else node->prev->next = node;
nuclear@0 115 }
nuclear@0 116
nuclear@0 117 size++;
nuclear@0 118 }
nuclear@0 119
nuclear@0 120 template <class T>
nuclear@0 121 void LinkedList<T>::Insert(ListNode<T> *pos, T data) {
nuclear@0 122
nuclear@0 123 ListNode<T> *node = new ListNode<T>;
nuclear@0 124 node->data = data;
nuclear@0 125
nuclear@0 126 if(!head) {
nuclear@0 127 head = tail = node;
nuclear@0 128 node->next = node->prev = 0;
nuclear@0 129 } else {
nuclear@0 130 node->prev = pos->prev;
nuclear@0 131 pos->prev = node;
nuclear@0 132 node->next = pos;
nuclear@0 133 if(head == pos) head = node; else node->prev->next = node;
nuclear@0 134 }
nuclear@0 135
nuclear@0 136 size++;
nuclear@0 137 }
nuclear@0 138
nuclear@0 139 template <class T>
nuclear@0 140 void LinkedList<T>::Remove(ListNode<T> *node) {
nuclear@0 141
nuclear@0 142 if(!node) return; // e.g. Remove(head) on an empty list
nuclear@0 143
nuclear@0 144 if(node->prev) {
nuclear@0 145 node->prev->next = node->next;
nuclear@0 146 } else {
nuclear@0 147 head = node->next;
nuclear@0 148 }
nuclear@0 149
nuclear@0 150 if(node->next) {
nuclear@0 151 node->next->prev = node->prev;
nuclear@0 152 } else {
nuclear@0 153 tail = node->prev;
nuclear@0 154 }
nuclear@0 155
nuclear@0 156 size--;
nuclear@0 157 }
nuclear@0 158
nuclear@0 159 template <class T>
nuclear@0 160 ListNode<T> *LinkedList<T>::Erase(ListNode<T> *node) {
nuclear@0 161
nuclear@0 162 if(!node) return 0; // e.g. Erase(head) on an empty list
nuclear@0 163
nuclear@0 164 if(node->prev) {
nuclear@0 165 node->prev->next = node->next;
nuclear@0 166 } else {
nuclear@0 167 head = node->next;
nuclear@0 168 }
nuclear@0 169
nuclear@0 170 if(node->next) {
nuclear@0 171 node->next->prev = node->prev;
nuclear@0 172 } else {
nuclear@0 173 tail = node->prev;
nuclear@0 174 }
nuclear@0 175
nuclear@0 176 ListNode<T> *destr = node;
nuclear@0 177 node = node->next;
nuclear@0 178
nuclear@0 179 delete destr;
nuclear@0 180
nuclear@0 181 size--;
nuclear@0 182
nuclear@0 183 return node;
nuclear@0 184 }
nuclear@0 185
nuclear@0 186 template <class T>
nuclear@0 187 ListNode<T> *LinkedList<T>::Find(T key) {
nuclear@0 188
nuclear@0 189 ListNode<T> *iter = head;
nuclear@0 190 while(iter) {
nuclear@0 191 if(iter->data == key) return iter;
nuclear@0 192 iter = iter->next;
nuclear@0 193 }
nuclear@0 194
nuclear@0 195 return 0; // null pointer if not found
nuclear@0 196 }
nuclear@0 197
nuclear@0 198 template <class T>
nuclear@0 199 int LinkedList<T>::CountNodes() {
nuclear@0 200
nuclear@0 201 size = 0;
nuclear@0 202
nuclear@0 203 ListNode<T> *iter = head;
nuclear@0 204 while(iter) {
nuclear@0 205 size++;
nuclear@0 206 iter = iter->next;
nuclear@0 207 }
nuclear@0 208
nuclear@0 209 return size;
nuclear@0 210 }
nuclear@0 211
nuclear@0 212 template <class T>
nuclear@0 213 int LinkedList<T>::Size() const {
nuclear@0 214 return size;
nuclear@0 215 }
nuclear@0 216
nuclear@0 217
nuclear@0 218 template <class T>
nuclear@0 219 void LinkedList<T>::operator =(LinkedList<T> &rhs) {
nuclear@0 220
nuclear@0 221 ListNode<T> *src = rhs.Begin();
nuclear@0 222 while(src) {
nuclear@0 223 PushBack(src->data);
nuclear@0 224 src = src->next;
nuclear@0 225 }
nuclear@0 226 }
nuclear@0 227
nuclear@0 228
nuclear@0 229 #endif // _LINKEDLIST_H_