user/wxLayout/kbList.h

   1 /*-*- c++ -*-********************************************************
   2  * kbList.h : a double linked list                                  *
   3  *                                                                  *
   4  * (C) 1998 by Karsten Ballüder (Ballueder@usa.net)                 *
   5  *                                                                  *
   6  * $Id$
   7  *
   8  *******************************************************************/
   9
  10 #ifndef   KBLIST_H
  11 #   define   KBLIST_H
  12
  13 #ifdef __GNUG__
  14 #   pragma interface "kbList.h"
  15 #endif
  16
  17 #ifndef   NULL
  18 #   define   NULL   0
  19 #endif
  20
  21 /**@name Double linked list implementation. */
  22 //@{
  23
  24 /** kbListNode is a class used by kbList. It represents a single
  25     element in the list. It is not intended for general use outside
  26     kbList functions.
  27 */
  28 struct kbListNode
  29 {
  30    /// pointer to next node or NULL
  31    struct kbListNode *next;
  32    /// pointer to previous node or NULL
  33    struct kbListNode *prev;
  34    /// pointer to the actual data
  35    void *element;
  36    /** Constructor - it automatically links the node into the list, if
  37        the iprev, inext parameters are given.
  38        @param ielement pointer to the data for this node (i.e. the data itself)
  39        @param iprev if not NULL, use this as previous element in list
  40        @param inext if not NULL, use this as next element in list
  41    */
  42    kbListNode( void *ielement,
  43                kbListNode *iprev = NULL,
  44                kbListNode *inext = NULL);
  45    /// Destructor.
  46    ~kbListNode();
  47 };
  48
  49 /** The main list class, handling void pointers as data.
  50   */
  51
  52 class kbList
  53 {
  54 public:
  55    /// An iterator class for kbList, just like for the STL classes.
  56    class iterator
  57    {
  58    protected:
  59       /// the node to which this iterator points
  60       kbListNode *node;
  61       friend class kbList;
  62          public:
  63       /** Constructor.
  64           @param n if not NULL, the node to which to point
  65       */
  66       iterator(kbListNode *n = NULL);
  67       /** Dereference operator.
  68           @return the data pointer of the node belonging to this
  69           iterator
  70       */
  71       void * operator*();
  72
  73       /** This operator allows us to write if(i). It is <em>not</em> a
  74           dereference operator and the result is always useless apart
  75           from its logical value!
  76       */
  77       operator void*() const { return node == NULL ? (void*)0 : (void*)(-1); }
  78
  79       /** Increment operator - prefix, goes to next node in list.
  80           @return itself
  81       */
  82       iterator & operator++();
  83
  84       /** Decrement operator - prefix, goes to previous node in list.
  85           @return itself
  86       */
  87       iterator & operator--();
  88
  89       /** Increment operator - prefix, goes to next node in list.
  90           @return itself
  91       */
  92       iterator & operator++(int); //postfix
  93
  94       /** Decrement operator - prefix, goes to previous node in list.
  95           @return itself
  96       */
  97       iterator & operator--(int); //postfix
  98
  99       /** Comparison operator.
 100           @return true if not equal.
 101       */
 102       bool operator !=(iterator const &) const;
 103
 104       /* Comparison operator.
 105          @return true if equal
 106       */
 107       bool operator ==(iterator const &) const;
 108
 109       /** Returns a pointer to the node associated with this iterator.
 110           This function is not for general use and should be
 111           protected. However, if protected, it cannot be called from
 112           derived classes' iterators. (Is this a bug in gcc/egcs?)
 113           @return the node pointer
 114       */
 115       inline kbListNode * Node(void) const
 116          { return node; }
 117    };
 118
 119    /** Constructor.
 120        @param ownsEntriesFlag if true, the list owns the entries and
 121        will issue a delete on each of them when deleting them. If
 122        false, the entries themselves will not get deleted. Do not use
 123        this with array types!
 124    */
 125    kbList(bool ownsEntriesFlag = true);
 126
 127    /** Destructor.
 128        If entries are owned, they will all get deleted from here.
 129    */
 130    ~kbList();
 131
 132    /** Tell list whether it owns objects. If owned, they can be
 133        deleted by list. See the constructor for more details.
 134        @param ownsflag if true, list will own entries
 135    */
 136    void ownsObjects(bool ownsflag = true)
 137       { ownsEntries = ownsflag; }
 138
 139    /** Query whether list owns entries.
 140        @return true if list owns entries
 141    */
 142    bool ownsObjects(void)
 143       { return ownsEntries; }
 144
 145    /** Add an entry at the end of the list.
 146        @param element pointer to data
 147    */
 148    void push_back(void *element);
 149
 150    /** Add an entry at the head of the list.
 151        @param element pointer to data
 152    */
 153    void push_front(void *element);
 154
 155    /** Get element from end of the list and delete it.
 156        NOTE: In this case the element's data will not get deleted by
 157        the list. It is the responsibility of the caller to free it.
 158        @return the element data
 159    */
 160    void *pop_back(void);
 161
 162    /** Get element from head of the list and delete it.
 163        NOTE: In this case the element's data will not get deleted by
 164        the list. It is the responsibility of the caller to free it.
 165        @return the element data
 166    */
 167    void *pop_front(void);
 168
 169    /** Insert an element into the list.
 170        @param i an iterator pointing to the element, before which the new one should be inserted
 171        @param element the element data
 172    */
 173    void insert(iterator & i, void *element);
 174
 175    /** Remove an element from the list _without_ deleting the object.
 176        @param  i iterator pointing to the element to be deleted
 177        @return the value of the element just removed
 178    */
 179    void *remove(iterator& i) { void *p = *i; doErase(i); return p; }
 180
 181    /** Erase an element, move iterator to following element.
 182        @param i iterator pointing to the element to be deleted
 183    */
 184    void erase(iterator & i) { deleteContent(i); doErase(i); }
 185
 186    /* Get head of list.
 187       @return iterator pointing to head of list
 188    */
 189    iterator begin(void) const;
 190
 191    /* Get end of list.
 192    @return iterator pointing after the end of the list. This is an
 193    invalid iterator which cannot be dereferenced or decremented. It is
 194    only of use in comparisons. NOTE: this is different from STL!
 195    @see tail
 196    */
 197    iterator end(void) const;
 198
 199    /* Get last element in list.
 200       @return iterator pointing to the last element in the list.
 201       @see end
 202    */
 203    iterator tail(void) const;
 204
 205    /* Get the number of elements in the list.
 206       @return number of elements in the list
 207    */
 208    unsigned size(void) const;
 209
 210    /* Query whether list is empty.
 211       @return true if list is empty
 212    */
 213    inline bool empty(void) const
 214       { return first == NULL ; }
 215
 216 protected:
 217    /// if true, list owns entries
 218    bool        ownsEntries;
 219    /// pointer to first element in list
 220    kbListNode *first;
 221    /// pointer to last element in list
 222    kbListNode *last;
 223 protected:
 224    /** Erase an element, move iterator to following element.
 225        @param i iterator pointing to the element to be deleted
 226    */
 227    void doErase(iterator & i);
 228
 229    /** Deletes the actual content if ownsflag is set.
 230        param iterator i
 231    */
 232    inline void deleteContent(iterator i)
 233       { if(ownsEntries) delete *i; }
 234
 235
 236 private:
 237    /// forbid copy construction
 238    kbList(kbList const &foo);
 239    /// forbid assignments
 240    kbList& operator=(const kbList& foo);
 241 };
 242
 243 /// just for backward compatibility, will be removed soon
 244 typedef kbList::iterator kbListIterator;
 245 /// cast an iterator to a pointer, compatibility only to be removed
 246 #define   kbListICast(type, iterator)   ((type *)*iterator)
 247 /// cast an iterator to a const pointer, compatibility only to be removed
 248 #define   kbListIcCast(type, iterator)   ((type const *)*iterator)
 249
 250 /** Macro to define a kbList with a given name, having elements of
 251     pointer to the given type. I.e. KBLIST_DEFINE(Int,int) would
 252     create a kbListInt type holding int pointers.
 253 */
 254 #define   KBLIST_DEFINE(name,type)   \
 255 class name : public kbList \
 256 { \
 257 public: \
 258    class iterator : public kbList::iterator \
 259    { \
 260    protected: \
 261       inline iterator(kbList::iterator const & i) \
 262          { node = i.Node(); } \
 263       friend class name; \
 264    public: \
 265       inline iterator(kbListNode *n = NULL) \
 266          : kbList::iterator(n) {} \
 267       inline type * operator*() \
 268          /* the cast is needed for MS VC++ 5.0 */ \
 269          { return (type *)((kbList::iterator *)this)->operator*() ; } \
 270    }; \
 271    inline name(bool ownsEntriesFlag = TRUE) \
 272       : kbList(ownsEntriesFlag) {} \
 273    \
 274    inline type *pop_back(void) \
 275       { return (type *) kbList::pop_back(); } \
 276    \
 277    inline type *pop_front(void) \
 278       { return (type *) kbList::pop_front(); } \
 279    \
 280    type *remove(iterator& i) \
 281       { return (type *)kbList::remove(i); } \
 282    inline void erase(iterator & i) \
 283       { deleteContent(i); doErase(i); } \
 284    \
 285    inline iterator begin(void) const \
 286       { return kbList::begin(); } \
 287    \
 288    inline iterator end(void) const \
 289       { return kbList::end(); } \
 290    \
 291    inline iterator tail(void) const \
 292       { return kbList::tail(); } \
 293    ~name() \
 294    { \
 295       kbListNode *next; \
 296       while ( first != NULL ) \
 297       { \
 298          next = first->next; \
 299          if(ownsEntries) \
 300             delete (type *)first->element; \
 301          delete first; \
 302          first = next; \
 303       } \
 304    } \
 305 protected: \
 306    inline void deleteContent(iterator i) \
 307       { if(ownsEntries) delete *i; } \
 308 }
 309
 310 #ifdef   MCONFIG_H
 311 /// define the most commonly used list type once:
 312 KBLIST_DEFINE(kbStringList, String);
 313 #endif
 314 //@}
 315 #endif // KBLIST_H