interface/list.h

   1 /////////////////////////////////////////////////////////////////////////////
   2 // Name:        list.h
   3 // Purpose:     interface of wxList<T>
   4 // Author:      wxWidgets team
   5 // RCS-ID:      $Id$
   6 // Licence:     wxWindows license
   7 /////////////////////////////////////////////////////////////////////////////
   8
   9 /**
  10     @wxheader{list.h}
  11
  12     The wxList<T> class provides linked list functionality. It has been rewritten
  13     to be type safe and to provide the full API of the STL std::list container and
  14     should be used like it. The exception is that wxList<T> actually stores
  15     pointers and therefore its iterators return pointers and not references
  16     to the actual objets in the list (see example below) and @e value_type
  17     is defined as @e T*. wxList<T> destroys an object after removing it only
  18     if wxList::DeleteContents has been called.
  19
  20     wxList<T> is not a real template and it requires that you declare and define
  21     each wxListT class in your program. This is done with @e WX_DECLARE_LIST
  22     and @e WX_DEFINE_LIST macros (see example). We hope that we'll be able
  23     to provide a proper template class providing both the STL std::list
  24     and the old wxList API in the future.
  25
  26     Please refer to the STL std::list documentation for further
  27     information on how to use the class. Below we documented both
  28     the supported STL and the legacy API that originated from the
  29     old wxList class and which can still be used alternatively for
  30     the the same class.
  31
  32     Note that if you compile wxWidgets in STL mode (wxUSE_STL defined as 1)
  33     then wxList<T> will actually derive from std::list and just add a legacy
  34     compatibility layer for the old wxList class.
  35
  36     @code
  37     // this part might be in a header or source (.cpp) file
  38     class MyListElement
  39     {
  40         ... // whatever
  41     };
  42
  43     // this macro declares and partly implements MyList class
  44     WX_DECLARE_LIST(MyListElement, MyList);
  45
  46     ...
  47
  48     // the only requirement for the rest is to be AFTER the full declaration of
  49     // MyListElement (for WX_DECLARE_LIST forward declaration is enough), but
  50     // usually it will be found in the source file and not in the header
  51
  52     #include <wx/listimpl.cpp>
  53     WX_DEFINE_LIST(MyList);
  54
  55
  56     MyList list;
  57     MyListElement element;
  58     list.Append(&element);     // ok
  59     list.Append(17);           // error: incorrect type
  60
  61     // let's iterate over the list in STL syntax
  62     MyList::iterator iter;
  63     for (iter = list.begin(); iter != list.end(); ++iter)
  64     {
  65         MyListElement *current = *iter;
  66
  67         ...process the current element...
  68     }
  69
  70     // the same with the legacy API from the old wxList class
  71     MyList::compatibility_iterator node = list.GetFirst();
  72     while (node)
  73     {
  74         MyListElement *current = node->GetData();
  75
  76         ...process the current element...
  77
  78         node = node->GetNext();
  79     }
  80     @endcode
  81
  82
  83     @library{wxbase}
  84     @category{FIXME}
  85
  86     @see wxArray<T>, wxVector<T>
  87 */
  88 class wxList<T>
  89 {
  90 public:
  91     /**
  92         Default constructor.
  93     */
  94     wxList<T>();
  95
  96     /**
  97         Constructor which initialized the list with an array of @count elements.
  98     */
  99     wxList<T>(size_t count, T* elements[]);
 100
 101     /**
 102         Destroys the list, but does not delete the objects stored in the list
 103         unless you called DeleteContents(@true ).
 104     */
 105     ~wxList<T>();
 106
 107     /**
 108         Appends the pointer to @a object to the list.
 109     */
 110     wxList<T>::compatibility_iterator Append(T* object);
 111
 112     /**
 113         Clears the list.
 114         Deletes the actual objects if DeleteContents( @true ) was called previously.
 115     */
 116     void Clear();
 117
 118     /**
 119         If @a destroy is @true, instructs the list to call @e delete
 120         on objects stored in the list whenever they are removed.
 121         The default is @false.
 122     */
 123     void DeleteContents(bool destroy);
 124
 125     /**
 126         Deletes the given element refered to by @a iter from the list
 127         if @a iter is a valid iterator. Returns @true if successful.
 128
 129         Deletes the actual object if DeleteContents( @true ) was called previously.
 130     */
 131     bool DeleteNode(const compatibility_iterator& iter);
 132
 133     /**
 134         Finds the given @a object and removes it from the list, returning
 135         @true if successful.
 136
 137         Deletes @a object if DeleteContents( @true ) was called previously.
 138     */
 139     bool DeleteObject(T* object);
 140
 141     /**
 142         Removes element refered to be @a iter.
 143
 144         Deletes the actualy object if DeleteContents( @true ) was called previously.
 145     */
 146     void Erase(const compatibility_iterator& iter);
 147
 148     /**
 149         Returns the iterator refering to @a object or @NULL if none found.
 150     */
 151     wxList<T>::compatibility_iterator Find(T* object) const;
 152
 153     /**
 154         Returns the number of elements in the list.
 155     */
 156     size_t GetCount() const;
 157
 158     /**
 159         Returns the first iterator in the list (@NULL if the list is empty).
 160     */
 161     wxList<T>::compatibility_iterator GetFirst() const;
 162
 163     /**
 164         Returns the last iterator in the list (@NULL if the list is empty).
 165     */
 166     wxList<T>::compatibility_iterator GetLast() const;
 167
 168     /**
 169         Returns the index of @a obj within the list or @c wxNOT_FOUND if
 170         @a obj is not found in the list.
 171     */
 172     int IndexOf(T* obj) const;
 173
 174     /**
 175         Inserts @a object at the beginning of the list.
 176     */
 177     wxList<T>::compatibility_iterator Insert(T* object);
 178
 179     /**
 180         Inserts @a object at @a position.
 181     */
 182     wxList<T>::compatibility_iterator Insert(size_t position,
 183                                            T* object);
 184
 185     /**
 186         Inserts @a object before the object refered to be @a iter.
 187     */
 188     wxList<T>::compatibility_iterator Insert(compatibility_iterator iter,
 189                                            T* object);
 190
 191     /**
 192         Returns @true if the list is empty, @false otherwise.
 193     */
 194     bool IsEmpty() const;
 195
 196     /**
 197         Returns the iterator refering to the object at the given
 198         @a index in the list.
 199     */
 200     wxList<T>::compatibility_iterator Item(size_t index) const;
 201
 202     /**
 203         @note This function is deprecated, use Find() instead.
 204     */
 205     wxList<T>::compatibility_iterator Member(T* object) const;
 206
 207     /**
 208         @note This function is deprecated, use Item() instead.
 209     */
 210     wxList<T>::compatibility_iterator Nth(int n) const;
 211
 212     /**
 213         @note This function is deprecated, use wxList::GetCount instead.
 214         Returns the number of elements in the list.
 215     */
 216     int Number() const;
 217
 218     /**
 219         Allows the sorting of arbitrary lists by giving a function to compare
 220         two list elements. We use the system @b qsort function for the actual
 221         sorting process.
 222     */
 223     void Sort(wxSortCompareFunction compfunc);
 224
 225     /**
 226        Clears the list and item from @a first to @a last from another list to it.
 227     */
 228     void assign(const_iterator first, const const_iterator& last);
 229
 230     /**
 231        Clears the list and adds @a n items with value @a v to it.
 232     */
 233     void assign(size_type n, const_reference v = value_type())          \
 234
 235     /**
 236         Returns the last item of the list.
 237     */
 238     reference back() const;
 239
 240     /**
 241         Returns the last item of the list as a const reference.
 242     */
 243     const_reference back() const;
 244
 245     /**
 246         Returns an iterator pointing to the beginning of the list.
 247     */
 248     iterator begin() const;
 249
 250     /**
 251         Returns a const iterator pointing to the beginning of the list.
 252     */
 253     const_iterator begin() const;
 254
 255     /**
 256         Removes all items from the list.
 257     */
 258     void clear();
 259
 260     /**
 261         Returns @e @true if the list is empty.
 262     */
 263     bool empty() const;
 264
 265     /**
 266         Returns a const iterator pointing at the end of the list.
 267     */
 268     const_iterator end() const;
 269
 270     /**
 271         Returns a iterator pointing at the end of the list.
 272     */
 273     iterator end() const;
 274
 275     /**
 276         Erases the given item
 277     */
 278     iterator erase(const iterator& it);
 279
 280     /**
 281         Erases the items from @e first to @e last.
 282     */
 283     iterator erase(const iterator& first,
 284                    const iterator& last);
 285
 286     /**
 287         Returns the first item in the list.
 288     */
 289     reference front() const;
 290
 291     /**
 292         Returns the first item in the list as a const reference.
 293     */
 294     const_reference front() const;
 295
 296     /**
 297         Inserts an item at the head of the list
 298     */
 299     iterator insert(const iterator& it);
 300
 301     /**
 302         Inserts an item at the given position
 303     */
 304     void insert(const iterator& it, size_type n);
 305
 306     /**
 307         Inserts several items at the given position.
 308     */
 309     void insert(const iterator& it, const_iterator first,
 310                 const const_iterator& last);
 311
 312     /**
 313         Returns the largest possible size of the list.
 314     */
 315     size_type max_size() const;
 316
 317     /**
 318         Removes the last item from the list.
 319     */
 320     void pop_back();
 321
 322     /**
 323         Removes the first item from the list.
 324     */
 325     void pop_front();
 326
 327     /**
 328         Adds an item to end of the list.
 329     */
 330     void push_back();
 331
 332     /**
 333         Adds an item to the front of the list.
 334     */
 335     void push_front();
 336
 337     /**
 338         Returns a reverse iterator pointing to the beginning of the
 339         reversed list.
 340     */
 341     reverse_iterator rbegin() const;
 342
 343     /**
 344         Returns a const reverse iterator pointing to the beginning of the
 345         reversed list.
 346     */
 347     const_reverse_iterator rbegin() const;
 348
 349     /**
 350         Removes an item from the list.
 351     */
 352     void remove(const_reference v);
 353
 354     /**
 355         Returns a reverse iterator pointing to the end of the
 356         reversed list.
 357     */
 358     reverse_iterator rend() const;
 359
 360     /**
 361         Returns a const reverse iterator pointing to the end of the
 362         reversed list.
 363     */
 364     const_reverse_iterator rend() const;
 365
 366     /**
 367         Resizes the list. If the the list is enlarges items with
 368         the value @e v are appended to the list.
 369     */
 370     void resize(size_type n);
 371
 372     /**
 373         Reverses the list.
 374     */
 375     void reverse();
 376
 377     /**
 378         Returns the size of the list.
 379     */
 380     size_type size() const;
 381 };
 382
 383
 384
 385 /**
 386     @class wxNode
 387     @wxheader{list.h}
 388
 389     wxNodeBase is the node structure used in linked lists (see
 390     wxList) and derived classes. You should never use wxNodeBase
 391     class directly, however, because it works with untyped (@c void *) data and
 392     this is unsafe. Use wxNodeBase-derived classes which are automatically defined
 393     by WX_DECLARE_LIST and WX_DEFINE_LIST macros instead as described in
 394     wxList documentation (see example there). Also note that
 395     although there is a class called wxNode, it is defined for backwards
 396     compatibility only and usage of this class is strongly deprecated.
 397
 398     In the documentation below, the type @c T should be thought of as a
 399     "template" parameter: this is the type of data stored in the linked list or,
 400     in other words, the first argument of WX_DECLARE_LIST macro. Also, wxNode is
 401     written as wxNodeT even though it isn't really a template class -- but it
 402     helps to think of it as if it were.
 403
 404     @library{wxbase}
 405     @category{FIXME}
 406
 407     @see wxList<T>, wxHashTable
 408 */
 409 class wxNode<T>
 410 {
 411 public:
 412     /**
 413         Retrieves the client data pointer associated with the node.
 414     */
 415     T* GetData() const;
 416
 417     /**
 418         Retrieves the next node or @NULL if this node is the last one.
 419     */
 420     wxNode<T>* GetNext() const;
 421
 422     /**
 423         Retrieves the previous node or @NULL if this node is the first one in the list.
 424     */
 425     wxNode<T>* GetPrevious();
 426
 427     /**
 428         Returns the zero-based index of this node within the list. The return value
 429         will be @c wxNOT_FOUND if the node has not been added to a list yet.
 430     */
 431     int IndexOf();
 432
 433     /**
 434         Sets the data associated with the node (usually the pointer will have been
 435         set when the node was created).
 436     */
 437     void SetData(T* data);
 438 };
 439