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