]>
Commit | Line | Data |
---|---|---|
c801d85f KB |
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" | |
1a5a8367 | 27 | #include <wx/intl.h> |
c801d85f KB |
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; | |
c67daf87 | 55 | key.string = (char *) NULL; |
c801d85f KB |
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 | { | |
c67daf87 UR |
129 | first_node = (wxNode *) NULL; |
130 | last_node = (wxNode *) NULL; | |
c801d85f KB |
131 | n = 0; |
132 | destroy_data = 0; | |
133 | key_type = wxKEY_NONE; | |
134 | } | |
135 | ||
debe6624 | 136 | wxList::wxList (int N, wxObject * Objects[]) |
c801d85f | 137 | { |
c67daf87 | 138 | wxNode *last = (wxNode *) NULL; |
c801d85f KB |
139 | |
140 | int i; | |
141 | for (i = 0; i < N; i++) | |
142 | { | |
c67daf87 | 143 | wxNode *next = new wxNode (this, last, (wxNode *) NULL, Objects[i]); |
c801d85f KB |
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; | |
c67daf87 UR |
157 | first_node = (wxNode *) NULL; |
158 | last_node = (wxNode *) NULL; | |
c801d85f KB |
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 | ||
c67daf87 | 170 | wxNode *last = new wxNode (this, (wxNode *) NULL, (wxNode *) NULL, first_one); |
c801d85f KB |
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! | |
2049ba38 | 178 | #ifdef __WXMSW__ |
c801d85f KB |
179 | if ((int) object == 0) |
180 | #else | |
181 | if ((long) object == 0) | |
182 | #endif | |
183 | break; | |
184 | else | |
185 | { | |
c67daf87 | 186 | wxNode *node = new wxNode (this, last, (wxNode *) NULL, object); |
c801d85f KB |
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 | ||
c801d85f KB |
214 | wxNode *wxList::Append(wxObject *object) |
215 | { | |
c67daf87 | 216 | wxNode *node = new wxNode(this, last_node, (wxNode *) NULL, object); |
c801d85f KB |
217 | if (!first_node) |
218 | first_node = node; | |
219 | last_node = node; | |
220 | n ++; | |
221 | return node; | |
222 | } | |
223 | ||
debe6624 | 224 | wxNode *wxList::Nth (int i) const |
c801d85f KB |
225 | { |
226 | int j = 0; | |
227 | for (wxNode * current = First (); current; current = current->Next ()) | |
228 | { | |
229 | if (j++ == i) | |
230 | return current; | |
231 | } | |
c67daf87 | 232 | return (wxNode *) NULL; // No such element |
c801d85f KB |
233 | |
234 | } | |
235 | ||
debe6624 | 236 | wxNode *wxList::Find (long key) const |
c801d85f KB |
237 | { |
238 | wxNode *current = First(); | |
239 | while (current) | |
240 | { | |
241 | if (current->key.integer == key) | |
242 | return current; | |
243 | current = current->Next(); | |
244 | } | |
245 | ||
c67daf87 | 246 | return (wxNode *) NULL; // Not found! |
c801d85f KB |
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 | { | |
1a5a8367 | 256 | wxFatalError (_("wxList: string key not present, probably did not Append correctly!")); |
c801d85f KB |
257 | break; |
258 | } | |
259 | if (strcmp (current->key.string, key) == 0) | |
260 | return current; | |
261 | current = current->Next(); | |
262 | } | |
263 | ||
c67daf87 | 264 | return (wxNode *) NULL; // Not found! |
c801d85f KB |
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 | } | |
c67daf87 | 276 | return (wxNode *) NULL; |
c801d85f KB |
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 | { | |
c67daf87 | 308 | wxNode *node = new wxNode (this, (wxNode *) NULL, First (), object); |
c801d85f KB |
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 | { | |
c67daf87 | 322 | wxNode *prev = (wxNode *) NULL; |
c801d85f KB |
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 | |
debe6624 | 340 | wxNode *wxList::Append (long key, wxObject * object) |
c801d85f | 341 | { |
c67daf87 | 342 | wxNode *node = new wxNode (this, last_node, (wxNode *) NULL, object, key); |
c801d85f KB |
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 | { | |
c67daf87 | 352 | wxNode *node = new wxNode (this, last_node, (wxNode *) NULL, object, key); |
c801d85f KB |
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 | } | |
c67daf87 UR |
369 | first_node = (wxNode *) NULL; |
370 | last_node = (wxNode *) NULL; | |
c801d85f KB |
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 | } | |
c67daf87 | 392 | return (wxNode *) NULL; |
c801d85f KB |
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 | } | |
c67daf87 | 402 | return (wxNode *) NULL; |
c801d85f KB |
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 | // Variable argument list, terminated by a zero | |
470 | // Makes new storage for the strings | |
471 | wxStringList::wxStringList (const char *first...) | |
472 | { | |
473 | // #ifndef __SGI__ | |
474 | n = 0; | |
475 | destroy_data = 0; | |
476 | key_type = wxKEY_NONE; | |
c67daf87 UR |
477 | first_node = (wxNode *) NULL; |
478 | last_node = (wxNode *) NULL; | |
c801d85f KB |
479 | |
480 | if (!first) | |
481 | return; | |
482 | ||
483 | va_list ap; | |
484 | ||
485 | va_start (ap, first); | |
486 | ||
c67daf87 | 487 | wxNode *last = new wxNode (this, (wxNode *) NULL, (wxNode *) NULL, (wxObject *) copystring (first)); |
c801d85f KB |
488 | first_node = last; |
489 | n = 1; | |
490 | ||
491 | for (;;) | |
492 | { | |
493 | char *s = va_arg (ap, char *); | |
494 | // if (s == NULL) | |
2049ba38 | 495 | #ifdef __WXMSW__ |
c801d85f KB |
496 | if ((int) s == 0) |
497 | #else | |
498 | if ((long) s == 0) | |
499 | #endif | |
500 | break; | |
501 | else | |
502 | { | |
c67daf87 | 503 | wxNode *node = new wxNode (this, last, (wxNode *) NULL, (wxObject *) copystring (s)); |
c801d85f KB |
504 | last = node; |
505 | n++; | |
506 | } | |
507 | } | |
508 | last_node = last; | |
509 | va_end (ap); | |
510 | /* | |
511 | #else | |
512 | fprintf (stderr, "Error: cannot use variable-argument functions on SGI!\n"); | |
513 | #endif | |
514 | */ | |
515 | } | |
516 | ||
517 | wxStringList::~wxStringList (void) | |
518 | { | |
519 | wxNode *each = first_node; | |
520 | while (each) | |
521 | { | |
522 | char *s = (char *) each->Data (); | |
523 | delete[]s; | |
524 | wxNode *next = each->Next (); | |
525 | delete each; | |
526 | each = next; | |
527 | } | |
528 | } | |
529 | ||
530 | wxNode *wxStringList::Add (const char *s) | |
531 | { | |
532 | return Append ((wxObject *) (copystring (s))); | |
533 | } | |
534 | ||
535 | void wxStringList::Delete (const char *s) | |
536 | { | |
537 | for (wxNode * node = First (); node; node = node->Next ()) | |
538 | { | |
539 | char *string = (char *) node->Data (); | |
540 | if (string == s || strcmp (string, s) == 0) | |
541 | { | |
542 | delete[]string; | |
543 | delete node; | |
544 | break; // Done! | |
545 | ||
546 | } | |
547 | } // for | |
548 | ||
549 | } | |
550 | ||
551 | // Only makes new strings if arg is TRUE | |
debe6624 | 552 | char **wxStringList::ListToArray (bool new_copies) const |
c801d85f KB |
553 | { |
554 | char **string_array = new char *[Number ()]; | |
555 | wxNode *node = First (); | |
556 | int i; | |
557 | for (i = 0; i < n; i++) | |
558 | { | |
559 | char *s = (char *) node->Data (); | |
560 | if (new_copies) | |
561 | string_array[i] = copystring (s); | |
562 | else | |
563 | string_array[i] = s; | |
564 | node = node->Next (); | |
565 | } | |
566 | return string_array; | |
567 | } | |
568 | ||
569 | static int | |
570 | wx_comparestrings (const void *arg1, const void *arg2) | |
571 | { | |
572 | char **s1 = (char **) arg1; | |
573 | char **s2 = (char **) arg2; | |
574 | ||
575 | return strcmp (*s1, *s2); | |
576 | } | |
577 | ||
578 | // Sort a list of strings - deallocates old nodes, allocates new | |
579 | void wxStringList::Sort (void) | |
580 | { | |
581 | size_t N = n; | |
582 | char **array = new char *[N]; | |
583 | ||
584 | size_t i = 0; | |
585 | for (wxNode * node = First (); node; node = node->Next ()) | |
586 | array[i++] = (char *) node->Data (); | |
587 | ||
588 | qsort (array, N, sizeof (char *), wx_comparestrings); | |
589 | Clear (); | |
590 | ||
591 | for (i = 0; i < N; i++) | |
592 | Append ((wxObject *) (array[i])); | |
593 | ||
594 | delete[]array; | |
595 | } | |
596 | ||
597 | // Checks whether s is a member of the list | |
598 | bool wxStringList::Member (const char *s) const | |
599 | { | |
600 | for (wxNode * node = First (); node; node = node->Next ()) | |
601 | { | |
602 | const char *s1 = (const char *) node->Data (); | |
603 | if (s == s1 || strcmp (s, s1) == 0) | |
604 | return TRUE; | |
605 | } | |
606 | return FALSE; | |
607 | } |