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       /** Increment operator - prefix, goes to next node in list.
  74           @return itself
  75       */
  76       iterator & operator++();
  77
  78       /** Decrement operator - prefix, goes to previous node in list.
  79           @return itself
  80       */
  81       iterator & operator--();
  82
  83       /** Increment operator - prefix, goes to next node in list.
  84           @return itself
  85       */
  86       iterator & operator++(int); //postfix
  87
  88       /** Decrement operator - prefix, goes to previous node in list.
  89           @return itself
  90       */
  91       iterator & operator--(int); //postfix
  92
  93       /** Comparison operator.
  94           @return true if not equal.
  95       */
  96       bool operator !=(iterator const &) const;
  97
  98       /* Comparison operator.
  99          @return true if equal
 100       */
 101       bool operator ==(iterator const &) const;
 102
 103       /** Returns a pointer to the node associated with this iterator.
 104           This function is not for general use and should be
 105           protected. However, if protected, it cannot be called from
 106           derived classes' iterators. (Is this a bug in gcc/egcs?)
 107           @return the node pointer
 108       */
 109       inline kbListNode * Node(void) const
 110          { return node; }
 111    };
 112
 113    /** Constructor.
 114        @param ownsEntriesFlag if true, the list owns the entries and
 115        will issue a delete on each of them when deleting them. If
 116        false, the entries themselves will not get deleted. Do not use
 117        this with array types!
 118    */
 119    kbList(bool ownsEntriesFlag = true);
 120
 121    /** Destructor.
 122        If entries are owned, they will all get deleted from here.
 123    */
 124    ~kbList();
 125
 126    /** Tell list whether it owns objects. If owned, they can be
 127        deleted by list. See the constructor for more details.
 128        @param ownsflag if true, list will own entries
 129    */
 130    void ownsObjects(bool ownsflag = true)
 131       { ownsEntries = ownsflag; }
 132
 133    /** Query whether list owns entries.
 134        @return true if list owns entries
 135    */
 136    bool ownsObjects(void)
 137       { return ownsEntries; }
 138
 139    /** Add an entry at the end of the list.
 140        @param element pointer to data
 141    */
 142    void push_back(void *element);
 143
 144    /** Add an entry at the head of the list.
 145        @param element pointer to data
 146    */
 147    void push_front(void *element);
 148
 149    /** Get element from end of the list and delete it.
 150        NOTE: In this case the element's data will not get deleted by
 151        the list. It is the responsibility of the caller to free it.
 152        @return the element data
 153    */
 154    void *pop_back(void);
 155
 156    /** Get element from head of the list and delete it.
 157        NOTE: In this case the element's data will not get deleted by
 158        the list. It is the responsibility of the caller to free it.
 159        @return the element data
 160    */
 161    void *pop_front(void);
 162
 163    /** Insert an element into the list.
 164        @param i an iterator pointing to the element, before which the new one should be inserted
 165        @param element the element data
 166    */
 167    void insert(iterator & i, void *element);
 168
 169    /** Erase an element, move iterator to following element.
 170        @param i iterator pointing to the element to be deleted
 171    */
 172    void erase(iterator & i);
 173
 174    /* Get head of list.
 175       @return iterator pointing to head of list
 176    */
 177    iterator begin(void) const;
 178
 179    /* Get end of list.
 180    @return iterator pointing after the end of the list. This is an
 181    invalid iterator which cannot be dereferenced or decremented. It is
 182    only of use in comparisons. NOTE: this is different from STL!
 183    @see tail
 184    */
 185    iterator end(void) const;
 186
 187    /* Get last element in list.
 188       @return iterator pointing to the last element in the list.
 189       @see end
 190    */
 191    iterator tail(void) const;
 192
 193    /* Get the number of elements in the list.
 194       @return number of elements in the list
 195    */
 196    unsigned size(void) const;
 197
 198    /* Query whether list is empty.
 199       @return true if list is empty
 200    */
 201    bool empty(void) const
 202       { return first == NULL ; }
 203
 204 protected:
 205    /// if true, list owns entries
 206    bool        ownsEntries;
 207    /// pointer to first element in list
 208    kbListNode *first;
 209    /// pointer to last element in list
 210    kbListNode *last;
 211
 212 private:
 213    /// forbid copy construction
 214    kbList(kbList const &foo);
 215    /// forbid assignments
 216    kbList& operator=(const kbList& foo);
 217 };
 218
 219 /// just for backward compatibility, will be removed soon
 220 typedef kbList::iterator kbListIterator;
 221 /// cast an iterator to a pointer, compatibility only to be removed
 222 #define   kbListICast(type, iterator)   ((type *)*iterator)
 223 /// cast an iterator to a const pointer, compatibility only to be removed
 224 #define   kbListIcCast(type, iterator)   ((type const *)*iterator)
 225
 226 /** Macro to define a kbList with a given name, having elements of
 227     pointer to the given type. I.e. KBLIST_DEFINE(Int,int) would
 228     create a kbListInt type holding int pointers.
 229 */
 230 #define   KBLIST_DEFINE(name,type)   \
 231 class name : public kbList \
 232 { \
 233 public: \
 234    class iterator : public kbList::iterator \
 235    { \
 236    protected: \
 237       inline iterator(kbList::iterator const & i) \
 238          { node = i.Node(); } \
 239       friend class name; \
 240    public: \
 241       inline iterator(kbListNode *n = NULL) \
 242          : kbList::iterator(n) {} \
 243       inline type * operator*() \
 244          /* the cast is needed for MS VC++ 5.0 */ \
 245          { return (type *)((kbList::iterator *)this)->operator*() ; } \
 246    }; \
 247    inline name(bool ownsEntriesFlag = FALSE) \
 248       : kbList(ownsEntriesFlag) {} \
 249    \
 250    inline void push_back(type *element) \
 251       { kbList::push_back((void *)element); } \
 252    \
 253    inline void push_front(type *element) \
 254       { kbList::push_front((void *)element); } \
 255    \
 256    inline type *pop_back(void) \
 257       { return (type *) kbList::pop_back(); } \
 258    \
 259    inline type *pop_front(void) \
 260       { return (type *) kbList::pop_front(); } \
 261    \
 262    inline void insert(iterator & i, type *element) \
 263       { kbList::insert(i, (void *) element); } \
 264    \
 265    inline void erase(iterator & i) \
 266       { kbList::erase(i); } \
 267    \
 268    inline iterator begin(void) const \
 269       { return kbList::begin(); } \
 270    \
 271    inline iterator end(void) const \
 272       { return kbList::end(); } \
 273    \
 274    inline iterator tail(void) const \
 275       { return kbList::tail(); } \
 276    ~name() \
 277    { \
 278       kbListNode *next; \
 279       while ( first != NULL ) \
 280       { \
 281          next = first->next; \
 282          if(ownsEntries) \
 283             delete typecast(first->element); \
 284          delete first; \
 285          first = next; \
 286       } \
 287    } \
 288    private: \
 289    inline type * typecast(void *ptr) \
 290       { return (type *) ptr; } \
 291    }
 292
 293 #ifdef   MCONFIG_H
 294 /// define the most commonly used list type once:
 295 KBLIST_DEFINE(kbStringList, String);
 296 #endif
 297
 298 #endif // KBLIST_H