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