1/************************************************************************* 2 $Header$ 3 FILE: slist.h 4 DESCR: Single linked list 5 AUTH: Jorn Lind 6 DATE: (C) 7*************************************************************************/ 8 9#ifndef _SLIST_H 10#define _SLIST_H 11 12#include <string.h> 13 14 15/* === Base void list ==================================================*/ 16 17class voidSList; 18 19class voidSList 20{ 21protected: 22 class voidSListElem 23 { 24 public: 25 void *data; 26 voidSListElem *next; 27 ~voidSListElem(void) { delete next; } 28 29 private: 30 voidSListElem(void *d) { data=d; next=NULL; } 31 friend voidSList; 32 }; 33 34public: 35 voidSList(void) { head=tail=NULL; len=0; } 36 ~voidSList(void) { delete head; } 37 void *append(void *); 38 void *append(voidSListElem *p, void *d); 39 void *insert(void *); 40 int size(void) const { return len; } 41 int empty(void) const { return len==0; } 42 void reverse(void); 43 void eraseHead(void); 44 void eraseAll(void) { delete head; head=tail=NULL; len=0; } 45 46protected: 47 int len; 48 voidSListElem *head, *tail; 49}; 50 51 52#ifdef IMPLEMENTSLIST 53 54void *voidSList::append(void *d) 55{ 56 voidSListElem *elem = new voidSListElem(d); 57 58 if (tail) 59 tail->next = elem; 60 else 61 head = elem; 62 63 tail = elem; 64 len++; 65 66 return elem->data; 67} 68 69 70void *voidSList::append(voidSListElem *p, void *d) 71{ 72 voidSListElem *elem = new voidSListElem(d); 73 74 if (p) 75 { 76 elem->next = p->next; 77 p->next = elem; 78 if (p == tail) 79 tail = p->next; 80 } 81 else 82 { 83 if (tail) 84 tail->next = elem; 85 else 86 head = elem; 87 tail = elem; 88 } 89 90 len++; 91 92 return elem->data; 93} 94 95 96void *voidSList::insert(void *d) 97{ 98 voidSListElem *elem = new voidSListElem(d); 99 100 if (tail == NULL) 101 tail = elem; 102 103 elem->next = head; 104 head = elem; 105 len++; 106 107 return elem->data; 108} 109 110 111void voidSList::reverse(void) 112{ 113 voidSListElem *newTail = head; 114 voidSListElem *tmpHead = NULL; 115 116 if (len < 2) 117 return ; 118 119 while (head != NULL) 120 { 121 voidSListElem *tmpNext = head->next; 122 123 head->next = tmpHead; 124 tmpHead = head; 125 126 head = tmpNext; 127 } 128 129 tail = newTail; 130 head = tmpHead; 131} 132 133 134void voidSList::eraseHead(void) 135{ 136 if (head != NULL) 137 { 138 head = head->next; 139 if (head == NULL) 140 tail = NULL; 141 len--; 142 } 143} 144 145#endif /* IMPLEMENTSLIST */ 146 147 148/* === Base void list ==================================================*/ 149 150//sorting 151 152template <class T> 153class SList : private voidSList 154{ 155public: 156 class ite 157 { 158 public: 159 ite(void) { next=NULL; } 160 ite(const ite &start) { next=start.next;} 161 ite(voidSListElem *start) { next=start; } 162 int more(void) const { return next!=NULL; } 163 ite &operator=(const ite &start) { next=start.next; return *this; } 164 ite operator++(void) 165 { if (next) next=next->next; return *this; } 166 ite operator++(int) 167 { ite tmp=*this; if (next) next=next->next; return tmp; } 168 T &operator*(void) const { return *((T*)next->data); } 169 int operator==(ite x) { return x.next==next; } 170 private: 171 voidSListElem *next; 172 friend SList<T>; 173 }; 174 175 ~SList(void) { for (ite x=first() ; x.more() ; x++) delete &(*x); } 176 T &append(const T &d) { return *((T*)voidSList::append(new T(d))); } 177 T &insert(const T &d) { return *((T*)voidSList::insert(new T(d))); } 178 T &head(void) const { return *((T*)voidSList::head->data); } 179 T &tail(void) const { return *((T*)voidSList::tail->data); } 180 ite first(void) const { return ite(voidSList::head); } 181 int empty(void) const { return voidSList::empty(); } 182 int size(void) const { return voidSList::size(); } 183 void reverse(void) { voidSList::reverse(); } 184 void filter(int (*)(T&)); 185 void append(SList<T> &l) 186 { for (ite x=l.first() ; x.more() ; x++) append(*x); } 187 T &append(ite &i, const T &d) 188 { return *((T*)voidSList::append(i.next, new T(d))); } 189 void eraseHead(void) 190 { delete ((T*)voidSList::head->data); voidSList::eraseHead(); } 191 void eraseAll(void) 192 { for (ite x=first() ; x.more() ; x++) delete &(*x); voidSList::eraseAll();} 193 void map(void (*f)(T&)) 194 { for (ite x=first() ; x.more() ; x++) f(*x); } 195}; 196 197 198template <class T> 199void SList<T>::filter(int (*f)(T&)) 200{ 201 voidSListElem *prev=NULL, *next=voidSList::head; 202 203 while (next) 204 { 205 if (f(*((T*)next->data))) 206 { 207 prev = next; 208 next = next->next; 209 } 210 else 211 { 212 voidSListElem *n = next->next; 213 214 if (prev == NULL) 215 voidSList::head = next->next; 216 else 217 prev->next = next->next; 218 if (voidSList::head == NULL) 219 voidSList::tail = NULL; 220 221 delete next->data; 222 next->next = NULL; 223 delete next; 224 225 next = n; 226 len--; 227 } 228 } 229} 230 231 232#endif /* _SLIST_H */ 233 234 235/* EOF */ 236