]> git.saurik.com Git - wxWidgets.git/blob - include/wx/list.h
1. new wxList code
[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/debug.h"
38 #include "wx/object.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 char* WXDLLEXPORT copystring(const char *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 (*wxSortCompareFunction)(const void *elem1, const void *elem2);
68
69 //
70 typedef int (*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 char *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 char *s)
97 { m_keyType = wxKEY_STRING; m_key.string = strdup(s); }
98 wxListKey(const wxString& s)
99 { m_keyType = wxKEY_STRING; m_key.string = strdup(s.c_str()); }
100
101 // accessors
102 wxKeyType GetKeyType() const { return m_keyType; }
103 const char *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 // comparaison
109 bool operator==(wxListKeyValue value) const
110 {
111 switch ( m_keyType )
112 {
113 default:
114 wxFAIL_MSG("bad key type.");
115 // let compiler optimize the line above away in release build
116 // by not putting return here...
117
118 case wxKEY_STRING:
119 return strcmp(m_key.string, value.string) == 0;
120
121 case wxKEY_INTEGER:
122 return m_key.integer == value.integer;
123 }
124 }
125
126 // dtor
127 ~wxListKey()
128 {
129 if ( m_keyType == wxKEY_STRING )
130 free(m_key.string);
131 }
132
133 private:
134 wxKeyType m_keyType;
135 wxListKeyValue m_key;
136 };
137
138 // -----------------------------------------------------------------------------
139 // wxNodeBase class is a (base for) node in a double linked list
140 // -----------------------------------------------------------------------------
141
142 class WXDLLEXPORT wxNodeBase
143 {
144 friend class wxListBase;
145 public:
146 // ctor
147 wxNodeBase(wxListBase *list = (wxListBase *)NULL,
148 wxNodeBase *previous = (wxNodeBase *)NULL,
149 wxNodeBase *next = (wxNodeBase *)NULL,
150 void *data = NULL,
151 const wxListKey& key = wxListKey());
152
153 virtual ~wxNodeBase();
154
155 // @@ no check is done that the list is really keyed on strings
156 const char *GetKeyString() const { return m_key.string; }
157
158 #ifdef wxLIST_COMPATIBILITY
159 // compatibility methods
160 wxNode *Next() const { return (wxNode *)GetNext(); }
161 wxNode *Previous() const { return (wxNode *)GetPrevious(); }
162 wxObject *Data() const { return (wxObject *)GetData(); }
163 #endif // wxLIST_COMPATIBILITY
164
165 protected:
166 // all these are going to be "overloaded" in the derived classes
167 wxNodeBase *GetNext() const { return m_next; }
168 wxNodeBase *GetPrevious() const { return m_previous; }
169
170 void *GetData() const { return m_data; }
171 void SetData(void *data) { m_data = data; }
172
173 virtual void DeleteData() { }
174
175 private:
176 // optional key stuff
177 wxListKeyValue m_key;
178
179 void *m_data; // user data
180 wxNodeBase *m_next, // next and previous nodes in the list
181 *m_previous;
182
183 wxListBase *m_list; // list we belong to
184 };
185
186 // -----------------------------------------------------------------------------
187 // a double-linked list class
188 // -----------------------------------------------------------------------------
189 class WXDLLEXPORT wxListBase : public wxObject
190 {
191 friend class wxNodeBase; // should be able to call DetachNode()
192 public:
193 // default ctor & dtor
194 wxListBase(wxKeyType keyType = wxKEY_NONE) { Init(keyType); }
195 virtual ~wxListBase();
196
197 // accessors
198 // count of items in the list
199 size_t GetCount() const { return m_count; }
200
201 // operations
202 // delete all nodes
203 virtual void Clear();
204 // instruct it to destroy user data when deleting nodes
205 void DeleteContents(bool destroy) { m_destroy = destroy; }
206
207 protected:
208 // all methods here are "overloaded" in derived classes to provide compile
209 // time type checking
210
211 // create a node for the list of this type
212 virtual wxNodeBase *CreateNode(wxNodeBase *prev, wxNodeBase *next,
213 void *data,
214 const wxListKey& key = wxListKey()) = 0;
215
216 // ctors
217 // from an array
218 wxListBase(size_t count, void *elements[]);
219 // from a sequence of objects
220 wxListBase(void *object, ... /* terminate with NULL */);
221
222 // copy ctor and assignment operator
223 wxListBase(const wxListBase& list)
224 { DoCopy(list); }
225 wxListBase& operator=(const wxListBase& list)
226 { Clear(); DoCopy(list); return *this; }
227
228 // get list head/tail
229 wxNodeBase *GetFirst() const { return m_nodeFirst; }
230 wxNodeBase *GetLast() const { return m_nodeLast; }
231
232 // by (0-based) index
233 wxNodeBase *Item(size_t index) const;
234
235 // get the list item's data
236 void *operator[](size_t index) const
237 { wxNodeBase *node = Item(index); return node ? node->GetData() : NULL; }
238
239 // operations
240 // append to end of list
241 wxNodeBase *Append(void *object);
242 // insert a new item at the beginning of the list
243 wxNodeBase *Insert(void *object) { return Insert(NULL, object); }
244 // insert before given node or at front of list if prev == NULL
245 wxNodeBase *Insert(wxNodeBase *prev, void *object);
246
247 // keyed append
248 wxNodeBase *Append(long key, void *object);
249 wxNodeBase *Append(const char *key, void *object);
250
251 // removes node from the list but doesn't delete it (returns pointer
252 // to the node or NULL if it wasn't found in the list)
253 wxNodeBase *DetachNode(wxNodeBase *node);
254 // delete element from list, returns FALSE if node not found
255 bool DeleteNode(wxNodeBase *node);
256 // finds object pointer and deletes node (and object if DeleteContents
257 // is on), returns FALSE if object not found
258 bool DeleteObject(void *object);
259
260 // search (all return NULL if item not found)
261 // by data
262 wxNodeBase *Find(void *object) const;
263
264 // by key
265 wxNodeBase *Find(const wxListKey& key) const;
266
267 // this function allows the sorting of arbitrary lists by giving
268 // a function to compare two list elements. The list is sorted in place.
269 void Sort(wxSortCompareFunction compfunc);
270
271 // functions for iterating over the list
272 void *FirstThat(wxListIterateFunction func);
273 void ForEach(wxListIterateFunction func);
274 void *LastThat(wxListIterateFunction func);
275
276 private:
277 // helpers
278 // common part of all ctors
279 void Init(wxKeyType keyType);
280 // common part of copy ctor and assignment operator
281 void DoCopy(const wxListBase& list);
282 // common part of all Append()s
283 wxNodeBase *AppendCommon(wxNodeBase *node);
284 // free node's data and node itself
285 void DoDeleteNode(wxNodeBase *node);
286
287 size_t m_count; // number of elements in the list
288 bool m_destroy; // destroy user data when deleting list items?
289 wxNodeBase *m_nodeFirst, // pointers to the head and tail of the list
290 *m_nodeLast;
291
292 wxKeyType m_keyType; // type of our keys (may be wxKEY_NONE)
293 };
294
295 // -----------------------------------------------------------------------------
296 // macros for definition of "template" list type
297 // -----------------------------------------------------------------------------
298
299 // and now some heavy magic...
300
301 // declare a list type named 'name' and containing elements of type 'T *'
302 // (as a by product of macro expansion you also get wx##name##Node
303 // wxNode-dervied type)
304 //
305 // implementation details:
306 // 1. we define _WX_LIST_ITEM_TYPE_##name typedef to save in it the item type
307 // for the list of given type - this allows us to pass only the list name
308 // to WX_DEFINE_LIST() even if it needs both the name and the type
309 //
310 // 2. We redefine all not type-safe wxList functions withtype-safe versions
311 // which don't take any place (everything is inline), but bring compile
312 // time error checking.
313
314 #define WX_DECLARE_LIST_2(T, name, nodetype) \
315 typedef int (*wxSortFuncFor_##name)(const T *, const T *); \
316 \
317 class WXDLLEXPORT nodetype : public wxNodeBase \
318 { \
319 public: \
320 nodetype(wxListBase *list = (wxListBase *)NULL, \
321 nodetype *previous = (nodetype *)NULL, \
322 nodetype *next = (nodetype *)NULL, \
323 T *data = NULL, \
324 const wxListKey& key = wxListKey()) \
325 : wxNodeBase(list, previous, next, data, key) { } \
326 \
327 nodetype *GetNext() const \
328 { return (nodetype *)wxNodeBase::GetNext(); } \
329 nodetype *GetPrevious() const \
330 { return (nodetype *)wxNodeBase::GetPrevious(); } \
331 \
332 T *GetData() const \
333 { return (T *)wxNodeBase::GetData(); } \
334 void SetData(T *data) \
335 { wxNodeBase::SetData(data); } \
336 \
337 virtual void DeleteData(); \
338 }; \
339 \
340 class name : public wxListBase \
341 { \
342 public: \
343 name(wxKeyType keyType = wxKEY_NONE) : wxListBase(keyType) \
344 { } \
345 name(size_t count, T *elements[]) \
346 : wxListBase(count, (void **)elements) { } \
347 \
348 nodetype *GetFirst() const \
349 { return (nodetype *)wxListBase::GetFirst(); } \
350 nodetype *GetLast() const \
351 { return (nodetype *)wxListBase::GetLast(); } \
352 \
353 nodetype *Item(size_t index) const \
354 { return (nodetype *)wxListBase::Item(index); } \
355 \
356 T *operator[](size_t index) const \
357 { \
358 nodetype *node = Item(index); \
359 return node ? node->GetData() : NULL; \
360 } \
361 \
362 nodetype *Append(T *object) \
363 { return (nodetype *)wxListBase::Append(object); } \
364 nodetype *Insert(T *object) \
365 { return (nodetype *)Insert(NULL, object); } \
366 nodetype *Insert(nodetype *prev, T *object) \
367 { return (nodetype *)wxListBase::Insert(prev, object); } \
368 \
369 nodetype *Append(long key, void *object) \
370 { return (nodetype *)wxListBase::Append(key, object); } \
371 nodetype *Append(const char *key, void *object) \
372 { return (nodetype *)wxListBase::Append(key, object); } \
373 \
374 nodetype *DetachNode(nodetype *node) \
375 { return (nodetype *)wxListBase::DetachNode(node); } \
376 bool DeleteNode(nodetype *node) \
377 { return wxListBase::DeleteNode(node); } \
378 bool DeleteObject(T *object) \
379 { return wxListBase::DeleteObject(object); } \
380 \
381 nodetype *Find(T *object) const \
382 { return (nodetype *)wxListBase::Find(object); } \
383 \
384 virtual nodetype *Find(const wxListKey& key) const \
385 { return (nodetype *)wxListBase::Find(key); } \
386 \
387 void Sort(wxSortFuncFor_##name func) \
388 { wxListBase::Sort((wxSortCompareFunction)func); } \
389 \
390 protected: \
391 wxNodeBase *CreateNode(wxNodeBase *prev, wxNodeBase *next, \
392 void *data, \
393 const wxListKey& key = wxListKey()) \
394 { \
395 return new nodetype(this, \
396 (nodetype *)prev, (nodetype *)next, \
397 (T *)data, key); \
398 } \
399 }
400
401 #define WX_DECLARE_LIST(elementtype, listname) \
402 typedef elementtype _WX_LIST_ITEM_TYPE_##listname; \
403 WX_DECLARE_LIST_2(elementtype, listname, wx##listname##Node)
404
405 // this macro must be inserted in your program after
406 // #include <wx/listimpl.cpp>
407 #define WX_DEFINE_LIST(name) "don't forget to include listimpl.cpp!"
408
409
410 // =============================================================================
411 // now we can define classes 100% compatible with the old ones
412 // =============================================================================
413
414 #ifdef wxLIST_COMPATIBILITY
415
416 // -----------------------------------------------------------------------------
417 // wxList compatibility class: in fact, it's a list of wxObjects
418 // -----------------------------------------------------------------------------
419
420 WX_DECLARE_LIST_2(wxObject, wxObjectList, wxObjectListNode);
421
422 class WXDLLEXPORT wxList : public wxObjectList
423 {
424 public:
425 wxList(int key_type = wxKEY_NONE) : wxObjectList((wxKeyType)key_type) { }
426
427 // compatibility methods
428 int Number() const { return GetCount(); }
429 wxNode *First() const { return (wxNode *)GetFirst(); }
430 wxNode *Last() const { return (wxNode *)GetLast(); }
431 wxNode *Nth(size_t index) const { return (wxNode *)Item(index); }
432 wxNode *Member(wxObject *object) const { return (wxNode *)Find(object); }
433 };
434
435 // -----------------------------------------------------------------------------
436 // wxStringList class for compatibility with the old code
437 // -----------------------------------------------------------------------------
438
439 WX_DECLARE_LIST_2(char, wxStringListBase, wxStringListNode);
440
441 class WXDLLEXPORT wxStringList : public wxStringListBase
442 {
443 public:
444 // ctors and such
445 // default
446 wxStringList() { DeleteContents(TRUE); }
447 wxStringList(const char *first ...);
448
449 // operations
450 // makes a copy of the string
451 wxNode *Add(const char *s)
452 { return (wxNode *)wxStringListBase::Append(copystring(s)); }
453
454 void Delete(const char *s)
455 { wxStringListBase::DeleteObject((char *)s); }
456
457 char **ListToArray(bool new_copies = FALSE) const;
458 bool Member(const char *s) const;
459
460 // alphabetic sort
461 void Sort();
462
463 // compatibility methods
464 int Number() const { return GetCount(); }
465 wxNode *First() const { return (wxNode *)GetFirst(); }
466 wxNode *Last() const { return (wxNode *)GetLast(); }
467 wxNode *Nth(size_t index) const { return (wxNode *)Item(index); }
468 };
469
470 #endif // wxLIST_COMPATIBILITY
471
472 #endif
473 // _WX_LISTH__