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