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