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