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 #if defined(__GNUG__) && !defined(__APPLE__)
  29 #pragma interface "list.h"
  30 #endif
  31
  32 // -----------------------------------------------------------------------------
  33 // headers
  34 // -----------------------------------------------------------------------------
  35
  36 #include "wx/defs.h"
  37 #include "wx/object.h"
  38 #include "wx/string.h"
  39
  40 // due to circular header dependencies this function has to be declared here
  41 // (normally it's found in utils.h which includes itself list.h...)
  42 extern WXDLLEXPORT wxChar* copystring(const wxChar *s);
  43
  44 class WXDLLEXPORT wxObjectListNode;
  45 typedef wxObjectListNode wxNode;
  46
  47 // undef it to get rid of old, deprecated functions
  48 #define wxLIST_COMPATIBILITY
  49
  50 // -----------------------------------------------------------------------------
  51 // constants
  52 // -----------------------------------------------------------------------------
  53 enum wxKeyType
  54 {
  55     wxKEY_NONE,
  56     wxKEY_INTEGER,
  57     wxKEY_STRING
  58 };
  59
  60 // -----------------------------------------------------------------------------
  61 // types
  62 // -----------------------------------------------------------------------------
  63
  64 // type of compare function for list sort operation (as in 'qsort'): it should
  65 // return a negative value, 0 or positive value if the first element is less
  66 // than, equal or greater than the second
  67 extern "C"
  68 {
  69 typedef int (* LINKAGEMODE wxSortCompareFunction)(const void *elem1, const void *elem2);
  70 }
  71
  72 //
  73 typedef int (* LINKAGEMODE wxListIterateFunction)(void *current);
  74
  75 // -----------------------------------------------------------------------------
  76 // key stuff: a list may be optionally keyed on integer or string key
  77 // -----------------------------------------------------------------------------
  78
  79 union wxListKeyValue
  80 {
  81     long integer;
  82     wxChar *string;
  83 };
  84
  85 // a struct which may contain both types of keys
  86 //
  87 // implementation note: on one hand, this class allows to have only one function
  88 // for any keyed operation instead of 2 almost equivalent. OTOH, it's needed to
  89 // resolve ambiguity which we would otherwise have with wxStringList::Find() and
  90 // wxList::Find(const char *).
  91 class WXDLLEXPORT wxListKey
  92 {
  93 public:
  94     // implicit ctors
  95     wxListKey() : m_keyType(wxKEY_NONE)
  96         { }
  97     wxListKey(long i) : m_keyType(wxKEY_INTEGER)
  98         { m_key.integer = i; }
  99     wxListKey(const wxChar *s) : m_keyType(wxKEY_STRING)
 100         { m_key.string = wxStrdup(s); }
 101     wxListKey(const wxString& s) : m_keyType(wxKEY_STRING)
 102         { m_key.string = wxStrdup(s.c_str()); }
 103
 104     // accessors
 105     wxKeyType GetKeyType() const { return m_keyType; }
 106     const wxChar *GetString() const
 107         { wxASSERT( m_keyType == wxKEY_STRING ); return m_key.string; }
 108     long GetNumber() const
 109         { wxASSERT( m_keyType == wxKEY_INTEGER ); return m_key.integer; }
 110
 111     // comparison
 112     // Note: implementation moved to list.cpp to prevent BC++ inline
 113     // expansion warning.
 114     bool operator==(wxListKeyValue value) const ;
 115
 116     // dtor
 117     ~wxListKey()
 118     {
 119         if ( m_keyType == wxKEY_STRING )
 120             free(m_key.string);
 121     }
 122
 123 private:
 124     wxKeyType m_keyType;
 125     wxListKeyValue m_key;
 126 };
 127
 128 // -----------------------------------------------------------------------------
 129 // wxNodeBase class is a (base for) node in a double linked list
 130 // -----------------------------------------------------------------------------
 131
 132 WXDLLEXPORT_DATA(extern wxListKey) wxDefaultListKey;
 133
 134 class WXDLLEXPORT wxListBase;
 135
 136 class WXDLLEXPORT wxNodeBase
 137 {
 138 friend class wxListBase;
 139 public:
 140     // ctor
 141     wxNodeBase(wxListBase *list = (wxListBase *)NULL,
 142                wxNodeBase *previous = (wxNodeBase *)NULL,
 143                wxNodeBase *next = (wxNodeBase *)NULL,
 144                void *data = NULL,
 145                const wxListKey& key = wxDefaultListKey);
 146
 147     virtual ~wxNodeBase();
 148
 149     // FIXME no check is done that the list is really keyed on strings
 150     const wxChar *GetKeyString() const { return m_key.string; }
 151     long GetKeyInteger() const { return m_key.integer; }
 152
 153     // Necessary for some existing code
 154     void SetKeyString(wxChar* s) { m_key.string = s; }
 155     void SetKeyInteger(long i) { m_key.integer = i; }
 156
 157 #ifdef wxLIST_COMPATIBILITY
 158     // compatibility methods
 159     wxNode *Next() const { return (wxNode *)GetNext(); }
 160     wxNode *Previous() const { return (wxNode *)GetPrevious(); }
 161     wxObject *Data() const { return (wxObject *)GetData(); }
 162 #endif // wxLIST_COMPATIBILITY
 163
 164 protected:
 165     // all these are going to be "overloaded" in the derived classes
 166     wxNodeBase *GetNext() const { return m_next; }
 167     wxNodeBase *GetPrevious() const { return m_previous; }
 168
 169     void *GetData() const { return m_data; }
 170     void SetData(void *data) { m_data = data; }
 171
 172     // get 0-based index of this node within the list or wxNOT_FOUND
 173     int IndexOf() const;
 174
 175     virtual void DeleteData() { }
 176
 177 private:
 178     // optional key stuff
 179     wxListKeyValue m_key;
 180
 181     void        *m_data;        // user data
 182     wxNodeBase  *m_next,        // next and previous nodes in the list
 183                 *m_previous;
 184
 185     wxListBase  *m_list;        // list we belong to
 186
 187     DECLARE_NO_COPY_CLASS(wxNodeBase)
 188 };
 189
 190 // -----------------------------------------------------------------------------
 191 // a double-linked list class
 192 // -----------------------------------------------------------------------------
 193
 194 class WXDLLEXPORT wxListBase : public wxObject
 195 {
 196 friend class WXDLLEXPORT wxNodeBase; // should be able to call DetachNode()
 197 friend class wxHashTableBase;   // should be able to call untyped Find()
 198 private:
 199         // common part of all ctors
 200     void Init(wxKeyType keyType = wxKEY_NONE); // Must be declared before it's used (for VC++ 1.5)
 201 public:
 202     // default ctor & dtor
 203     wxListBase(wxKeyType keyType = wxKEY_NONE)
 204         { Init(keyType); }
 205     virtual ~wxListBase();
 206
 207     // accessors
 208         // count of items in the list
 209     size_t GetCount() const { return m_count; }
 210
 211         // return TRUE if this list is empty
 212     bool IsEmpty() const { return m_count == 0; }
 213
 214     // operations
 215
 216         // delete all nodes
 217     void Clear();
 218
 219         // instruct it to destroy user data when deleting nodes
 220     void DeleteContents(bool destroy) { m_destroy = destroy; }
 221
 222        // query if to delete
 223     bool GetDeleteContents() const
 224         { return m_destroy; }
 225
 226       // get the keytype
 227     wxKeyType GetKeyType() const
 228         { return m_keyType; }
 229
 230       // set the keytype (required by the serial code)
 231     void SetKeyType(wxKeyType keyType)
 232         { wxASSERT( m_count==0 ); m_keyType = keyType; }
 233
 234 #ifdef wxLIST_COMPATIBILITY
 235     int Number() const { return GetCount(); }
 236     wxNode *First() const { return (wxNode *)GetFirst(); }
 237     wxNode *Last() const { return (wxNode *)GetLast(); }
 238     wxNode *Nth(size_t n) const { return (wxNode *)Item(n); }
 239 #endif // wxLIST_COMPATIBILITY
 240
 241 protected:
 242
 243     // all methods here are "overloaded" in derived classes to provide compile
 244     // time type checking
 245
 246     // create a node for the list of this type
 247     virtual wxNodeBase *CreateNode(wxNodeBase *prev, wxNodeBase *next,
 248                                    void *data,
 249                                    const wxListKey& key = wxDefaultListKey) = 0;
 250
 251 // Can't access these from derived classes otherwise (bug in Salford C++?)
 252 #ifdef __SALFORDC__
 253 public:
 254 #endif
 255
 256     // ctors
 257         // from an array
 258     wxListBase(size_t count, void *elements[]);
 259         // from a sequence of objects
 260     wxListBase(void *object, ... /* terminate with NULL */);
 261
 262 protected:
 263         // copy ctor and assignment operator
 264     wxListBase(const wxListBase& list) : wxObject()
 265         { Init(); DoCopy(list); }
 266     wxListBase& operator=(const wxListBase& list)
 267         { Clear(); DoCopy(list); return *this; }
 268
 269         // get list head/tail
 270     wxNodeBase *GetFirst() const { return m_nodeFirst; }
 271     wxNodeBase *GetLast() const { return m_nodeLast; }
 272
 273         // by (0-based) index
 274     wxNodeBase *Item(size_t index) const;
 275
 276         // get the list item's data
 277     void *operator[](size_t n) const
 278     {
 279         wxNodeBase *node = Item(n);
 280
 281         return node ? node->GetData() : (wxNodeBase *)NULL;
 282     }
 283
 284     // operations
 285         // append to end of list
 286     wxNodeBase *Prepend(void *object)
 287         { return (wxNodeBase *)wxListBase::Insert(object); }
 288         // append to beginning of list
 289     wxNodeBase *Append(void *object);
 290         // insert a new item at the beginning of the list
 291     wxNodeBase *Insert(void *object) { return Insert( (wxNodeBase*)NULL, object); }
 292         // insert a new item at the given position
 293     wxNodeBase *Insert(size_t pos, void *object)
 294         { return pos == GetCount() ? Append(object)
 295                                    : Insert(Item(pos), object); }
 296         // insert before given node or at front of list if prev == NULL
 297     wxNodeBase *Insert(wxNodeBase *prev, void *object);
 298
 299         // keyed append
 300     wxNodeBase *Append(long key, void *object);
 301     wxNodeBase *Append(const wxChar *key, void *object);
 302
 303         // removes node from the list but doesn't delete it (returns pointer
 304         // to the node or NULL if it wasn't found in the list)
 305     wxNodeBase *DetachNode(wxNodeBase *node);
 306         // delete element from list, returns FALSE if node not found
 307     bool DeleteNode(wxNodeBase *node);
 308         // finds object pointer and deletes node (and object if DeleteContents
 309         // is on), returns FALSE if object not found
 310     bool DeleteObject(void *object);
 311
 312     // search (all return NULL if item not found)
 313         // by data
 314     wxNodeBase *Find(void *object) const;
 315
 316         // by key
 317     wxNodeBase *Find(const wxListKey& key) const;
 318
 319     // get 0-based index of object or wxNOT_FOUND
 320     int IndexOf( void *object ) const;
 321
 322     // this function allows the sorting of arbitrary lists by giving
 323     // a function to compare two list elements. The list is sorted in place.
 324     void Sort(const wxSortCompareFunction compfunc);
 325
 326     // functions for iterating over the list
 327     void *FirstThat(wxListIterateFunction func);
 328     void ForEach(wxListIterateFunction func);
 329     void *LastThat(wxListIterateFunction func);
 330
 331 private:
 332     // helpers
 333         // common part of copy ctor and assignment operator
 334     void DoCopy(const wxListBase& list);
 335         // common part of all Append()s
 336     wxNodeBase *AppendCommon(wxNodeBase *node);
 337         // free node's data and node itself
 338     void DoDeleteNode(wxNodeBase *node);
 339
 340     size_t m_count;             // number of elements in the list
 341     bool m_destroy;             // destroy user data when deleting list items?
 342     wxNodeBase *m_nodeFirst,    // pointers to the head and tail of the list
 343                *m_nodeLast;
 344
 345     wxKeyType m_keyType;        // type of our keys (may be wxKEY_NONE)
 346 };
 347
 348 // -----------------------------------------------------------------------------
 349 // macros for definition of "template" list type
 350 // -----------------------------------------------------------------------------
 351
 352 // and now some heavy magic...
 353
 354 // declare a list type named 'name' and containing elements of type 'T *'
 355 // (as a by product of macro expansion you also get wx##name##Node
 356 // wxNode-derived type)
 357 //
 358 // implementation details:
 359 //  1. We define _WX_LIST_ITEM_TYPE_##name typedef to save in it the item type
 360 //     for the list of given type - this allows us to pass only the list name
 361 //     to WX_DEFINE_LIST() even if it needs both the name and the type
 362 //
 363 //  2. We redefine all non-type-safe wxList functions with type-safe versions
 364 //     which don't take any space (everything is inline), but bring compile
 365 //     time error checking.
 366 //
 367 //  3. The macro which is usually used (WX_DECLARE_LIST) is defined in terms of
 368 //     a more generic WX_DECLARE_LIST_2 macro which, in turn, uses the most
 369 //     generic WX_DECLARE_LIST_3 one. The last macro adds a sometimes
 370 //     interesting capability to store polymorphic objects in the list and is
 371 //     particularly useful with, for example, "wxWindow *" list where the
 372 //     wxWindowBase pointers are put into the list, but wxWindow pointers are
 373 //     retrieved from it.
 374
 375 #define WX_DECLARE_LIST_3(T, Tbase, name, nodetype, classexp)               \
 376     typedef int (*wxSortFuncFor_##name)(const T **, const T **);            \
 377                                                                             \
 378     classexp nodetype : public wxNodeBase                                   \
 379     {                                                                       \
 380     public:                                                                 \
 381         nodetype(wxListBase *list = (wxListBase *)NULL,                     \
 382                  nodetype *previous = (nodetype *)NULL,                     \
 383                  nodetype *next = (nodetype *)NULL,                         \
 384                  T *data = (T *)NULL,                                       \
 385                  const wxListKey& key = wxDefaultListKey)                   \
 386             : wxNodeBase(list, previous, next, data, key) { }               \
 387                                                                             \
 388         nodetype *GetNext() const                                           \
 389             { return (nodetype *)wxNodeBase::GetNext(); }                   \
 390         nodetype *GetPrevious() const                                       \
 391             { return (nodetype *)wxNodeBase::GetPrevious(); }               \
 392                                                                             \
 393         T *GetData() const                                                  \
 394             { return (T *)wxNodeBase::GetData(); }                          \
 395         void SetData(T *data)                                               \
 396             { wxNodeBase::SetData(data); }                                  \
 397                                                                             \
 398         virtual void DeleteData();                                          \
 399     };                                                                      \
 400                                                                             \
 401     classexp name : public wxListBase                                       \
 402     {                                                                       \
 403     public:                                                                 \
 404         typedef nodetype Node;                                              \
 405                                                                             \
 406         name(wxKeyType keyType = wxKEY_NONE) : wxListBase(keyType)          \
 407             { }                                                             \
 408         name(size_t count, T *elements[])                                   \
 409             : wxListBase(count, (void **)elements) { }                      \
 410                                                                             \
 411         name& operator=(const name& list)                                   \
 412             { (void) wxListBase::operator=(list); return *this; }           \
 413                                                                             \
 414         nodetype *GetFirst() const                                          \
 415             { return (nodetype *)wxListBase::GetFirst(); }                  \
 416         nodetype *GetLast() const                                           \
 417             { return (nodetype *)wxListBase::GetLast(); }                   \
 418                                                                             \
 419         nodetype *Item(size_t index) const                                  \
 420             { return (nodetype *)wxListBase::Item(index); }                 \
 421                                                                             \
 422         T *operator[](size_t index) const                                   \
 423         {                                                                   \
 424             nodetype *node = Item(index);                                   \
 425             return node ? (T*)(node->GetData()) : (T*)NULL;                 \
 426         }                                                                   \
 427                                                                             \
 428         nodetype *Append(Tbase *object)                                     \
 429             { return (nodetype *)wxListBase::Append(object); }              \
 430         nodetype *Insert(Tbase *object)                                     \
 431             { return (nodetype *)Insert((nodetype*)NULL, object); }         \
 432         nodetype *Insert(size_t pos, Tbase *object)                         \
 433             { return (nodetype *)wxListBase::Insert(pos, object); }         \
 434         nodetype *Insert(nodetype *prev, Tbase *object)                     \
 435             { return (nodetype *)wxListBase::Insert(prev, object); }        \
 436                                                                             \
 437         nodetype *Append(long key, void *object)                            \
 438             { return (nodetype *)wxListBase::Append(key, object); }         \
 439         nodetype *Append(const wxChar *key, void *object)                   \
 440             { return (nodetype *)wxListBase::Append(key, object); }         \
 441                                                                             \
 442         nodetype *DetachNode(nodetype *node)                                \
 443             { return (nodetype *)wxListBase::DetachNode(node); }            \
 444         bool DeleteNode(nodetype *node)                                     \
 445             { return wxListBase::DeleteNode(node); }                        \
 446         bool DeleteObject(Tbase *object)                                    \
 447             { return wxListBase::DeleteObject(object); }                    \
 448                                                                             \
 449         nodetype *Find(Tbase *object) const                                 \
 450             { return (nodetype *)wxListBase::Find(object); }                \
 451                                                                             \
 452         virtual nodetype *Find(const wxListKey& key) const                  \
 453             { return (nodetype *)wxListBase::Find(key); }                   \
 454                                                                             \
 455         int IndexOf(Tbase *object) const                                    \
 456             { return wxListBase::IndexOf(object); }                         \
 457                                                                             \
 458         void Sort(wxSortFuncFor_##name func)                                \
 459             { wxListBase::Sort((wxSortCompareFunction)func); }              \
 460                                                                             \
 461     protected:                                                              \
 462         virtual wxNodeBase *CreateNode(wxNodeBase *prev, wxNodeBase *next,  \
 463                                void *data,                                  \
 464                                const wxListKey& key = wxDefaultListKey)     \
 465             {                                                               \
 466                 return new nodetype(this,                                   \
 467                                     (nodetype *)prev, (nodetype *)next,     \
 468                                     (T *)data, key);                        \
 469             }                                                               \
 470     }
 471
 472 #define WX_DECLARE_LIST_2(elementtype, listname, nodename, classexp)        \
 473     WX_DECLARE_LIST_3(elementtype, elementtype, listname, nodename, classexp)
 474
 475 #define WX_DECLARE_LIST(elementtype, listname)                              \
 476     typedef elementtype _WX_LIST_ITEM_TYPE_##listname;                      \
 477     WX_DECLARE_LIST_2(elementtype, listname, wx##listname##Node, class)
 478
 479 #define WX_DECLARE_EXPORTED_LIST(elementtype, listname)                     \
 480     typedef elementtype _WX_LIST_ITEM_TYPE_##listname;                      \
 481     WX_DECLARE_LIST_2(elementtype, listname, wx##listname##Node, class WXDLLEXPORT)
 482
 483 #define WX_DECLARE_USER_EXPORTED_LIST(elementtype, listname, usergoo)       \
 484     typedef elementtype _WX_LIST_ITEM_TYPE_##listname;                      \
 485     WX_DECLARE_LIST_2(elementtype, listname, wx##listname##Node, class usergoo)
 486
 487 // this macro must be inserted in your program after
 488 //      #include <wx/listimpl.cpp>
 489 #define WX_DEFINE_LIST(name)    "don't forget to include listimpl.cpp!"
 490
 491 #define WX_DEFINE_EXPORTED_LIST(name)      WX_DEFINE_LIST(name)
 492 #define WX_DEFINE_USER_EXPORTED_LIST(name) WX_DEFINE_LIST(name)
 493
 494
 495 // =============================================================================
 496 // now we can define classes 100% compatible with the old ones
 497 // =============================================================================
 498
 499 // ----------------------------------------------------------------------------
 500 // commonly used list classes
 501 // ----------------------------------------------------------------------------
 502
 503 #ifdef wxLIST_COMPATIBILITY
 504
 505 // -----------------------------------------------------------------------------
 506 // wxList compatibility class: in fact, it's a list of wxObjects
 507 // -----------------------------------------------------------------------------
 508
 509 WX_DECLARE_LIST_2(wxObject, wxObjectList, wxObjectListNode, class WXDLLEXPORT);
 510
 511 class WXDLLEXPORT wxList : public wxObjectList
 512 {
 513 public:
 514     wxList(int key_type = wxKEY_NONE) : wxObjectList((wxKeyType)key_type) { }
 515     // this destructor is required for Darwin
 516    ~wxList() { }
 517
 518     wxList& operator=(const wxList& list)
 519         { (void) wxListBase::operator=(list); return *this; }
 520
 521     // compatibility methods
 522     void Sort(wxSortCompareFunction compfunc) { wxListBase::Sort(compfunc); }
 523
 524     wxNode *Member(wxObject *object) const { return (wxNode *)Find(object); }
 525
 526 private:
 527     DECLARE_DYNAMIC_CLASS(wxList)
 528 };
 529
 530 // -----------------------------------------------------------------------------
 531 // wxStringList class for compatibility with the old code
 532 // -----------------------------------------------------------------------------
 533
 534 WX_DECLARE_LIST_2(wxChar, wxStringListBase, wxStringListNode, class WXDLLEXPORT);
 535
 536 class WXDLLEXPORT wxStringList : public wxStringListBase
 537 {
 538 public:
 539     // ctors and such
 540         // default
 541     wxStringList() { DeleteContents(TRUE); }
 542     wxStringList(const wxChar *first ...);
 543
 544         // copying the string list: the strings are copied, too (extremely
 545         // inefficient!)
 546     wxStringList(const wxStringList& other) : wxStringListBase() { DeleteContents(TRUE); DoCopy(other); }
 547     wxStringList& operator=(const wxStringList& other)
 548         { Clear(); DoCopy(other); return *this; }
 549
 550     // operations
 551         // makes a copy of the string
 552     wxNode *Add(const wxChar *s)
 553         { return (wxNode *)wxStringListBase::Append(copystring(s)); }
 554
 555         // Append to beginning of list
 556     wxNode *Prepend(const wxChar *s)
 557         { return (wxNode *)wxStringListBase::Insert(copystring(s)); }
 558
 559     bool Delete(const wxChar *s);
 560
 561     wxChar **ListToArray(bool new_copies = FALSE) const;
 562     bool Member(const wxChar *s) const;
 563
 564     // alphabetic sort
 565     void Sort();
 566
 567 private:
 568     void DoCopy(const wxStringList&); // common part of copy ctor and operator=
 569
 570     DECLARE_DYNAMIC_CLASS(wxStringList)
 571 };
 572
 573 #endif // wxLIST_COMPATIBILITY
 574
 575 #endif
 576     // _WX_LISTH__