include/wx/list.h

   1 /////////////////////////////////////////////////////////////////////////////
   2 // Name:        list.h
   3 // Purpose:     wxList, wxStringList classes
   4 // Author:      Julian Smart
   5 // Modified by: VZ at 16/11/98: WX_DECLARE_LIST() and typesafe lists added
   6 // Created:     29/01/98
   7 // RCS-ID:      $Id$
   8 // Copyright:   (c) 1998 Julian Smart
   9 // Licence:     wxWindows licence
  10 /////////////////////////////////////////////////////////////////////////////
  11
  12 /*
  13   All this is quite ugly but serves two purposes:
  14     1. Be almost 100% compatible with old, untyped, wxList class
  15     2. Ensure compile-time type checking for the linked lists
  16
  17   The idea is to have one base class (wxListBase) working with "void *" data,
  18   but to hide these untyped functions - i.e. make them protected, so they
  19   can only be used from derived classes which have inline member functions
  20   working with right types. This achieves the 2nd goal. As for the first one,
  21   we provide a special derivation of wxListBase called wxList which looks just
  22   like the old class.
  23 */
  24
  25 #ifndef _WX_LISTH__
  26 #define _WX_LISTH__
  27
  28 #if defined(__GNUG__) && !defined(__APPLE__)
  29 #pragma interface "list.h"
  30 #endif
  31
  32 // -----------------------------------------------------------------------------
  33 // headers
  34 // -----------------------------------------------------------------------------
  35
  36 #include "wx/defs.h"
  37 #include "wx/object.h"
  38 #include "wx/string.h"
  39
  40 // due to circular header dependencies this function has to be declared here
  41 // (normally it's found in utils.h which includes itself list.h...)
  42 extern WXDLLIMPEXP_BASE wxChar* copystring(const wxChar *s);
  43
  44 class WXDLLIMPEXP_BASE wxObjectListNode;
  45 typedef wxObjectListNode wxNode;
  46
  47 // undef it to get rid of old, deprecated functions
  48 #define wxLIST_COMPATIBILITY
  49
  50 // -----------------------------------------------------------------------------
  51 // constants
  52 // -----------------------------------------------------------------------------
  53 enum wxKeyType
  54 {
  55     wxKEY_NONE,
  56     wxKEY_INTEGER,
  57     wxKEY_STRING
  58 };
  59
  60 // -----------------------------------------------------------------------------
  61 // types
  62 // -----------------------------------------------------------------------------
  63
  64 // type of compare function for list sort operation (as in 'qsort'): it should
  65 // return a negative value, 0 or positive value if the first element is less
  66 // than, equal or greater than the second
  67 extern "C"
  68 {
  69 typedef int (* LINKAGEMODE wxSortCompareFunction)(const void *elem1, const void *elem2);
  70 }
  71
  72 //
  73 typedef int (* LINKAGEMODE wxListIterateFunction)(void *current);
  74
  75 // -----------------------------------------------------------------------------
  76 // key stuff: a list may be optionally keyed on integer or string key
  77 // -----------------------------------------------------------------------------
  78
  79 union wxListKeyValue
  80 {
  81     long integer;
  82     wxChar *string;
  83 };
  84
  85 // a struct which may contain both types of keys
  86 //
  87 // implementation note: on one hand, this class allows to have only one function
  88 // for any keyed operation instead of 2 almost equivalent. OTOH, it's needed to
  89 // resolve ambiguity which we would otherwise have with wxStringList::Find() and
  90 // wxList::Find(const char *).
  91 class WXDLLIMPEXP_BASE wxListKey
  92 {
  93 public:
  94     // implicit ctors
  95     wxListKey() : m_keyType(wxKEY_NONE)
  96         { }
  97     wxListKey(long i) : m_keyType(wxKEY_INTEGER)
  98         { m_key.integer = i; }
  99     wxListKey(const wxChar *s) : m_keyType(wxKEY_STRING)
 100         { m_key.string = wxStrdup(s); }
 101     wxListKey(const wxString& s) : m_keyType(wxKEY_STRING)
 102         { m_key.string = wxStrdup(s.c_str()); }
 103
 104     // accessors
 105     wxKeyType GetKeyType() const { return m_keyType; }
 106     const wxChar *GetString() const
 107         { wxASSERT( m_keyType == wxKEY_STRING ); return m_key.string; }
 108     long GetNumber() const
 109         { wxASSERT( m_keyType == wxKEY_INTEGER ); return m_key.integer; }
 110
 111     // comparison
 112     // Note: implementation moved to list.cpp to prevent BC++ inline
 113     // expansion warning.
 114     bool operator==(wxListKeyValue value) const ;
 115
 116     // dtor
 117     ~wxListKey()
 118     {
 119         if ( m_keyType == wxKEY_STRING )
 120             free(m_key.string);
 121     }
 122
 123 private:
 124     wxKeyType m_keyType;
 125     wxListKeyValue m_key;
 126 };
 127
 128 // -----------------------------------------------------------------------------
 129 // wxNodeBase class is a (base for) node in a double linked list
 130 // -----------------------------------------------------------------------------
 131
 132 WXDLLIMPEXP_DATA_BASE(extern wxListKey) wxDefaultListKey;
 133
 134 class WXDLLIMPEXP_BASE wxListBase;
 135
 136 class WXDLLIMPEXP_BASE wxNodeBase
 137 {
 138 friend class wxListBase;
 139 public:
 140     // ctor
 141     wxNodeBase(wxListBase *list = (wxListBase *)NULL,
 142                wxNodeBase *previous = (wxNodeBase *)NULL,
 143                wxNodeBase *next = (wxNodeBase *)NULL,
 144                void *data = NULL,
 145                const wxListKey& key = wxDefaultListKey);
 146
 147     virtual ~wxNodeBase();
 148
 149     // FIXME no check is done that the list is really keyed on strings
 150     const wxChar *GetKeyString() const { return m_key.string; }
 151     long GetKeyInteger() const { return m_key.integer; }
 152
 153     // Necessary for some existing code
 154     void SetKeyString(wxChar* s) { m_key.string = s; }
 155     void SetKeyInteger(long i) { m_key.integer = i; }
 156
 157 #ifdef wxLIST_COMPATIBILITY
 158     // compatibility methods, use Get* instead.
 159     wxDEPRECATED( wxNode *Next() const );
 160     wxDEPRECATED( wxNode *Previous() const );
 161     wxDEPRECATED( wxObject *Data() const );
 162 #endif // wxLIST_COMPATIBILITY
 163
 164 protected:
 165     // all these are going to be "overloaded" in the derived classes
 166     wxNodeBase *GetNext() const { return m_next; }
 167     wxNodeBase *GetPrevious() const { return m_previous; }
 168
 169     void *GetData() const { return m_data; }
 170     void SetData(void *data) { m_data = data; }
 171
 172     // get 0-based index of this node within the list or wxNOT_FOUND
 173     int IndexOf() const;
 174
 175     virtual void DeleteData() { }
 176
 177 private:
 178     // optional key stuff
 179     wxListKeyValue m_key;
 180
 181     void        *m_data;        // user data
 182     wxNodeBase  *m_next,        // next and previous nodes in the list
 183                 *m_previous;
 184
 185     wxListBase  *m_list;        // list we belong to
 186
 187     DECLARE_NO_COPY_CLASS(wxNodeBase)
 188 };
 189
 190 // -----------------------------------------------------------------------------
 191 // a double-linked list class
 192 // -----------------------------------------------------------------------------
 193
 194 class wxList;
 195
 196 class WXDLLIMPEXP_BASE wxListBase : public wxObject
 197 {
 198 friend class WXDLLIMPEXP_BASE wxNodeBase; // should be able to call DetachNode()
 199 friend class wxHashTableBase;   // should be able to call untyped Find()
 200 private:
 201         // common part of all ctors
 202     void Init(wxKeyType keyType = wxKEY_NONE); // Must be declared before it's used (for VC++ 1.5)
 203 public:
 204     // default ctor & dtor
 205     wxListBase(wxKeyType keyType = wxKEY_NONE)
 206         { Init(keyType); }
 207     virtual ~wxListBase();
 208
 209     // accessors
 210         // count of items in the list
 211     size_t GetCount() const { return m_count; }
 212
 213         // return TRUE if this list is empty
 214     bool IsEmpty() const { return m_count == 0; }
 215
 216     // operations
 217
 218         // delete all nodes
 219     void Clear();
 220
 221         // instruct it to destroy user data when deleting nodes
 222     void DeleteContents(bool destroy) { m_destroy = destroy; }
 223
 224        // query if to delete
 225     bool GetDeleteContents() const
 226         { return m_destroy; }
 227
 228       // get the keytype
 229     wxKeyType GetKeyType() const
 230         { return m_keyType; }
 231
 232       // set the keytype (required by the serial code)
 233     void SetKeyType(wxKeyType keyType)
 234         { wxASSERT( m_count==0 ); m_keyType = keyType; }
 235
 236 #ifdef wxLIST_COMPATIBILITY
 237     // compatibility methods from old wxList
 238     wxDEPRECATED( int Number() const );             // use GetCount instead.
 239     wxDEPRECATED( wxNode *First() const );          // use GetFirst
 240     wxDEPRECATED( wxNode *Last() const );           // use GetLast
 241     wxDEPRECATED( wxNode *Nth(size_t n) const );    // use Item
 242
 243     // kludge for typesafe list migration in core classes.
 244     wxDEPRECATED( operator wxList&() const );
 245 #endif // wxLIST_COMPATIBILITY
 246
 247 protected:
 248
 249     // all methods here are "overloaded" in derived classes to provide compile
 250     // time type checking
 251
 252     // create a node for the list of this type
 253     virtual wxNodeBase *CreateNode(wxNodeBase *prev, wxNodeBase *next,
 254                                    void *data,
 255                                    const wxListKey& key = wxDefaultListKey) = 0;
 256
 257 // Can't access these from derived classes otherwise (bug in Salford C++?)
 258 #ifdef __SALFORDC__
 259 public:
 260 #endif
 261
 262     // ctors
 263         // from an array
 264     wxListBase(size_t count, void *elements[]);
 265         // from a sequence of objects
 266     wxListBase(void *object, ... /* terminate with NULL */);
 267
 268 protected:
 269         // copy ctor and assignment operator
 270     wxListBase(const wxListBase& list) : wxObject()
 271         { Init(); DoCopy(list); }
 272     wxListBase& operator=(const wxListBase& list)
 273         { Clear(); DoCopy(list); return *this; }
 274
 275         // get list head/tail
 276     wxNodeBase *GetFirst() const { return m_nodeFirst; }
 277     wxNodeBase *GetLast() const { return m_nodeLast; }
 278
 279         // by (0-based) index
 280     wxNodeBase *Item(size_t index) const;
 281
 282         // get the list item's data
 283     void *operator[](size_t n) const
 284     {
 285         wxNodeBase *node = Item(n);
 286
 287         return node ? node->GetData() : (wxNodeBase *)NULL;
 288     }
 289
 290     // operations
 291         // append to end of list
 292     wxNodeBase *Prepend(void *object)
 293         { return (wxNodeBase *)wxListBase::Insert(object); }
 294         // append to beginning of list
 295     wxNodeBase *Append(void *object);
 296         // insert a new item at the beginning of the list
 297     wxNodeBase *Insert(void *object) { return Insert( (wxNodeBase*)NULL, object); }
 298         // insert a new item at the given position
 299     wxNodeBase *Insert(size_t pos, void *object)
 300         { return pos == GetCount() ? Append(object)
 301                                    : Insert(Item(pos), object); }
 302         // insert before given node or at front of list if prev == NULL
 303     wxNodeBase *Insert(wxNodeBase *prev, void *object);
 304
 305         // keyed append
 306     wxNodeBase *Append(long key, void *object);
 307     wxNodeBase *Append(const wxChar *key, void *object);
 308
 309         // removes node from the list but doesn't delete it (returns pointer
 310         // to the node or NULL if it wasn't found in the list)
 311     wxNodeBase *DetachNode(wxNodeBase *node);
 312         // delete element from list, returns FALSE if node not found
 313     bool DeleteNode(wxNodeBase *node);
 314         // finds object pointer and deletes node (and object if DeleteContents
 315         // is on), returns FALSE if object not found
 316     bool DeleteObject(void *object);
 317
 318     // search (all return NULL if item not found)
 319         // by data
 320     wxNodeBase *Find(void *object) const;
 321
 322         // by key
 323     wxNodeBase *Find(const wxListKey& key) const;
 324
 325     // get 0-based index of object or wxNOT_FOUND
 326     int IndexOf( void *object ) const;
 327
 328     // this function allows the sorting of arbitrary lists by giving
 329     // a function to compare two list elements. The list is sorted in place.
 330     void Sort(const wxSortCompareFunction compfunc);
 331
 332     // functions for iterating over the list
 333     void *FirstThat(wxListIterateFunction func);
 334     void ForEach(wxListIterateFunction func);
 335     void *LastThat(wxListIterateFunction func);
 336
 337 private:
 338     // helpers
 339         // common part of copy ctor and assignment operator
 340     void DoCopy(const wxListBase& list);
 341         // common part of all Append()s
 342     wxNodeBase *AppendCommon(wxNodeBase *node);
 343         // free node's data and node itself
 344     void DoDeleteNode(wxNodeBase *node);
 345
 346     size_t m_count;             // number of elements in the list
 347     bool m_destroy;             // destroy user data when deleting list items?
 348     wxNodeBase *m_nodeFirst,    // pointers to the head and tail of the list
 349                *m_nodeLast;
 350
 351     wxKeyType m_keyType;        // type of our keys (may be wxKEY_NONE)
 352 };
 353
 354 // -----------------------------------------------------------------------------
 355 // macros for definition of "template" list type
 356 // -----------------------------------------------------------------------------
 357
 358 // and now some heavy magic...
 359
 360 // declare a list type named 'name' and containing elements of type 'T *'
 361 // (as a by product of macro expansion you also get wx##name##Node
 362 // wxNode-derived type)
 363 //
 364 // implementation details:
 365 //  1. We define _WX_LIST_ITEM_TYPE_##name typedef to save in it the item type
 366 //     for the list of given type - this allows us to pass only the list name
 367 //     to WX_DEFINE_LIST() even if it needs both the name and the type
 368 //
 369 //  2. We redefine all non-type-safe wxList functions with type-safe versions
 370 //     which don't take any space (everything is inline), but bring compile
 371 //     time error checking.
 372 //
 373 //  3. The macro which is usually used (WX_DECLARE_LIST) is defined in terms of
 374 //     a more generic WX_DECLARE_LIST_2 macro which, in turn, uses the most
 375 //     generic WX_DECLARE_LIST_3 one. The last macro adds a sometimes
 376 //     interesting capability to store polymorphic objects in the list and is
 377 //     particularly useful with, for example, "wxWindow *" list where the
 378 //     wxWindowBase pointers are put into the list, but wxWindow pointers are
 379 //     retrieved from it.
 380
 381 #define WX_DECLARE_LIST_3(T, Tbase, name, nodetype, classexp)               \
 382     typedef int (*wxSortFuncFor_##name)(const T **, const T **);            \
 383                                                                             \
 384     classexp nodetype : public wxNodeBase                                   \
 385     {                                                                       \
 386     public:                                                                 \
 387         nodetype(wxListBase *list = (wxListBase *)NULL,                     \
 388                  nodetype *previous = (nodetype *)NULL,                     \
 389                  nodetype *next = (nodetype *)NULL,                         \
 390                  T *data = (T *)NULL,                                       \
 391                  const wxListKey& key = wxDefaultListKey)                   \
 392             : wxNodeBase(list, previous, next, data, key) { }               \
 393                                                                             \
 394         nodetype *GetNext() const                                           \
 395             { return (nodetype *)wxNodeBase::GetNext(); }                   \
 396         nodetype *GetPrevious() const                                       \
 397             { return (nodetype *)wxNodeBase::GetPrevious(); }               \
 398                                                                             \
 399         T *GetData() const                                                  \
 400             { return (T *)wxNodeBase::GetData(); }                          \
 401         void SetData(T *data)                                               \
 402             { wxNodeBase::SetData(data); }                                  \
 403                                                                             \
 404         virtual void DeleteData();                                          \
 405     };                                                                      \
 406                                                                             \
 407     classexp name : public wxListBase                                       \
 408     {                                                                       \
 409     public:                                                                 \
 410         typedef nodetype Node;                                              \
 411                                                                             \
 412         name(wxKeyType keyType = wxKEY_NONE) : wxListBase(keyType)          \
 413             { }                                                             \
 414         name(size_t count, T *elements[])                                   \
 415             : wxListBase(count, (void **)elements) { }                      \
 416                                                                             \
 417         name& operator=(const name& list)                                   \
 418             { (void) wxListBase::operator=(list); return *this; }           \
 419                                                                             \
 420         nodetype *GetFirst() const                                          \
 421             { return (nodetype *)wxListBase::GetFirst(); }                  \
 422         nodetype *GetLast() const                                           \
 423             { return (nodetype *)wxListBase::GetLast(); }                   \
 424                                                                             \
 425         nodetype *Item(size_t index) const                                  \
 426             { return (nodetype *)wxListBase::Item(index); }                 \
 427                                                                             \
 428         T *operator[](size_t index) const                                   \
 429         {                                                                   \
 430             nodetype *node = Item(index);                                   \
 431             return node ? (T*)(node->GetData()) : (T*)NULL;                 \
 432         }                                                                   \
 433                                                                             \
 434         nodetype *Append(Tbase *object)                                     \
 435             { return (nodetype *)wxListBase::Append(object); }              \
 436         nodetype *Insert(Tbase *object)                                     \
 437             { return (nodetype *)Insert((nodetype*)NULL, object); }         \
 438         nodetype *Insert(size_t pos, Tbase *object)                         \
 439             { return (nodetype *)wxListBase::Insert(pos, object); }         \
 440         nodetype *Insert(nodetype *prev, Tbase *object)                     \
 441             { return (nodetype *)wxListBase::Insert(prev, object); }        \
 442                                                                             \
 443         nodetype *Append(long key, void *object)                            \
 444             { return (nodetype *)wxListBase::Append(key, object); }         \
 445         nodetype *Append(const wxChar *key, void *object)                   \
 446             { return (nodetype *)wxListBase::Append(key, object); }         \
 447                                                                             \
 448         nodetype *DetachNode(nodetype *node)                                \
 449             { return (nodetype *)wxListBase::DetachNode(node); }            \
 450         bool DeleteNode(nodetype *node)                                     \
 451             { return wxListBase::DeleteNode(node); }                        \
 452         bool DeleteObject(Tbase *object)                                    \
 453             { return wxListBase::DeleteObject(object); }                    \
 454                                                                             \
 455         nodetype *Find(Tbase *object) const                                 \
 456             { return (nodetype *)wxListBase::Find(object); }                \
 457                                                                             \
 458         virtual nodetype *Find(const wxListKey& key) const                  \
 459             { return (nodetype *)wxListBase::Find(key); }                   \
 460                                                                             \
 461         int IndexOf(Tbase *object) const                                    \
 462             { return wxListBase::IndexOf(object); }                         \
 463                                                                             \
 464         void Sort(wxSortFuncFor_##name func)                                \
 465             { wxListBase::Sort((wxSortCompareFunction)func); }              \
 466                                                                             \
 467     protected:                                                              \
 468         virtual wxNodeBase *CreateNode(wxNodeBase *prev, wxNodeBase *next,  \
 469                                void *data,                                  \
 470                                const wxListKey& key = wxDefaultListKey)     \
 471             {                                                               \
 472                 return new nodetype(this,                                   \
 473                                     (nodetype *)prev, (nodetype *)next,     \
 474                                     (T *)data, key);                        \
 475             }                                                               \
 476     }
 477
 478 #define WX_DECLARE_LIST_2(elementtype, listname, nodename, classexp)        \
 479     WX_DECLARE_LIST_3(elementtype, elementtype, listname, nodename, classexp)
 480
 481 #define WX_DECLARE_LIST(elementtype, listname)                              \
 482     typedef elementtype _WX_LIST_ITEM_TYPE_##listname;                      \
 483     WX_DECLARE_LIST_2(elementtype, listname, wx##listname##Node, class)
 484
 485 #define WX_DECLARE_EXPORTED_LIST(elementtype, listname)                     \
 486     typedef elementtype _WX_LIST_ITEM_TYPE_##listname;                      \
 487     WX_DECLARE_LIST_2(elementtype, listname, wx##listname##Node, class WXDLLEXPORT)
 488
 489 #define WX_DECLARE_USER_EXPORTED_LIST(elementtype, listname, usergoo)       \
 490     typedef elementtype _WX_LIST_ITEM_TYPE_##listname;                      \
 491     WX_DECLARE_LIST_2(elementtype, listname, wx##listname##Node, class usergoo)
 492
 493 // this macro must be inserted in your program after
 494 //      #include <wx/listimpl.cpp>
 495 #define WX_DEFINE_LIST(name)    "don't forget to include listimpl.cpp!"
 496
 497 #define WX_DEFINE_EXPORTED_LIST(name)      WX_DEFINE_LIST(name)
 498 #define WX_DEFINE_USER_EXPORTED_LIST(name) WX_DEFINE_LIST(name)
 499
 500
 501 // =============================================================================
 502 // now we can define classes 100% compatible with the old ones
 503 // =============================================================================
 504
 505 // ----------------------------------------------------------------------------
 506 // commonly used list classes
 507 // ----------------------------------------------------------------------------
 508
 509 #ifdef wxLIST_COMPATIBILITY
 510
 511 // define this to make a lot of noise about use of the old wxList classes.
 512 //#define wxWARN_COMPAT_LIST_USE
 513
 514 // -----------------------------------------------------------------------------
 515 // wxList compatibility class: in fact, it's a list of wxObjects
 516 // -----------------------------------------------------------------------------
 517
 518 WX_DECLARE_LIST_2(wxObject, wxObjectList, wxObjectListNode, class WXDLLIMPEXP_BASE);
 519
 520 class WXDLLIMPEXP_BASE wxList : public wxObjectList
 521 {
 522 public:
 523 #ifdef wxWARN_COMPAT_LIST_USE
 524     wxDEPRECATED( wxList(int key_type = wxKEY_NONE) );
 525 #else
 526     wxList(int key_type = wxKEY_NONE);
 527 #endif
 528
 529     // this destructor is required for Darwin
 530    ~wxList() { }
 531
 532     wxList& operator=(const wxList& list)
 533         { (void) wxListBase::operator=(list); return *this; }
 534
 535     // compatibility methods
 536     void Sort(wxSortCompareFunction compfunc) { wxListBase::Sort(compfunc); }
 537
 538     wxNode *Member(wxObject *object) const { return (wxNode *)Find(object); }
 539
 540 private:
 541     DECLARE_DYNAMIC_CLASS(wxList)
 542 };
 543
 544 // -----------------------------------------------------------------------------
 545 // wxStringList class for compatibility with the old code
 546 // -----------------------------------------------------------------------------
 547
 548 WX_DECLARE_LIST_2(wxChar, wxStringListBase, wxStringListNode, class WXDLLIMPEXP_BASE);
 549
 550 class WXDLLIMPEXP_BASE wxStringList : public wxStringListBase
 551 {
 552 public:
 553     // ctors and such
 554         // default
 555 #ifdef wxWARN_COMPAT_LIST_USE
 556     wxDEPRECATED( wxStringList() );
 557     wxDEPRECATED( wxStringList(const wxChar *first ...) );
 558 #else
 559     wxStringList();
 560     wxStringList(const wxChar *first ...);
 561 #endif
 562
 563         // copying the string list: the strings are copied, too (extremely
 564         // inefficient!)
 565     wxStringList(const wxStringList& other) : wxStringListBase() { DeleteContents(TRUE); DoCopy(other); }
 566     wxStringList& operator=(const wxStringList& other)
 567         { Clear(); DoCopy(other); return *this; }
 568
 569     // operations
 570         // makes a copy of the string
 571     wxNode *Add(const wxChar *s)
 572         { return (wxNode *)wxStringListBase::Append(copystring(s)); }
 573
 574         // Append to beginning of list
 575     wxNode *Prepend(const wxChar *s)
 576         { return (wxNode *)wxStringListBase::Insert(copystring(s)); }
 577
 578     bool Delete(const wxChar *s);
 579
 580     wxChar **ListToArray(bool new_copies = FALSE) const;
 581     bool Member(const wxChar *s) const;
 582
 583     // alphabetic sort
 584     void Sort();
 585
 586 private:
 587     void DoCopy(const wxStringList&); // common part of copy ctor and operator=
 588
 589     DECLARE_DYNAMIC_CLASS(wxStringList)
 590 };
 591
 592 #endif // wxLIST_COMPATIBILITY
 593
 594 #endif
 595     // _WX_LISTH__