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 = 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 = NULL;
 130   last_node = 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 = NULL;
 139
 140   int i;
 141   for (i = 0; i < N; i++)
 142     {
 143       wxNode *next = new wxNode (this, last, 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 = NULL;
 158   last_node = 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, NULL, 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, 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, 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 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 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 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 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, 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 = 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, 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, 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 = NULL;
 370   last_node = 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 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 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 // 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;
 477   first_node = NULL;
 478   last_node = NULL;
 479
 480   if (!first)
 481     return;
 482
 483   va_list ap;
 484
 485   va_start (ap, first);
 486
 487   wxNode *last = new wxNode (this, NULL, NULL, (wxObject *) copystring (first));
 488   first_node = last;
 489   n = 1;
 490
 491   for (;;)
 492     {
 493       char *s = va_arg (ap, char *);
 494 //    if (s == NULL)
 495 #ifdef __WXMSW__
 496       if ((int) s == 0)
 497 #else
 498       if ((long) s == 0)
 499 #endif
 500         break;
 501       else
 502         {
 503           wxNode *node = new wxNode (this, last, NULL, (wxObject *) copystring (s));
 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
 552 char **wxStringList::ListToArray (bool new_copies) const
 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 }