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