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