samples/richedit/kbList.h

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