1 //
2 // List.cc
3 //
4 // List: A List class which holds objects of type Object.
5 //
6 // Part of the ht://Dig package <http://www.htdig.org/>
7 // Copyright (c) 1999, 2000, 2001 The ht://Dig Group
8 // For copyright details, see the file COPYING in your distribution
9 // or the GNU General Public License version 2 or later
10 // <http://www.gnu.org/copyleft/gpl.html>
11 //
12 // $Id: List.cc,v 1.7 2001/06/29 14:14:08 loic Exp $
13 //
14
15 #ifdef HAVE_CONFIG_H
16 #include "config.h"
17 #endif /* HAVE_CONFIG_H */
18
19 #include "List.h"
20
21 class listnode
22 {
23 public:
24
25 listnode *next;
26 listnode *prev;
27 Object *object;
28 };
29
30
31 //*********************************************************************
32 // List::List()
33 // Constructor
34 //
List()35 List::List()
36 {
37 head = tail = 0;
38 number = 0;
39 }
40
41
42 //*********************************************************************
43 // List::~List()
44 // Destructor
45 //
~List()46 List::~List()
47 {
48 Destroy();
49 }
50
51
52 //*********************************************************************
53 // void List::Release()
54 // Release all the objects from our list.
55 //
Release()56 void List::Release()
57 {
58 listnode *node;
59 while (head)
60 {
61 node = head;
62 head = head->next;
63 delete node;
64 }
65 head = tail = 0;
66 number = 0;
67 cursor.Clear();
68 }
69
70
71 //*********************************************************************
72 // void List::Destroy()
73 // Delete all the objects from our list.
74 //
Destroy()75 void List::Destroy()
76 {
77 listnode *node;
78 while (head)
79 {
80 node = head;
81 head = head->next;
82 delete node->object;
83 delete node;
84 }
85 head = tail = 0;
86 number = 0;
87 cursor.Clear();
88 }
89
90
91 //*********************************************************************
92 // void List::Add(Object *object)
93 // Add an object to the list.
94 //
Add(Object * object)95 void List::Add(Object *object)
96 {
97 listnode *node = new listnode;
98 node->next = 0;
99 node->prev = tail;
100 node->object = object;
101 if (tail)
102 {
103 tail->next = node;
104 tail = node;
105 }
106 else
107 {
108 head = tail = node;
109 }
110
111 number++;
112 }
113
114
115 //*********************************************************************
116 // void List::Insert(Object *object, int position)
117 // Add an object to the list.
118 //
Insert(Object * object,int position)119 void List::Insert(Object *object, int position)
120 {
121 listnode *node = new listnode;
122 node->next = 0;
123 node->prev = 0;
124 node->object = object;
125
126 listnode *ln = head;
127
128 for (int i = 0; i < position && ln; i++, ln = ln->next)
129 ;
130 if (!ln)
131 {
132 node->prev = tail;
133 if (tail)
134 tail->next = node;
135 tail = node;
136
137 //
138 // The list is empty. This is a simple case, then.
139 //
140 if (!head)
141 head = node;
142 }
143 else
144 {
145 if (ln == head)
146 {
147 node->next = head;
148 node->next->prev = node;
149 head = node;
150 }
151 else
152 {
153 node->next = ln;
154 node->prev = ln->prev;
155 node->prev->next = node;
156 node->next->prev = node;
157 }
158 }
159
160 cursor.current_index = -1;
161 number++;
162 }
163
164
165 //*********************************************************************
166 // void List::Assign(Object *object, int position)
167 // Assign a new value to an index.
168 //
Assign(Object * object,int position)169 void List::Assign(Object *object, int position)
170 {
171 //
172 // First make sure that there is something there!
173 //
174 while (number < position + 1)
175 {
176 Add(0);
177 }
178
179 //
180 // Now find the listnode to put the new object in
181 //
182 listnode *temp = head;
183
184 for (int i = 0; temp && i < position; i++)
185 {
186 temp = temp->next;
187 }
188
189 cursor.current_index = -1;
190 delete temp->object;
191 temp->object = object;
192 }
193
194
195 //*********************************************************************
196 // int List::Remove(Object *object)
197 // Remove an object from the list.
198 //
Remove(Object * object)199 int List::Remove(Object *object)
200 {
201 listnode *node = head;
202 while (node)
203 {
204 if (node->object == object)
205 {
206 //
207 // Found it!
208 //
209 //
210 // If we are in the middle of a Get_Next() sequence, we need to
211 // fix up any problems with the current node.
212 //
213 if (cursor.current == node)
214 {
215 cursor.current = node->next;
216 }
217
218 if (head == tail)
219 {
220 head = tail = 0;
221 }
222 else if (head == node)
223 {
224 head = head->next;
225 head->prev = 0;
226 }
227 else if (tail == node)
228 {
229 tail = tail->prev;
230 tail->next = 0;
231 }
232 else
233 {
234 node->next->prev = node->prev;
235 node->prev->next = node->next;
236 }
237
238 delete node;
239 number--;
240 cursor.current_index = -1;
241 return 1;
242 }
243 node = node->next;
244 }
245 return 0;
246 }
247
248 //*********************************************************************
249 //
Remove(int position,int action)250 int List::Remove(int position, int action /* = LIST_REMOVE_DESTROY */)
251 {
252 Object *o = List::operator[](position);
253 if(action == LIST_REMOVE_DESTROY) delete o;
254 return List::Remove(o);
255 }
256
257 //*********************************************************************
258 // Object *List::Get_Next()
259 // Return the next object in the list.
260 //
Get_Next(ListCursor & cursor) const261 Object *List::Get_Next(ListCursor& cursor) const
262 {
263 listnode *temp = cursor.current;
264
265 if (cursor.current)
266 {
267 cursor.current = cursor.current->next;
268 if (cursor.current_index >= 0)
269 cursor.current_index++;
270 }
271 else
272 return 0;
273 return temp->object;
274 }
275
276
277 //*********************************************************************
278 // Object *List::Get_First()
279 // Return the first object in the list.
280 //
Get_First()281 Object *List::Get_First()
282 {
283 if (head)
284 return head->object;
285 else
286 return 0;
287 }
288
289
290 //*********************************************************************
291 // int List::Index(Object *obj)
292 // Return the index of an object in the list.
293 //
Index(Object * obj)294 int List::Index(Object *obj)
295 {
296 listnode *temp = head;
297 int index = 0;
298
299 while (temp && temp->object != obj)
300 {
301 temp = temp->next;
302 index++;
303 }
304 if (index >= number)
305 return -1;
306 else
307 return index;
308 }
309
310
311 //*********************************************************************
312 // Object *List::Next(Object *prev)
313 // Return the next object in the list. Using this, the list will
314 // appear as a circular list.
315 //
Next(Object * prev)316 Object *List::Next(Object *prev)
317 {
318 listnode *node = head;
319 while (node)
320 {
321 if (node->object == prev)
322 {
323 node = node->next;
324 if (!node)
325 return head->object;
326 else
327 return node->object;
328 }
329 node = node->next;
330 }
331
332 return 0;
333 }
334
335
336 //*********************************************************************
337 // Object *List::Previous(Object *prev)
338 // Return the previous object in the list. Using this, the list will
339 // appear as a circular list.
340 //
Previous(Object * prev)341 Object *List::Previous(Object *prev)
342 {
343 listnode *node = tail;
344 while (node)
345 {
346 if (node->object == prev)
347 {
348 node = node->prev;
349 if (!node)
350 return tail->object;
351 else
352 return node->object;
353 }
354 node = node->prev;
355 }
356
357 return 0;
358 }
359
360
361 //*********************************************************************
362 // Return the nth object in the list.
363 //
Nth(ListCursor & cursor,int n) const364 const Object *List::Nth(ListCursor& cursor, int n) const
365 {
366 if (n < 0 || n >= number)
367 return 0;
368
369 listnode *temp = head;
370
371 if (cursor.current_index == n)
372 return cursor.current->object;
373
374 if (cursor.current && cursor.current_index >= 0 && n == cursor.current_index + 1)
375 {
376 cursor.current = cursor.current->next;
377 if (!cursor.current)
378 {
379 cursor.current_index = -1;
380 return 0;
381 }
382 cursor.current_index = n;
383 return cursor.current->object;
384 }
385
386 for (int i = 0; temp && i < n; i++)
387 {
388 temp = temp->next;
389 }
390
391 if (temp)
392 {
393 cursor.current_index = n;
394 cursor.current = temp;
395 return temp->object;
396 }
397 else
398 return 0;
399 }
400
401
402 //*********************************************************************
403 // Object *List::Last()
404 // Return the last object inserted.
405 //
Last()406 Object *List::Last()
407 {
408 if (tail)
409 {
410 return tail->object;
411 }
412
413 return 0;
414 }
415
416 //*********************************************************************
417 //
Pop(int action)418 Object *List::Pop(int action /* = LIST_REMOVE_DESTROY */)
419 {
420 Object *o = 0;
421
422 if (tail) {
423 if(action == LIST_REMOVE_DESTROY) {
424 delete tail->object;
425 } else {
426 o = tail->object;
427 }
428 if(head == tail) {
429 head = tail = 0;
430 } else {
431 tail = tail->prev;
432 tail->next = 0;
433 }
434 }
435
436 return o;
437 }
438
439
440 //*********************************************************************
441 // Object *List::Copy() const
442 // Return a deep copy of the list.
443 //
Copy() const444 Object *List::Copy() const
445 {
446 List *list = new List;
447 ListCursor cursor;
448
449 Start_Get(cursor);
450 Object *obj;
451 while ((obj = Get_Next(cursor)))
452 {
453 list->Add(obj->Copy());
454 }
455 return list;
456 }
457
458
459 //*********************************************************************
460 // List &List::operator=(List &list)
461 // Return a deep copy of the list.
462 //
operator =(List & list)463 List &List::operator=(List &list)
464 {
465 Destroy();
466 list.Start_Get();
467 Object *obj;
468 while ((obj = list.Get_Next()))
469 {
470 Add(obj->Copy());
471 }
472 return *this;
473 }
474
475
476 //*********************************************************************
477 // void AppendList(List &list)
478 // Move contents of other list to the end of this list, and empty the
479 // other list.
480 //
AppendList(List & list)481 void List::AppendList(List &list)
482 {
483 // Never mind an empty list or ourselves.
484 if (list.number == 0 || &list == this)
485 return;
486
487 // Correct our pointers in head and tail.
488 if (tail)
489 {
490 // Link in other list.
491 tail->next = list.head;
492 list.head->prev = tail;
493
494 // Update members for added contents.
495 number += list.number;
496 tail = list.tail;
497 }
498 else
499 {
500 head = list.head;
501 tail = list.tail;
502 number = list.number;
503 }
504
505 // Clear others members to be an empty list.
506 list.head = list.tail = 0;
507 list.cursor.current = 0;
508 list.cursor.current_index = -1;
509 list.number = 0;
510 }
511