projects / wxWidgets.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
Applied wxList::Prepend() patch.
[wxWidgets.git] / 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 *Prepend(void *object)
277 { return (wxNodeBase *)wxListBase::Insert(object); }
278 // append to beginning of list
279 wxNodeBase *Append(void *object);
280 // insert a new item at the beginning of the list
281 wxNodeBase *Insert(void *object) { return Insert( (wxNodeBase*)NULL, object); }
282 // insert a new item at the given position
283 wxNodeBase *Insert(size_t pos, void *object)
284 { return pos == GetCount() ? Append(object)
285 : Insert(Item(pos), object); }
286 // insert before given node or at front of list if prev == NULL
287 wxNodeBase *Insert(wxNodeBase *prev, void *object);
288
289 // keyed append
290 wxNodeBase *Append(long key, void *object);
291 wxNodeBase *Append(const wxChar *key, void *object);
292
293 // removes node from the list but doesn't delete it (returns pointer
294 // to the node or NULL if it wasn't found in the list)
295 wxNodeBase *DetachNode(wxNodeBase *node);
296 // delete element from list, returns FALSE if node not found
297 bool DeleteNode(wxNodeBase *node);
298 // finds object pointer and deletes node (and object if DeleteContents
299 // is on), returns FALSE if object not found
300 bool DeleteObject(void *object);
301
302 // search (all return NULL if item not found)
303 // by data
304 wxNodeBase *Find(void *object) const;
305
306 // by key
307 wxNodeBase *Find(const wxListKey& key) const;
308
309 // get 0-based index of object or wxNOT_FOUND
310 int IndexOf( void *object ) const;
311
312 // this function allows the sorting of arbitrary lists by giving
313 // a function to compare two list elements. The list is sorted in place.
314 void Sort(const wxSortCompareFunction compfunc);
315
316 // functions for iterating over the list
317 void *FirstThat(wxListIterateFunction func);
318 void ForEach(wxListIterateFunction func);
319 void *LastThat(wxListIterateFunction func);
320
321 private:
322 // helpers
323 // common part of copy ctor and assignment operator
324 void DoCopy(const wxListBase& list);
325 // common part of all Append()s
326 wxNodeBase *AppendCommon(wxNodeBase *node);
327 // free node's data and node itself
328 void DoDeleteNode(wxNodeBase *node);
329
330 size_t m_count; // number of elements in the list
331 bool m_destroy; // destroy user data when deleting list items?
332 wxNodeBase *m_nodeFirst, // pointers to the head and tail of the list
333 *m_nodeLast;
334
335 wxKeyType m_keyType; // type of our keys (may be wxKEY_NONE)
336 };
337
338 // -----------------------------------------------------------------------------
339 // macros for definition of "template" list type
340 // -----------------------------------------------------------------------------
341
342 // and now some heavy magic...
343
344 // declare a list type named 'name' and containing elements of type 'T *'
345 // (as a by product of macro expansion you also get wx##name##Node
346 // wxNode-derived type)
347 //
348 // implementation details:
349 // 1. We define _WX_LIST_ITEM_TYPE_##name typedef to save in it the item type
350 // for the list of given type - this allows us to pass only the list name
351 // to WX_DEFINE_LIST() even if it needs both the name and the type
352 //
353 // 2. We redefine all non-type-safe wxList functions with type-safe versions
354 // which don't take any space (everything is inline), but bring compile
355 // time error checking.
356 //
357 // 3. The macro which is usually used (WX_DECLARE_LIST) is defined in terms of
358 // a more generic WX_DECLARE_LIST_2 macro which, in turn, uses the most
359 // generic WX_DECLARE_LIST_3 one. The last macro adds a sometimes
360 // interesting capability to store polymorphic objects in the list and is
361 // particularly useful with, for example, "wxWindow *" list where the
362 // wxWindowBase pointers are put into the list, but wxWindow pointers are
363 // retrieved from it.
364
365 #define WX_DECLARE_LIST_3(T, Tbase, name, nodetype, classexp) \
366 typedef int (*wxSortFuncFor_##name)(const T **, const T **); \
367 \
368 classexp nodetype : public wxNodeBase \
369 { \
370 public: \
371 nodetype(wxListBase *list = (wxListBase *)NULL, \
372 nodetype *previous = (nodetype *)NULL, \
373 nodetype *next = (nodetype *)NULL, \
374 T *data = (T *)NULL, \
375 const wxListKey& key = wxDefaultListKey) \
376 : wxNodeBase(list, previous, next, data, key) { } \
377 \
378 nodetype *GetNext() const \
379 { return (nodetype *)wxNodeBase::GetNext(); } \
380 nodetype *GetPrevious() const \
381 { return (nodetype *)wxNodeBase::GetPrevious(); } \
382 \
383 T *GetData() const \
384 { return (T *)wxNodeBase::GetData(); } \
385 void SetData(T *data) \
386 { wxNodeBase::SetData(data); } \
387 \
388 virtual void DeleteData(); \
389 }; \
390 \
391 classexp name : public wxListBase \
392 { \
393 public: \
394 typedef nodetype Node; \
395 \
396 name(wxKeyType keyType = wxKEY_NONE) : wxListBase(keyType) \
397 { } \
398 name(size_t count, T *elements[]) \
399 : wxListBase(count, (void **)elements) { } \
400 \
401 name& operator=(const name& list) \
402 { return (name&)wxListBase::operator=(list); } \
403 \
404 nodetype *GetFirst() const \
405 { return (nodetype *)wxListBase::GetFirst(); } \
406 nodetype *GetLast() const \
407 { return (nodetype *)wxListBase::GetLast(); } \
408 \
409 nodetype *Item(size_t index) const \
410 { return (nodetype *)wxListBase::Item(index); } \
411 \
412 T *operator[](size_t index) const \
413 { \
414 nodetype *node = Item(index); \
415 return node ? (T*)(node->GetData()) : (T*)NULL; \
416 } \
417 \
418 nodetype *Append(Tbase *object) \
419 { return (nodetype *)wxListBase::Append(object); } \
420 nodetype *Insert(Tbase *object) \
421 { return (nodetype *)Insert((nodetype*)NULL, object); } \
422 nodetype *Insert(size_t pos, Tbase *object) \
423 { return (nodetype *)wxListBase::Insert(pos, object); } \
424 nodetype *Insert(nodetype *prev, Tbase *object) \
425 { return (nodetype *)wxListBase::Insert(prev, object); } \
426 \
427 nodetype *Append(long key, void *object) \
428 { return (nodetype *)wxListBase::Append(key, object); } \
429 nodetype *Append(const wxChar *key, void *object) \
430 { return (nodetype *)wxListBase::Append(key, object); } \
431 \
432 nodetype *DetachNode(nodetype *node) \
433 { return (nodetype *)wxListBase::DetachNode(node); } \
434 bool DeleteNode(nodetype *node) \
435 { return wxListBase::DeleteNode(node); } \
436 bool DeleteObject(Tbase *object) \
437 { return wxListBase::DeleteObject(object); } \
438 \
439 nodetype *Find(Tbase *object) const \
440 { return (nodetype *)wxListBase::Find(object); } \
441 \
442 virtual nodetype *Find(const wxListKey& key) const \
443 { return (nodetype *)wxListBase::Find(key); } \
444 \
445 int IndexOf(Tbase *object) const \
446 { return wxListBase::IndexOf(object); } \
447 \
448 void Sort(wxSortFuncFor_##name func) \
449 { wxListBase::Sort((wxSortCompareFunction)func); } \
450 \
451 protected: \
452 virtual wxNodeBase *CreateNode(wxNodeBase *prev, wxNodeBase *next, \
453 void *data, \
454 const wxListKey& key = wxDefaultListKey) \
455 { \
456 return new nodetype(this, \
457 (nodetype *)prev, (nodetype *)next, \
458 (T *)data, key); \
459 } \
460 }
461
462 #define WX_DECLARE_LIST_2(elementtype, listname, nodename, classexp) \
463 WX_DECLARE_LIST_3(elementtype, elementtype, listname, nodename, classexp)
464
465 #define WX_DECLARE_LIST(elementtype, listname) \
466 typedef elementtype _WX_LIST_ITEM_TYPE_##listname; \
467 WX_DECLARE_LIST_2(elementtype, listname, wx##listname##Node, class)
468
469 #define WX_DECLARE_EXPORTED_LIST(elementtype, listname) \
470 typedef elementtype _WX_LIST_ITEM_TYPE_##listname; \
471 WX_DECLARE_LIST_2(elementtype, listname, wx##listname##Node, class WXDLLEXPORT)
472
473 #define WX_DECLARE_USER_EXPORTED_LIST(elementtype, listname, usergoo) \
474 typedef elementtype _WX_LIST_ITEM_TYPE_##listname; \
475 WX_DECLARE_LIST_2(elementtype, listname, wx##listname##Node, class usergoo)
476
477 // this macro must be inserted in your program after
478 // #include <wx/listimpl.cpp>
479 #define WX_DEFINE_LIST(name) "don't forget to include listimpl.cpp!"
480
481 #define WX_DEFINE_EXPORTED_LIST(name) WX_DEFINE_LIST(name)
482 #define WX_DEFINE_USER_EXPORTED_LIST(name) WX_DEFINE_LIST(name)
483
484
485 // =============================================================================
486 // now we can define classes 100% compatible with the old ones
487 // =============================================================================
488
489 // ----------------------------------------------------------------------------
490 // commonly used list classes
491 // ----------------------------------------------------------------------------
492
493 #ifdef wxLIST_COMPATIBILITY
494
495 // -----------------------------------------------------------------------------
496 // wxList compatibility class: in fact, it's a list of wxObjects
497 // -----------------------------------------------------------------------------
498
499 WX_DECLARE_LIST_2(wxObject, wxObjectList, wxObjectListNode, class WXDLLEXPORT);
500
501 class WXDLLEXPORT wxList : public wxObjectList
502 {
503 public:
504 wxList(int key_type = wxKEY_NONE) : wxObjectList((wxKeyType)key_type) { }
505 // this destructor is required for Darwin
506 ~wxList() { }
507
508 wxList& operator=(const wxList& list)
509 { return (wxList&)wxListBase::operator=(list); }
510
511 // compatibility methods
512 void Sort(wxSortCompareFunction compfunc) { wxListBase::Sort(compfunc); }
513
514 wxNode *Member(wxObject *object) const { return (wxNode *)Find(object); }
515
516 private:
517 DECLARE_DYNAMIC_CLASS(wxList)
518 };
519
520 // -----------------------------------------------------------------------------
521 // wxStringList class for compatibility with the old code
522 // -----------------------------------------------------------------------------
523
524 WX_DECLARE_LIST_2(wxChar, wxStringListBase, wxStringListNode, class WXDLLEXPORT);
525
526 class WXDLLEXPORT wxStringList : public wxStringListBase
527 {
528 public:
529 // ctors and such
530 // default
531 wxStringList() { DeleteContents(TRUE); }
532 wxStringList(const wxChar *first ...);
533
534 // copying the string list: the strings are copied, too (extremely
535 // inefficient!)
536 wxStringList(const wxStringList& other) : wxStringListBase() { DeleteContents(TRUE); DoCopy(other); }
537 wxStringList& operator=(const wxStringList& other)
538 { Clear(); DoCopy(other); return *this; }
539
540 // operations
541 // makes a copy of the string
542 wxNode *Add(const wxChar *s)
543 { return (wxNode *)wxStringListBase::Append(copystring(s)); }
544
545 // Append to beginning of list
546 wxNode *Prepend(const wxChar *s)
547 { return (wxNode *)wxStringListBase::Insert(copystring(s)); }
548
549 bool Delete(const wxChar *s);
550
551 wxChar **ListToArray(bool new_copies = FALSE) const;
552 bool Member(const wxChar *s) const;
553
554 // alphabetic sort
555 void Sort();
556
557 private:
558 void DoCopy(const wxStringList&); // common part of copy ctor and operator=
559
560 DECLARE_DYNAMIC_CLASS(wxStringList)
561 };
562
563 #endif // wxLIST_COMPATIBILITY
564
565 #endif
566 // _WX_LISTH__
wxWidgets (Impactor)