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 __WINDOWS__
 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 #ifdef USE_STORABLE_CLASSES
 214 wxList::wxList( istream &stream, char *WXUNUSED(data) )
 215 {
 216   char buf[200];
 217   unsigned int num;
 218   stream.read( (char*)(&num), sizeof(num) );
 219   for (unsigned int i = 0; i < num; i++)
 220   {
 221     int len;
 222     stream.read( (char*)(&len), sizeof(len) );
 223     stream.read( (char*)(&buf), len );
 224     buf[len] = 0;
 225     Append( wxCreateStoredObject( buf, stream, NULL ) );
 226   };
 227 };
 228
 229 void wxList::StoreObject( ostream &stream )
 230 {
 231   unsigned int num = Number();
 232   stream.write( (char*)(&num), sizeof(num) );
 233   wxNode *node = First();
 234   while (node)
 235   {
 236     wxObject *obj = (wxObject*) node->Data();
 237     wxClassInfo *obj_info = obj->GetClassInfo();
 238     int len = strlen(obj_info->className);
 239     stream.write( (char*)(&len), sizeof(len) );
 240     stream.write( obj_info->className, len );
 241     obj->StoreObject( stream );
 242     node = node->Next();
 243   };
 244 };
 245 #endif
 246
 247 wxNode *wxList::Append(wxObject *object)
 248 {
 249     wxNode *node = new wxNode(this, last_node, NULL, object);
 250     if (!first_node)
 251       first_node = node;
 252     last_node = node;
 253     n ++;
 254     return node;
 255 }
 256
 257 wxNode *wxList::Nth (int i) const
 258 {
 259   int j = 0;
 260   for (wxNode * current = First (); current; current = current->Next ())
 261     {
 262       if (j++ == i)
 263         return current;
 264     }
 265   return NULL;                  // No such element
 266
 267 }
 268
 269 wxNode *wxList::Find (long key) const
 270 {
 271   wxNode *current = First();
 272   while (current)
 273   {
 274     if (current->key.integer == key)
 275       return current;
 276     current = current->Next();
 277   }
 278
 279   return NULL;                  // Not found!
 280 }
 281
 282 wxNode *wxList::Find (const char *key) const
 283 {
 284   wxNode *current = First();
 285   while (current)
 286   {
 287       if (!current->key.string)
 288         {
 289           wxFatalError ("wxList: string key not present, probably did not Append correctly!");
 290           break;
 291         }
 292       if (strcmp (current->key.string, key) == 0)
 293         return current;
 294       current = current->Next();
 295   }
 296
 297   return NULL;                  // Not found!
 298
 299 }
 300
 301 wxNode *wxList::Member (wxObject * object) const
 302 {
 303   for (wxNode * current = First (); current; current = current->Next ())
 304     {
 305       wxObject *each = current->Data ();
 306       if (each == object)
 307         return current;
 308     }
 309   return NULL;
 310 }
 311
 312 bool wxList::DeleteNode (wxNode * node)
 313 {
 314   if (node)
 315     {
 316       delete node;
 317       return TRUE;
 318     }
 319   return FALSE;
 320 }
 321
 322 bool wxList::DeleteObject (wxObject * object)
 323 {
 324   // Search list for object
 325   for (wxNode * current = first_node; current; current = current->Next ())
 326     {
 327       if (current->Data () == object)
 328         {
 329           delete current;
 330           return TRUE;
 331         }
 332     }
 333   return FALSE;                 // Did not find the object
 334
 335 }
 336
 337
 338 // Insert new node at front of list
 339 wxNode *wxList::Insert (wxObject * object)
 340 {
 341   wxNode *node = new wxNode (this, NULL, First (), object);
 342   first_node = node;
 343
 344   if (!(node->Next ()))
 345     last_node = node;
 346
 347   n++;
 348   return node;
 349 }
 350
 351
 352 // Insert new node before given node.
 353 wxNode *wxList::Insert (wxNode * position, wxObject * object)
 354 {
 355   wxNode *prev = NULL;
 356   if (position)
 357     prev = position->Previous ();
 358
 359   wxNode *node = new wxNode (this, prev, position, object);
 360   if (!first_node)
 361     {
 362       first_node = node;
 363       last_node = node;
 364     }
 365   if (!prev)
 366     first_node = node;
 367
 368   n++;
 369   return node;
 370 }
 371
 372 // Keyed append
 373 wxNode *wxList::Append (long key, wxObject * object)
 374 {
 375   wxNode *node = new wxNode (this, last_node, NULL, object, key);
 376   if (!first_node)
 377     first_node = node;
 378   last_node = node;
 379   n++;
 380   return node;
 381 }
 382
 383 wxNode *wxList::Append (const char *key, wxObject * object)
 384 {
 385   wxNode *node = new wxNode (this, last_node, NULL, object, key);
 386   if (!first_node)
 387     first_node = node;
 388   last_node = node;
 389   n++;
 390   return node;
 391 }
 392
 393 void wxList::Clear (void)
 394 {
 395   wxNode *current = first_node;
 396   while (current)
 397     {
 398       wxNode *next = current->Next ();
 399       delete current;
 400       current = next;
 401     }
 402   first_node = NULL;
 403   last_node = NULL;
 404   n = 0;
 405 }
 406
 407 //Executes function F with all items present in the list
 408 void wxList::ForEach(wxListIterateFunction F)
 409 {
 410   wxNode *each = first_node;
 411   while (each)
 412     { (*F)( each->Data ());
 413       each = each->Next();
 414     }
 415 }
 416 // Returns a pointer to the item which returns TRUE with function F
 417 // or NULL if no such item found
 418 wxObject *wxList::FirstThat(wxListIterateFunction F)
 419 {
 420   wxNode *each = first_node;
 421   while (each)
 422     { if ((*F)( each->Data ())) return each->Data();
 423       each = each->Next();
 424     }
 425   return NULL;
 426 }
 427 // Like FirstThat, but proceeds from the end backward
 428 wxObject *wxList::LastThat(wxListIterateFunction F)
 429 {
 430   wxNode *each = last_node;
 431   while (each)
 432     { if ((*F)( each->Data ())) return each->Data();
 433       each = each->Previous();
 434     }
 435   return NULL;
 436 }
 437
 438 // (stefan.hammes@urz.uni-heidelberg.de)
 439 //
 440 // function for sorting lists. the concept is borrowed from 'qsort'.
 441 // by giving a sort function, arbitrary lists can be sorted.
 442 // method:
 443 // - put wxObject pointers into an array
 444 // - sort the array with qsort
 445 // - put back the sorted wxObject pointers into the list
 446 //
 447 // CAVE: the sort function receives pointers to wxObject pointers (wxObject **),
 448 //       so dereference right!
 449 // EXAMPLE:
 450 //   int listcompare(const void *arg1, const void *arg2)
 451 //   {
 452 //      return(compare(**(wxString **)arg1,
 453 //                     **(wxString **)arg2));
 454 //   }
 455 //
 456 //   void main()
 457 //   {
 458 //     wxList list;
 459 //
 460 //     list.Append(new wxString("DEF"));
 461 //     list.Append(new wxString("GHI"));
 462 //     list.Append(new wxString("ABC"));
 463 //     list.Sort(listcompare);
 464 //   }
 465
 466 void wxList::Sort(const wxSortCompareFunction compfunc)
 467 {
 468   // allocate an array for the wxObject pointers of the list
 469   const size_t num = Number();
 470   wxObject **objArray = new wxObject *[num];
 471   wxObject **objPtr = objArray;
 472
 473   // go through the list and put the pointers into the array
 474   wxNode *node = First();
 475   while(node!=NULL){
 476     *objPtr++ = node->Data();
 477     node = node->Next();
 478   }
 479   // sort the array
 480   qsort((void *)objArray,num,sizeof(wxObject *),compfunc);
 481   // put the sorted pointers back into the list
 482   objPtr = objArray;
 483   node = First();
 484   while(node!=NULL){
 485     node->SetData(*objPtr++);
 486     node = node->Next();
 487   }
 488   // free the array
 489   delete[] objArray;
 490 }
 491
 492 /*
 493  * String list
 494  *
 495  */
 496
 497 wxStringList::wxStringList (void):
 498 wxList ()
 499 {
 500 }
 501
 502 // Variable argument list, terminated by a zero
 503 // Makes new storage for the strings
 504 wxStringList::wxStringList (const char *first...)
 505 {
 506 // #ifndef __SGI__
 507   n = 0;
 508   destroy_data = 0;
 509   key_type = wxKEY_NONE;
 510   first_node = NULL;
 511   last_node = NULL;
 512
 513   if (!first)
 514     return;
 515
 516   va_list ap;
 517
 518   va_start (ap, first);
 519
 520   wxNode *last = new wxNode (this, NULL, NULL, (wxObject *) copystring (first));
 521   first_node = last;
 522   n = 1;
 523
 524   for (;;)
 525     {
 526       char *s = va_arg (ap, char *);
 527 //    if (s == NULL)
 528 #ifdef __WINDOWS__
 529       if ((int) s == 0)
 530 #else
 531       if ((long) s == 0)
 532 #endif
 533         break;
 534       else
 535         {
 536           wxNode *node = new wxNode (this, last, NULL, (wxObject *) copystring (s));
 537           last = node;
 538           n++;
 539         }
 540     }
 541   last_node = last;
 542   va_end (ap);
 543 /*
 544 #else
 545   fprintf (stderr, "Error: cannot use variable-argument functions on SGI!\n");
 546 #endif
 547 */
 548 }
 549
 550 wxStringList::~wxStringList (void)
 551 {
 552   wxNode *each = first_node;
 553   while (each)
 554     {
 555       char *s = (char *) each->Data ();
 556       delete[]s;
 557       wxNode *next = each->Next ();
 558       delete each;
 559       each = next;
 560     }
 561 }
 562
 563 wxNode *wxStringList::Add (const char *s)
 564 {
 565   return Append ((wxObject *) (copystring (s)));
 566 }
 567
 568 void wxStringList::Delete (const char *s)
 569 {
 570   for (wxNode * node = First (); node; node = node->Next ())
 571     {
 572       char *string = (char *) node->Data ();
 573       if (string == s || strcmp (string, s) == 0)
 574         {
 575           delete[]string;
 576           delete node;
 577           break;                // Done!
 578
 579         }
 580     }                           // for
 581
 582 }
 583
 584 // Only makes new strings if arg is TRUE
 585 char **wxStringList::ListToArray (bool new_copies) const
 586 {
 587   char **string_array = new char *[Number ()];
 588   wxNode *node = First ();
 589   int i;
 590   for (i = 0; i < n; i++)
 591     {
 592       char *s = (char *) node->Data ();
 593       if (new_copies)
 594         string_array[i] = copystring (s);
 595       else
 596         string_array[i] = s;
 597       node = node->Next ();
 598     }
 599   return string_array;
 600 }
 601
 602 static int
 603 wx_comparestrings (const void *arg1, const void *arg2)
 604 {
 605   char **s1 = (char **) arg1;
 606   char **s2 = (char **) arg2;
 607
 608   return strcmp (*s1, *s2);
 609 }
 610
 611 // Sort a list of strings - deallocates old nodes, allocates new
 612 void wxStringList::Sort (void)
 613 {
 614   size_t N = n;
 615   char **array = new char *[N];
 616
 617   size_t i = 0;
 618   for (wxNode * node = First (); node; node = node->Next ())
 619     array[i++] = (char *) node->Data ();
 620
 621   qsort (array, N, sizeof (char *), wx_comparestrings);
 622   Clear ();
 623
 624   for (i = 0; i < N; i++)
 625     Append ((wxObject *) (array[i]));
 626
 627   delete[]array;
 628 }
 629
 630 // Checks whether s is a member of the list
 631 bool wxStringList::Member (const char *s) const
 632 {
 633   for (wxNode * node = First (); node; node = node->Next ())
 634     {
 635       const char *s1 = (const char *) node->Data ();
 636       if (s == s1 || strcmp (s, s1) == 0)
 637         return TRUE;
 638     }
 639   return FALSE;
 640 }