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 */
37template <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};
64template <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
200template <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 =======================*/
270template <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 ===========================*/
281template <class T>
282VDKItem<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 ================================*/
295template <class T>
296int 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 ============*/
305template <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*/
327template <class T>
329 VDKItem<T>* p;
330 for(p = head; p && (p->x != x); p = p->next) ;
331return p ? p->x : (T*) 0;
332}
333
334/*
335============================
336remove a type<T>.
337Return a 1 or 0 (not removed)
338==============================
339*/
340template <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/*
366insert an item a <t> position
367*/
368template <class T>
369void VDKList<T>::insertVDKItem(VDKItem<T>* i, int pos)
370{
371int t = 0;
372VDKItem<T>* p = NULL;
373for(p = head; p && t < pos; p=p->next,t++)
374 ;
375if(!p)
376 addToTail(i);
377else 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 }
385else
386 addToHead(i);
387}
388
389#endif
390
391
392
393
394
Provides a reference semantic double linked list.
Definition: dlist.h:65
VDKList()
Definition: dlist.h:112
int at(T *x)
Definition: dlist.h:296
~VDKList()
Definition: dlist.h:123
void insertAt(T *t, int pos)
Definition: dlist.h:150
int remove(T *x)
Definition: dlist.h:341
void add(T *t)
Definition: dlist.h:129
int size()
Definition: dlist.h:181
void flush()
Definition: dlist.h:306
T * find(T *x)
Definition: dlist.h:328
T * operator[](int n)
Definition: dlist.h:172
Provides a VDKList iterator.
Definition: dlist.h:201
void operator++()
Definition: dlist.h:217
void last()
Definition: dlist.h:237
void operator--(int)
Definition: dlist.h:229
void operator--()
Definition: dlist.h:225
void operator++(int)
Definition: dlist.h:221
VDKListiterator(VDKList< T > &c)
Definition: dlist.h:209
T * current()
Definition: dlist.h:245
void first()
Definition: dlist.h:233
void restart()
Definition: dlist.h:261
virtual ~VDKListiterator()
Definition: dlist.h:213