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