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 char* WXDLLEXPORT 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     // comparaison
 110     bool operator==(wxListKeyValue value) const
 111     {
 112         switch ( m_keyType )
 113         {
 114             default:
 115                 wxFAIL_MSG("bad key type.");
 116                 // let compiler optimize the line above away in release build
 117                 // by not putting return here...
 118
 119             case wxKEY_STRING:
 120                 return strcmp(m_key.string, value.string) == 0;
 121
 122             case wxKEY_INTEGER:
 123                 return m_key.integer == value.integer;
 124         }
 125     }
 126
 127     // dtor
 128     ~wxListKey()
 129     {
 130         if ( m_keyType == wxKEY_STRING )
 131             free(m_key.string);
 132     }
 133
 134 private:
 135     wxKeyType m_keyType;
 136     wxListKeyValue m_key;
 137 };
 138
 139 // -----------------------------------------------------------------------------
 140 // wxNodeBase class is a (base for) node in a double linked list
 141 // -----------------------------------------------------------------------------
 142
 143 class WXDLLEXPORT wxNodeBase
 144 {
 145 friend class wxListBase;
 146 public:
 147     // ctor
 148     wxNodeBase(wxListBase *list = (wxListBase *)NULL,
 149                wxNodeBase *previous = (wxNodeBase *)NULL,
 150                wxNodeBase *next = (wxNodeBase *)NULL,
 151                void *data = NULL,
 152                const wxListKey& key = wxListKey());
 153
 154     virtual ~wxNodeBase();
 155
 156     // @@ no check is done that the list is really keyed on strings
 157     const char *GetKeyString() const { return m_key.string; }
 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     virtual void DeleteData() { }
 175
 176 private:
 177     // optional key stuff
 178     wxListKeyValue m_key;
 179
 180     void        *m_data;        // user data
 181     wxNodeBase  *m_next,        // next and previous nodes in the list
 182                 *m_previous;
 183
 184     wxListBase  *m_list;        // list we belong to
 185 };
 186
 187 // -----------------------------------------------------------------------------
 188 // a double-linked list class
 189 // -----------------------------------------------------------------------------
 190 class WXDLLEXPORT wxListBase : public wxObject
 191 {
 192 friend class wxNodeBase; // should be able to call DetachNode()
 193 public:
 194     // default ctor & dtor
 195     wxListBase(wxKeyType keyType = wxKEY_NONE) { Init(keyType); }
 196     virtual ~wxListBase();
 197
 198     // accessors
 199         // count of items in the list
 200     size_t GetCount() const { return m_count; }
 201
 202     // operations
 203         // delete all nodes
 204     virtual void Clear();
 205         // instruct it to destroy user data when deleting nodes
 206     void DeleteContents(bool destroy) { m_destroy = destroy; }
 207
 208 protected:
 209     // all methods here are "overloaded" in derived classes to provide compile
 210     // time type checking
 211
 212     // create a node for the list of this type
 213     virtual wxNodeBase *CreateNode(wxNodeBase *prev, wxNodeBase *next,
 214                                    void *data,
 215                                    const wxListKey& key = wxListKey()) = 0;
 216
 217     // ctors
 218         // from an array
 219     wxListBase(size_t count, void *elements[]);
 220         // from a sequence of objects
 221     wxListBase(void *object, ... /* terminate with NULL */);
 222
 223         // copy ctor and assignment operator
 224     wxListBase(const wxListBase& list)
 225         { DoCopy(list); }
 226     wxListBase& operator=(const wxListBase& list)
 227         { Clear(); DoCopy(list); return *this; }
 228
 229         // get list head/tail
 230     wxNodeBase *GetFirst() const { return m_nodeFirst; }
 231     wxNodeBase *GetLast() const { return m_nodeLast; }
 232
 233         // by (0-based) index
 234     wxNodeBase *Item(size_t index) const;
 235
 236         // get the list item's data
 237     void *operator[](size_t index) const
 238         { wxNodeBase *node = Item(index); return node ? node->GetData() : NULL; }
 239
 240     // operations
 241         // append to end of list
 242     wxNodeBase *Append(void *object);
 243         // insert a new item at the beginning of the list
 244     wxNodeBase *Insert(void *object) { return Insert(NULL, object); }
 245         // insert before given node or at front of list if prev == NULL
 246     wxNodeBase *Insert(wxNodeBase *prev, void *object);
 247
 248         // keyed append
 249     wxNodeBase *Append(long key, void *object);
 250     wxNodeBase *Append(const char *key, void *object);
 251
 252         // removes node from the list but doesn't delete it (returns pointer
 253         // to the node or NULL if it wasn't found in the list)
 254     wxNodeBase *DetachNode(wxNodeBase *node);
 255         // delete element from list, returns FALSE if node not found
 256     bool DeleteNode(wxNodeBase *node);
 257         // finds object pointer and deletes node (and object if DeleteContents
 258         // is on), returns FALSE if object not found
 259     bool DeleteObject(void *object);
 260
 261     // search (all return NULL if item not found)
 262         // by data
 263     wxNodeBase *Find(void *object) const;
 264
 265         // by key
 266     wxNodeBase *Find(const wxListKey& key) const;
 267
 268     // this function allows the sorting of arbitrary lists by giving
 269     // a function to compare two list elements. The list is sorted in place.
 270     void Sort(wxSortCompareFunction compfunc);
 271
 272     // functions for iterating over the list
 273     void *FirstThat(wxListIterateFunction func);
 274     void ForEach(wxListIterateFunction func);
 275     void *LastThat(wxListIterateFunction func);
 276
 277 private:
 278     // helpers
 279         // common part of all ctors
 280     void Init(wxKeyType keyType);
 281         // common part of copy ctor and assignment operator
 282     void DoCopy(const wxListBase& list);
 283         // common part of all Append()s
 284     wxNodeBase *AppendCommon(wxNodeBase *node);
 285         // free node's data and node itself
 286     void DoDeleteNode(wxNodeBase *node);
 287
 288     size_t m_count;             // number of elements in the list
 289     bool m_destroy;             // destroy user data when deleting list items?
 290     wxNodeBase *m_nodeFirst,    // pointers to the head and tail of the list
 291                *m_nodeLast;
 292
 293     wxKeyType m_keyType;        // type of our keys (may be wxKEY_NONE)
 294 };
 295
 296 // -----------------------------------------------------------------------------
 297 // macros for definition of "template" list type
 298 // -----------------------------------------------------------------------------
 299
 300 // and now some heavy magic...
 301
 302 // declare a list type named 'name' and containing elements of type 'T *'
 303 // (as a by product of macro expansion you also get wx##name##Node
 304 // wxNode-dervied type)
 305 //
 306 // implementation details:
 307 //  1. we define _WX_LIST_ITEM_TYPE_##name typedef to save in it the item type
 308 //     for the list of given type - this allows us to pass only the list name
 309 //     to WX_DEFINE_LIST() even if it needs both the name and the type
 310 //
 311 //  2. We redefine all not type-safe wxList functions withtype-safe versions
 312 //     which don't take any place (everything is inline), but bring compile
 313 //     time error checking.
 314
 315 #define WX_DECLARE_LIST_2(T, name, nodetype)                                \
 316     typedef int (*wxSortFuncFor_##name)(const T *, const T *);              \
 317                                                                             \
 318     class WXDLLEXPORT nodetype : public wxNodeBase                          \
 319     {                                                                       \
 320     public:                                                                 \
 321         nodetype(wxListBase *list = (wxListBase *)NULL,                     \
 322                  nodetype *previous = (nodetype *)NULL,                     \
 323                  nodetype *next = (nodetype *)NULL,                         \
 324                  T *data = NULL,                                            \
 325                  const wxListKey& key = wxListKey())                        \
 326             : wxNodeBase(list, previous, next, data, key) { }               \
 327                                                                             \
 328         nodetype *GetNext() const                                           \
 329             { return (nodetype *)wxNodeBase::GetNext(); }                   \
 330         nodetype *GetPrevious() const                                       \
 331             { return (nodetype *)wxNodeBase::GetPrevious(); }               \
 332                                                                             \
 333         T *GetData() const                                                  \
 334             { return (T *)wxNodeBase::GetData(); }                          \
 335         void SetData(T *data)                                               \
 336             { wxNodeBase::SetData(data); }                                  \
 337                                                                             \
 338         virtual void DeleteData();                                          \
 339     };                                                                      \
 340                                                                             \
 341     class name : public wxListBase                                          \
 342     {                                                                       \
 343     public:                                                                 \
 344         name(wxKeyType keyType = wxKEY_NONE) : wxListBase(keyType)          \
 345             { }                                                             \
 346         name(size_t count, T *elements[])                                   \
 347             : wxListBase(count, (void **)elements) { }                      \
 348                                                                             \
 349         nodetype *GetFirst() const                                          \
 350             { return (nodetype *)wxListBase::GetFirst(); }                  \
 351         nodetype *GetLast() const                                           \
 352             { return (nodetype *)wxListBase::GetLast(); }                   \
 353                                                                             \
 354         nodetype *Item(size_t index) const                                  \
 355             { return (nodetype *)wxListBase::Item(index); }                 \
 356                                                                             \
 357         T *operator[](size_t index) const                                   \
 358         {                                                                   \
 359             nodetype *node = Item(index);                                   \
 360             return node ? node->GetData() : NULL;                           \
 361         }                                                                   \
 362                                                                             \
 363         nodetype *Append(T *object)                                         \
 364             { return (nodetype *)wxListBase::Append(object); }              \
 365         nodetype *Insert(T *object)                                         \
 366             { return (nodetype *)Insert(NULL, object); }                    \
 367         nodetype *Insert(nodetype *prev, T *object)                         \
 368             { return (nodetype *)wxListBase::Insert(prev, object); }        \
 369                                                                             \
 370         nodetype *Append(long key, void *object)                            \
 371             { return (nodetype *)wxListBase::Append(key, object); }         \
 372         nodetype *Append(const char *key, void *object)                     \
 373             { return (nodetype *)wxListBase::Append(key, object); }         \
 374                                                                             \
 375         nodetype *DetachNode(nodetype *node)                                \
 376             { return (nodetype *)wxListBase::DetachNode(node); }            \
 377         bool DeleteNode(nodetype *node)                                     \
 378             { return wxListBase::DeleteNode(node); }                        \
 379         bool DeleteObject(T *object)                                        \
 380             { return wxListBase::DeleteObject(object); }                    \
 381                                                                             \
 382         nodetype *Find(T *object) const                                     \
 383             { return (nodetype *)wxListBase::Find(object); }                \
 384                                                                             \
 385         virtual nodetype *Find(const wxListKey& key) const                  \
 386             { return (nodetype *)wxListBase::Find(key); }                   \
 387                                                                             \
 388         void Sort(wxSortFuncFor_##name func)                                \
 389             { wxListBase::Sort((wxSortCompareFunction)func); }              \
 390                                                                             \
 391     protected:                                                              \
 392         wxNodeBase *CreateNode(wxNodeBase *prev, wxNodeBase *next,          \
 393                                void *data,                                  \
 394                                const wxListKey& key = wxListKey())          \
 395             {                                                               \
 396                 return new nodetype(this,                                   \
 397                                     (nodetype *)prev, (nodetype *)next,     \
 398                                     (T *)data, key);                        \
 399             }                                                               \
 400     }
 401
 402 #define WX_DECLARE_LIST(elementtype, listname)                              \
 403     typedef elementtype _WX_LIST_ITEM_TYPE_##listname;                      \
 404     WX_DECLARE_LIST_2(elementtype, listname, wx##listname##Node)
 405
 406 // this macro must be inserted in your program after
 407 //      #include <wx/listimpl.cpp>
 408 #define WX_DEFINE_LIST(name)    "don't forget to include listimpl.cpp!"
 409
 410
 411 // =============================================================================
 412 // now we can define classes 100% compatible with the old ones
 413 // =============================================================================
 414
 415 #ifdef wxLIST_COMPATIBILITY
 416
 417 // -----------------------------------------------------------------------------
 418 // wxList compatibility class: in fact, it's a list of wxObjects
 419 // -----------------------------------------------------------------------------
 420
 421 WX_DECLARE_LIST_2(wxObject, wxObjectList, wxObjectListNode);
 422
 423 class WXDLLEXPORT wxList : public wxObjectList
 424 {
 425 public:
 426     wxList(int key_type = wxKEY_NONE) : wxObjectList((wxKeyType)key_type) { }
 427
 428     // compatibility methods
 429     void Sort(wxSortCompareFunction compfunc) { wxListBase::Sort(compfunc); }
 430
 431     int Number() const { return GetCount(); }
 432     wxNode *First() const { return (wxNode *)GetFirst(); }
 433     wxNode *Last() const { return (wxNode *)GetLast(); }
 434     wxNode *Nth(size_t index) const { return (wxNode *)Item(index); }
 435     wxNode *Member(wxObject *object) const { return (wxNode *)Find(object); }
 436 };
 437
 438 // -----------------------------------------------------------------------------
 439 // wxStringList class for compatibility with the old code
 440 // -----------------------------------------------------------------------------
 441
 442 WX_DECLARE_LIST_2(char, wxStringListBase, wxStringListNode);
 443
 444 class WXDLLEXPORT wxStringList : public wxStringListBase
 445 {
 446 public:
 447     // ctors and such
 448         // default
 449     wxStringList() { DeleteContents(TRUE); }
 450     wxStringList(const char *first ...);
 451
 452     // operations
 453         // makes a copy of the string
 454     wxNode *Add(const char *s)
 455         { return (wxNode *)wxStringListBase::Append(copystring(s)); }
 456
 457     void Delete(const char *s)
 458         { wxStringListBase::DeleteObject((char *)s); }
 459
 460     char **ListToArray(bool new_copies = FALSE) const;
 461     bool Member(const char *s) const;
 462
 463     // alphabetic sort
 464     void Sort();
 465
 466     // compatibility methods
 467     int Number() const { return GetCount(); }
 468     wxNode *First() const { return (wxNode *)GetFirst(); }
 469     wxNode *Last() const { return (wxNode *)GetLast(); }
 470     wxNode *Nth(size_t index) const { return (wxNode *)Item(index); }
 471 };
 472
 473 #endif // wxLIST_COMPATIBILITY
 474
 475 #endif
 476     // _WX_LISTH__