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