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