]> git.saurik.com Git - wxWidgets.git/blob - src/common/list.cpp
Remove all lines containing cvs/svn "$Id$" keyword.
[wxWidgets.git] / src / common / list.cpp
1 ////////////////////////////////////////////////////////////////////////////////
2 // Name: src/common/list.cpp
3 // Purpose: wxList implementation
4 // Author: Julian Smart
5 // Modified by: VZ at 16/11/98: WX_DECLARE_LIST() and typesafe lists added
6 // Created: 04/01/98
7 // Copyright: (c) Julian Smart
8 // Licence: wxWindows licence
9 ////////////////////////////////////////////////////////////////////////////////
10
11 // =============================================================================
12 // declarations
13 // =============================================================================
14
15 // -----------------------------------------------------------------------------
16 // headers
17 // -----------------------------------------------------------------------------
18
19 // For compilers that support precompilation, includes "wx.h".
20 #include "wx/wxprec.h"
21
22 #ifdef __BORLANDC__
23 #pragma hdrstop
24 #endif
25
26 #include <stdarg.h>
27 #include <stdlib.h>
28 #include <string.h>
29
30 #ifndef WX_PRECOMP
31 #include "wx/list.h"
32 #include "wx/crt.h"
33 #endif
34
35 #if !wxUSE_STD_CONTAINERS
36
37 // =============================================================================
38 // implementation
39 // =============================================================================
40
41 // -----------------------------------------------------------------------------
42 // wxListKey
43 // -----------------------------------------------------------------------------
44 wxListKey wxDefaultListKey;
45
46 bool wxListKey::operator==(wxListKeyValue value) const
47 {
48 switch ( m_keyType )
49 {
50 default:
51 wxFAIL_MSG(wxT("bad key type."));
52 // let compiler optimize the line above away in release build
53 // by not putting return here...
54
55 case wxKEY_STRING:
56 return *m_key.string == *value.string;
57
58 case wxKEY_INTEGER:
59 return m_key.integer == value.integer;
60 }
61 }
62
63 // -----------------------------------------------------------------------------
64 // wxNodeBase
65 // -----------------------------------------------------------------------------
66
67 wxNodeBase::wxNodeBase(wxListBase *list,
68 wxNodeBase *previous, wxNodeBase *next,
69 void *data, const wxListKey& key)
70 {
71 m_list = list;
72 m_data = data;
73 m_previous = previous;
74 m_next = next;
75
76 switch ( key.GetKeyType() )
77 {
78 case wxKEY_NONE:
79 break;
80
81 case wxKEY_INTEGER:
82 m_key.integer = key.GetNumber();
83 break;
84
85 case wxKEY_STRING:
86 // to be free()d later
87 m_key.string = new wxString(key.GetString());
88 break;
89
90 default:
91 wxFAIL_MSG(wxT("invalid key type"));
92 }
93
94 if ( previous )
95 previous->m_next = this;
96
97 if ( next )
98 next->m_previous = this;
99 }
100
101 wxNodeBase::~wxNodeBase()
102 {
103 // handle the case when we're being deleted from the list by the user (i.e.
104 // not by the list itself from DeleteNode) - we must do it for
105 // compatibility with old code
106 if ( m_list != NULL )
107 {
108 if ( m_list->m_keyType == wxKEY_STRING )
109 {
110 delete m_key.string;
111 }
112
113 m_list->DetachNode(this);
114 }
115 }
116
117 int wxNodeBase::IndexOf() const
118 {
119 wxCHECK_MSG( m_list, wxNOT_FOUND, wxT("node doesn't belong to a list in IndexOf"));
120
121 // It would be more efficient to implement IndexOf() completely inside
122 // wxListBase (only traverse the list once), but this is probably a more
123 // reusable way of doing it. Can always be optimized at a later date (since
124 // IndexOf() resides in wxListBase as well) if efficiency is a problem.
125 int i;
126 wxNodeBase *prev = m_previous;
127
128 for( i = 0; prev; i++ )
129 {
130 prev = prev->m_previous;
131 }
132
133 return i;
134 }
135
136 // -----------------------------------------------------------------------------
137 // wxListBase
138 // -----------------------------------------------------------------------------
139
140 void wxListBase::Init(wxKeyType keyType)
141 {
142 m_nodeFirst =
143 m_nodeLast = NULL;
144 m_count = 0;
145 m_destroy = false;
146 m_keyType = keyType;
147 }
148
149 wxListBase::wxListBase(size_t count, void *elements[])
150 {
151 Init();
152
153 for ( size_t n = 0; n < count; n++ )
154 {
155 Append(elements[n]);
156 }
157 }
158
159 void wxListBase::DoCopy(const wxListBase& list)
160 {
161 wxASSERT_MSG( !list.m_destroy,
162 wxT("copying list which owns it's elements is a bad idea") );
163
164 m_destroy = list.m_destroy;
165 m_keyType = list.m_keyType;
166 m_nodeFirst =
167 m_nodeLast = NULL;
168
169 switch (m_keyType)
170 {
171 case wxKEY_INTEGER:
172 {
173 for ( wxNodeBase *node = list.GetFirst(); node; node = node->GetNext() )
174 {
175 Append(node->GetKeyInteger(), node->GetData());
176 }
177 break;
178 }
179
180 case wxKEY_STRING:
181 {
182 for ( wxNodeBase *node = list.GetFirst(); node; node = node->GetNext() )
183 {
184 Append(node->GetKeyString(), node->GetData());
185 }
186 break;
187 }
188
189 default:
190 {
191 for ( wxNodeBase *node = list.GetFirst(); node; node = node->GetNext() )
192 {
193 Append(node->GetData());
194 }
195 break;
196 }
197 }
198
199 wxASSERT_MSG( m_count == list.m_count, wxT("logic error in wxList::DoCopy") );
200 }
201
202 wxListBase::~wxListBase()
203 {
204 wxNodeBase *each = m_nodeFirst;
205 while ( each != NULL )
206 {
207 wxNodeBase *next = each->GetNext();
208 DoDeleteNode(each);
209 each = next;
210 }
211 }
212
213 wxNodeBase *wxListBase::AppendCommon(wxNodeBase *node)
214 {
215 if ( !m_nodeFirst )
216 {
217 m_nodeFirst = node;
218 m_nodeLast = m_nodeFirst;
219 }
220 else
221 {
222 m_nodeLast->m_next = node;
223 m_nodeLast = node;
224 }
225
226 m_count++;
227
228 return node;
229 }
230
231 wxNodeBase *wxListBase::Append(void *object)
232 {
233 // all objects in a keyed list should have a key
234 wxCHECK_MSG( m_keyType == wxKEY_NONE, NULL,
235 wxT("need a key for the object to append") );
236
237 // we use wxDefaultListKey even though it is the default parameter value
238 // because gcc under Mac OS X seems to miscompile this call otherwise
239 wxNodeBase *node = CreateNode(m_nodeLast, NULL, object,
240 wxDefaultListKey);
241
242 return AppendCommon(node);
243 }
244
245 wxNodeBase *wxListBase::Append(long key, void *object)
246 {
247 wxCHECK_MSG( (m_keyType == wxKEY_INTEGER) ||
248 (m_keyType == wxKEY_NONE && m_count == 0),
249 NULL,
250 wxT("can't append object with numeric key to this list") );
251
252 wxNodeBase *node = CreateNode(m_nodeLast, NULL, object, key);
253 return AppendCommon(node);
254 }
255
256 wxNodeBase *wxListBase::Append (const wxString& key, void *object)
257 {
258 wxCHECK_MSG( (m_keyType == wxKEY_STRING) ||
259 (m_keyType == wxKEY_NONE && m_count == 0),
260 NULL,
261 wxT("can't append object with string key to this list") );
262
263 wxNodeBase *node = CreateNode(m_nodeLast, NULL, object, key);
264 return AppendCommon(node);
265 }
266
267 wxNodeBase *wxListBase::Insert(wxNodeBase *position, void *object)
268 {
269 // all objects in a keyed list should have a key
270 wxCHECK_MSG( m_keyType == wxKEY_NONE, NULL,
271 wxT("need a key for the object to insert") );
272
273 wxCHECK_MSG( !position || position->m_list == this, NULL,
274 wxT("can't insert before a node from another list") );
275
276 // previous and next node for the node being inserted
277 wxNodeBase *prev, *next;
278 if ( position )
279 {
280 prev = position->GetPrevious();
281 next = position;
282 }
283 else
284 {
285 // inserting in the beginning of the list
286 prev = NULL;
287 next = m_nodeFirst;
288 }
289
290 // wxDefaultListKey: see comment in Append() above
291 wxNodeBase *node = CreateNode(prev, next, object, wxDefaultListKey);
292 if ( !m_nodeFirst )
293 {
294 m_nodeLast = node;
295 }
296
297 if ( prev == NULL )
298 {
299 m_nodeFirst = node;
300 }
301
302 m_count++;
303
304 return node;
305 }
306
307 wxNodeBase *wxListBase::Item(size_t n) const
308 {
309 for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() )
310 {
311 if ( n-- == 0 )
312 {
313 return current;
314 }
315 }
316
317 wxFAIL_MSG( wxT("invalid index in wxListBase::Item") );
318
319 return NULL;
320 }
321
322 wxNodeBase *wxListBase::Find(const wxListKey& key) const
323 {
324 wxASSERT_MSG( m_keyType == key.GetKeyType(),
325 wxT("this list is not keyed on the type of this key") );
326
327 for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() )
328 {
329 if ( key == current->m_key )
330 {
331 return current;
332 }
333 }
334
335 // not found
336 return NULL;
337 }
338
339 wxNodeBase *wxListBase::Find(const void *object) const
340 {
341 for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() )
342 {
343 if ( current->GetData() == object )
344 return current;
345 }
346
347 // not found
348 return NULL;
349 }
350
351 int wxListBase::IndexOf(void *object) const
352 {
353 wxNodeBase *node = Find( object );
354
355 return node ? node->IndexOf() : wxNOT_FOUND;
356 }
357
358 void wxListBase::DoDeleteNode(wxNodeBase *node)
359 {
360 // free node's data
361 if ( m_keyType == wxKEY_STRING )
362 {
363 free(node->m_key.string);
364 }
365
366 if ( m_destroy )
367 {
368 node->DeleteData();
369 }
370
371 // so that the node knows that it's being deleted by the list
372 node->m_list = NULL;
373 delete node;
374 }
375
376 wxNodeBase *wxListBase::DetachNode(wxNodeBase *node)
377 {
378 wxCHECK_MSG( node, NULL, wxT("detaching NULL wxNodeBase") );
379 wxCHECK_MSG( node->m_list == this, NULL,
380 wxT("detaching node which is not from this list") );
381
382 // update the list
383 wxNodeBase **prevNext = node->GetPrevious() ? &node->GetPrevious()->m_next
384 : &m_nodeFirst;
385 wxNodeBase **nextPrev = node->GetNext() ? &node->GetNext()->m_previous
386 : &m_nodeLast;
387
388 *prevNext = node->GetNext();
389 *nextPrev = node->GetPrevious();
390
391 m_count--;
392
393 // mark the node as not belonging to this list any more
394 node->m_list = NULL;
395
396 return node;
397 }
398
399 bool wxListBase::DeleteNode(wxNodeBase *node)
400 {
401 if ( !DetachNode(node) )
402 return false;
403
404 DoDeleteNode(node);
405
406 return true;
407 }
408
409 bool wxListBase::DeleteObject(void *object)
410 {
411 for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() )
412 {
413 if ( current->GetData() == object )
414 {
415 DeleteNode(current);
416 return true;
417 }
418 }
419
420 // not found
421 return false;
422 }
423
424 void wxListBase::Clear()
425 {
426 wxNodeBase *current = m_nodeFirst;
427 while ( current )
428 {
429 wxNodeBase *next = current->GetNext();
430 DoDeleteNode(current);
431 current = next;
432 }
433
434 m_nodeFirst =
435 m_nodeLast = NULL;
436
437 m_count = 0;
438 }
439
440 void wxListBase::ForEach(wxListIterateFunction F)
441 {
442 for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() )
443 {
444 (*F)(current->GetData());
445 }
446 }
447
448 void *wxListBase::FirstThat(wxListIterateFunction F)
449 {
450 for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() )
451 {
452 if ( (*F)(current->GetData()) )
453 return current->GetData();
454 }
455
456 return NULL;
457 }
458
459 void *wxListBase::LastThat(wxListIterateFunction F)
460 {
461 for ( wxNodeBase *current = GetLast(); current; current = current->GetPrevious() )
462 {
463 if ( (*F)(current->GetData()) )
464 return current->GetData();
465 }
466
467 return NULL;
468 }
469
470 // (stefan.hammes@urz.uni-heidelberg.de)
471 //
472 // function for sorting lists. the concept is borrowed from 'qsort'.
473 // by giving a sort function, arbitrary lists can be sorted.
474 // method:
475 // - put wxObject pointers into an array
476 // - sort the array with qsort
477 // - put back the sorted wxObject pointers into the list
478 //
479 // CAVE: the sort function receives pointers to wxObject pointers (wxObject **),
480 // so dereference right!
481 // EXAMPLE:
482 // int listcompare(const void *arg1, const void *arg2)
483 // {
484 // return(compare(**(wxString **)arg1,
485 // **(wxString **)arg2));
486 // }
487 //
488 // void main()
489 // {
490 // wxListBase list;
491 //
492 // list.Append(new wxString("DEF"));
493 // list.Append(new wxString("GHI"));
494 // list.Append(new wxString("ABC"));
495 // list.Sort(listcompare);
496 // }
497
498 void wxListBase::Sort(const wxSortCompareFunction compfunc)
499 {
500 // allocate an array for the wxObject pointers of the list
501 const size_t num = GetCount();
502 void **objArray = new void *[num];
503 void **objPtr = objArray;
504
505 // go through the list and put the pointers into the array
506 wxNodeBase *node;
507 for ( node = GetFirst(); node; node = node->GetNext() )
508 {
509 *objPtr++ = node->GetData();
510 }
511
512 // sort the array
513 qsort((void *)objArray,num,sizeof(wxObject *),
514 #ifdef __WXWINCE__
515 (int (__cdecl *)(const void *,const void *))
516 #endif
517 compfunc);
518
519 // put the sorted pointers back into the list
520 objPtr = objArray;
521 for ( node = GetFirst(); node; node = node->GetNext() )
522 {
523 node->SetData(*objPtr++);
524 }
525
526 // free the array
527 delete[] objArray;
528 }
529
530 void wxListBase::Reverse()
531 {
532 wxNodeBase* node = m_nodeFirst;
533 wxNodeBase* tmp;
534
535 while (node)
536 {
537 // swap prev and next pointers
538 tmp = node->m_next;
539 node->m_next = node->m_previous;
540 node->m_previous = tmp;
541
542 // this is the node that was next before swapping
543 node = tmp;
544 }
545
546 // swap first and last node
547 tmp = m_nodeFirst; m_nodeFirst = m_nodeLast; m_nodeLast = tmp;
548 }
549
550 void wxListBase::DeleteNodes(wxNodeBase* first, wxNodeBase* last)
551 {
552 wxNodeBase* node = first;
553
554 while (node != last)
555 {
556 wxNodeBase* next = node->GetNext();
557 DeleteNode(node);
558 node = next;
559 }
560 }
561
562 // ============================================================================
563 // compatibility section from now on
564 // ============================================================================
565
566 #ifdef wxLIST_COMPATIBILITY
567
568 // -----------------------------------------------------------------------------
569 // wxList (a.k.a. wxObjectList)
570 // -----------------------------------------------------------------------------
571
572 wxList::wxList( int key_type )
573 : wxObjectList( (wxKeyType)key_type )
574 {
575 }
576
577 void wxObjectListNode::DeleteData()
578 {
579 delete (wxObject *)GetData();
580 }
581
582 // ----------------------------------------------------------------------------
583 // wxStringList
584 // ----------------------------------------------------------------------------
585
586 static inline wxChar* MYcopystring(const wxChar* s)
587 {
588 wxChar* copy = new wxChar[wxStrlen(s) + 1];
589 return wxStrcpy(copy, s);
590 }
591
592 // instead of WX_DEFINE_LIST(wxStringListBase) we define this function
593 // ourselves
594 void wxStringListNode::DeleteData()
595 {
596 delete [] (char *)GetData();
597 }
598
599 bool wxStringList::Delete(const wxChar *s)
600 {
601 wxStringListNode *current;
602
603 for ( current = GetFirst(); current; current = current->GetNext() )
604 {
605 if ( wxStrcmp(current->GetData(), s) == 0 )
606 {
607 DeleteNode(current);
608 return true;
609 }
610 }
611
612 // not found
613 return false;
614 }
615
616 void wxStringList::DoCopy(const wxStringList& other)
617 {
618 wxASSERT( GetCount() == 0 ); // this list must be empty before copying!
619
620 size_t count = other.GetCount();
621 for ( size_t n = 0; n < count; n++ )
622 {
623 Add(other.Item(n)->GetData());
624 }
625 }
626
627 wxStringList::wxStringList()
628 {
629 DeleteContents(true);
630 }
631
632 // Variable argument list, terminated by a zero
633 // Makes new storage for the strings
634 wxStringList::wxStringList (const wxChar *first, ...)
635 {
636 DeleteContents(true);
637 if ( !first )
638 return;
639
640 va_list ap;
641 va_start(ap, first);
642
643 const wxChar *s = first;
644 for (;;)
645 {
646 Add(s);
647
648 // icc gives this warning in its own va_arg() macro, argh
649 #ifdef __INTELC__
650 #pragma warning(push)
651 #pragma warning(disable: 1684)
652 #endif
653
654 s = va_arg(ap, const wxChar *);
655
656 #ifdef __INTELC__
657 #pragma warning(pop)
658 #endif
659
660 if ( !s )
661 break;
662 }
663
664 va_end(ap);
665 }
666
667 // Only makes new strings if arg is true
668 wxChar **wxStringList::ListToArray(bool new_copies) const
669 {
670 wxChar **string_array = new wxChar *[GetCount()];
671 wxStringListNode *node = GetFirst();
672 for (size_t i = 0; i < GetCount(); i++)
673 {
674 wxChar *s = node->GetData();
675 if ( new_copies )
676 string_array[i] = MYcopystring(s);
677 else
678 string_array[i] = s;
679 node = node->GetNext();
680 }
681
682 return string_array;
683 }
684
685 // Checks whether s is a member of the list
686 bool wxStringList::Member(const wxChar *s) const
687 {
688 for ( wxStringListNode *node = GetFirst(); node; node = node->GetNext() )
689 {
690 const wxChar *s1 = node->GetData();
691 if (s == s1 || wxStrcmp (s, s1) == 0)
692 return true;
693 }
694
695 return false;
696 }
697
698 #ifdef __WXWINCE__
699 extern "C"
700 {
701 static int __cdecl
702 #else
703 extern "C"
704 {
705 static int LINKAGEMODE
706 #endif
707
708 wx_comparestrings(const void *arg1, const void *arg2)
709 {
710 wxChar **s1 = (wxChar **) arg1;
711 wxChar **s2 = (wxChar **) arg2;
712
713 return wxStrcmp (*s1, *s2);
714 }
715
716 } // end of extern "C" (required because of GCC Bug c++/33078
717
718 // Sort a list of strings - deallocates old nodes, allocates new
719 void wxStringList::Sort()
720 {
721 size_t N = GetCount();
722 wxChar **array = new wxChar *[N];
723 wxStringListNode *node;
724
725 size_t i = 0;
726 for ( node = GetFirst(); node; node = node->GetNext() )
727 {
728 array[i++] = node->GetData();
729 }
730
731 qsort (array, N, sizeof (wxChar *), wx_comparestrings);
732
733 i = 0;
734 for ( node = GetFirst(); node; node = node->GetNext() )
735 node->SetData( array[i++] );
736
737 delete [] array;
738 }
739
740 wxNode *wxStringList::Add(const wxChar *s)
741 {
742 return (wxNode *)(wxStringListBase::Node *)
743 wxStringListBase::Append(MYcopystring(s));
744 }
745
746 wxNode *wxStringList::Prepend(const wxChar *s)
747 {
748 return (wxNode *)(wxStringListBase::Node *)
749 wxStringListBase::Insert(MYcopystring(s));
750 }
751
752 #endif // wxLIST_COMPATIBILITY
753
754 #else // wxUSE_STD_CONTAINERS = 1
755
756 #include "wx/listimpl.cpp"
757 WX_DEFINE_LIST(wxObjectList)
758
759 // with wxUSE_STD_CONTAINERS wxStringList contains wxString objects, not pointers
760 void _WX_LIST_HELPER_wxStringListBase::DeleteFunction( wxString WXUNUSED(X) )
761 {
762 }
763
764 _WX_LIST_HELPER_wxStringListBase::BaseListType _WX_LIST_HELPER_wxStringListBase::EmptyList;
765
766 #endif // !wxUSE_STD_CONTAINERS