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