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