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