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