vdk 2.4.0
dlist.h
1 /*
2  * ===========================
3  * VDK Visual Develeopment Kit
4  * Version 0.4
5  * October 1998
6  * ===========================
7  *
8  * Copyright (C) 1998, Mario Motta
9  * Developed by Mario Motta <mmotta@guest.net>
10  *
11  * This library is free software; you can redistribute it and/or
12  * modify it under the terms of the GNU Library General Public
13  * License as published by the Free Software Foundation; either
14  * version 2 of the License, or (at your option) any later version.
15  *
16  * This library is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19  * Library General Public License for more details.
20  *
21  * You should have received a copy of the GNU Library General Public
22  * License along with this library; if not, write to the Free Software
23  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
24  * 02111-1307, USA.
25  */
26 
27 #ifndef DLIST_H
28 #define DLIST_H
29 // just a cosmetic capitalizing (suggestion by Ionutz Borcoman)
30 #define VDKListIterator VDKListiterator
31 
32 /*
33  ============
34  VDKItem class
35  ============
36  */
37 template <class T> class VDKItem
38 {
39 
40  public:
41  T* x;
42  VDKItem* next,*prev;
43  VDKItem(T* x): x(x), next((VDKItem<T>*) 0),prev((VDKItem<T>*)0)
44  {
45  }
46 ~VDKItem()
47  {
48  }
49 };
64 template <class T> class VDKList
65 {
66 
67  VDKItem<T>* head,* tail;
68  int count;
69 
70  // append to list
71  void addToTail(VDKItem<T>* i)
72  {
73  if(! head) head = tail = i;
74  else { tail->next = i; i->prev=tail; tail = i; }
75  count++;
76  }
77  // over head loading
78  void addToHead(VDKItem<T>* i)
79  {
80  if(! head) head = tail = i;
81  else { head->prev = i; i->next = head; head = i; }
82  count++;
83  }
84  // insert at pos
85  void insertVDKItem(VDKItem<T>* i, int pos);
86 
87  // fetch an VDKItem at <n> position
88  VDKItem<T>* fetch(int n);
89 
90  // assign VDKItems to container
91  void assign(VDKList& l);
92  // on reference semantic copy-assign is prohibited
93  VDKList(VDKList& c)
94  {
95  count = 0;
96  head = tail = (VDKItem<T>* ) 0;
97  assign(c);
98  }
99 
100  VDKList& operator=(VDKList<T>& l)
101  {
102  // avoid l = l;
103  if(this != &l) { flush(); assign(l); }
104  return *this;
105  }
106 
107  /* class interface methods */
108  public:
112  VDKList() : head(0),tail(0),count(0) {}
123  ~VDKList() { flush(); }
129  void add(T* t)
130  {
131  if(!find(t))
132  addToTail(new VDKItem<T>(t));
133  }
139  void addH(T* t)
140  {
141  if(! find(t))
142  addToHead(new VDKItem<T>(t));
143  }
150  void insertAt(T* t, int pos)
151  {
152  if(!find(t))
153  insertVDKItem(new VDKItem<T>(t),pos);
154  }
159  T* find(T* x);
163  T* listhead() { return fetch(0)->x; }
168  int at(T* x);
172  T* operator[](int n) { return fetch(n)->x; }
177  int remove(T* x);
181  int size() { return count; }
185  void flush();
189  VDKItem<T>* Head() { return head; }
193  VDKItem<T>* Tail() { return tail; }
194 };
195 
200 template <class T> class VDKListiterator
201 {
202 
203  VDKItem<T> *head,*tail,*p;
204  public:
209  VDKListiterator(VDKList<T>& c) { p = head = c.Head(); tail = c.Tail(); }
213  virtual ~VDKListiterator() {}
217  void operator++() { p = p->next; }
221  void operator++(int) { p = p->next; }
225  void operator--() { p = p->prev; }
229  void operator--(int) { p = p->prev; }
233  void first() { p = head; }
237  void last() { p = tail; }
241  operator int() { return p != (VDKItem<T>*) 0; }
245  T* current() { return p->x; }
249  VDKItem<T>* Next(VDKItem<T> *t) { return t->next;}
253  VDKItem<T>* Head() { return head; }
257  T* Now(VDKItem<T> * t) { return t->x; }
261  void restart() { p = head; }
262 };
263 //
264 //NON-INLINE MEMBER FUNCTIONS
265 /*=======================
266  PRIVATE:
267  assign VDKItems copyng them
268  from another list
269  =======================*/
270 template <class T>
272 {
273  VDKListiterator<T> ci(l);
274  while(ci) { add(ci.current()); ci++; }
275 }
276 
277 /*==========================
278  PRIVATE:
279  fetch VDKItem<T> at n position
280  ===========================*/
281 template <class T>
282 VDKItem<T>* VDKList<T>::fetch(int n) {
283  int t = 0;
284  if(n >= count || n < 0) return (VDKItem<T>*) 0;
285  VDKItem<T>* p = head;
286  for( ;p && (t < n) ; t++, p = p->next);
287  return p;
288 }
289 /*================================
290  PRIVATE:
291  find ordinal position of VDKItem
292  containing a type<T> object,
293  return -1 if not found
294  ================================*/
295 template <class T>
296 int VDKList<T>::at(T* x) {
297  register int t = 0;
298  VDKItem<T>* p = head;
299  for(; p && (p->x != x);p = p->next,t++) ;
300  return p ? t : -1;
301 }
302 /*===========
303  flushes list
304  ============*/
305 template <class T>
307 {
308  VDKItem<T>*p = head;
309  VDKItem<T>*p1;
310  while(p) {
311  p1 = p->next;
312  delete p;
313  p = p1;
314  }
315  head = tail = 0;
316  count = 0;
317 }
318 /*
319  ============================
320  find(type<T>) , iterate
321  over container to find
322  an object.
323  hint: compare pointers only..
324  so is good only for identities..
325  ============================
326 */
327 template <class T>
329  VDKItem<T>* p;
330  for(p = head; p && (p->x != x); p = p->next) ;
331 return p ? p->x : (T*) 0;
332 }
333 
334 /*
335 ============================
336 remove a type<T>.
337 Return a 1 or 0 (not removed)
338 ==============================
339 */
340 template <class T>
342 {
343  VDKItem<T>* cur;
344  int n = at(x);
345  // object not found
346  if(n < 0) return 0;
347  else cur = fetch(n);
348  // removing head
349  if(cur == head) {
350  head = cur->next;
351  // one element list
352  if(head != (VDKItem<T>*) 0) head->prev = (VDKItem<T>*) 0;
353  else tail = (VDKItem<T>*) 0;
354  }
355  else { // remove tail or intermediate element
356  cur->prev->next = cur->next;
357  if(cur != tail) cur->next->prev = cur->prev;
358  // remove tail
359  else tail = cur->prev;
360  }
361  delete cur;
362  count--;
363  return 1;
364 }
365 /*
366 insert an item a <t> position
367 */
368 template <class T>
369 void VDKList<T>::insertVDKItem(VDKItem<T>* i, int pos)
370 {
371 int t = 0;
372 VDKItem<T>* p = NULL;
373 for(p = head; p && t < pos; p=p->next,t++)
374  ;
375 if(!p)
376  addToTail(i);
377 else if(p->prev)
378  {
379  p->prev->next = i;
380  i->prev = p->prev;
381  p->prev = i;
382  i->next = p;
383  count++;
384  }
385 else
386  addToHead(i);
387 }
388 
389 #endif
390 
391 
392 
393 
394