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