]> git.saurik.com Git - wxWidgets.git/blob - src/common/list.cpp
no message
[wxWidgets.git] / src / common / list.cpp
1 /////////////////////////////////////////////////////////////////////////////
2 // Name: list.cpp
3 // Purpose: wxList implementation
4 // Author: Julian Smart
5 // Modified by:
6 // Created: 04/01/98
7 // RCS-ID: $Id$
8 // Copyright: (c) Julian Smart and Markus Holzem
9 // Licence: wxWindows license
10 /////////////////////////////////////////////////////////////////////////////
11
12 #ifdef __GNUG__
13 #pragma implementation "list.h"
14 #endif
15
16 // For compilers that support precompilation, includes "wx.h".
17 #include "wx/wxprec.h"
18
19 #ifdef __BORLANDC__
20 #pragma hdrstop
21 #endif
22
23 #ifndef WX_PRECOMP
24 #include "wx/defs.h"
25 #include "wx/list.h"
26 #include "wx/utils.h"
27 #include <wx/intl.h>
28 #endif
29
30 // Sun CC compatibility (interference with xview/pkg.h, apparently...)
31 #if defined(SUN_CC) && defined(__XVIEW__)
32 #undef va_start
33 #undef va_end
34 #undef va_arg
35 #undef va_list
36 #endif
37
38 #include <stdarg.h>
39 #include <stdlib.h>
40 #include <string.h>
41
42 #if !USE_SHARED_LIBRARY
43 IMPLEMENT_DYNAMIC_CLASS(wxNode, wxObject)
44 IMPLEMENT_DYNAMIC_CLASS(wxList, wxObject)
45 IMPLEMENT_DYNAMIC_CLASS(wxStringList, wxList)
46 #endif
47
48 wxNode::wxNode (wxList * the_list, wxNode * last_one, wxNode * next_one,
49 wxObject * object)
50 {
51 data = object;
52 previous = last_one;
53 next = next_one;
54 list = the_list;
55 key.string = (char *) NULL;
56
57 if (previous)
58 previous->next = this;
59
60 if (next)
61 next->previous = this;
62 }
63
64 // Keyed constructor
65 wxNode::wxNode (wxList * the_list, wxNode * last_one, wxNode * next_one,
66 wxObject * object, long the_key)
67 {
68 data = object;
69 previous = last_one;
70 next = next_one;
71 list = the_list;
72 key.integer = the_key;
73
74 if (previous)
75 previous->next = this;
76
77 if (next)
78 next->previous = this;
79 }
80
81 wxNode::wxNode (wxList * the_list, wxNode * last_one, wxNode * next_one,
82 wxObject * object, const char *the_key)
83 {
84 data = object;
85 previous = last_one;
86 next = next_one;
87 list = the_list;
88 key.string = copystring (the_key);
89
90 if (previous)
91 previous->next = this;
92
93 if (next)
94 next->previous = this;
95 }
96
97
98 wxNode::~wxNode (void)
99 {
100 if (list)
101 list->n--;
102
103 if (list && list->destroy_data)
104 delete data;
105
106 if (list && list->key_type == wxKEY_STRING && key.string)
107 delete[]key.string;
108
109 // Make next node point back to the previous node from here
110 if (next)
111 next->previous = previous;
112 else if (list)
113 // If there's a new end of list (deleting the last one)
114 // make sure the list knows about it.
115 list->last_node = previous;
116
117 // Make the previous node point to the next node from here
118 if (previous)
119 previous->next = next;
120
121 // Or if no previous node (start of list), make sure list points at
122 // the next node which becomes the first!.
123 else if (list)
124 list->first_node = next;
125 }
126
127 wxList::wxList (void)
128 {
129 first_node = (wxNode *) NULL;
130 last_node = (wxNode *) NULL;
131 n = 0;
132 destroy_data = 0;
133 key_type = wxKEY_NONE;
134 }
135
136 wxList::wxList (int N, wxObject * Objects[])
137 {
138 wxNode *last = (wxNode *) NULL;
139
140 int i;
141 for (i = 0; i < N; i++)
142 {
143 wxNode *next = new wxNode (this, last, (wxNode *) NULL, Objects[i]);
144 last = next;
145 if (i == 0)
146 first_node = next;
147 }
148 last_node = last;
149 n = N;
150 key_type = wxKEY_NONE;
151 }
152
153 wxList::wxList (const unsigned int the_key_type)
154 {
155 n = 0;
156 destroy_data = 0;
157 first_node = (wxNode *) NULL;
158 last_node = (wxNode *) NULL;
159 key_type = the_key_type;
160 }
161
162 // Variable argument list, terminated by a zero
163 wxList::wxList (wxObject * first_one...)
164 {
165 // #ifndef __SGI__
166 va_list ap;
167
168 va_start (ap, first_one);
169
170 wxNode *last = new wxNode (this, (wxNode *) NULL, (wxNode *) NULL, first_one);
171 first_node = last;
172 n = 1;
173
174 for (;;)
175 {
176 wxObject *object = va_arg (ap, wxObject *);
177 // if (object == NULL) // Doesn't work in Windows -- segment is non-zero for NULL!
178 #ifdef __WXMSW__
179 if ((int) object == 0)
180 #else
181 if ((long) object == 0)
182 #endif
183 break;
184 else
185 {
186 wxNode *node = new wxNode (this, last, (wxNode *) NULL, object);
187 last = node;
188 n++;
189 }
190 }
191 last_node = last;
192 va_end (ap);
193
194 destroy_data = 0;
195 key_type = wxKEY_NONE;
196 /*
197 #else
198 fprintf (stderr, "Error: cannot use variable-argument functions on SGI!\n");
199 #endif
200 */
201 }
202
203 wxList::~wxList (void)
204 {
205 wxNode *each = first_node;
206 while (each)
207 {
208 wxNode *next = each->Next ();
209 delete each;
210 each = next;
211 }
212 }
213
214 wxNode *wxList::Append(wxObject *object)
215 {
216 wxNode *node = new wxNode(this, last_node, (wxNode *) NULL, object);
217 if (!first_node)
218 first_node = node;
219 last_node = node;
220 n ++;
221 return node;
222 }
223
224 wxNode *wxList::Nth (int i) const
225 {
226 int j = 0;
227 for (wxNode * current = First (); current; current = current->Next ())
228 {
229 if (j++ == i)
230 return current;
231 }
232 return (wxNode *) NULL; // No such element
233
234 }
235
236 wxNode *wxList::Find (long key) const
237 {
238 wxNode *current = First();
239 while (current)
240 {
241 if (current->key.integer == key)
242 return current;
243 current = current->Next();
244 }
245
246 return (wxNode *) NULL; // Not found!
247 }
248
249 wxNode *wxList::Find (const char *key) const
250 {
251 wxNode *current = First();
252 while (current)
253 {
254 if (!current->key.string)
255 {
256 wxFatalError (_("wxList: string key not present, probably did not Append correctly!"));
257 break;
258 }
259 if (strcmp (current->key.string, key) == 0)
260 return current;
261 current = current->Next();
262 }
263
264 return (wxNode *) NULL; // Not found!
265
266 }
267
268 wxNode *wxList::Member (wxObject * object) const
269 {
270 for (wxNode * current = First (); current; current = current->Next ())
271 {
272 wxObject *each = current->Data ();
273 if (each == object)
274 return current;
275 }
276 return (wxNode *) NULL;
277 }
278
279 bool wxList::DeleteNode (wxNode * node)
280 {
281 if (node)
282 {
283 delete node;
284 return TRUE;
285 }
286 return FALSE;
287 }
288
289 bool wxList::DeleteObject (wxObject * object)
290 {
291 // Search list for object
292 for (wxNode * current = first_node; current; current = current->Next ())
293 {
294 if (current->Data () == object)
295 {
296 delete current;
297 return TRUE;
298 }
299 }
300 return FALSE; // Did not find the object
301
302 }
303
304
305 // Insert new node at front of list
306 wxNode *wxList::Insert (wxObject * object)
307 {
308 wxNode *node = new wxNode (this, (wxNode *) NULL, First (), object);
309 first_node = node;
310
311 if (!(node->Next ()))
312 last_node = node;
313
314 n++;
315 return node;
316 }
317
318
319 // Insert new node before given node.
320 wxNode *wxList::Insert (wxNode * position, wxObject * object)
321 {
322 wxNode *prev = (wxNode *) NULL;
323 if (position)
324 prev = position->Previous ();
325
326 wxNode *node = new wxNode (this, prev, position, object);
327 if (!first_node)
328 {
329 first_node = node;
330 last_node = node;
331 }
332 if (!prev)
333 first_node = node;
334
335 n++;
336 return node;
337 }
338
339 // Keyed append
340 wxNode *wxList::Append (long key, wxObject * object)
341 {
342 wxNode *node = new wxNode (this, last_node, (wxNode *) NULL, object, key);
343 if (!first_node)
344 first_node = node;
345 last_node = node;
346 n++;
347 return node;
348 }
349
350 wxNode *wxList::Append (const char *key, wxObject * object)
351 {
352 wxNode *node = new wxNode (this, last_node, (wxNode *) NULL, object, key);
353 if (!first_node)
354 first_node = node;
355 last_node = node;
356 n++;
357 return node;
358 }
359
360 void wxList::Clear (void)
361 {
362 wxNode *current = first_node;
363 while (current)
364 {
365 wxNode *next = current->Next ();
366 delete current;
367 current = next;
368 }
369 first_node = (wxNode *) NULL;
370 last_node = (wxNode *) NULL;
371 n = 0;
372 }
373
374 //Executes function F with all items present in the list
375 void wxList::ForEach(wxListIterateFunction F)
376 {
377 wxNode *each = first_node;
378 while (each)
379 { (*F)( each->Data ());
380 each = each->Next();
381 }
382 }
383 // Returns a pointer to the item which returns TRUE with function F
384 // or NULL if no such item found
385 wxObject *wxList::FirstThat(wxListIterateFunction F)
386 {
387 wxNode *each = first_node;
388 while (each)
389 { if ((*F)( each->Data ())) return each->Data();
390 each = each->Next();
391 }
392 return (wxNode *) NULL;
393 }
394 // Like FirstThat, but proceeds from the end backward
395 wxObject *wxList::LastThat(wxListIterateFunction F)
396 {
397 wxNode *each = last_node;
398 while (each)
399 { if ((*F)( each->Data ())) return each->Data();
400 each = each->Previous();
401 }
402 return (wxNode *) NULL;
403 }
404
405 // (stefan.hammes@urz.uni-heidelberg.de)
406 //
407 // function for sorting lists. the concept is borrowed from 'qsort'.
408 // by giving a sort function, arbitrary lists can be sorted.
409 // method:
410 // - put wxObject pointers into an array
411 // - sort the array with qsort
412 // - put back the sorted wxObject pointers into the list
413 //
414 // CAVE: the sort function receives pointers to wxObject pointers (wxObject **),
415 // so dereference right!
416 // EXAMPLE:
417 // int listcompare(const void *arg1, const void *arg2)
418 // {
419 // return(compare(**(wxString **)arg1,
420 // **(wxString **)arg2));
421 // }
422 //
423 // void main()
424 // {
425 // wxList list;
426 //
427 // list.Append(new wxString("DEF"));
428 // list.Append(new wxString("GHI"));
429 // list.Append(new wxString("ABC"));
430 // list.Sort(listcompare);
431 // }
432
433 void wxList::Sort(const wxSortCompareFunction compfunc)
434 {
435 // allocate an array for the wxObject pointers of the list
436 const size_t num = Number();
437 wxObject **objArray = new wxObject *[num];
438 wxObject **objPtr = objArray;
439
440 // go through the list and put the pointers into the array
441 wxNode *node = First();
442 while(node!=NULL){
443 *objPtr++ = node->Data();
444 node = node->Next();
445 }
446 // sort the array
447 qsort((void *)objArray,num,sizeof(wxObject *),compfunc);
448 // put the sorted pointers back into the list
449 objPtr = objArray;
450 node = First();
451 while(node!=NULL){
452 node->SetData(*objPtr++);
453 node = node->Next();
454 }
455 // free the array
456 delete[] objArray;
457 }
458
459 /*
460 * String list
461 *
462 */
463
464 wxStringList::wxStringList (void):
465 wxList ()
466 {
467 }
468
469 wxStringList::wxStringList (const wxStringList& list)
470 {
471 (*this) = list;
472 }
473
474 // Variable argument list, terminated by a zero
475 // Makes new storage for the strings
476 wxStringList::wxStringList (const char *first...)
477 {
478 // #ifndef __SGI__
479 n = 0;
480 destroy_data = 0;
481 key_type = wxKEY_NONE;
482 first_node = (wxNode *) NULL;
483 last_node = (wxNode *) NULL;
484
485 if (!first)
486 return;
487
488 va_list ap;
489
490 va_start (ap, first);
491
492 wxNode *last = new wxNode (this, (wxNode *) NULL, (wxNode *) NULL, (wxObject *) copystring (first));
493 first_node = last;
494 n = 1;
495
496 for (;;)
497 {
498 char *s = va_arg (ap, char *);
499 // if (s == NULL)
500 #ifdef __WXMSW__
501 if ((int) s == 0)
502 #else
503 if ((long) s == 0)
504 #endif
505 break;
506 else
507 {
508 wxNode *node = new wxNode (this, last, (wxNode *) NULL, (wxObject *) copystring (s));
509 last = node;
510 n++;
511 }
512 }
513 last_node = last;
514 va_end (ap);
515 /*
516 #else
517 fprintf (stderr, "Error: cannot use variable-argument functions on SGI!\n");
518 #endif
519 */
520 }
521
522 wxStringList::~wxStringList (void)
523 {
524 Clear();
525 }
526
527 void wxStringList::Clear(void)
528 {
529 wxNode *each = First();
530 while (each)
531 {
532 char *s = (char *) each->Data ();
533 delete[]s;
534 wxNode *next = each->Next ();
535 delete each;
536 each = next;
537 }
538 wxList::Clear();
539 }
540
541 wxNode *wxStringList::Add (const char *s)
542 {
543 return Append ((wxObject *) (copystring (s)));
544 }
545
546 void wxStringList::Delete (const char *s)
547 {
548 for (wxNode * node = First (); node; node = node->Next ())
549 {
550 char *string = (char *) node->Data ();
551 if (string == s || strcmp (string, s) == 0)
552 {
553 delete[]string;
554 delete node;
555 break; // Done!
556
557 }
558 } // for
559
560 }
561
562 // Only makes new strings if arg is TRUE
563 char **wxStringList::ListToArray (bool new_copies) const
564 {
565 char **string_array = new char *[Number ()];
566 wxNode *node = First ();
567 int i;
568 for (i = 0; i < n; i++)
569 {
570 char *s = (char *) node->Data ();
571 if (new_copies)
572 string_array[i] = copystring (s);
573 else
574 string_array[i] = s;
575 node = node->Next ();
576 }
577 return string_array;
578 }
579
580 static int
581 wx_comparestrings (const void *arg1, const void *arg2)
582 {
583 char **s1 = (char **) arg1;
584 char **s2 = (char **) arg2;
585
586 return strcmp (*s1, *s2);
587 }
588
589 // Sort a list of strings - deallocates old nodes, allocates new
590 void wxStringList::Sort (void)
591 {
592 size_t N = n;
593 char **array = new char *[N];
594
595 size_t i = 0;
596 for (wxNode * node = First (); node; node = node->Next ())
597 array[i++] = (char *) node->Data ();
598
599 qsort (array, N, sizeof (char *), wx_comparestrings);
600 Clear ();
601
602 for (i = 0; i < N; i++)
603 Append ((wxObject *) (array[i]));
604
605 delete[]array;
606 }
607
608 // Checks whether s is a member of the list
609 bool wxStringList::Member (const char *s) const
610 {
611 for (wxNode * node = First (); node; node = node->Next ())
612 {
613 const char *s1 = (const char *) node->Data ();
614 if (s == s1 || strcmp (s, s1) == 0)
615 return TRUE;
616 }
617 return FALSE;
618 }
619
620 void wxStringList::operator= (const wxStringList& list)
621 {
622 Clear();
623
624 wxNode *node = list.First();
625 while (node)
626 {
627 char *s = (char *) node->Data ();
628 Add(s);
629 node = node->Next();
630 }
631 }
632
633 char* wxStringList::operator[] (int i) const
634 {
635 wxASSERT_MSG( (i < Number()), "Invalid index for wxStringList" );
636
637 return (char*) (Nth(i)->Data());
638 }
639