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 char* copystring(const char *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 (*wxSortCompareFunction)(const void *elem1, const void *elem2);
  69
  70 //
  71 typedef int (*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     char *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 char *s)
  98         { m_keyType = wxKEY_STRING; m_key.string = strdup(s); }
  99     wxListKey(const wxString& s)
 100         { m_keyType = wxKEY_STRING; m_key.string = strdup(s.c_str()); }
 101
 102     // accessors
 103     wxKeyType GetKeyType() const { return m_keyType; }
 104     const char *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     // @@ no check is done that the list is really keyed on strings
 146     const char *GetKeyString() const { return m_key.string; }
 147     long GetKeyInteger() const { return m_key.integer; }
 148
 149     // Necessary for some existing code
 150     void SetKeyString(char* 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 public:
 191     // default ctor & dtor
 192     wxListBase(wxKeyType keyType = wxKEY_NONE) { Init(keyType); }
 193     virtual ~wxListBase();
 194
 195     // accessors
 196         // count of items in the list
 197     size_t GetCount() const { return m_count; }
 198
 199     // operations
 200
 201         // delete all nodes
 202     void Clear();
 203
 204         // instruct it to destroy user data when deleting nodes
 205     void DeleteContents(bool destroy) { m_destroy = destroy; }
 206
 207        // query if to delete
 208     bool GetDeleteContents() const
 209         { return m_destroy; }
 210
 211       // get the keytype
 212     wxKeyType GetKeyType() const
 213         { return m_keyType; }
 214
 215       // set the keytype (required by the serial code)
 216     void SetKeyType(wxKeyType keyType)
 217         { wxASSERT( m_count==0 ); m_keyType = keyType; }
 218
 219 protected:
 220
 221     // all methods here are "overloaded" in derived classes to provide compile
 222     // time type checking
 223
 224     // create a node for the list of this type
 225     virtual wxNodeBase *CreateNode(wxNodeBase *prev, wxNodeBase *next,
 226                                    void *data,
 227                                    const wxListKey& key = wxDefaultListKey) = 0;
 228
 229 // Can't access these from derived classes otherwise (bug in Salford C++?)
 230 #ifdef __SALFORDC__
 231 public:
 232 #endif
 233
 234     // ctors
 235         // from an array
 236     wxListBase(size_t count, void *elements[]);
 237         // from a sequence of objects
 238     wxListBase(void *object, ... /* terminate with NULL */);
 239
 240 protected:
 241         // copy ctor and assignment operator
 242     wxListBase(const wxListBase& list)
 243         { DoCopy(list); }
 244     wxListBase& operator=(const wxListBase& list)
 245         { Clear(); DoCopy(list); return *this; }
 246
 247         // get list head/tail
 248     wxNodeBase *GetFirst() const { return m_nodeFirst; }
 249     wxNodeBase *GetLast() const { return m_nodeLast; }
 250
 251         // by (0-based) index
 252     wxNodeBase *Item(size_t index) const;
 253
 254         // get the list item's data
 255     void *operator[](size_t index) const
 256         { wxNodeBase *node = Item(index); return node ? node->GetData() : (wxNodeBase*)NULL; }
 257
 258     // operations
 259         // append to end of list
 260     wxNodeBase *Append(void *object);
 261         // insert a new item at the beginning of the list
 262     wxNodeBase *Insert(void *object) { return Insert( (wxNodeBase*)NULL, object); }
 263         // insert before given node or at front of list if prev == NULL
 264     wxNodeBase *Insert(wxNodeBase *prev, void *object);
 265
 266         // keyed append
 267     wxNodeBase *Append(long key, void *object);
 268     wxNodeBase *Append(const char *key, void *object);
 269
 270         // removes node from the list but doesn't delete it (returns pointer
 271         // to the node or NULL if it wasn't found in the list)
 272     wxNodeBase *DetachNode(wxNodeBase *node);
 273         // delete element from list, returns FALSE if node not found
 274     bool DeleteNode(wxNodeBase *node);
 275         // finds object pointer and deletes node (and object if DeleteContents
 276         // is on), returns FALSE if object not found
 277     bool DeleteObject(void *object);
 278
 279     // search (all return NULL if item not found)
 280         // by data
 281     wxNodeBase *Find(void *object) const;
 282
 283         // by key
 284     wxNodeBase *Find(const wxListKey& key) const;
 285
 286     // get 0-based index of object or wxNOT_FOUND
 287     int IndexOf( void *object ) const;
 288
 289     // this function allows the sorting of arbitrary lists by giving
 290     // a function to compare two list elements. The list is sorted in place.
 291     void Sort(const wxSortCompareFunction compfunc);
 292
 293     // functions for iterating over the list
 294     void *FirstThat(wxListIterateFunction func);
 295     void ForEach(wxListIterateFunction func);
 296     void *LastThat(wxListIterateFunction func);
 297
 298 private:
 299     // helpers
 300         // common part of all ctors
 301     void Init(wxKeyType keyType = wxKEY_NONE);
 302         // common part of copy ctor and assignment operator
 303     void DoCopy(const wxListBase& list);
 304         // common part of all Append()s
 305     wxNodeBase *AppendCommon(wxNodeBase *node);
 306         // free node's data and node itself
 307     void DoDeleteNode(wxNodeBase *node);
 308
 309     size_t m_count;             // number of elements in the list
 310     bool m_destroy;             // destroy user data when deleting list items?
 311     wxNodeBase *m_nodeFirst,    // pointers to the head and tail of the list
 312                *m_nodeLast;
 313
 314     wxKeyType m_keyType;        // type of our keys (may be wxKEY_NONE)
 315 };
 316
 317 // -----------------------------------------------------------------------------
 318 // macros for definition of "template" list type
 319 // -----------------------------------------------------------------------------
 320
 321 // and now some heavy magic...
 322
 323 // declare a list type named 'name' and containing elements of type 'T *'
 324 // (as a by product of macro expansion you also get wx##name##Node
 325 // wxNode-derived type)
 326 //
 327 // implementation details:
 328 //  1. We define _WX_LIST_ITEM_TYPE_##name typedef to save in it the item type
 329 //     for the list of given type - this allows us to pass only the list name
 330 //     to WX_DEFINE_LIST() even if it needs both the name and the type
 331 //
 332 //  2. We redefine all non-type-safe wxList functions with type-safe versions
 333 //     which don't take any space (everything is inline), but bring compile
 334 //     time error checking.
 335
 336 #define WX_DECLARE_LIST_2(T, name, nodetype)                                \
 337     typedef int (*wxSortFuncFor_##name)(const T *, const T *);              \
 338                                                                             \
 339     class WXDLLEXPORT nodetype : public wxNodeBase                          \
 340     {                                                                       \
 341     public:                                                                 \
 342         nodetype(wxListBase *list = (wxListBase *)NULL,                     \
 343                  nodetype *previous = (nodetype *)NULL,                     \
 344                  nodetype *next = (nodetype *)NULL,                         \
 345                  T *data = (T *)NULL,                                       \
 346                  const wxListKey& key = wxDefaultListKey)                        \
 347             : wxNodeBase(list, previous, next, data, key) { }               \
 348                                                                             \
 349         nodetype *GetNext() const                                           \
 350             { return (nodetype *)wxNodeBase::GetNext(); }                   \
 351         nodetype *GetPrevious() const                                       \
 352             { return (nodetype *)wxNodeBase::GetPrevious(); }               \
 353                                                                             \
 354         T *GetData() const                                                  \
 355             { return (T *)wxNodeBase::GetData(); }                          \
 356         void SetData(T *data)                                               \
 357             { wxNodeBase::SetData(data); }                                  \
 358                                                                             \
 359         virtual void DeleteData();                                          \
 360     };                                                                      \
 361                                                                             \
 362     class WXDLLEXPORT name : public wxListBase                                          \
 363     {                                                                       \
 364     public:                                                                 \
 365         typedef nodetype Node;                                              \
 366                                                                             \
 367         name(wxKeyType keyType = wxKEY_NONE) : wxListBase(keyType)          \
 368             { }                                                             \
 369         name(size_t count, T *elements[])                                   \
 370             : wxListBase(count, (void **)elements) { }                      \
 371                                                                             \
 372         nodetype *GetFirst() const                                          \
 373             { return (nodetype *)wxListBase::GetFirst(); }                  \
 374         nodetype *GetLast() const                                           \
 375             { return (nodetype *)wxListBase::GetLast(); }                   \
 376                                                                             \
 377         nodetype *Item(size_t index) const                                  \
 378             { return (nodetype *)wxListBase::Item(index); }                 \
 379                                                                             \
 380         T *operator[](size_t index) const                                   \
 381         {                                                                   \
 382             nodetype *node = Item(index);                                   \
 383             return node ? (T*)(node->GetData()) : (T*)NULL;                 \
 384         }                                                                   \
 385                                                                             \
 386         nodetype *Append(T *object)                                         \
 387             { return (nodetype *)wxListBase::Append(object); }              \
 388         nodetype *Insert(T *object)                                         \
 389             { return (nodetype *)Insert((nodetype*)NULL, object); }         \
 390         nodetype *Insert(nodetype *prev, T *object)                         \
 391             { return (nodetype *)wxListBase::Insert(prev, object); }        \
 392                                                                             \
 393         nodetype *Append(long key, void *object)                            \
 394             { return (nodetype *)wxListBase::Append(key, object); }         \
 395         nodetype *Append(const char *key, void *object)                     \
 396             { return (nodetype *)wxListBase::Append(key, object); }         \
 397                                                                             \
 398         nodetype *DetachNode(nodetype *node)                                \
 399             { return (nodetype *)wxListBase::DetachNode(node); }            \
 400         bool DeleteNode(nodetype *node)                                     \
 401             { return wxListBase::DeleteNode(node); }                        \
 402         bool DeleteObject(T *object)                                        \
 403             { return wxListBase::DeleteObject(object); }                    \
 404                                                                             \
 405         nodetype *Find(T *object) const                                     \
 406             { return (nodetype *)wxListBase::Find(object); }                \
 407                                                                             \
 408         virtual nodetype *Find(const wxListKey& key) const                  \
 409             { return (nodetype *)wxListBase::Find(key); }                   \
 410                                                                             \
 411         int IndexOf( T *object ) const                                      \
 412             { return wxListBase::IndexOf(object); }                         \
 413                                                                             \
 414         void Sort(wxSortFuncFor_##name func)                                \
 415             { wxListBase::Sort((wxSortCompareFunction)func); }              \
 416                                                                             \
 417     protected:                                                              \
 418         wxNodeBase *CreateNode(wxNodeBase *prev, wxNodeBase *next,          \
 419                                void *data,                                  \
 420                                const wxListKey& key = wxDefaultListKey)          \
 421             {                                                               \
 422                 return new nodetype(this,                                   \
 423                                     (nodetype *)prev, (nodetype *)next,     \
 424                                     (T *)data, key);                        \
 425             }                                                               \
 426     }
 427
 428 #define WX_DECLARE_LIST(elementtype, listname)                              \
 429     typedef elementtype _WX_LIST_ITEM_TYPE_##listname;                      \
 430     WX_DECLARE_LIST_2(elementtype, listname, wx##listname##Node)
 431
 432 // this macro must be inserted in your program after
 433 //      #include <wx/listimpl.cpp>
 434 #define WX_DEFINE_LIST(name)    "don't forget to include listimpl.cpp!"
 435
 436
 437 // =============================================================================
 438 // now we can define classes 100% compatible with the old ones
 439 // =============================================================================
 440
 441 #ifdef wxLIST_COMPATIBILITY
 442
 443 // -----------------------------------------------------------------------------
 444 // wxList compatibility class: in fact, it's a list of wxObjects
 445 // -----------------------------------------------------------------------------
 446
 447 WX_DECLARE_LIST_2(wxObject, wxObjectList, wxObjectListNode);
 448
 449 class WXDLLEXPORT wxList : public wxObjectList
 450 {
 451 public:
 452     wxList(int key_type = wxKEY_NONE) : wxObjectList((wxKeyType)key_type) { }
 453
 454     // compatibility methods
 455     void Sort(wxSortCompareFunction compfunc) { wxListBase::Sort(compfunc); }
 456
 457     int Number() const { return GetCount(); }
 458     wxNode *First() const { return (wxNode *)GetFirst(); }
 459     wxNode *Last() const { return (wxNode *)GetLast(); }
 460     wxNode *Nth(size_t index) const { return (wxNode *)Item(index); }
 461     wxNode *Member(wxObject *object) const { return (wxNode *)Find(object); }
 462 };
 463
 464 // -----------------------------------------------------------------------------
 465 // wxStringList class for compatibility with the old code
 466 // -----------------------------------------------------------------------------
 467
 468 WX_DECLARE_LIST_2(char, wxStringListBase, wxStringListNode);
 469
 470 class WXDLLEXPORT wxStringList : public wxStringListBase
 471 {
 472 public:
 473     // ctors and such
 474         // default
 475     wxStringList() { DeleteContents(TRUE); }
 476     wxStringList(const char *first ...);
 477
 478         // copying the string list: the strings are copied, too (extremely
 479         // inefficient!)
 480     wxStringList(const wxStringList& other) { DoCopy(other); }
 481     wxStringList& operator=(const wxStringList& other)
 482         { Clear(); DoCopy(other); return *this; }
 483
 484     // operations
 485         // makes a copy of the string
 486     wxNode *Add(const char *s)
 487         { return (wxNode *)wxStringListBase::Append(copystring(s)); }
 488
 489     bool Delete(const char *s);
 490
 491     char **ListToArray(bool new_copies = FALSE) const;
 492     bool Member(const char *s) const;
 493
 494     // alphabetic sort
 495     void Sort();
 496
 497     // compatibility methods
 498     int Number() const { return GetCount(); }
 499     wxNode *First() const { return (wxNode *)GetFirst(); }
 500     wxNode *Last() const { return (wxNode *)GetLast(); }
 501     wxNode *Nth(size_t index) const { return (wxNode *)Item(index); }
 502
 503 private:
 504     void DoCopy(const wxStringList&); // common part of copy ctor and operator=
 505 };
 506
 507 #endif // wxLIST_COMPATIBILITY
 508
 509 #endif
 510     // _WX_LISTH__