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