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: list.h,v 1.1 2006/12/02 15:58:25 scara Exp $ 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 wxListKey()95 wxListKey() : m_keyType(wxKEY_NONE) 96 { } wxListKey(long i)97 wxListKey(long i) : m_keyType(wxKEY_INTEGER) 98 { m_key.integer = i; } wxListKey(const wxChar * s)99 wxListKey(const wxChar *s) : m_keyType(wxKEY_STRING) 100 { m_key.string = wxStrdup(s); } wxListKey(const wxString & s)101 wxListKey(const wxString& s) : m_keyType(wxKEY_STRING) 102 { m_key.string = wxStrdup(s.c_str()); } 103 104 // accessors GetKeyType()105 wxKeyType GetKeyType() const { return m_keyType; } GetString()106 const wxChar *GetString() const 107 { wxASSERT( m_keyType == wxKEY_STRING ); return m_key.string; } GetNumber()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 ~wxListKey()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 GetKeyString()150 const wxChar *GetKeyString() const { return m_key.string; } GetKeyInteger()151 long GetKeyInteger() const { return m_key.integer; } 152 153 // Necessary for some existing code SetKeyString(wxChar * s)154 void SetKeyString(wxChar* s) { m_key.string = s; } SetKeyInteger(long i)155 void SetKeyInteger(long i) { m_key.integer = i; } 156 157 #ifdef wxLIST_COMPATIBILITY 158 // compatibility methods Next()159 wxNode *Next() const { return (wxNode *)GetNext(); } Previous()160 wxNode *Previous() const { return (wxNode *)GetPrevious(); } Data()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 GetNext()166 wxNodeBase *GetNext() const { return m_next; } GetPrevious()167 wxNodeBase *GetPrevious() const { return m_previous; } 168 GetData()169 void *GetData() const { return m_data; } SetData(void * 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 DeleteData()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 GetCount()209 size_t GetCount() const { return m_count; } 210 211 // return TRUE if this list is empty IsEmpty()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 DeleteContents(bool destroy)220 void DeleteContents(bool destroy) { m_destroy = destroy; } 221 222 // query if to delete GetDeleteContents()223 bool GetDeleteContents() const 224 { return m_destroy; } 225 226 // get the keytype GetKeyType()227 wxKeyType GetKeyType() const 228 { return m_keyType; } 229 230 // set the keytype (required by the serial code) SetKeyType(wxKeyType keyType)231 void SetKeyType(wxKeyType keyType) 232 { wxASSERT( m_count==0 ); m_keyType = keyType; } 233 234 #ifdef wxLIST_COMPATIBILITY Number()235 int Number() const { return GetCount(); } First()236 wxNode *First() const { return (wxNode *)GetFirst(); } Last()237 wxNode *Last() const { return (wxNode *)GetLast(); } Nth(size_t n)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 wxListBase(const wxListBase & list)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 GetFirst()270 wxNodeBase *GetFirst() const { return m_nodeFirst; } GetLast()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 Prepend(void * object)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 Insert(void * object)291 wxNodeBase *Insert(void *object) { return Insert( (wxNodeBase*)NULL, object); } 292 // insert a new item at the given position Insert(size_t pos,void * object)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 ~wxList()516 ~wxList() { } 517 518 wxList& operator=(const wxList& list) 519 { (void) wxListBase::operator=(list); return *this; } 520 521 // compatibility methods Sort(wxSortCompareFunction compfunc)522 void Sort(wxSortCompareFunction compfunc) { wxListBase::Sort(compfunc); } 523 Member(wxObject * object)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 wxStringList()541 wxStringList() { DeleteContents(TRUE); } 542 wxStringList(const wxChar *first ...); 543 544 // copying the string list: the strings are copied, too (extremely 545 // inefficient!) wxStringList(const wxStringList & other)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 Add(const wxChar * s)552 wxNode *Add(const wxChar *s) 553 { return (wxNode *)wxStringListBase::Append(copystring(s)); } 554 555 // Append to beginning of list Prepend(const wxChar * s)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__ 577